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.