# Cost and Collision Engine Spec

This document describes the methods for ensuring "analytic correctness" while maintaining a computationally efficient cost function.

## 1. Analytic Correctness
The router balances speed and verification using a two-tier approach.

### 1.1. R-Tree Geometry Engine
The router uses an **R-Tree of Polygons** for all geometric queries.
*   **Move Validation:** Every "Move" proposed by the search is checked for intersection against the R-Tree.
*   **Pre-dilation for Clearance:** All obstacles and paths use a global clearance $C$. At the start of the session, all user-provided obstacles are **pre-dilated by $(W_{max} + C)/2$** for initial broad pruning. However, individual path dilation for intersection tests uses $(W_i + C)/2$ for a specific net's width $W_i$.
*   **Safety Zone:** To prevent immediate collision flags for ports placed on or near obstacle boundaries, the router ignores collisions within a radius of **2nm** of start and end ports.
*   **Single Layer:** All routing and collision detection occur on a single layer.

### 1.2. Cost Calculation (Soft Constraint)
The "Danger Cost" $g_{proximity}(n)$ is a function of the distance $d$ to the nearest obstacle:
$$g_{proximity}(n) = \begin{cases} \infty & \text{if } d < (W_i + C)/2 \\ \frac{k}{d^2} & \text{if } (W_i + C)/2 \le d < \text{Safety Threshold} \\ 0 & \text{if } d \ge \text{Safety Threshold} \end{cases}$$

To optimize A* search, a **Static Danger Map (Precomputed Grid)** is used for the heuristic.
*   **Grid Resolution:** Default **1000nm (1µm)**.
*   **Static Nature:** The grid only accounts for fixed obstacles. It is computed once at the start of the session and is **not re-computed** during the Negotiated Congestion loop.
*   **Efficiency:** For a 20x20mm layout, this results in a 20k x 20k matrix.
    *   **Memory:** Using a `uint8` or `float16` representation, this consumes ~400-800MB (Default < 2GB). For extremely high resolution or larger areas, the system supports up to **20GB** allocation.
*   **Precision:** Strict intersection checks still use the R-Tree for "analytic correctness."

## 2. Collision Detection Implementation
The system relies on `shapely` for geometry and `rtree` for spatial indexing.
1.  **Arc Resolution:** Arcs are represented as polygons approximated by segments with a maximum deviation (sagitta).
2.  **Intersection Test:** A "Move" is valid only if its geometry does not intersect any obstacle in the R-Tree.
3.  **Self-Intersection:** Paths from the same net must not intersect themselves.
4.  **No Crossings:** Strictly 2D; no crossings (vias or bridges) are supported.

## 3. Negotiated Congestion (Path R-Tree)
To handle multiple nets, the router maintains a separate R-Tree containing the dilated geometries ($C/2$) of all currently routed paths.
*   **Congestion Cost:** $P \times (\text{Overlaps in Path R-Tree})$.
*   **Failure Policy:** If no collision-free path is found after the max iterations, the router returns the **"least-bad" (lowest cost)** path. These paths MUST be explicitly flagged as invalid (e.g., via an `is_valid=False` attribute or a non-zero `collision_count`) so the user can identify and manually fix the failure.

## 4. Handling Global Clearances
Clearances are global. Both obstacles and paths are pre-dilated once. This ensures that any two objects maintain at least $C$ distance if their dilated versions do not intersect.

## 5. Locked Paths
The router supports **Locked Paths**—existing geometries inserted into the static Obstacle R-Tree, ensuring they are never modified or rerouted.