3 months ago
- A* algorithm finds optimal paths on any graph, not just grids.
- It uses a priority queue with estimated length: actual length + heuristic underestimation.
- Convert round obstacles to a graph using surfing edges (bitangents) and hugging edges.
- Tangent visibility graph: internal and external bitangents connect circles.
- Cull blocked edges via point-line-distance checks for obstacles.
- Handling touching/overlapping circles requires domain checks for arccosine.
- Hugging edges can also be blocked; intersection points determine eligibility.
- Simplify by applying Minkowski addition: treat moving circle as point with enlarged obstacles.
- Generate graph lazily during A* to save time, using neighbors() function.
- Filter cusped hugging edges to maintain optimal path rotation consistency.