Maze Generation Algorithms - Recursive Backtrack

11 May, 2017

I have recently been playing around with the idea of generating mazes. This is mostly due to the tower defence game I am working on and generating mazes is a very interesting topic. I have decided to start by implementing the Recursive Backtracker algorithm as it seemed both easy to implement and I like the mazes produced by it. By far the best resource I found while learning about mazes was a blog by Jamis Buck and his book “Mazes for Programmers”.

 

You can see my implementation of the Recursive Backtracker algorithm below.

Maze Seed:


Regenerate

The code is all on my Github

Find best solution to any maze

02 May, 2017

I am currently working on a Tower Defence game with Caleb and Natasha Op’tLand. As part of this game the player will be able to place down towers in such a way that it creates a maze for the enemies to traverse. The enemies should be able to find the best possible solution to any maze that the player creates. The game is based on a 2d grid, A map may look like the following with some towers and rocks blocking the enemy path.

undefined

The numbers represent the path the enemies will use to traverse this maze.

 

The method I have used to solve the maze is by no means the most efficient but it will however always find the best possible solution. This is done by assigning values to tiles beginning with the starting tile and finishing when the end tile has a value assigned. Firstly the starting tile is assigned the value of 1. Tiles adjacent to this are given a value of 2 and then 3 and so on until the end tile is assigned a value.

undefined

Values being assigned to tiles until the end tile is reached.


Once the end tile has a value assigned (In this case 12) we can use this information to backtrack from the end tile to find the solution. This is done by looking for tiles adjacent to the end tile with a value of one less (11). This is repeated until the starting tile is found.

undefined

The final solution being mapped out

 

Home