# Animating Pathfinding Generically

This is part of a project I built to visualise pathfinding algorithms. These files run the algorithms and gather a list of frames, which are used to show the animations.

algorithms.ts

export type Algorithm = (start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) => GridFrame[];

export function breadthFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const queue = new Queue<Coord>();
const distances = new HashMap<Coord, number>();

return genericUnidirectionalSearch(start, goal, queue, distances, weights, walls);
}

export function depthFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const stack = new Stack<Coord>();
const distances = new HashMap<Coord, number>();

return genericUnidirectionalSearch(start, goal, stack, distances, weights, walls);
}

export function bestFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const heuristicComparator = stringToHeuristic.get(heuristic)(goal);
const priorityQueue = new PriorityQueue(heuristicComparator);
const distances = new HashMap<Coord, number>();

return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function dijkstra(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const distances = new HashMap<Coord, number>();
const distanceComparator = generateDijkstraComparator(distances);
const priorityQueue = new PriorityQueue(distanceComparator);

return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function aStar(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const distances = new HashMap<Coord, number>();
const comparator = generateAStarComparator(goal, distances, heuristic);
const priorityQueue = new PriorityQueue(comparator);

return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function randomSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const distances = new HashMap<Coord, number>();
const comparator = generateRandomComparator();
const priorityQueue = new PriorityQueue(comparator);

return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function bidirectionalBFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const forwardQueue = new Queue<Coord>();
const backwardQueue = new Queue<Coord>();

return genericBidirectionalSearch(forwardQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalDFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const forwardsStack = new Stack<Coord>();
const backwardStack = new Stack<Coord>();

return genericBidirectionalSearch(forwardsStack, backwardStack, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalGBFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const forwardsComparator = stringToHeuristic.get(heuristic)(goal);
const backwardsComparator = stringToHeuristic.get(heuristic)(start);
const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalDijkstra(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const forwardsComparator = generateDijkstraComparator(forwardsDistances);
const backwardsComparator = generateDijkstraComparator(backwardsDistances);
const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalAStar(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const forwardsComparator = generateAStarComparator(goal, forwardsDistances, heuristic);
const backwardsComparator = generateAStarComparator(start, backwardsDistances, heuristic);
const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalRandom(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
const forwardsDistances = new HashMap<Coord, number>();
const backwardsDistances = new HashMap<Coord, number>();
const comparator = generateRandomComparator();
const forwardsQueue = new PriorityQueue<Coord>(comparator);
const backwardQueue = new PriorityQueue<Coord>(comparator);

return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}


genericPathfinding.ts


// Generic pathfinding algo for searching from a source. Parameterized with the data structure used to make it generic
export function genericUnidirectionalSearch(
start: Coord,
goal: Coord,
agenda: Collection<Coord>,
distances: HashMap<Coord, number>,
weights: number[][],
walls: boolean[][]) {

const path = new HashMap<Coord, Coord>();
const visited = initialseGridWith(false);
const considered = initialseGridWith(false);
const frames: GridFrame[] = [];

visited[start.row][start.col] = true;

while (!agenda.isEmpty()) {
const isFound = considerNextNode(path, visited, agenda, goal, weights, considered, walls, distances, frames);

if (isFound) {
const finalPath = pathMapToGrid(path, goal);

createFinalPathFrame(finalPath, visited, considered, frames);
break;
}
}

return frames;
}

// Generic pathfinding algo for searching from both the source and goal concurrently
export function genericBidirectionalSearch(
forwardAgenda: Collection<Coord>,
backwardAgenda: Collection<Coord>,
forwardDistances: HashMap<Coord, number>,
backwardDistances: HashMap<Coord, number>,
start: Coord,
goal: Coord,
weights: number[][],
walls: boolean[][]) {

const forwardPath = new HashMap<Coord, Coord>();
const backwardPath = new HashMap<Coord, Coord>();

const forwardVisited = initialseGridWith(false);
const backwardVisited = initialseGridWith(false);

const forwardConsidered = initialseGridWith(false);
const backwardConsidered = initialseGridWith(false);

const frames: GridFrame[] = [];

forwardVisited[start.row][start.col] = true;
backwardVisited[goal.row][goal.col] = true;

while (!forwardAgenda.isEmpty() && !backwardAgenda.isEmpty()) {
const foundForwards = considerNextNode(forwardPath, forwardVisited, forwardAgenda, goal, weights, forwardConsidered, walls, forwardDistances, frames);
const foundBackwards = considerNextNode(backwardPath, backwardVisited, backwardAgenda, start, weights, backwardConsidered, walls, backwardDistances, frames);

mergeFrames(frames);

if (foundForwards) {
const finalPath = pathMapToGrid(forwardPath, goal);
const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
break;
} else if (foundBackwards) {
const finalPath = pathMapToGrid(backwardPath, start);
const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
break;
} else if (hasIntersection(forwardConsidered, backwardConsidered)) {
const intersection = getIntersection(forwardConsidered, backwardConsidered);
const finalPath = mergeGrids(pathMapToGrid(forwardPath, intersection), pathMapToGrid(backwardPath, intersection));
const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
break;
}
}

return frames;
}

// Generic function for making one step in a pathfinding algorithm
function considerNextNode(
path: HashMap<Coord, Coord>,
visited: boolean[][],
agenda: Collection<Coord>,
goal: Coord,
weights: number[][],
considered: boolean[][],
walls: boolean[][],
distances: HashMap<Coord, number>,
frames: GridFrame[]) {

const currentPos = agenda.remove();
const currentNeighbours = generateNeighbours(currentPos);

considered[currentPos.row][currentPos.col] = true;
frames.push(generateGridFrame(visited, considered, []));

if (isSameCoord(currentPos, goal)) {
return true;
}

currentNeighbours.forEach(neighbour => {
if (!isOutOfBounds(neighbour) && !walls[neighbour.row][neighbour.col]) {
const neighbourDistance = distances.get(currentPos) + weights[neighbour.row][neighbour.col];

if (!visited[neighbour.row][neighbour.col]) {
visited[neighbour.row][neighbour.col] = true;
}
}
});

return false;
}

// Given two boolean grids, for all tiles, take the logical OR and return a new grid
function mergeGrids(grid: boolean[][], matrix: boolean[][]) {
const mergedGrid = initialseGridWith(false);

for (let row = 0; row < HEIGHT; row++) {
for (let col = 0; col < WIDTH; col++) {
mergedGrid[row][col] = grid[row][col] || matrix[row][col];
}
}

return mergedGrid;
}

// Merge two animation frames to produce a frame that contains the information encoded in both
function mergeFrames(frames: GridFrame[]) {
const backwardsFrame = frames.pop();
const forwardsFrame = frames.pop();
const mergedFrame = initialseGridWith(TileFrame.Blank);

for (let row = 0; row < HEIGHT; row++) {
for (let col = 0; col < WIDTH; col++) {
if (forwardsFrame[row][col] === TileFrame.Searching || backwardsFrame[row][col] === TileFrame.Searching) {
mergedFrame[row][col] = TileFrame.Searching;
} else if (forwardsFrame[row][col] === TileFrame.Frontier || backwardsFrame[row][col] === TileFrame.Frontier) {
mergedFrame[row][col] = TileFrame.Frontier;
}
}
}

frames.push(mergedFrame);
}

// Add a frame containing the final path to the list
function createFinalPathFrame(path: boolean[][], visited: boolean[][], considered: boolean[][], frames: GridFrame[]) {
frames.push(generateGridFrame(visited, considered, path));
}

// Convert the hashmap pointer based path to a boolean grid based path
function pathMapToGrid(pathMap: HashMap<Coord, Coord>, goal: Coord) {
const path = initialseGridWith(false);
let pos = goal;

while (pathMap.get(pos) !== undefined) {
path[pos.row][pos.col] = true;

pos = pathMap.get(pos);
}

return path;
}

// Encode the state of a pathfinding algorithm into a frame
function generateGridFrame(visited: boolean[][], considered: boolean[][], path: boolean[][]) {
const grid = initialseGridWith(TileFrame.Blank);

for (let row = 0; row < HEIGHT; row++) {
for (let col = 0; col < WIDTH; col++) {
if (path.length > 0 && path[row][col]) {
grid[row][col] = TileFrame.Path;
} else if (considered[row][col]) {
grid[row][col] = TileFrame.Searching;
} else if (visited[row][col]) {
grid[row][col] = TileFrame.Frontier;
}
}
}

return grid;
}


Comparators.ts


type Heuristic = (goal: Coord) => (c1: Coord, c2: Coord) => number;

// Map a heuristics JSX representation onto its implementation
export const stringToHeuristic = new Map<string, Heuristic>([
["manhattan", generateManhattanComparator],
["euclidean", generateEuclideanComparator],
["chebyshev", generateChebyshevComparator]
]);

// Return a comparator that compares by adding the distance from the starting tile and estimated distance from the goal
export function generateAStarComparator(goal: Coord, distances: HashMap<Coord, number>, heuristic: string) {
return (c1: Coord, c2: Coord) => {
const heuristicGenerator = stringToHeuristic.get(heuristic);
const dijkstraComparison = generateDijkstraComparator(distances)(c1, c2);
const heuristicComparison = heuristicGenerator(goal)(c1, c2);

return dijkstraComparison + heuristicComparison;
}
}

// Returns a comparator that compares using the distance from the starting tile
export function generateDijkstraComparator(distances: HashMap<Coord, number>) {
return (c1: Coord, c2: Coord) =>
distances.get(c2) - distances.get(c1);
}

// Returns a comparator that selects an item randomly
export function generateRandomComparator() {
return (c1: Coord, c2: Coord) => Math.random() - 0.6;
}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula max(abs(p1 - g1), abs(p2 - g2))
function generateChebyshevComparator({ row: goalRow, col: goalCol }: Coord) {
return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) =>
Math.max(Math.abs(r2 - goalRow), Math.abs(c2 - goalCol)) - Math.max(Math.abs(r1 - goalRow), Math.abs(c1 - goalCol));

}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula sqrt((p1 - g1)^2 + abs(p2 - g2)^2)
function generateEuclideanComparator({ row: goalRow, col: goalCol }: Coord) {
return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) => {
const r1Dist = Math.sqrt(Math.pow(r1 - goalRow, 2) + Math.pow(c1 - goalCol, 2));
const r2Dist = Math.sqrt(Math.pow(r2 - goalRow, 2) + Math.pow(c2 - goalCol, 2));

return r2Dist - r1Dist;
}
}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula abs(p1 - g1) + abs(p2 - g2)
function generateManhattanComparator({ row: goalRow, col: goalCol }: Coord) {
return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) =>
(Math.abs(r2 - goalRow) + Math.abs(c2 - goalCol)) - (Math.abs(r1 - goalRow) + Math.abs(c1 - goalCol));

}