Game

The web application here is KnightRush, a free beta version of ChessNext. If you are using a desktop browser, it is recommended to switch to windowed mode.

Click to start!

♕

♞

♜

♝

Optimized Pathfinding for Knight Moves in JavaScript

I use a 4-dimensional array for the knight's movement heuristic, which stores the minimum number of moves between every possible start and target square. The array structure is: hCost[x1][y1][x2][y2], where (x1, y1) is the starting position and (x2, y2) is the target.

The heuristic is not calculated at runtime but instead generated by a separate C program using a brute-force method. This program computes the minimum number of moves for every possible start–target square pair on an 8x8 board, resulting in a complete 8x8x8x8 array. Since it uses exhaustive search, it provides accurate values for all combinations, giving the A* algorithm a perfect estimate.

On my laptop, it took about 12 minutes for the C program to generate the entire array. I then loaded the result into JavaScript, where the knight's movement now always follows the shortest path using the A* algorithm.

This approach is extremely fast, as each heuristic lookup is a simple array access (O(1) time), and extremely accurate, since the heuristic is not an estimate but the actual minimum number of moves.

This is especially useful because knight movements don’t conform to standard heuristics like Manhattan or Euclidean distances, which would result in inaccurate estimates. However, by using precomputed move counts, the knight always finds the optimal path.

This system is easily extendable to other pieces as well, such as rook, bishop, king, etc., with different heuristics for each.