Home

Slider #2 - Cheating my way to victory

May 05, 2021 — Development, Algorithm

In this post

Slider #1 presented a concept: we now have a map containing a start and end block, yet how do we go from one to another? Well the answer is in this post, optimal path and maze solving, here we come!

If you haven't read previous posts in the Slider series, start here

The Goal

Nowadays I'm mostly working as a full-stack developer, juggling between AWS, Node Js, React and (no)SQL databases; the time when I used to learn and implement algorithms seems so far away... however, as lazy as I am, I do not plan to solve and verify every map by hand, a solver could be the solution so we'll try to have one at-the-ready by the end of this post.

What we have:

A well-defined rectangle map, of size $n = w \times h$
A starting position
An end position

What we want:

A way to know if a map is doable
The minimum number of moves needed to complete a map
The move list for said solution
A fast algorithm
Be able to (later) take into account special blocks

In order to do this we'll split the problem into 3 steps: studying and understanding, writing pseudo-code, writing real code.

Solving

The problem

This is when my background studies are supposed to come in handy, I have studied Introductory Combinatorics - a book about apples, bananas, oranges and how many different baskets you can arrange with $x$ given fruits - and Introduction to Algorithms (widely known as the algorithm Bible). Fact, my combinatorics book came from 机械工业出版社 (China Machine Press) and the whole back cover was in Chinese: the only thing I could make out was that the author is American.

Even though I've mainly studied these two subjects at Tsinghua University and got one of the highest grade at the final combinatorics exam, I'll level with you: I do not remember bugger all of all this. Which is why what follows was re-learned, shamelessly stolen from papers, inspired by math exchange posts and explanations will stay shallow, in order for me to avoid any blunders (and at the same time, you leaving this blog).

I've recently discovered in this research document that Slider is a puzzle variant of pushing games (such as Sokoban). Push and PushPush puzzles have been widely studied and have a similar complexity to our ice sliding game, that can be summarized to - quote unquote -: "Searching for a (and not the) shortest path between the start and end block, in an underlying subgraph of the grid"... lot of complex ideas for something quite straightforward. While I am not keen on raw maths, I believe to have an acute sense of observation; through 3 apparent postulates (and only 3), I'll show you how evident the problem is.

Postulates

#1

Have a look at the following 3x3 empty map:

How many positions can you access on the map ? Four, each corner is accessible with 1 or 2 moves; but only the corners: out of the $3 \times 3 = 9$ blocks, only 4 of them are accessible.

Now let us consider the following map:

Not only can you not access each empty block, but it is impossible to pass through the center of the map, as you would need a corner obstacle in order the access it. We could actually translate the previous map into this one:

Postulate 1: All empty blocks of a map are not necessarily accessible, others have simply no use.

#2

Even though a user input can result to nothing (trying to go right against a wall, will not change the player's position), each move, results to at least a one block position difference, may it be vertically or horizontally .

In the previous map, the player needs to consecutively make one block moves in order to reach the end. Even if the path is visually unclear (maze-like), it is impossible for the player to lose himself, as each position contain only two possible directions: either move forward into the unknown, or backtrack to where you came from.

The map contains 49 blocks, 34 empty blocks (start and end included), and requires 19 moves to finish it. It is obvious that a given Slider puzzle can not require more moves than the size of its map: the simplest puzzle would be a straight line, solvable in 1 input, however, each map needs at least 2 blocks: start and end.

A 7 block long line (1 move required):

A 2 block long line (1 move required):

Thus, in the exception that a mechanism forces us to take the same path multiple times (switches, buttons, portals, ...),

For:

\begin{aligned} m && \text{minimum number of moves} \\ e && \text{number of empty blocks} \\ n && \text{size of the map} \end{aligned}

We get

m < e \le n

Postulate 2: The minimum number of moves required to solve a map, shall be smaller than the number of empty blocks, which cannot be greater than the size of the map itself.

#3

I do not believe you will be able to solve the following puzzle:

Frustrating isn't it? Because the goal is to stop on the end block, and stopping is only possible against obstacles or the limits of the map, the objective should be placed on an accessible block (remember postulate 1). However this is true for any move: for every next aimed position, there should a previous position allowing to access it, and the next position should have not been visited before, otherwise the player would be going in circles.

Postulate 3: In order to solve the puzzle, one should find an accessible position, that was not accessed before.

Analysis

Postulates 1 and 2 tell us that the complexity (ie the number of moves) evolves with the size of the map, but cannot be greater than it. Because there is no need to take the same path twice, we know that all possible moves are contained in a map of size $n = w \times h$ . Those of you who have a background in computer science have guessed it: we can safely conclude that the algorithm needed is of $P$ complexity (polynomial) and can thus be expressed with $O(n^k)$ if it is linear/quadratic. This means that the algorithm run time grows as the input grows (obviously) and while I've talked about the $n^k$ form, logarithmic complexity should not be left aside yet. Nevertheless, focusing on the quadratic shape is the easiest and most probable approach: what's left is finding the exponent $k$ defining our growth.

Postulate 3 actually gives us the answer as how to solve our problem. Similarly to the Djikstra algorithm, we want to evaluate all paths bringing us to a new position: ie, looking for possible paths, trying one, looking for possible paths in that path, trying one, looking for possible paths in the path of that path, trying one, and so on... Remember our first complex idea: "Searching for a (and not the) shortest path between the start and end block, in an underlying subgraph of the grid", because each evaluated move in the grid creates a smaller range of possibilities, we can talk about a subgraph, in which once again, each move will create an even smaller subgraph in its parent grid. Much clearer now I hope!

In order to generate subgraphs and find the shortest path, we first need to detect all possible next positions. Taking the puzzle presented in Slider #1, the initial position is set to 0 (because no moves were required in order to get to the position).

Note that the end block is not represented, indeed, just like Djikstra, we are computing all needed paths from the source node (our initial position) to all others nodes (all other accessible blocks). More info on wikipedia.

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline \bold{0} & & \hphantom{A} & \\ \hline & \blacksquare & & \\ \hline & & & \blacksquare \\ \hline \blacksquare & & & \\ \hline \end{array}

From there, we try all possible directions (Up, Left, Down, Right) and check where we would end up on the map.

Up and Left are ignored, because we instantaneously hit a wall, whereas Down and Right take us somewhere else on the map. Their respective positions are noted as 1 on the map, because 1 move is needed in order to get there.

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline 0 & & \hphantom{A} & \bold{1} \\ \hline & \blacksquare & & \\ \hline \bold{1} & & & \blacksquare \\ \hline \blacksquare & & & \\ \hline \end{array}

Two subgraphs have now been generated, where the positions to consider are those marked 1, to which will be applied exactly the same logic. Here are the decomposed steps:

Top-right position

Up is ignored because it hits a wall
Right is ignored for the same reason
Left ends up on a previously visited block. Postulate 3 tells us that we should only search for unvisited blocks, meaning we should ignore this direction.
Down gets us to a new position, marked 2: the number of moves needed to get there

Bottom-left position

Up ends up on a previously visited block. Postulate 3 tells us that we should only search for unvisited blocks, meaning we should ignore this direction.
Left is ignored because it hits a wall
Down is ignored for the same reason
Right gets us to a new position, marked 2: the number of moves needed to get there

Next state:

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline 0 & & \hphantom{A} & 1 \\ \hline & \blacksquare & & \bold{2} \\ \hline 1 & & \bold{2} & \blacksquare \\ \hline \blacksquare & & & \\ \hline \end{array}

Continuing the algorithm until all accessible blocks have been visited...

3rd move:

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline 0 & & \bold{3} & 1 \\ \hline & \blacksquare & \bold{3} & 2 \\ \hline 1 & & 2 & \blacksquare \\ \hline \blacksquare & & \bold{3} & \\ \hline \end{array}

4th move:

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline 0 & & 3 & 1 \\ \hline & \blacksquare & 3 & 2 \\ \hline 1 & & 2 & \blacksquare \\ \hline \blacksquare & \bold{4} & 3 & \bold{4} \\ \hline \end{array}

5th move:

\def\arraystretch{1.5} \begin{array}{|c|c|c|c|} \hline 0 & & 3 & 1 \\ \hline & \blacksquare & 3 & 2 \\ \hline 1 & \bold{5} & 2 & \blacksquare \\ \hline \blacksquare & 4 & 3 & 4 \\ \hline \end{array}

Ignoring possible optimizations, we found all accessible positions for the puzzle, and the number of moves needed to get there. We can now cross-check our results with any position: if the end block happens to be on an empty square, the map is unsolvable, however, if the end block is somewhere else, we know it will take the linked number of moves to solve the puzzle (eg: if we want to get to the bottom right of the map, the minimum number of moves required is 4).

That's it, we just solved a puzzle. Getting back to our problem at hand, we still need to find our final complexity, more precisely, our $k$ exponent... or do we? We just proved we are exploring the map through subgraphs (defined by 4 possible directions), so each position, will generate at most 4 positions. Wait, 4 new positions? We know thanks to postulate 3 that it makes no sense to go back, so 3 positions! Still no, we need an obstacle in order to bring ourselves to a halt, and once against the wall, we are stuck. We just proved there are only 2 moves that should be evaluated each time: because we generate subgraphs each time, our exponent is $k = 2$ and our running time ends up being $O(n^2)$ . This is where I should prove that just like Djikstra, because only 2 positions are checked, we would end up with $O(n\log n)$ in most cases, but I'll leave that to professionals.

We now have everything we need to automate our puzzle resolution, see you in the next step, it is down to coding!

Draft code

For simplification purposes, lot of things will be implied in this section, the goal is only to sketch the coding process of our future script.

First, we need to setup some variables

// we expect map to be a 2D array
// with obstacles and empty blocks
set Map = getMap()

// measurements will come in handy
set mapWidth = Map.getWidth()
set mapHeight = Map.getHeight()

// all directions we will need to check
set possibleDirections = ["Up", "Left", "Down", "Right"]

Ok, even though I am leaving aside obvious necessities, that's a good start. Now that we have defined the basics, we want to list core functions of our algorithm

// takes a string input, and parses it into an array
function getMap(mapString) do
  // this function will not be detailed here

  // returns well formatted map
end

// given a direction, computes the next position on the map
function getNewPos(currentPosition, direction, map) do
  // tries to go into a direction, until player hits a wall

  // returns the new position
end

// creates a map, containing all accessible block
// and their respective required number of moves
// (exactly like in the analysis part)
function getAccessibleMap(startPosition, map) do
  // creates an empty map
  // tries to go into all possible directions
  // fills the map with accessible blocks
  //  loops until no positions are accessible

  // returns the moveMap
end

// first function called
function main() do
  // calls getMap() and getAccessibleMap()
  // prints the result
end

Having described everything, the next step is detailing each function. getMap is not needed yet, main will be completed at the end, getNewPos is quite effortless to understand; left is getAccessibleMap, which will contain our algorithm, it is consequently key to understand what it should do, and how it should do it.

getNewPos

In order to compute our new position, we start from the player's current position. We then move forward as long as we are still in the map (we would not want falling at the end of the world), checking at the same time that the block in front of us is not a wall. If it is a wall, we stop looping and return the position we got to, else we continue looping (until we hit the border of the map, or a wall).

function getNewPos(currentPosition, direction, map) do
  // we start moving from currentPosition
  set newPosition = currentPosition

  // as long as there exists a block in the chosen direction
  // we try moving one block forward
  while isInMapBoundaries(newPosition + direction) do
    // test next position
    testPosition = newPosition + direction

    // hitting a wall breaks the loop
    if map[testPosition] is WALL do
      break
    // tested position is ok, we can move forward
    else do
      newPosition = testPosition
    end
  end

  return newPosition
end

getAccessibleMap

First step is initializing our access map with the size of our input map. The map should eventually contain some positive values corresponding to the number of moves required to get there, thus we want to avoid any confusion between accessed and unaccessed blocks. More over, we need a list containing positions to check (if each move can generate two new positions, we'll quickly have a lot of positons requiring our attention).

set accessibleMap = newMap(mapWidth, mapHeight)

// filling our new map with negative values will ease the
// difference detection between visited and unvisited blocks
accessibleMap.fill(-1)

// just like in our analysis,
// we define the start as move zero
accessibleMap[startPosition] = 0

set positionToCheck = []

// startPosition is the first one we need to evaluate
positionsToCheck.push(startPosition)

Coming next is our main loop. As long as there are positions to check in our array, we want to

Loop through all directions
Get new positions computed from these directions
Ignore those not ending on -1 cells (which would mean we have already visited the position)
Set the accessibleMap positions value to number of moves to get there + 1
Add our new positions to positionToCheck

The loop should eventually stop once we have computed everything, because no new positions would end up -1, getting ignored, meaning we'll finally run out of positions to check.

// loop until we hit the end of the array
for (set i = 0; i < positionsToCheck.length; i = i + 1) do
  // set position variable, it is clearer this way
  set position = positionsToCheck[i]

  set nextPositions = []

  // iterate on all four directions to test positions
  foreach (direction in possibleDirections) do
    // get new position
    newPosition = getNewPos(position, direction, map)
    // if the new position was not visited
    // add it to our nextPositions array
    if (accessibleMap[newPosition] == -1) do
      nextPositions.push(newPosition)
    end
  end

  // use our newly computed positions
  foreach (nextPos in nextPositions) do
    // set cell to minimum number of moves to get there
    accessibleMap[nextPos] = accessibleMap[position] + 1

    // we will need to check this position next iteration
    // so we add it to our main loop array
    positionsToCheck.push(nextPos)
  end
end

We're done for getAccessibleMap logic, here's the uncommented merged version, and main function:

Click to expand

function getNewPos(currentPosition, direction, map) do
  set newPosition = currentPosition

  while isInMapBoundaries(newPosition + direction) do
    testPosition = newPosition + direction

    if map[testPosition] is WALL do
      break
    else do
      newPosition = testPosition
    end
  end

  return newPosition
end

function getAccessibleMap(startPosition, map) do
  set accessibleMap = newMap(mapWidth, mapHeight)
  accessibleMap.fill(-1)
  accessibleMap[startPosition] = 0

  set positionToCheck = []
  positionsToCheck.push(startPosition)

  for (set i = 0; i < positionsToCheck.length; i = i + 1) do
    set position = positionsToCheck[i]
    set nextPositions = []

    foreach (direction in possibleDirections) do
      newPosition = getNewPos(position, direction, map)
      if (accessibleMap[newPosition] == -1) do
        nextPositions.push(newPosition)
      end
    end

    foreach (nextPos in nextPositions) do
      accessibleMap[nextPos] = accessibleMap[position] + 1
      positionsToCheck.push(nextPos)
    end
  end

  return accessibleMap
end

function main() do
  // arbitrarily set start and end positions
  set startPosition = {x: 0, y: 0}
  set endPosition = {x: 3, y: 4}

  set accessibleMap = getAccessibleMap(startPosition, map)

  // get value set at the end position
  set nbMoves = accessibleMap[endPosition]
  // a -1 value means we never accessed the cell
  // => puzzle is unsolvable
  if (nbMoves == -1) do
    print("no solutions were found")
  // otherwise we can get to endPosition in n moves
  // => puzzle is solvable
  else do
    print("map can be solved in {nbMoves} moves!")
  end
end

Djikstra is known as a recursive algorithm for good reasons, and knowing that what was presented above is similar, you could (and probably should) ask yourself why I chose loops. The first reason is personal, recursion is needed for certain functions (such as Divide and Conquer algorithms) but I believe it to be mostly unreadable, hard to debug, and messy to modify. The second reason is in prediction of what's coming next, I'm relieved that the algorithm works and can solve simple puzzles, but I did not take the time (yet) to prepare all future game mechanisms: those will probably require special conditions that do not go well with recursion.

I already hear some of you saying "pushing values in a non-fixed size array is O(N), recursion is better!". First of all, that's simply not true in modern array implementations, and I could use linked list if I really wanted to, making it O(1). Oh and I do not plan to create 1000x1000 maps, meaning memory does not need that kind of optimization.

Congratulations to you, for having followed me up to here! Next section is about real world script, with real world problems, where things usually go real wrong. However, if you do not feel like diving into it you can skip it and jump to the conclusion: the algorithm logical core has already been explained.

Real code

In an effort to, at last, efficiently cheat in ice sliding puzzles, I will use Javascript and basic NodeJS scripting. Because this post starts feeling like it is going on forever, only technical choices will be justified in a succession of small steps.

Setup

Defining our text map, global variables, and directions object:

// usually defined in another file
const mapDemo = {
  mapTxt: `
    ____
    _*__
    ___*
    *___
  `,
  startPos: [0, 0],
  endPos: [3, 3],
};

const WALL = '*';
const EMPTY = '_';

let mapWidth;
let mapHeight;

// position to add in order to move player in direction
const dirMap = {
  'Up': [-1, 0],
  'Down': [1, 0],
  'Left': [0, -1],
  'Right': [0, 1],
};

// useful to reduce the number of iterations
const oppositeDirMap = {
  'Up': 'Down',
  'Down': 'Up',
  'Left': 'Right',
  'Right': 'Left',
};

// accessibleMap will be 1D, this will come in handy
function posToFlat(pos) {
  return pos[0] * mapWidth + pos[1];
}

// same reason
// those 2 functions are here to make code more readable
function flatToPos(flat) {
  return [Math.floor(flat / mapWidth), flat % mapWidth];
}

Parsing

Next step is parsing the map from its text form. However we will not use a 2D array, like show in the draft code part. 2D arrays are human readable and quite simple to conceptualize, but add nothing else in this case, if not the bonus of making some operations more complicated.

function parse(mapTxt) {
  let map = mapTxt
    // deleting indentation
    .replace(/( |\t)/g, '')
    // separating map by line
    .split('\n')
    // moving empty lines that could appear with
    // useless linebreaks or empty spaces
    .filter(e => e.length !== 0);

  // set map sizings
  mapWidth = map[0].length;
  mapHeight = map.length;

  // flatten array to make it 1D
  map = map.flat();

  return map;
}

Getting new position

This one does not change much from the draft code. However this is where flatToPos and posToFlat will come into play, because it is really messy making boundary checks with flat coordinates.

function getNewPos(pos, dir, map) {
  const dirPos = dirMap[dir];
  let newPos = flatToPos(pos);
  // this syntax creates a deep copy
  // we wouldn't want a reference
  let tmpPos = [...newPos];

  tmpPos[0] += dirPos[0];
  tmpPos[1] += dirPos[1];
  // boundary checks
  while (
    tmpPos[0] < mapHeight
    && tmpPos[0] >= 0
    && tmpPos[1] < mapWidth
    && tmpPos[1] >= 0
  ) {
    // if whats is in front of us is not an empty block,
    // we stop moving forward
    if (map[posToFlat(tmpPos)] !== EMPTY) break;
    //start again
    newPos = [...tmpPos];
    tmpPos[0] += dirPos[0];
    tmpPos[1] += dirPos[1];
  }

  // return 1D position
  return posToFlat(newPos);
};

Getting access map

Three modifications will come up in this function:

Instead of storing move numbers, we will directly store the move list (eg: ["Up", "Left", "Down"]). This cuts a computing step, and we can still get the minimum required number of moves to complete the map, by looking at our move list's length.
We proved each iteration only needs to look at 2 directions each time, selecting them will be done thanks to our oppositeDirMap.
endPos is passed as a parameter in order to stop our algorithm as soon as we hit the exit. No need to compute all accessible blocks in this case.

function getAccessibleMap(startPos, endPos, map) {
  // create a null-filled array
  const moveList = new Array(mapWidth * mapHeight).fill(null);
  // first position needed no move, so moveList is empty
  moveList[startPos] = [];
  // first position to check is the initial one
  const positionsToCheck = [startPos];

  for (let i = 0; i < positionsToCheck.length; i++) {
    const position = positionsToCheck[i];

    // get last direction used by player
    const lastMoveList = moveList[position];
    const lastDirection = lastMoveList[lastMoveList.length - 1];

    // iterate other all directions
    const nextPositions = Object.keys(dirMap)
      // filter out uneeded directions
      // => the last used direction
      // => the opposition direction to the last one
      .filter((direction) => {
        if (!lastDirection) return true;
        return (direction !== lastDirection
          && direction !== oppositeDirMap[lastDirection]);
      })
      // we need to store the chosen direction and the new position
      .map((direction) => ({
        dir: direction,
        nextPos: getNewPos(position, direction, map),
      }))
      // we do not want positions ending on visited blocks
      .filter(({ nextPos }) => moveList[nextPos] === null);

    // iterating other new found positions
    for (let j = 0; j < nextPositions.length; j++) {
      const { dir, nextPos } = nextPositions[j];
      // adding our direction to the moveList
      moveList[nextPos] = moveList[position].concat(dir);
      // if the next position corresponds to the end position
      // no need to continue
      if (nextPos === endPos)
        return moveList[nextPos];
      // add next position to positions needing a checkup
      positionsToCheck.push(nextPos);
    }
  }

  // if the final block was not found, return null
  return null;
}

Main function

Parse the puzzle map, gets the accessibleMap, prints the result.

function main() {
  const map = parse(mapDemo.mapTxt);
  const { startPos, endPos } = mapDemo;

  const solution = getAccessibleMap(
    posToFlat(startPos),
    posToFlat(endPos),
    map,
  );

  if (solution) {
    console.log(`Map can be solved in ${solution.length} moves:\n`, solution)
  } else {
    console.log('Map has no solution');
  }
}

Just like previously, here's the full version:

If you have nodeJs installed, you can simply paste the script into a .js file and run node file.js to test it

Click to expand

const mapDemo = {
  mapTxt: `
    ____
    _*__
    ___*
    *___
  `,
  startPos: [0, 0],
  endPos: [3, 3],
};

// never used in the end
const WALL = '*';
const EMPTY = '_';

let mapWidth;
let mapHeight;

const dirMap = {
  'Up': [-1, 0],
  'Down': [1, 0],
  'Left': [0, -1],
  'Right': [0, 1],
};

const oppositeDirMap = {
  'Up': 'Down',
  'Down': 'Up',
  'Left': 'Right',
  'Right': 'Left',
};

function posToFlat(pos) {
  return pos[0] * mapWidth + pos[1];
}

function flatToPos(flat) {
  return [Math.floor(flat / mapWidth), flat % mapWidth];
}

function parse(mapTxt) {
  let map = mapTxt.replace(/( |\t)/g, '')
    .split('\n')
    .filter(e => e.length !== 0);

  mapWidth = map[0].length;
  mapHeight = map.length;

  map = map.reduce((acc, val) => acc.concat(val.split('')), []);

  return map;
}

function newPos(pos, dir, map) {
  const dirPos = dirMap[dir];
  let newPos = flatToPos(pos);
  let tmpPos = [...newPos];

  tmpPos[0] += dirPos[0];
  tmpPos[1] += dirPos[1];
  while (
    tmpPos[0] < mapHeight
    && tmpPos[0] >= 0
    && tmpPos[1] < mapWidth
    && tmpPos[1] >= 0
  ) {
    if (map[posToFlat(tmpPos)] !== EMPTY) break;
    newPos = [...tmpPos];
    tmpPos[0] += dirPos[0];
    tmpPos[1] += dirPos[1];
  }

  return posToFlat(newPos);
};

function getPossibleMoves(startPos, endPos, map) {
  const moveList = new Array(mapWidth * mapHeight).fill(null);
  moveList[startPos] = [];
  const positionsToCheck = [startPos];

  for (let i = 0; i < positionsToCheck.length; i++) {
    const position = positionsToCheck[i];

    const lastMoveList = moveList[position];
    const lastDirection = lastMoveList[lastMoveList.length - 1];

    const nextPositions = Object.keys(dirMap)
      .filter((direction) => {
        if (!lastDirection) return true;
        return (direction !== lastDirection
          && direction !== oppositeDirMap[lastDirection]);
      })
      .map((direction) => ({
        dir: direction,
        nextPos: newPos(position, direction, map),
      }))
      .filter(({ nextPos }) => moveList[nextPos] === null);

    for (let j = 0; j < nextPositions.length; j++) {
      const { dir, nextPos } = nextPositions[j];
      moveList[nextPos] = moveList[position].concat(dir);
      if (nextPos === endPos)
        return moveList[nextPos];
      positionsToCheck.push(nextPos);
    }
  }

  return null;
}

function main() {
  const map = parse(mapDemo.mapTxt);
  const { startPos, endPos } = mapDemo;

  const solution = getPossibleMoves(
    posToFlat(startPos),
    posToFlat(endPos),
    map,
  );

  if (solution) {
    console.log(`Map can be solved in ${solution.length} moves:\n`, solution)
  } else {
    console.log('Map has no solution');
  }
}

main();

Phew! What a wild ride that was, but we made it. In the end, how many things did we accomplish from our initial checklist?

A way to know if a map is doable: check
The minimum number of moves needed to complete a map: check
The move list for said solution: check
A fast algorithm: check
Be able to (later) take into account special blocks half-check

The good thing about our getNewPos function is its ability to change in order to fit our needs: portals special moves can be computed in the function, boosters or deadly holes too. However, things wil start getting tough once I try adding multiple players on the map or one-time use powerups... I'm sure future-me will manage.

Conclusion

Implementing algorithms is usually the opposite of fun: wondering why nothing is working as expected and how to debug hundreds or iterations, only to realise I had typoed a + into a -. All those little things are part of the job, and even if they are a pain most of the time, they also sometimes lead to a jubilant feeling: success.

Above is one of the ice path puzzle that can be found in pokemon Gold/Silver, below is its translation in txt.

export const mapIcePath = {
  mapTxt: `
    ________*_____
    ___*__________
    _________*____
    _*____________
    *_______*_____
    _____________*
    ______*_______
    __*___________
    _____________*
    _______*______
    _____*___*____
    ______________
  `,
  startPos: [11, 13],
  endPos: [7, 13],
};

With that I ran the solver, and this is what I got

$> node solver.js

Map can be solved in 15 moves:
 [
  'Left',  'Up',    'Right',
  'Up',    'Right', 'Down',
  'Left',  'Up',    'Left',
  'Down',  'Right', 'Down',
  'Right', 'Up',    'Right'
]

Impressed? I sure hope so, but the last step is testing it out on the puzzle below, keep me posted on the result: if there is one thing you can not cheat on, it is sleep. No worries though, we'll see each other again in Slider #3!