[General] Random Dungeon Generator

[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

 

[IcemanBo]

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..?

 

[rulerofiron99]

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]

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.

 

[rulerofiron99]

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]

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?

 

[rulerofiron99]

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]

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.

 

[rulerofiron99]

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

image

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.

 

[sentrywiz]

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

image

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.

 

[rulerofiron99]

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]

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.

 

[rulerofiron99]

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".