Pathfinding &

Mazes

Platform

Windows

Language

C++

Project Type

Course Work

Role

Solo

Duration

~6 Months

This is the applications I created for the second year course Data Structures and Algorithms.

This was the first iteration of the program, a simple Dijkstra algorithm. Put simply, each time a node is processed (goes from light grey to dark grey) how many steps the program has taken to get to that node is calculated (+1 from the previous node). Once it reaches the red target node, it backtracks through the nodes, choosing the node with the lowest step count, to get to the starting green node. This path is then reversed to obtain the shortest path.

The black obstacles are randomly spawned and sized to make the area less boring.

The next step was to convert the Dijkstra algorithm into an A* algorithm. This was accomplished by prioritising the nodes to check by their distance to the target and by how many steps it has taken to get there. Only the closest neighbour of each node is checked. This results in a much faster pathfinding algorithm, so much so that the program in the video is being made to run 15x slower than the Dijkstra version so you can actually see how it works.

To make the area, the program pathfinds through, more interesting I decided to create a random maze generator. To decide where the maze is going, at each node, it randomly chooses one of the nodes viable neighbours (that being a neighbour that isn't an edge or is already a path). This continues until either the current path is a predefined length or there are no viable neighbours. At this point, a random node, with viable neighbours, is chosen from the maze and the process can start again. A* is then used to find the path through the maze.

For the second semester, we had to develop an application which used multi-threading and showed the performance benefits this can bring. I felt my maze generator was a perfect candidate for this, as it can take a while to make a large maze. The application basically creates many small mazes, with each little maze being created on a different thread, and then randomly adds connections so there is a way through.

Andrew Milne