While there is a whole dungeon created, it is very possible that it cannot be sufficiently traversed because the player is walled in to only a handful of rooms. So to find a dungeon that is valid there needs to be a path found that reaches far enough for the player to progress. A common search algorithm for video games is the A* (A star) algorithm and this project is no exception. The hardest part about implementing this algorithm was making work with a dungeon that is created at runtime. The solution seems to be having a long enough amount of time between the world being created and the wall checking algorithm run. This implementation of A* runs on a grid so each tile is either walkable or not. The wall checking algorithm goes through each space and marks it if it detects a wall atop it. Once there is this grid of 0s and 1s then A* can run and find the shortest path to the given destination, such as a key. Not every dungeon can have a complete path and so there has to be some retrying until the valid paths are found.
There isn’t much more work to be added to also use A* for the navigation of a computer controlled monster. When the player is far enough away from the monster, the algorithm can be given some point far away. The found path can then be fed to the monster as a list of points to walk to. If the player is too close, then the destination for the monster would be the players position and a chase would ensue.
