Context :
I am making a solver for a board game in Javascript. The game is set on fixed sized grid with 5 robots and some of the cells marked as goals. The player has to find the minimum amount of moves to reach a set goal with one of the robots. My solver uses Breadth First Search because I want to find the best solution. The main loop is based a Queue to hold the GameStates that need to be looked at.
My issue :
As of right now, my solver can find solutions for a depth of up to around 9 moves (solving takes 4s at that depth). I’m trying to optimise my code to gain performance.
What I’ve already done :
- I changed most of the Arrays into TypedArrays
- I added a Map to memorise the GameStates that I have already seen (different orders of moves can lead to the exact same position which can be skipped)
- I factored out some computaion outside the main loop for data that is needed very often like distances to walls.
What I want to try :
To better understand where performance was lost I took a look at the Chrome Performance Call Tree. From what I understand, it’s the GameState class that is very slow. To be fair I do create quite a lot of them but I feel I could gain from changing data structure here. Additionnaly, the main functions in my solver are quite fast in comparaison (solve which is the main loop, Move which computes a new GameState after playing a move and CheckWin which checks if a GameState is a valid solution)
My GameState class contains 2 fields :
- robots which is a Uint8Array(10)
- moves which is a Uint32Array(32)
I’m using low level datatypes like numbers and TypedArrays to represent positions, moves, robot colors and basically everything that I need to read/write while solving. The only things left that are a bit high level is the GameState class as well as the todoStates array used as the main Queue for BFS (see below).
My questions :
- Will I gain performance by changing the GameState Queue into a single linearised TypeArray ?
- Is there any better way to write a Queue in javascript ?
- Are there any other optimisations I can make to improve performance ?
export function solve(board, startingState, goal, maxDepth){
board = preComputeBoard(board);
let seenStates = new Map();
let todoStates = [startingState];
let checks = 0;
let stateId = -1;
let numOfStates = 1;
let startTime = Date.now();
while(stateId + 1 < numOfStates){
stateId++;
let state = todoStates[stateId];
if(state.moves[0] > maxDepth){continue;}
let stateKey = EncodeRobots(state.robots);
if(seenStates.has(stateKey)){continue;}
seenStates.set(stateKey, true);
checks++;
if(state.CheckWin(board, goal)){
console.log("checks", checks);
console.log("loops", stateId);
console.log("time", Date.now() - startTime);
return state;
}
for(let move = 0; move < 20; move++){
let newGameState = new GameState(state);
newGameState.Move(board, 1 << move);
todoStates.push(newGameState);
numOfStates++;
}
todoStates[stateId] = null;
}
return false;
}
