🍔

Ice Maze Solver

2020-05-09 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:

Ice Map Key

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. 


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;

Spiral solution using the 32x32 tiles:

32x32 Example

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.