• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • 🏆 Hive's 6th HD Modeling Contest: Mechanical is now open! Design and model a mechanical creature, mechanized animal, a futuristic robotic being, or anything else your imagination can tinker with! 📅 Submissions close on June 30, 2024. Don't miss this opportunity to let your creativity shine! Enter now and show us your mechanical masterpiece! 🔗 Click here to enter!

[General] Random Dungeon Generator

Status
Not open for further replies.

sentrywiz

S

sentrywiz

I want to create a map that creates random dungeons.

But even if I just try to copy an already existing algorithm, most of them work on a matrix. So how can I turn the map into a matrix?

Do I have to lay small regions of size (2, 2) next to each other all around the map? What are the maximum number of regions I can have on the map anyway?

If you got a different way, please share. TY
 
Level 25
Joined
Jul 10, 2006
Messages
3,315
The terrain is divided up into cells of size 128x128 - that's your matrix. You can use terrain types in your generator trigger to create random rooms, and then go over it all again afterwards to create walls on specific terrain types.

Have a look at my map Dead Lab (link in my signature) which has a random room generator. If you'd like to have rooms like that, feel free to learn from it or copy it.

Another method you could use is a random labyrinth generator. This page has several methods: http://bost.ocks.org/mike/algorithms/#maze-generation

Once again, just use terrain tiles as your matrix. If you want paths greater than the size of one terrain tile, just multiply everything by some amount.
 

sentrywiz

S

sentrywiz

People would probably need some more information.

It would help if there would be explained what you exactly expect to achieve with creating a random "dungeon".
For example you want have to have random tilesets of a certain list, or also doodads, etc..?

I want to split the map into row-column, like a matrix or a table.
The only way I know how is to make regions of same size and manually add them.
Then I can manipulate them through triggers to iterate either recursively or not through the map
and either copy or make my own dungeon algorithm.

I am asking is there is a simpler and/or better way? Because my solution is bothersome at least.

The terrain is divided up into cells of size 128x128 - that's your matrix. You can use terrain types in your generator trigger to create random rooms, and then go over it all again afterwards to create walls on specific terrain types.

Have a look at my map Dead Lab (link in my signature) which has a random room generator. If you'd like to have rooms like that, feel free to learn from it or copy it.

Another method you could use is a random labyrinth generator. This page has several methods: http://bost.ocks.org/mike/algorithms/#maze-generation

Once again, just use terrain tiles as your matrix. If you want paths greater than the size of one terrain tile, just multiply everything by some amount.

I know all this. I will take a look at your map, but I understand about 60-70% how the random dungeon generator works by looking at C# or Java source codes.

The map isn't divided, I cannot manipulate each tile separately until I have a region over it so I can say this tile is "4 152" and it is a room tile.

I was just asking if there is a simpler way than to make 200+ regions and spread them equally around the map.
 
Level 25
Joined
Jul 10, 2006
Messages
3,315
The map isn't divided, I cannot manipulate each tile separately until I have a region over it so I can say this tile is "4 152" and it is a room tile.

I was just asking if there is a simpler way than to make 200+ regions and spread them equally around the map.

I don't understand what the problem is.

You don't need regions at all.

You start with some point or coordinates, apply terrain changes to neighbouring tiles, save a list of next potential coordinates, and repeat with the next point on the list.

Why/how are you using regions?
 

sentrywiz

S

sentrywiz

I don't understand what the problem is.

You don't need regions at all.

You start with some point or coordinates, apply terrain changes to neighbouring tiles, save a list of next potential coordinates, and repeat with the next point on the list.

Why/how are you using regions?

Because I don't understand coordinates. I understand the X/Y but I don't understand how can I use this?
Plus I've never used X and Y directly in the editor so I don't know how.

EDIT:

I downloaded your map. Wow. So amazing.

But as far as I saw it doesn't randomize the map. The crates and boxes used are randomized, but everything else the same?
 
Last edited by a moderator:
Level 25
Joined
Jul 10, 2006
Messages
3,315
Thanks. If you restart it a few times, you'll see that the rooms are randomised. If you were launching it as a test map from editor, check if "use fixed random seed" is maybe enabled.

My strategy was this:
Loop through every "block" (an area of 384x384) - loop x from -5 to 5, inside this loop, loop y from -5 to 5
Pick a random room x size and y size, so anything from 1x1 to 4x4 of the aforementioned blocks.
I then paint "walls" (another terrain type) around this shape and move on to the next block.
When I've gone through the entire area, I loop over every tile (128x128) and place a wall if the correct terrain type is detected.

To use X/Y coordinates to make a labyrinth, you first need a starting point: you can use x = 0, y = 0 which is the center of the map.
From there, you can check each neighbouring point for viability if you want to make a room or wall, using coordinates like this:
(current x) + 128 ... east
(current x) - 128 ... west
(current y) + 128 ... north
(current y) - 128 ... south

The strategy you should use is going to depend greatly on how exactly you want the dungeon to look.
 

sentrywiz

S

sentrywiz

Thanks. If you restart it a few times, you'll see that the rooms are randomised. If you were launching it as a test map from editor, check if "use fixed random seed" is maybe enabled.

My strategy was this:
Loop through every "block" (an area of 384x384) - loop x from -5 to 5, inside this loop, loop y from -5 to 5
Pick a random room x size and y size, so anything from 1x1 to 4x4 of the aforementioned blocks.
I then paint "walls" (another terrain type) around this shape and move on to the next block.
When I've gone through the entire area, I loop over every tile (128x128) and place a wall if the correct terrain type is detected.

To use X/Y coordinates to make a labyrinth, you first need a starting point: you can use x = 0, y = 0 which is the center of the map.
From there, you can check each neighbouring point for viability if you want to make a room or wall, using coordinates like this:
(current x) + 128 ... east
(current x) - 128 ... west
(current y) + 128 ... north
(current y) - 128 ... south

The strategy you should use is going to depend greatly on how exactly you want the dungeon to look.

Oh its open. Didn't check the map directly. I just played the map 4-5 times to see but I didn't notice much of a difference. Maybe its the terrain and the fog.

I'll check your map. The room generation will be useful, only in the cast of dungeon creation you have to have corridors as well. The empty hallways between rooms.
 
Level 25
Joined
Jul 10, 2006
Messages
3,315
Here's an example of a generator we could make:

attachment.php


As you can see, the map would be divided up into large "blocks" (bordered by the rock lines). Each block could be one of several things:
- Empty
- Small room
- Big room (joins with adjacent blocks - we could have complex shapes instead of just some N x M rectangle)
- Corridor, elbow, t-junction or cross, which are paths to link rooms together.

If you'd like, I'd be more than happy to make this for you. I intend to make something similar eventually for my own purposes anyhow.
 

Attachments

  • dungeonexample.png
    dungeonexample.png
    2.6 MB · Views: 403

sentrywiz

S

sentrywiz

Here's an example of a generator we could make:

attachment.php


As you can see, the map would be divided up into large "blocks" (bordered by the rock lines). Each block could be one of several things:
- Empty
- Small room
- Big room (joins with adjacent blocks - we could have complex shapes instead of just some N x M rectangle)
- Corridor, elbow, t-junction or cross, which are paths to link rooms together.

If you'd like, I'd be more than happy to make this for you. I intend to make something similar eventually for my own purposes anyhow.

That's amazing. Its exactly the generator I wanted to make, only didn't exactly know all the details. I hoped that once I get started on it, it would make sense.

But I don't understand warcraft's X and Y system that's why the whole matrix/table idea isn't clear to me.

Is this image of generator in action or just an example?

If you're up to the task, maybe we can make a map together. Not sure if our ideas would match, but we can talk about it in chat.
 
Level 25
Joined
Jul 10, 2006
Messages
3,315
This is just an example, but it's something that could be easily done using the same method I used in my Dead Lab generator.

In my image, I've also written the "block" x and y coordinates in each block. To translate this integer coordinate into the game, you just multiply it by the size of the room. A yellow block is 512x512, so these rooms would be 1536x1536.

I've got a few project ideas I want to work on so for now I don't intend to make this map, but as I said I'd be more than happy to make the generator. It's a nice bite sized coding task :)
 

sentrywiz

S

sentrywiz

This is just an example, but it's something that could be easily done using the same method I used in my Dead Lab generator.

In my image, I've also written the "block" x and y coordinates in each block. To translate this integer coordinate into the game, you just multiply it by the size of the room. A yellow block is 512x512, so these rooms would be 1536x1536.

I've got a few project ideas I want to work on so for now I don't intend to make this map, but as I said I'd be more than happy to make the generator. It's a nice bite sized coding task :)

You see, what I don't understand is that X and Y coords in warcraft are too big. I'm used to smaller digits like -10 10 to represent that. And the way you do it is confusing, because 512x512 doesn't sound like X and Y to me.

Well if you think you can do it, awesome. I'll be happy to re-use your little project for a map.
 
Level 25
Joined
Jul 10, 2006
Messages
3,315
You just multiply your matrix by some "size" (like 512) to make it into a warcraft coordinate.

So if you have a matrix with x and y each from -10 to 10 and a block size of 512,
The bottom left block will be:
x = -10 x 512 = -5120
y = -10 x 512 = -5120
and the block to the east of it will be
x = -9 x 512 = -4608
y = -10 x 512 = -5120

A nice way to familiarize yourself with the way x and y coordinates work in warcraft is to look at the coordinates in the editor at the bottom left of the window. These are the coordinates of the point where your mouse cursor currently is.

Anyway, I'm going to be doing a labyrinth implementation instead of the fill method I used in my Dead Lab generator. The effect of this should make the dungeon feel a bit more "natural".
 
Status
Not open for further replies.
Top