javascript Simple Maze generation algorithm

[a_bertrand]

There is many maze generation algorithm, some perform better in some cases some perform better in others. Some generate mazes with long lines, while others generate with huge number of branches. There is so many different options that for sure I will not cover all of them but you may have a look here:

http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap

For my engine ( https://www.dotworldmaker.com ) I offer base procedural maps which can be edited by the game owner, one of the generator uses the Prim's algorithm (if I don't mix up as it is actually pretty old code of mine):

https://jsfiddle.net/a_bertrand/eb1qgjj2/

You can run multiple times the example, and each time you get a different maze.

The steps involved are:

1. Generate a maze array which have "rooms" separated by walls. Think about small rectangles touching each others.
2. You start from one of those "rooms" and then select all the wall and open then up if the room there has not been visited already.
3. Add those reached "rooms" as new points in the todo.
4. If there is still rooms to visit go back to point 2.

At the end of the process you should have visited all the possible rooms and therefore opened many walls. You will also have a fully solvable maze (starting from any room you will be able to reach any other room). Drawback it requires quite some memory and the maze is pretty messy. But that is not an issue in my case.

From this array generation to my maps, I do have like a factor of conversion, ideally between 3-5 which means for each maze cell I have 3-5 map tiles involved. My tile code allows also to blend tiles and find automatically the transition between 2 types of tiles.

 

I also added some "erosion" code which makes the look of the maze a bit more natural

 

The erosion involves a Perlin noise generator and checking the neighbors tiles to see if that particular tile need to be changed or not. The erosion is run before the transition is run.

Of course on top of that you could place objects, monsters or anything else you may think could improve your game.

Be careful with maze generation, mazes can be really difficult to solve once you are playing them and... too difficult means boring in most cases.

if you need more information please ask