Bookmark this: tool.io/pathfinding/a-star/source-code
A* Pathfinding Visualizer Source Code
Browse the implementation files for A* Pathfinding Visualizer.tool.ts typescript
// Tool: A* Pathfinding Visualizer
type Heuristic =
| 'automatic'
| 'chebyshev'
| 'euclidean'
| 'manhattan'
| 'octile'
| 'zero';
type Movement = '4-way' | '8-way';
interface Point {
x: number;
y: number;
}
interface QueueItem {
index: number;
priority: number;
sequence: number;
}
const HEURISTICS: Heuristic[] = [
'automatic',
'manhattan',
'euclidean',
'chebyshev',
'octile',
'zero'
];
const MAX_CELLS = 10_000;
const MOVEMENTS: Movement[] = ['4-way', '8-way'];
class MinHeap {
private values: QueueItem[] = [];
get length(): number {
return this.values.length;
}
push(value: QueueItem): void {
this.values.push(value);
let index = this.values.length - 1;
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (!this.less(value, this.values[parent])) break;
this.values[index] = this.values[parent];
index = parent;
}
this.values[index] = value;
}
pop(): QueueItem | undefined {
const first = this.values[0];
const last = this.values.pop();
if (first === undefined || last === undefined) return first;
if (this.values.length === 0) return first;
let index = 0;
this.values[0] = last;
while (true) {
const left = index * 2 + 1;
const right = left + 1;
let smallest = index;
if (
left < this.values.length &&
this.less(this.values[left], this.values[smallest])
) {
smallest = left;
}
if (
right < this.values.length &&
this.less(this.values[right], this.values[smallest])
) {
smallest = right;
}
if (smallest === index) break;
[this.values[index], this.values[smallest]] = [
this.values[smallest],
this.values[index]
];
index = smallest;
}
return first;
}
private less(first: QueueItem, second: QueueItem): boolean {
return (
first.priority < second.priority ||
(first.priority === second.priority &&
first.sequence < second.sequence)
);
}
}
const parseGrid = (input: unknown): number[][] | null => {
if (typeof input !== 'string' || input.trim() === '') return null;
try {
const grid = JSON.parse(input);
if (
!Array.isArray(grid) ||
grid.length === 0 ||
!Array.isArray(grid[0]) ||
grid[0].length === 0 ||
grid.length * grid[0].length > MAX_CELLS
) {
return null;
}
const width = grid[0].length;
return grid.every(
(row: unknown) =>
Array.isArray(row) &&
row.length === width &&
row.every((cell) => cell === 0 || cell === 1)
)
? grid
: null;
} catch {
return null;
}
};
const parsePoint = (input: unknown): Point | null => {
if (typeof input !== 'string') return null;
const match = input.match(/^\s*(\d+)\s*,\s*(\d+)\s*$/);
if (match === null) return null;
const x = Number(match[1]);
const y = Number(match[2]);
return Number.isSafeInteger(x) && Number.isSafeInteger(y)
? { x, y }
: null;
};
const distance = (
from: Point,
to: Point,
heuristic: Heuristic,
movement: Movement
): number => {
const dx = Math.abs(from.x - to.x);
const dy = Math.abs(from.y - to.y);
const selected =
heuristic === 'automatic'
? movement === '4-way'
? 'manhattan'
: 'octile'
: heuristic;
switch (selected) {
case 'manhattan':
return dx + dy;
case 'euclidean':
return Math.hypot(dx, dy);
case 'chebyshev':
return Math.max(dx, dy);
case 'octile':
return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy);
default:
return 0;
}
};
export const aStarPathfinding = (
gridInput: unknown,
startInput: unknown,
goalInput: unknown,
movementInput: unknown,
heuristicInput: unknown
): string => {
const grid = parseGrid(gridInput);
const start = parsePoint(startInput);
const goal = parsePoint(goalInput);
if (
grid === null ||
start === null ||
goal === null ||
!MOVEMENTS.includes(movementInput as Movement) ||
!HEURISTICS.includes(heuristicInput as Heuristic)
) {
return '';
}
const movement = movementInput as Movement;
const heuristic = heuristicInput as Heuristic;
if (
(movement === '4-way' && heuristic === 'octile') ||
(movement === '8-way' && heuristic === 'manhattan')
) {
return '';
}
const height = grid.length;
const width = grid[0].length;
const inBounds = ({ x, y }: Point): boolean =>
x >= 0 && x < width && y >= 0 && y < height;
if (
!inBounds(start) ||
!inBounds(goal) ||
grid[start.y][start.x] === 1 ||
grid[goal.y][goal.x] === 1
) {
return '';
}
const toIndex = ({ x, y }: Point): number => y * width + x;
const toPoint = (index: number): Point => ({
x: index % width,
y: Math.floor(index / width)
});
const startIndex = toIndex(start);
const goalIndex = toIndex(goal);
const scores = new Float64Array(width * height);
const previous = new Int32Array(width * height);
const closed = new Uint8Array(width * height);
const queue = new MinHeap();
const explored: Point[] = [];
let sequence = 0;
scores.fill(Infinity);
previous.fill(-1);
scores[startIndex] = 0;
queue.push({
index: startIndex,
priority: distance(start, goal, heuristic, movement),
sequence: sequence++
});
const directions =
movement === '4-way'
? [
[1, 0, 1],
[0, 1, 1],
[-1, 0, 1],
[0, -1, 1]
]
: [
[1, 0, 1],
[0, 1, 1],
[-1, 0, 1],
[0, -1, 1],
[1, 1, Math.SQRT2],
[-1, 1, Math.SQRT2],
[-1, -1, Math.SQRT2],
[1, -1, Math.SQRT2]
];
while (queue.length > 0) {
const currentItem = queue.pop();
if (currentItem === undefined) break;
if (closed[currentItem.index] === 1) continue;
closed[currentItem.index] = 1;
const current = toPoint(currentItem.index);
explored.push(current);
if (currentItem.index === goalIndex) {
const path: Point[] = [];
let index = goalIndex;
while (index !== -1) {
path.push(toPoint(index));
index = previous[index];
}
path.reverse();
return JSON.stringify(
{
cost: Number(scores[goalIndex].toFixed(6)),
explored,
found: true,
path,
visitedNodes: explored.length
},
null,
2
);
}
for (const [dx, dy, stepCost] of directions) {
const neighbor = {
x: current.x + dx,
y: current.y + dy
};
if (!inBounds(neighbor) || grid[neighbor.y][neighbor.x] === 1) {
continue;
}
const neighborIndex = toIndex(neighbor);
if (closed[neighborIndex] === 1) continue;
const candidateScore =
scores[currentItem.index] + stepCost;
if (candidateScore >= scores[neighborIndex]) continue;
scores[neighborIndex] = candidateScore;
previous[neighborIndex] = currentItem.index;
queue.push({
index: neighborIndex,
priority:
candidateScore +
distance(neighbor, goal, heuristic, movement),
sequence: sequence++
});
}
}
return JSON.stringify(
{
cost: null,
explored,
found: false,
path: [],
visitedNodes: explored.length
},
null,
2
);
};
const defaultGrid = JSON.stringify([
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]);
export const Tool: TypeTool = {
name: 'A* Pathfinding Visualizer',
slug: 'pathfinding/a-star',
intro:
'Find and inspect a shortest path through a JSON grid using A* search.',
tool: aStarPathfinding,
i: [
{
example: defaultGrid,
help: 'Use a rectangular JSON matrix where 0 is open and 1 is blocked.',
label: 'Grid',
placeholder: 'JSON grid',
render: 'textarea',
type: 'text',
value: defaultGrid
},
{
example: '0,0',
label: 'Start',
placeholder: 'x,y',
type: 'text',
value: '0,0'
},
{
example: '4,4',
label: 'Goal',
placeholder: 'x,y',
type: 'text',
value: '4,4'
},
{
example: '4-way',
label: 'Movement',
placeholder: 'Select movement',
type: 'select',
value: '4-way',
options: [
{ value: '4-way', text: '4-way', selected: true },
{ value: '8-way', text: '8-way' }
]
},
{
example: 'automatic',
label: 'Heuristic',
placeholder: 'Select a heuristic',
type: 'select',
value: 'automatic',
options: [
{
value: 'automatic',
text: 'Automatic',
selected: true
},
{ value: 'manhattan', text: 'Manhattan' },
{ value: 'euclidean', text: 'Euclidean' },
{ value: 'chebyshev', text: 'Chebyshev' },
{ value: 'octile', text: 'Octile' },
{ value: 'zero', text: 'Zero (Dijkstra)' }
]
}
],
o: [
{
example: '{ "found": true, "path": [] }',
label: 'Pathfinding Result',
placeholder: 'Pathfinding JSON will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'A* search algorithm - Wikipedia',
url: 'https://en.wikipedia.org/wiki/A*_search_algorithm'
}
]
};
export default Tool;
Description
Browse the implementation files for A* Pathfinding Visualizer.