This project was made for a course during my first year at University of Applied Sciences Saxion in Enschede for the algorithms course. The code is based on the GXPEngine, an engine made by Saxion.
The dungeon gets generated through binary space partitioning, rooms get split up at random points until the rooms are too small to split up any further.
In the first version of the generator the doors get generated alongside the rooms making a door between the two split rooms each time:
In the second version of the generator the biggest and smallest rooms are removed, the door get generated after the rooms are done generating:
In the third and last version of the generator the rooms get shrinked down making the doors into hallways:
The nodegraphs are generated to provide a path for "Morc the Orc" to explore the dungeon.
The first version of this graph only makes a single node in the center of each room and one at the doors. These nodes are then connected appropriately. This version doesn't work with the third version of the dungeon generator so we use the second version.
The second version makes a node at every tile Morc should be able to walk. These nodes are then connected appropriately diagonally, horizontally and vertically.
The nodegraph agents make Morc walk through the dungeon.
The first version only allows Morc to walk to a node that's connected to his node.
The second version allows Morc to walk to any node he wants but he doesn't pathfind, he justs chooses a random node to go to each time that isn't the previous one.
The third version handles Morcs movement by getting the path from a pathfinder...
For pathfinding I implemented a couple of algorithms.
The first one I implemented was DFS (depth first search) an algorithm that finds the shortest path by checking out all possible paths. Because of this it is really slow and doesn't work well with the second version of the nodegraph so for this one I switched to the first version.
The second one is BFS (breadth first search) this algorithm is faster and stops checking when it reaches the end node which DFS doesn't. It searches by searching in an expanding circle around it until it finds the end node.
The previous algorithms search for the shortest path in regards to the amount of nodes not the distance. This next algorithm does however, Dijkstra is an algorithm that generates a path based on the total physical distance from the start node to the end node.
The last and best algorithm is A* this is an algorithm that works like Dijkstra but instead of only taking the shortest route so far into account it also takes the distance to the end node in account which means a lot less nodes are checked in the process.
