Build 1.0 Report and Analysis

Project Description:

For my project, I decided to implement a dungeon generator to create a dynamic dungeon and an A* shortest path finder algorithm. The dungeon generation was not the purpose of the assignment; rather, the purpose of the dungeon generator was to create an interesting environment for A* to run in. First, I will discuss some of my design choices for the dungeon; then, I will discuss my implementation of A*.

For my dungeon, it is a grid-based environment that generates a 2D dungeon that is rendered in a 3D space. My dungeon generation logic can be divided into 3 total steps: generating a perfect maze, removing random edges of the maze (making it imperfect), and placing obstacles in random rooms. For the perfect maze generation, I used basic depth-first search techniques to generate a perfect mxn maze. This method of generation ensures that there is exactly one path to the end room of the maze and that every single room in the dungeon has some kind of connection to another room (no impossible-to-reach rooms). Next, I iterate through every room in the dungeon (which is stored in a dictionary) and decide whether to add extra connections from the room or not based on a variable called extraDoorProb. If we decide to add an extra connection, we pick a random unconnected neighboring room and add a door and then decide again based on extraDoorProb whether or not to add another room connection on top of that. This was a crucial design decision for the dungeon generation because it justifies the usage of A* in the first place. Meaning, if the dungeon only has one path to the exit, then an algorithm made to find the shortest path would be unnecessary. Finally, another algorithm will run through every room in the maze again and determine whether or not to add obstacles to each room based on the addObstProb variable. Adding obstacles to a room gives that room “weight,” which is important because rooms with a higher weight are rooms that A* has to try to avoid more variable rooms. All in all, these design choices were chosen so that A*’s usage in this environment could be more justified. 

For the shortest path finder, I based the entire thing off of the A* pseudocode available online, which I translated to work with Unity. Essentially, once the dungeon generator has finished, it sends the shortest path finder the rooms of the starting room and the end room, and the shortest path finder uses those to find the shortest connection. For a heuristic function, I initially was just going to use Manhattan distance, but I ended up coming up with a better heuristic for this graph called weighted Manhattan distance. In short terms, I computed an estimated value for the average weight of any 1 room in my graph, and then I multiplied it by the Manhattan distance, which is more informed. This heuristic is neither admissible nor consistent, but it works better in practice because the obstacle rooms are uniformly distributed across the dungeon, making it very unlikely that the heuristic would overestimate the travel cost.

Result Analysis and Takeaways:

Below is some of the data I collected when evaluating my heuristic function and shortest path finder. These statistics are what made me realize Manhattan distance itself would not be an efficient enough algorithm for this. I ran 10 tests with each heuristic function. I ran these tests with a 250x250 dungeon, 0.5 obstacle spawn probability, 0.5 extra door spawn probability, and an obstacle room weight of 3. The results are below: