Welcome to the Mazerunner Kata!

In this Kata, you'll implement a pathfinding (also pathing) algorithm to help your avatar @ find a way through different mazes, ultimately finding the exit 0.

However, it is not enough to find any path through the maze, it has to be the shortest one possible. Where there are multiple shortest pathes of equal length, any of them suffices. While the simple scenarios in the visible test cases provide the definitive answers, the hidden test cases use complex problems with possible many correct answers and run more elaborate checks against your solution.

Rules

All scenarios take place in a two-dimensional coordinate system with [0 0] being the origin at the upper left corner, expanding to the bottom right.

 0123…
0....
1....
2....
3....
…

The system is limited within a given set of boundaries [w h]. A sample boundary of [5 2] would mean that there are 10 walkable floor tiles spanning from [0 0] to [4 1] (inclusive).

Legal moves are

[-1 -1] [0  -1] [1  -1]
       \   |   /
         \ | /
[-1  0] -- @ -- [1   0]
         / | \
       /   |   \
[-1  1] [0   1] [1   1]

The diagonal moves, #{[-1 -1] [1 -1] [-1 1] [1 1]}, are treated as having a simplified distance of 1.5, where 1 is the distance of a horizontal or vertical move, #{[-1 0] [0 -1] [1 0] [0 1]}.

A valid evaluation result starts with the starting coordinates tuple and ends with the goal coordinates. In between the two are other coordinate tuples which must be derives from any of the eight valid moves described above. For instance, in the simple scenario of

@...0

the only correct solution would be [[0 0] [1 0] [2 0] [3 0] [4 0]].

The final parameter to find-path, os, is a Set of coordinates with obstacles. These coordinates are inaccessible just like coordinates outside the boundaries. This means that in the slightly modified scenario from above

@.X.0

there would be no solution, whereas

.....
@.X.0
.....

there are two possible solutions that involve avoiding the obstructed coordinate at [2 1]. If no solution is available as in the former scenario, nil is the only correct evaluation result.

To help with the implementation, data.priority-map 0.0.5 is preloaded with this Kata and made available in full. The library can be used as a priority queue.

Further Reading

• The pathfinding Wikipedia article
• PathFinding.js is a great tool to visualize and observe different pathfinding algorithm behavior
• The Roguelike Dev FAQ
• google-fu :)

Have Fun & Good Luck!