Google+

Eller’s Algorithm

Leave a comment

November 21, 2015 by jonmillymiles


Continuing on from where I left off, I need to begin to create corridors to join my rooms together. To do this there are many ways I could employ…

I could place a room, pick a random square and test for an adjacent tile then spawn a corridor or a new room. This is then repeated until the desired map is generated.

I could place a random number of rooms and build a maze between them before finally linking the rooms in to the maze.

I could create a maze, then spawn the rooms on top of the maze.

My first attempt at this will be to generate a maze to place on my map and them put the rooms on top.

But I have a problem: at present all of my squares are adjacent to each other. This may not seem to be a problem at first but a maze must have walls, or at least some way of preventing the player from passing from one corridor to the next and bypassing the maze. So the first thing that I need to do is to space them out, or rather than increase the gaps I am going to use every other tile as a reference for building my maze.

There are many different ways of building a maze but the one that I settled on was called Eller’s Algorithm. I chose this because it has been proven to be the fasted algorithm for creating a perfect maze (one which only has a single route between two points).

The way that it works seems quite simple (I’ve simplified it a bit from the references below):

For each row…

  1. From left to right – Each square is given a set number if it doesn’t already have one.
  2. From left to right – Randomly join different sets together. If the tiles are already from the same set do not join them together.
  3. From left to right – Randomly join tiles to the row below and copy the set down. If the square is the last tile in the set and the set does not already link downwards then force it to join.
  4. If it is the last line of the maze – all unjoined sets must be joined to another.

While it may sound simple, it required me to rework the referencing of the maze in order to allow the squares to be created at every other square. Then rather than build a wall as per my references below, I would join rooms by placing a tile in between. I suppose that the other way that I could have done this would have been to fill the map with tiles and then take the tiles away for a wall.

The actual code for this is a maze all on its own…

Ellers Algorithm

And here’s what it looks like – black tiles are the normal tiles and green are where I have joined them (the different colours have helped massively with fault-finding):

Now there are some problems with the algorithm as I have made it:

  • There are some isolated tiles.
  • There are loops (in a perfect maze there shouldn’t be any.

And I need to ask myself a serious question… does it matter??? Is it honestly worth expending more effort on debugging this system in order to make it perfect when I am going to put rooms in on top of it? Isn’t it nice sometimes to have a second route?

So I thought I would try adding in the rooms anyway to see what it looks like:

And I am quite happy with this, most of the mazes are fully linked and the loops don’t really interfere.

My only problem is that there is now “too much maze”… we have too many corridors for the rooms. So to solve this problem I intend to remove most of the tiles that have less than two adjacent tiles. This will remove most deadends and all isolated tiles – solving one of my problems (the loops I can live with).

To do this I created a new function which gives a count of the number of adjacent tiles that any given tile has, if it is one or less then I would delete it.

Here is the code for the check and the removal:

Tile CheckRemove Tile

The result of adding this in (after running it a few times to reduce the map) are quite stunning:

But they are still broken and within a game we can’t have this happen.

I also found something else annoying – there is no sense of scale. The corridors are just barely large enough to walk through. So for my final piece I scaled everything up a bit and some of these maps look really good, and none are broken!!!

References:

http://www.neocomputer.org/projects/eller.html

http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm <— Primary source and such a good explanation of how the algorithm works.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog Stats

  • 10,074 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 580 other followers

Archive

%d bloggers like this: