Obstacle Generation¶

PASSAGE draws procedural obstacles as superellipses (Lamé curves). Shapes range from diamonds and ellipses to near-rectangles, with any rotation and size. In PASSAGE v1.0, obstacle cells are blocked: no route may enter them.

The Superellipse Equation¶

A superellipse is the set of cells that satisfy:

where \((x', y')\) are the cell's coordinates relative to the center \((c_x, c_y)\), rotated by the angle \(-\theta\):

Shape Exponent \(n\)¶

The exponent \(n\) sets the shape:

By default, \(n\) is drawn from a log-uniform distribution:

with \(n_{\min} = 1.0\) and \(n_{\max} = 80.0\). Under a log-uniform draw, each doubling of \(n\) (1–2, 2–4, 4–8, …) is equally likely. Pointed, elliptical and near-rectangular shapes therefore all occur.

Rotation¶

Each obstacle is rotated by an angle drawn uniformly:

The rotation is applied to the cell coordinates before the inequality above is tested.

Size Parameters¶

The size ratios set the full width and height of a shape, as fractions of the crop side \(R\). The width \(w\) and the height \(h\) are drawn independently as whole numbers of cells:

The semi-axes are half of these extents, with a minimum of one cell:

The default ratios are 2 % and 25 %. Rounding and the one-cell minimum for the semi-axes affect the dimensions on small crops. The center is drawn uniformly over the whole crop, so a shape near the edge is cut by the crop border.

Placement Algorithm¶

The generator adds shapes one at a time until the next shape would exceed a target coverage \(t\), the fraction of crop cells covered by obstacles:

1. Draw the target \(t \sim \mathcal{U}(0, \text{ratio\_max})\). If \(t = 0\), the mask stays empty.
2. Draw a shape: size, center, angle \(\theta\) and exponent \(n\).
3. If the shape covers the start or the goal, draw another one. After ten such shapes in a row, stop.
4. If adding the shape would raise the coverage above \(t\), stop; this shape is not added.
5. Otherwise add the shape and start another placement round, up to candidates_per_mask rounds in total. Retries in step 3 are within a round.

The final coverage is therefore at most \(t\), and \(t\) is at most ratio_max (30 %). Each scene records both values in its metadata (obstacles.ratio_target and obstacles.ratio_actual).

flowchart TD
    A["Draw target coverage<br>t ~ U(0, ratio_max)"] --> B[Start from an empty mask]
    B --> C{"Fewer than candidates_per_mask<br>shapes in the mask?"}
    C -->|No| R[Return the mask]
    C -->|Yes| D["Draw a shape<br>size, center, θ, n"]
    D --> E{"Covers the start<br>or the goal?"}
    E -->|"Yes, fewer than<br>10 times in a row"| D
    E -->|"Yes, 10th time<br>in a row"| R
    E -->|No| F{"Coverage with this shape<br>above t?"}
    F -->|Yes| R
    F -->|No| G[Add the shape to the mask]
    G --> C

    style A fill:#1565C0,color:#fff
    style D fill:#42A5F5,color:#fff
    style G fill:#D32F2F,color:#fff
    style R fill:#2E7D32,color:#fff

Configuration¶

All keys sit under obstacles in config/config.yaml.

Blocked Cells and Connected Endpoints¶

Each scene is solved twice per objective: once on free terrain, where the obstacle channel is ignored, and once with the obstacles. With obstacles, the obstacle cells are removed from the routing graph:

• A route never enters an obstacle cell.
• A diagonal step is checked against its destination cell only, so a route may pass between two obstacle cells that touch at a corner.
• A route always joins the start to the goal. Before any label is computed, passage.reference.endpoints_connected() checks the mask on exactly this graph (eight neighbours, obstacle cells blocked at the destination cell). If the obstacles disconnect the start from the goal, the crop is rejected like any other unusable input (nodata, elevations outside the calibration range), and the scene's seeded input stream supplies the next candidate crop. A rejected pair is precisely one that the exact search would prove to have no path, so all 26,400,000 variants of PASSAGE v1.0 are exact routes.

The v1.0 generator refuses a configuration with impassable: false.

Penalty Option (not used by the v1.0 release)¶

With impassable: false, the generator keeps obstacle cells in the graph and raises their elevation instead:

Changing the elevation can affect route costs, and routes can still cross obstacle cells. This option only affects the alternative solver backends described in Solvers & Heuristics.

Implementation¶

The superellipse helpers are in src/passage/obstacles.py:

• superellipse_mask() rasterizes one rotated superellipse as a boolean array.
• sample_n_from_config() draws the exponent from the configured distribution.
• sample_angle_from_config() draws the rotation angle.

The placement loop is _generate_obstacles_mask() in src/passage/generate.py. The v1.0 generator calls it for every scene, with the start and the goal as protected cells.