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