Ice Maze Solver
20200509 12:02:00
Spoiler Alert
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 breadthfirst 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[4];
if (lastDir != 'r')
trips[0] = walkLeft(map, p, wh);
if (lastDir != 'l')
trips[1] = walkRight(map, p, wh);
if (lastDir != 'd')
trips[2] = walkUp(map, p, wh);
if (lastDir != 'u')
trips[3] = 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 SG1: Cute and Fuzzy (Improved version)
. I used an AStar search to solve that one.