Ogun

[github] [crates.io] [docs.rs]

Spatial layout generation via sequential logit dynamics on potential games.

Given a weighted graph and a 2D grid, Ogun places nodes and routes edges at a controllable optimization level. Agents arrive sequentially and select positions via Boltzmann sampling against a potential function encoding overlap, repulsion, and attraction. The inverse temperature β governs output character — from near-random (low β) to near-optimal (high β).

Named after the Yoruba deity of iron, metalwork, and pathfinding — a god who routes paths through uncharted space.

[dependencies]
ogun = "0.4"

Example

use ogun::*;

let graph = Graph {
    nodes: vec![
        Node { id: NodeId(0), width: 3, height: 3, fixed: None },
        Node { id: NodeId(1), width: 3, height: 3, fixed: None },
    ],
    edges: vec![Edge {
        id: EdgeId(0),
        src: NodeId(0),
        dst: NodeId(1),
        weight: 1.0,
    }],
};
let space = Space { width: 20, height: 20, obstacles: vec![], routing_costs: None };
let config = OgunConfig { seed: 42, ..OgunConfig::default() };

let layout = generate(&graph, &space, &config);
assert!(layout.score.composite > 0.0);

Algorithm

for each agent in arrival order:
    1. EVAL  — score every grid position via potential Φ
    2. CHOOSE — Boltzmann sample: P(p) ∝ exp(β · Φ(p))
    3. COMMIT — place irrevocably, block footprint
    4. ROUTE  — negotiated Dijkstra to already-placed neighbors
score the completed layout

The potential Φ combines overlap penalty, pairwise repulsion (inverse-square), and edge attraction (distance to placed neighbors). See docs/research/ for theoretical foundations and complexity analysis.

Performance

Benchmarks across problem sizes, measured in --release mode. The stress test (500 nodes on a 500×500 grid) is the primary target.

Key optimizations: pre-built adjacency lists, SoA placed-node layout, fused overlap/repulsion pass, buffer reuse, Rayon parallel utility evaluation, and spatial repulsion cutoff. Full breakdown in docs/BENCHMARKS.md.

You can run the benchmarks with:

$ cargo test --release --test perf -- --ignored --nocapture

Paper

The algorithm is described in detail in docs/paper/ogun_paper.pdf:

Elias Vahlberg. Ogun: Spatial Layout Generation via Sequential Logit Dynamics on Potential Games. March 2026.

License

MIT