# Ice Maze Solver

2020-05-09 12:02:00

If you would like to try solving this puzzle before reading about how I'm doing it head over to codewars and search for ASCII Games: Warning: Ice!.

## Puzzle Details

This type of puzzle comes from games like Pokemon Gold. Here is a nice map key created by Daniel Chaviers: The CodeWars version gives you an ascii map made up of five tile types: start, end, rock, ice and snow. The goal is to return the shortest distance from the start to the end by returning a list of the directions taken: l for left, r for right, d for down and u for up. The trick here, that is different from other path finding puzzles, is ice. Once you are on an ice tile you continue to slide in that direction until hitting a wall, rock or snow.

## Practice and problem solving

When I read descriptions for these types of puzzles my brain goes oh yeah, backtracking, AStar, depth first, breath first. Following the ideas I outlined in the Practice Programming post, I try to dive right in and remember as much of those algorithms as possible without googling them.

My first attempt was depth first keeping a tree of the shortest path. C++ gives us a balanced search tree with `std::set` so that was used with a custom comparator to keep the shortest path at the root. This worked on simple maps but was way too slow for the larger random maps since it travels paths that have already been ruled out. To avoid this we need to keep a history to avoid doing duplicate work.

## High level solution

Similar to breadth-first searches we need a queue to keep track of the paths to visit, called `queue` below. This is the basic outline of the algorithm with the C++ implementation.

• The main loop continues until we are out of paths in the queue to explore.
• At the top of the loop a new `Trip` is started by dequeuing.
• Next we get the index for the starting position of this trip and check that it has not been visited.
• We get the last direction of this trip was travelling
• From there we walk in the three directions that would avoid backtracking
• Now we check the results for those walks
• Did we skip this direction? Continue.
• Are we at the end? Store this trip in the endings queue.
• Did we move, and we haven't visited the new spot? Keep exploring.
• Done. Do we have items in the `endings` queue? Return the shortest one.
``````
std::vector<char> walkMap(std::string map) {
V2 wh = { width(map), height(map) };
std::set<Trip, TripKeyCompare> queue;
std::set<Trip, TripKeyCompare> endings;
std::set<int> queueHistory;

V2 start = getStart(map, wh);
queue.insert({ start.x, start.y, "", 0 });
std::vector<char> result;

while (queue.size() > 0) {
Trip p = *queue.begin();
queue.erase(queue.begin());

long posKey = getIndex({p.x, p.y}, wh);
if (queueHistory.count(posKey) > 0)
continue;

queueHistory.insert(posKey);

char lastDir = ' ';
if (p.path.size() > 0) {
lastDir = p.path[p.path.size() - 1];
}

Trip trips;
if (lastDir != 'r')
trips = walkLeft(map, p, wh);
if (lastDir != 'l')
trips = walkRight(map, p, wh);
if (lastDir != 'd')
trips = walkUp(map, p, wh);
if (lastDir != 'u')
trips = walkDown(map, p, wh);

for (int i = 0; i < 4; i++) {
if (trips[i].x == SKIP) continue;

if (trips[i].x == END) {
endings.insert(trips[i]);
}

if (!(trips[i].x == p.x && trips[i].y == p.y)
&& trips[i].x != VISITED && trips[i].x != END) {
queue.insert(trips[i]);
}
}
}

if (endings.size() > 0) {
Trip end = *endings.begin();
for (int j = 0; j < end.path.size(); j++) {
result.push_back(end.path[j]);
}
}

return result;
}
``````

## Visualization

I converted the code to javascript and used p5.js to animate it. The frames were captured using ccapture.js and then the mp4 was created using ffmpeg.

### Creating the tile maps

The tile map was created from a pokemon sprite sheet I found. I then mapped the tiles to the ascii characters to generate the image. The original sheet had 32x32 tiles but I scaled those down to 16 and 8 to support larger maps.

The sprite sheet can be changed easily at the top of the animation by adjusting these constants:

``````
let SHEET_PATH = 'assets/iceMazeTiles.png'
let SWIDTH = 32;
let SHEIGHT = 32;
``````
• `assets/iceMazeTiles.png` for 32x32
• `assets/iceMazeTiles16.png` for 16x16
• `assets/iceMazeTiles8.png` for 8x8

Spiral solution using the 32x32 tiles: Here's a version in the online editor if you'd like to make changes: Ice Maze p5 sketch

### Drawing the animation

I cheated a little here. The solver is fast so we can do that in setup before entering the draw functions and then animate all the different paths that the solver generated. This is accomplished by keeping an animated frame list where each path is stored.

The `draw()` method moves to a `Trip` and continues drawing the directions travelled until the path is complete. It then moves to the next trip finally visiting the solution. The speed that it walks through the map and path can be controlled by the statement that checks the frame delta before incrementing the path index.

``````
if (abs(frameCount - lastFrame) > 1) {
animatedPathIdx++;
lastFrame = frameCount;
}
``````

### javascript set comparator

Internal javascript `sets` do not allow for a comparator to be passed in as a lambda function. I'm sure they have some javascript balanced tree algorithms out there but I didn't go looking. Instead, I ended up with this which is fast enough.

``````
function pathSort(a, b) {
//A doesn't have as many steps.  It goes first.
if (a.path.length < b.path.length) {
return -1;
}
//The path string has the same number of steps but not necessarily
//the same values.  We've also travelled the same distance
else if (a.path.length == b.path.length && a.distance == b.distance) {
//We want to keep unique paths
if (a.path < b.path)
return -1;
else
return 1;
}
//We've taken the same number of steps but the distance travelled is different
else if (a.path.length == b.path.length) {
if (a.distance < b.distance)
return -1;
else
return 1;
} else {
return 1;
}
}

function mySetInsert(myset, elem) {

let insert = true;
for (let i = 0; i < myset.length; i++) {
if (myset[i].path.length == elem.length && myset[i].distance == elem.distance &&
myset[i].path == elem.path) {
insert = false;
}
}
if (insert) {
myset.push(elem);
}
let result = myset.sort(pathSort);
return result;
}
``````

## Another fun search puzzle

CodeWars has another fun search problem `Stargate SG-1: Cute and Fuzzy (Improved version)`. I used an AStar search to solve that one.