Random maze/dungeon generator

[Wojak]

I had this in my mind for a while, an I had to do something about it…

So this is a little concept script that generates a random tile map with a complex maze:
first release:

version that generates less "serif’s" and unoccupied chunks:

Shot at 2012-06-08

Walls ale with, the two numbers in the upper left corner are:
- left one – number of times the generator function was called since the application started
- right one – amount of not used chunks (chunks are 3x3 tile squares)

pressing space will generate a different map

This may not be the best or the most efficient way of generating the maze, but the script works exactly like I expected, and things like that always make me happy
I may use this in some of my future projects, but it may take some time, I don’t want this to be wasted, so I hope someone will find it useful

[coffee]

Ah interesting. You working with pre-assembled blocks. It's a concept I like. Thanks, I actually need too do something a bit like this for rooms/vaults map generating. Seems fast but there isn't reason for not be. Nice work.

[dreadkillz]

Hey thanks for sharing it with us, it could come in handy if I wanted to know how to randomly generate dungeons.

[coffee]

Hey thanks for sharing it with us, it could come in handy if I wanted to know how to randomly generate dungeons.

Other similar generators made with LOVE (listed in no particular order)
viewtopic.php?f=5&t=3980 (AaronWizard)
viewtopic.php?f=5&t=7826 (Kadoba)
viewtopic.php?f=4&t=7394 (AaronWizard)
viewtopic.php?f=5&t=4020 (Kadoba)

[Jasoco]

Yeah, I had been working on my own maze generator a while back that I was going to use to make a randomly generated RPG. I will probably rewrite it some day. I love maze generators.

Actually, right now I'm working on a 3D Raycaster engine (Rewriting it) and am thinking of using my method to make generated mazes in 3D. Math is fun!

I don't really like the little... "serif" things at the end of hallways in your example. Is there a reason for them?

[coffee]

I don't really like the little... "serif" things at the end of hallways in your example. Is there a reason for them?

I notice that too. Maze roads/paths are built from pre-assembled "blocks" of 3x3 tiles. So should be only result of pure plain luck without haven't probabilities to get less "bifurcations" or "t-joints" if adjacent blocks aren't connected. Perhaps Wojak need to implement a trim/cleaner/beautify function after the maze is generated to reduce excess of "serifs" (short dead-ends).

[adnzzzzZ]

http://weblog.jamisbuck.org/2011/2/7/ma ... ithm-recap

This guy has a bunch of posts on different maze generation algorithms. Very well explained. He also had a very nice presentation about it but I can't find the link.

[Wojak]

Ah interesting. You working with pre-assembled blocks. It's a concept I like. Thanks, I actually need too do something a bit like this for rooms/vaults map generating. Seems fast but there isn't reason for not be. Nice work.

Hey thanks for sharing it with us, it could come in handy if I wanted to know how to randomly generate dungeons.

Yore welcome

http://weblog.jamisbuck.org/2011/2/7/ma ... ithm-recap

This guy has a bunch of posts on different maze generation algorithms. Very well explained. He also had a very nice presentation about it but I can't find the link.

My approach is completely different from any method mentioned in that link, I actually was inspired by strongholds and abandon mine shafts in minecraft

I don't really like the little... "serif" things at the end of hallways in your example. Is there a reason for them?

Its like coffee said – there ate 11 pre-assembled shapes, and the maze is a lithe bit like the tree that grows from the centre, attaching random pieces to It’s open ends, when there is no space to grove (area out side the map border, or occupied chunk) the branch simply stops growing living a random shape at the end. To be honest I did not sow this as a problem…

Perhaps Wojak need to implement a trim/cleaner/beautify function after the maze is generated to reduce excess of "serifs" (short dead-ends).

I suppose it is possible to check this kind of things during the generation, I will think about it, however the problem may be less visible with larger chunks:

Code: Select all

{{1,0,0,0,1},    + junction
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{1,0,0,0,1}}


{{1,1,1,1,1},    corner
{0,0,0,0,1},
{0,0,0,0,1},
{0,0,0,0,1},
{1,0,0,0,1}}

{{1,0,0,0,1},    T junction
{0,0,0,0,1},
{0,0,0,0,1},
{0,0,0,0,1},
{1,0,0,0,1}}

[Ref]

Wojak, do you have a version that generates a maze?
The script provided generates patterns but not a maze.
There is no path through the generated pattern.

[Wojak]

Wojak, do you have a version that generates a maze?
The script provided generates patterns but not a maze.
There is no path through the generated pattern.

This is not a “perfect maze” (it has loops), but it is “A maze” (the walls are white ) you can get from any black patch to any black patch (excluding the frame)

Anyway there are two more versions of the generator available in the OP:
- old version with a slowed down generation
- and a new version that generates less "serif’s" and unoccupied chunks (also with slowed down generation)

with the slow generation effect you can actually see it groves