therufa
3/23/2016 - 3:54 PM

## Finding a way between two points on a chess board with the knight

Finding a way between two points on a chess board with the knight

``````'use strict';

// Defining board dimensions
const board = {
width: 8,
height: 8
};

// Maximum steps per subtree
const maxSteps = 8;

/**
* Here his array holds the path of the Knight
*/
const userCoords = [
[1,1], // start coord
[1,3]  // end coord
];

/**
* This matrix is supposed to serve as a calculation helper for
* my algorithm to find the desired spot on the table
*
* eg.
* [
*	[ 0,1,0 ],
*	[ y,0,0 ],
*	[ x,0,2 ]
* ]
*/
var boardMatrix = [
];

/**
* To solve the issue, I have decided to use a star-like search algorithm,
* since each position on the table can have maximum 8 directions to step to
* in optimal case, this won't occur of course if a point is close to the border.
*/

/**
*  Here the board matrix gets filled with placeholder data
*/
function buildBoard() {
for( let y = 0; y < board.height; y++ ) {
boardMatrix[y] = [];

for( let x = 0; x < board.width; x++ ) {
boardMatrix[y][x] = 0;
}
}
}

/**
* This generator provices a list of every possible step from a certain point on
* the "board".
*/
function* generateNextSteps( x, y ) {
const vectorDirections = [
[-1, 2],
[ 1, 2],
[ 2, 1],
[ 2,-1],
[ 1,-2],
[-1,-2],
[-2,-1],
[-2, 1]
];

for( let i = 0; i < 8; i ++ ) {
let vD = vectorDirections[i],
vX = -vD[0] + x,
vY = -vD[1] + y;

if( (vX >= 0 && vX < board.width) && (vY >= 0 && vY < board.height) ) {
yield [vX, vY];
}
}
}

/**
* A greedy search for possible steps
*/
function buildStepMap( x, y, depth, steps ) {

var depth = !! depth ? depth+=1 : 1,
steps = !! steps ? steps : [];

if( depth > maxSteps ) return false;

var stepCoord = generateNextSteps( x, y ),
step;

while( ! (step = stepCoord.next()).done ) {
let stepVal = step.value,
sX = stepVal[0],
sY = stepVal[1];

if( sX === userCoords[1][0] && sY == userCoords[1][1] ) {
return steps;
}

if( boardMatrix[sX][sY] == 0 ) {
steps.push([sX,sY]);

boardMatrix[sX][sY] = depth;
let result = buildStepMap(sX, sY, depth, steps);

if( !! result ) return result;
}
}
}

/**
* bootstrap, setup, check and run
*/

var xStart = userCoords[0][0],
yStart = userCoords[0][1],
xEnd = userCoords[1][0],
yEnd = userCoords[1][1];

if( (xStart < 0 || xStart >= board.width) || (yStart < 0 || yStart >= board.height ) ) {
throw new RangeError('Start parameter out of bounds!');
}

console.log('Start position:', xStart, yStart);

buildBoard();
var steps = buildStepMap( xStart, yStart );

console.log('Steps required: ', steps.length);
console.log('Steps in depth: ', steps); ``````