Pathfinding Algorithm Visualization

A small Java Swing project for learning common pathfinding algorithms and demonstrating their behavior on editable grids.

This project is intended only for familiarization with general-purpose pathfinding algorithms and educational demonstrations. It is not a production navigation system, a multi-agent simulator, or a rigorous performance benchmark.

Requirements

• JDK 17 or newer, including java and javac.
• A graphical desktop to run the Swing demo.
• No third-party Java dependencies, Maven, or Gradle.

Run

Open this directory in IntelliJ IDEA, select JDK 17 or newer, and run src/Main.java.

Alternatively, from this directory in PowerShell:

./scripts/run.ps1

If Java is not configured on your PATH, pass its installation directory:

./scripts/run.ps1 -JavaHome "D:/Java/jdk-25.0.2"

The scripts also respect JAVA_HOME. Build without opening a window with ./scripts/build.ps1.

On any platform, compile all files under src/ into out/ with UTF-8 encoding and run java -cp out Main. For example, on Linux/macOS:

mkdir -p out
find src -name '*.java' > out/sources.txt
javac --release 17 -encoding UTF-8 -d out @out/sources.txt
java -cp out Main

Demo controls

1. Choose a map from TERRAIN.
2. Select a tool to move the unit, place the unit, set a goal, or paint terrain. Painting also supports dragging.
3. Choose an algorithm and select Find path.
4. Select Play / Pause or Step to move along the returned path.
5. Use Clear path to stop movement, or Reload terrain to restore the selected preset.

Selecting a preset replaces current edits and resets the unit, goal, and path. Editing terrain or changing the goal clears the current path. Editing is disabled while a search is running. The blue circle is the unit, the red outline is the goal, and the amber line is the remaining path.

The six presets are Open field, Zigzag maze, Forest shortcut, River crossings, Four rooms, and Island bridges.

Movement rules

The map has 24 columns and 16 rows. Movement is restricted to four directions; diagonals are not supported. Costs are charged when entering the destination cell.

Terrain	Entry cost	Traversable
Ground	1	Yes
Forest	3	Yes
Water	5	Yes
Wall	-	No

Movement cost is a search objective, not animation duration: playback advances one cell per timer tick regardless of terrain. Units check the next step before moving and discard blocked paths.

Algorithms

Algorithm	Objective / guarantee in this demo
BFS	Fewest steps; not necessarily minimum terrain cost
DFS	Finds a route; no shortest-path or minimum-cost guarantee
Dijkstra	Minimum total movement cost
A*	Minimum total movement cost with the default admissible Manhattan heuristic
DFID / IDDFS	Fewest steps using iterative depth limits
IDA*	Minimum total movement cost using iterative f-cost limits

Dijkstra shares the A* engine with a zero heuristic. A* and IDA* default to Manhattan distance scaled by 1, which is admissible for this four-direction grid with minimum step cost 1. If you change movement rules or edge costs, provide an appropriate heuristic; zero is a safe fallback.

DFID and IDA* use explicit stacks and path-local cycle detection. They can repeat substantial work. Both default to a total budget of 1,000,000 expanded nodes per search. If that limit is reached, the demo reports that the result is unknown and suggests A* or Dijkstra. A budget exhaustion is never reported as NO_PATH. Constructors allow another positive budget.

Results report steps, actual terrain cost, expanded nodes, and search time. Expanded nodes count states whose neighbors were examined; iterative algorithms include all iterations. Timings exclude animation, are affected by JVM warmup, and should not be treated as scientific benchmarks.

Project layout

src/
  Main.java
  pathfinding/
    algorithm/   Search implementations and heuristic interface
    model/       Positions, cells, terrain, and grid map
    navigation/  Graph interface and movement-aware grid adapter
    request/     Search request, result, and status
    unit/        Movement profiles and path execution
    demo/        Swing UI and terrain presets
tests/           Standalone test programs
scripts/         Build, run, and verification scripts
PAPER_ALGORITHMS.md
VALIDATION.md

Add your own algorithm

Implement PathFinder.findPath(PathRequest), optionally override getName(), and register your instance in DemoFrame.createAlgorithms(). You can also inject algorithms through new DemoFrame(List.of(...)).

Read navigation through request.graph():

• isTraversable(position): checks bounds and movement permissions.
• getNeighbors(position): returns legal four-direction neighbors.
• getMoveCost(from, to): returns the cost of a legal adjacent move.

Successful results contain both start and goal. Identical endpoints produce a one-position path with zero cost. Failed searches return an empty path and one of INVALID_START, INVALID_GOAL, or NO_PATH. Use PathResult.found(...) or PathResult.failure(...).

Keep search state local to each call. Algorithms run on a background thread and must not modify the map or access Swing components.

Verification

./scripts/test.ps1
# Or:
./scripts/test.ps1 -JavaHome "D:/Java/jdk-25.0.2"

This builds with Java 17 language compatibility and runs all non-UI test programs, stopping on any failure. See VALIDATION.md for scope and limitations. GitHub Actions runs the same checks on JDK 17 and 25.

For the literature-based additions and intentionally excluded algorithms, see PAPER_ALGORITHMS.md.