Algorithmic exploration
Finding the way out of the dungeon, as fast as possible.
- Type
- Algorithms
- Context
- Pair project, BUT year 1
- Year
- 2025
- Technologies
- Java, Graphes
A dungeon is described in a plain text file: rooms, passages, a start A and an exit B. The program turns it into a graph, looks for a path with three algorithms, depth-first search (DFS), breadth-first search (BFS) and A*, then translates the solution into directions: north, south, east, west.
Each dungeon is solved 10,000 times per algorithm to measure time, and the explored rooms are counted. On dungeon 6, DFS finds a 78-room path where BFS and A* find 10; A* gets there after exploring 63 rooms, against 275 for BFS.
I wrote the breadth-first search, A* with a Manhattan heuristic, the dungeon-to-graph conversion and the translation of the solution into directions. I also designed the two added dungeons: one almost linear with a forced detour, the other densely connected to show where DFS falls short.
- DFS, BFS and A* compared on eight dungeons
- Two dungeons designed to trap the algorithms
- Time and explored-room measurements