a_bertrand

Simple Maze generation algorithm

Recommended Posts

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.

upload_2016-11-21_15-19-6.png 

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

upload_2016-11-21_15-19-30.png 

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 

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.