_{Switch language / 언어 전환}

Circle-WFC

An experimental project that explores pathfinding by combining circle layers with Wave Function Collapse (WFC).

This repository is closer to a research prototype archive than a production-ready pathfinding library meant to replace A*. It documents how far the idea worked, where it broke down, and how the project was eventually repositioned.

At a Glance

The candidate ROAD area and the final path produced by Circle-WFC look like this. Light blue tiles are tiles guided or collapsed into ROAD, orange is the extracted path, and black tiles are ROAD-constrained tiles. The first three examples are GIFs, so you can see the path being formed over time.

Empty Grid

Maze

Reverse Path

That is not the whole story. The more interesting part of this repository is that it also shows, very clearly, where the same philosophy starts to collapse in harder environments.

Key Takeaways

• In empty maps and low-density obstacle maps, Circle-WFC clearly showed an ability to narrow the search space quickly.
• In complex mazes, narrow corridors, and topology-heavy environments, it could not reliably guarantee global connectivity.
• In the end, Circle-WFC is more honestly framed as:
  • search space reducer
  • candidate corridor generator
  • geometry-guided preprocessing module

The detailed failure analysis and repositioning are documented in result.en.md.

Idea Summary

• Split the line segment between the start and goal into multiple sections and place circle layers along that route.
• Use circle intersections, line hints, and ROAD constraints to build promising path regions first.
• Then try to form a path through WFC-style constraint propagation, while observing that this clashes structurally with the need for reliable global connectivity.

Current Positioning

This project is still meaningful for:

• narrowing candidate path regions on large empty maps or low-density obstacle maps
• experiments in geometry-guided search-space reduction
• preprocessing research for hybrid pathfinding systems

It is not a good fit for:

• stable general-purpose pathfinding in complex mazes
• production solvers that must strongly guarantee shortest paths
• standalone replacement of A* or JPS

Quick Start

The repository is currently source-oriented and does not require separate packaging.

Run the example:

python3 examples/simple_grid.py

Run the basic test:

python3 -m unittest discover -s tests -p 'test_basic.py'

Generate visualization images:

python3 tests/test_pathfinding.py --save-images --save-gifs

The default output is saved under tests/output/pathfinding/.

Regenerate only the assets used in the README gallery:

python3 tests/generate_readme_images.py

This recreates the README assets under docs/images/pathfinding/.

Visualization Gallery

Scenes Where It Works

Standard Circle-WFC pathfinding produces surprisingly readable corridors not only in simple maps, but also in narrow passages, reversed routes, and multi-turn structures.

Narrow Passage

U-shaped Obstacle

Spiral Path

Side-by-Side Algorithm Comparisons

From here on, the same maps are compared side by side with A*, MLMC, and MLMC-Ray. The point is not only whether an algorithm passes or fails, but where ROAD spreads too aggressively and where geometry misreads topology.

Narrow Corridor 30x30

All three algorithms succeed here, but the scene shows that success alone is not the full story. In a narrow corridor, A* stays lean, while MLMC and MLMC-Ray can reach the same answer with more spreading.

A* PASS

MLMC PASS

MLMC-Ray PASS

Failure Cases That Changed the Conclusion

The final conclusion of the project becomes clearer in the scenes below than in any hand-picked success screenshot. MLMC breaks as soon as topology becomes difficult, even when the geometry looks promising, and experiments like MLMC-Ray had to be added just to recover those failures. The first comparison is a GIF, so the failure footprint and recovery path are easier to see.

Maze 50x50

A* PASS

MLMC FAIL

MLMC-Ray PASS

Maze 100x100

A* PASS

MLMC FAIL

MLMC-Ray PASS

Complex Obstacle 50x50

A* PASS

MLMC FAIL

MLMC-Ray PASS

Repository Layout

• result.en.md: final failure analysis and repositioning document
• src/: Circle-WFC prototype implementation
• examples/: runnable examples
• tests/: tests, benchmarks, and debug or validation scripts
• docs/: step-oriented experiment notes and changelog

Recommended Reading Order

1. result.en.md
2. docs/steps/README.en.md
3. docs/CHANGELOG.en.md
4. examples/simple_grid.py
5. src/pathfinder.py

Documentation Note

• For the Korean documentation flow, start from README.ko.md.
• For the English documentation flow, follow docs/steps/README.en.md and result.en.md.