Maze Solver AI

Summary

  • Project Duration: 2 Months
  • Platform: PC – Console Window
  • Engine Used: Visual Studio (C++)
  • Developers: Only Me

Relevant Links

The Task

This was an early university assignment for programming fundamentals. The task was to make a solution that would make the mouse, signified as the character ” M “, move through the maze and reach the end goal signified with the character ” E “. The maze generation code and some base code for vector2’s was provided, but we had to make the mouse move and display correctly as it moved through the maze, replacing the start position with a character ” S ” when the mouse moved off the space.

My Solution

My solution to this problem was to make the mouse have a set of choices to make. I first prototyped this solution with paper and screenshots of generated mazes. During this stage I figured out how the mouse would prioritise its direction to travel in, how often to check for a new direction and when to backtrack on itself. After a couple of days I had a working solution in theory. It worked by the mouse finding the end and choosing which direction was the optimal to travel. It would then have a compass with 2nd, 3rd and 4th directions. when the mouse moved it would leave an invisible path behind it so it knew where it had travelled from, this would act as a wall for the mouse unless all other directions had been traversed. If the 1st direction was a wall, the 2nd would be chosen etc. every 5 steps the compass would update its directions from the new position. If all the directions were either walls or the path already travelled on then the mouse would backtrack until a new direction was open to the mouse and so on. This solution seemed to work flawlessly at solving any maze, even if it took a few incorrect paths. The only bug I had was a visual bug where the mouse would skip a tile when backtracking around a junction in the maze. Other than that it was a perfect solution getting me 97/100 for the assignment.