Oubliette | Devpost

Besty, Astar, Dijkstra, and Dogmog
Game Maze

Inspiration

We wanted to create an game that teaches computer science concepts through gameplay rather than lectures. Pathfinding algorithms are fundamental to AI and game development, but they're often presented abstractly in textbooks. What if you could feel the difference between A*, Dijkstra's, and Best-First Search by being chased through a procedurally-generated maze? Thus, Oubliette was born, a game where the enemies aren't just obstacles, but living demonstrations of classic algorithms.

What it does

In Oubliette, you play as Dogmog, a character trapped in a mysterious dungeon maze. Your goal is simple but challenging: find the key hidden somewhere in the maze, then escape through the exit, all while being hunted by three relentless enemies, each powered by a different pathfinding algorithm.

The Game Loop:

Navigate through a procedurally-generated maze
Locate and collect the golden key
Make your way to the exit (you can only escape if you have the key!)
Avoid being caught by the three algorithm-powered enemies

Power-ups: Scattered throughout the maze are magical chocolate bars that grant Ghost Mode, allowing Dogmog to phase through walls for a limited time. This can be crucial for escaping dead ends or evading enemies. Use them wisely!

The Enemies: Three unique adversaries hunt you down, each with distinct personalities based on their pathfinding algorithm:

A* (The Pink Pursuer) - Balanced and efficient, medium speed
Dijkstra (The Yellow Tracker) - Methodical and accurate, but slow
Besty (The Orange Speedster) - Lightning-fast but prone to mistakes

How we built it

Technology Stack:

C++ for core game logic and performance
SFML 3.0 for graphics and rendering

Maze Generation: The maze is generated using a Depth-First Search (DFS) algorithm:

Start from a random cell and mark it as a path
Randomly visit adjacent unvisited cells, carving paths as we go
Backtrack when no unvisited neighbors exist
After the base maze is created, we randomly carve additional branching paths to create loops and alternative routes (with a 25% chance per viable wall)

This approach creates perfect mazes with guaranteed solutions, then adds complexity through additional pathways.

Enemy AI & Pathfinding:

Dijkstra (Yellow) - The Methodical Tracker:

Algorithm: Classic Dijkstra's pathfinding explores all possible paths systematically, calculating the shortest distance from the start to every cell
How it works: Maintains a priority queue of cells to visit, always expanding to the nearest unexplored cell. No heuristics, pure mathematical certainty
Personality: Slow but accurate. Dijkstra takes its time to calculate the perfect path, resulting in slower movement speed. However, once it commits to a route, it never makes mistakes. This mirrors the algorithm's real-world behavior: slower to compute but guaranteed to find the optimal path

A* (Red spider cat) - The Balanced Hunter:

Algorithm: A* combines Dijkstra's accuracy with heuristic-based efficiency using Manhattan distance to estimate remaining distance to the target
How it works: Uses f(n) = g(n) + h(n), where g(n) is the actual distance traveled and h(n) is the estimated distance to the goal. This allows A* to prioritize promising paths without exploring everything
Personality: Medium speed, representing the sweet spot between speed and accuracy. A* is the "goldilocks" of pathfinding, not too slow, not too reckless

Best-First Search (Orange) - The Reckless Speedster:

Algorithm: Best-First Search is purely heuristic-driven, always moving toward whatever cell seems closest to the target without considering the actual path cost
How it works: Only uses h(n) (Manhattan distance), completely ignoring g(n). This makes it extremely fast to compute but prone to getting trapped
Personality: The fastest enemy but also the most chaotic. Besty can get stuck bumping into walls when its greedy heuristic leads it astray. To showcase its "greedy but unfocused" nature, Besty has a unique distraction mechanic:
- Besty has a 30% chance to become distracted and targets a random cell instead of the player for 2 seconds
- This creates tense cat-and-mouse moments where Besty is just about to catch you but suddenly veers off
- This emphasizes Best-First's nature: fast and aggressive, but not always reliable

Challenges we ran into

Game Balance: The biggest challenge was balancing three enemies with different speeds and behaviors. Early versions were either nearly impossible or way too easy. We had to implement several game balancing techniques.

Spawn Distance: Enemies spawn at least 10 cells away from the player and prioritize edge positions
Besty's Distraction: The random targeting mechanic (30% chance when close) creates crucial breathing room.
Round Progression: Enemies get faster each round (0.01s per round) but cap at 0.07s to prevent them from becoming impossible to escape

Accomplishments that we're proud of

Procedural Generation: Every playthrough is unique with a different maze layout, key location, and enemy spawn positions
Polish: Smooth sprite animations, proper scaling, visual feedback, and a complete game loop with round progression and game over states
Personality Through Code: Each enemy's behavior genuinely reflects its algorithm's strengths and weaknesses.