AStar-Labyrinth

Interactive web visualization of A* pathfinding on randomized labyrinths. The UI is built with React, while the algorithmic core lives in plain JavaScript modules.

Project Objective

Find the shortest path between a start cell and a goal cell in a randomized maze using A*:

• Evaluation function: $f(n) = g(n) + h(n)$
• Heuristic: Manhattan distance

Quick Start

Prerequisites:

• Node.js (LTS recommended)
• npm

Install and run:

npm install
npm run dev

Open the URL shown by Vite (usually http://localhost:5173).

Features

• Maze generation with guaranteed solvability (retry-based, with empty-grid fallback)
• A* visualization with open/closed/current/path states
• Interactive editing for start, goal, and wall painting
• Adjustable speed and grid size presets
• Stats panel for visited count, path length, and result

Controls and Interaction

Controls live in src/components/Controls.jsx:

• Grid Size: 20x20, 30x30, 50x50
• Speed: Fast (10ms), Medium (35ms), Slow (80ms)
• Generate Maze: new randomized layout
• Clear Walls: keep start/goal, remove walls
• Run A*: execute the search and animate steps
• Stop: halt an in-flight run
• Reset View: clear open/closed/path overlays
• Edit Modes: Set Start, Set Goal, Draw Walls, Erase Walls

Editing tips:

• Select an edit mode, then click (or click and drag) on the grid.
• Start/Goal placement automatically clears any wall on that cell.
• Edit modes are disabled while the algorithm is running.

Visualization Legend

Legend UI is defined in src/components/Legend.jsx. The grid uses the following states:

• Start
• Goal
• Wall
• Open List
• Closed List
• Current
• Path

How It Works

The main orchestration happens in src/App.jsx:

1. A maze is generated and stored as a 2D array of CELL values.
2. The A* engine runs with runAStar, returning steps and path data.
3. Steps are animated with a delay based on the selected speed.
4. The grid renders open/closed/current/path states using key sets.

Key data model facts:

• Coordinates are { row, col } objects (see src/logic/coords.js).
• Cell values are numbers from CELL in src/logic/types.js.
• Each step is one of STEP.OPEN, STEP.CLOSE, or STEP.PATH.

Data Structures (Syllabus Integration)

Topic 3: Binomial Heap (Open List)

The frontier (open list) is implemented with a binomial heap:

• peek for best candidate access
• popMin and pushOrUpdate in $O(\log n)$
• efficient priority updates during exploration

File: src/logic/structures/BinomialHeap.js

Topic 2: Red-Black Trees (Closed List)

Visited nodes (closed list) are stored in a Red-Black Tree:

• guaranteed self-balancing behavior
• membership checks in $O(\log n)$
• avoids degeneration for adversarial insertion orders

File: src/logic/structures/RedBlackTree.js

A* Engine

Core search logic:

• expands lowest $f(n)$ node first
• tracks cameFrom and gScore
• reconstructs final shortest path
• emits step events for live visualization

File: src/logic/pathfinding/aStar.js

Maze Generation

Maze generation is handled by src/logic/maze/generateMaze.js:

• Walls are placed probabilistically (default wallProbability = 0.28).
• A BFS-style check ensures the start and goal are connected.
• After maxRetries attempts, an empty maze is used as a fallback.

Architecture At A Glance

UI (React)                     Logic (plain JS)
----------------------------  ---------------------------
App.jsx                       pathfinding/aStar.js
	|-- Controls.jsx            maze/generateMaze.js
	|-- Legend.jsx              structures/BinomialHeap.js
	|-- Grid.jsx                structures/RedBlackTree.js
	|                           heuristics.js
	|                           coords.js
	v
State (maze, start, goal, overlays)
	|
	v
Grid rendering and animation steps

Project Structure

• UI: src/App.jsx, src/components
• Pathfinding core: src/logic/pathfinding
• Maze generation: src/logic/maze
• Data structures: src/logic/structures
• Shared types/helpers: src/logic/types.js, src/logic/coords.js

Documentation Index

• Architecture: docs/ARCHITECTURE.md
• Algorithm Guide: docs/ALGORITHM-GUIDE.md
• Data Structures: docs/DATA-STRUCTURES.md
• API Reference: docs/API-REFERENCE.md
• Developer Guide: docs/DEVELOPER-GUIDE.md
• Performance Notes: docs/PERFORMANCE.md

Scripts

From package.json:

• npm run dev: start Vite dev server
• npm run build: production build
• npm run preview: preview production build
• npm run lint: run ESLint
• npm run test: run Vitest once
• npm run test:watch: run Vitest in watch mode

Tests

Unit tests cover:

• Binomial Heap behavior
• Red-Black Tree insertion/membership behavior
• A* shortest-path correctness and no-path scenarios

Test files:

• src/logic/structures/BinomialHeap.test.js
• src/logic/structures/RedBlackTree.test.js
• src/logic/pathfinding/aStar.test.js

Troubleshooting

• The UI does not update while running: the animation step delay is controlled by Speed. Increase the speed value to slow it down.
• No path found: the maze might be very dense. Try Generate Maze again or Clear Walls.
• Tests fail immediately: run npm install to ensure dependencies are installed.