Javascript 2D pathfinding algorithm with a turns limit


2021.04.15

Here, I'll explained my solution to check if two points can be connected by a line with a turns limit, like in the game 4Rivers. I'm sure it's poorly implemented, not optimized but it works !

Notes

  • This algorithm will not always returns the shortest distance or minimal turns.
  • Diagonal movements are not possibles.

The code

Demo (Enable debug mode)

function findPath(a, b, m) {

  /* 
  a and b are coordinates
  a = {
    x: 3,
    y: 1,
  };

  b = {
    x: 15,
    y: 9,
  };

  m is a 2d array containing either a id or null
  */

  //Determine which direction to explore first

  let dy = slotB.row - slotA.row;
  let dx = slotB.col - slotA.col;

  let d = [
    { x: -1, y: 0, d: dx * -1 },
    { x: 1, y: 0, d: dx },
    { x: 0, y: -1, d: dy * -1 },
    { x: 0, y: 1, d: dy },
  ];

  d = d.sort((a, b) => b.d - a.d);

  let p = []; //Path
  let c = { x: a.x, y: a.y }; //Current position is set to a

  //Recursive method
  function explore(c, p, t) {

    //If is the destination then return full path
    if (c.x == b.x && c.y == b.y) return p.concat(c);

    //Get last position
    const l = p.length > 0 ? p[p.length - 1] : null;

    //Consider each directions
    const w = [];
    for (let i = 0; i < d.length; i++) {
      //Calculate coordinates to consider
      const e = { x: c.x + d[i].x, y: c.y + d[i].y };

      //If coordinates outside of limits then skip
      if (e.y < 0 || e.x < 0 || e.y >= m.length || e.x >= m[e.y].length)
        continue;

      //If is previous then skip
      if (l != null && l.x == e.x && l.y == e.y) continue;

      //If unpassable then skip
      if (m[e.y][e.x] == null) continue;

      let tt = t;
      //If turning then subtract one
      if (
        p.length > 0 &&
        ((l.x == c.x && c.x != e.x) || (l.y == c.y && c.y != e.y))
      )
        tt--;

      //If can't turn then skip
      if (tt < 0) continue;

      //If no more turns and not aligned then skip
      if (tt == 0 && e.x != b.x && e.y != b.y) continue;

      //Calculate proximity as a score
      const v = Math.abs(b.x - e.x) + Math.abs(b.y - e.y) + 1;

      //If last turn and passing by B then skip
      if (tt <= 1 && v > c.v) continue;

      //Add direction to array of possibles directions
      w.push({ x: e.x, y: e.y, v: v, t: tt });

      //If this direction leads to destination, don't considers others
      if (v == 1) break;
    }

    //Sort directions by best proximity
    w.sort((aa, bb) => aa.v - bb.v);

    //Explore recursively directions
    for (let i = 0; i < w.length; i++) {
      let result = explore(w[i], p.concat(c), w[i].t);
      if (result != null) return result;
    }

    return null;
  }

  //the function returns the path if there's one, else it returns null 

  return explore(c, p, 2); //Turns limit of 2
}

Possible improvements

  • Look around B to check which sides are not blocked by a impassable tile.
  • Instead of a recursive method, maybe use a simple loop who would check the next most promising tile.