Skip to content

Main content

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.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools