lafarren.com

---

Theseus and the Minotaur

Overview

Theseus and the Minotaur is a logic maze designed by Robert Abbott. Robert's own page for the maze contains the same Java applet, written by Toby Nelson, that I played nearly 10 years ago. The applet originally had two large mazes, Robert's original maze and Toby's "Dread Maze", both of which baffled me to the point of disbelief. How were these possible?

I decided to code my way past the Minotaur. I soon had a solver written in C++ that spewed a list of text directions to solve a maze: "left 3; right 5; up 1...". In early 2010 I decided to resurrect the solver, except I wanted to integrate it with a
Theseus and the Minotaur, with the solver enabled. playable version of the game, and I wanted it playable in a web browser. This version was developed using Flex, a sort of programmer-centric way of creating Flash apps that looked interesting enough to try.

The Solver

A fair amount of the code deals with the boring details, like UI flow and rendering. I originally planned on giving Theseus and the Minotaur flickering torches, which would dynamically light a stone textured and normal mapped floor and cast long soft shadows from the maze walls. Maybe someday. For now, the rendering code remains squarely in the boring category.

The solver is more interesting. It's based on A*, a search algorithm that's often used by video game AI for simple pathfinding. Because of A*'s ubiquity, others have written good, thorough explanations on how it works.

There are a few key differences between typical A* implementations and this Theseus and Minotaur solver. One is that each graph node stores both agent positions, rather than the position of a single agent. Another is that a "sandbox" instance of the game is cloned from the real game instance, and is used by the solver to position the agents, try a Theseus move, evaluate the outcome, expand and traverse the graph, reposition the agents, and try the next move. Because the solver uses a game instance without knowing its exact rules - for example, how the Minotaur moves, or how many times he moves - the solver can be used for alternate game types and mazes if someone was so inclined. For example, if the Minotaur could move three times per turn, some very different maps could be generated for that context, and the solver should just work without modification.

The A* cost and heuristic are calculated from Theseus's movements and proximity to the goal, without any regard to the Minotaur. It's possible to evaluate an approximate "goodness" of a Theseus position relative to the Minotaur, but it's a difficult, unnecessary calculation, since any dangerous position typically ends in a Minotaur victory a few more moves into the graph, and that branch will terminate. The simple Theseus-centric cost and heuristic guarantees a directed and unwasteful solution, assuming any solution exists given the current agents' positions.

Code

Git repository:
git://github.com/darrenlafreniere/lafarren-theseus-minotaur-solver.git

Or, browse the codebase at github.

Developed using:

• Flex 3.5 SDK, target-player 10.0.42.34
• FlashDevelop

---

Play Theseus and the Minotaur