Maze

In this example letters travel from the center of a randomly generated maze to a row of targets at the bottom, spelling out a piece of text supplied on the command line. Each letter is routed independently with a randomly chosen search algorithm — DFS, BFS, GBFS or AStar — and all letters search and animate concurrently on a small thread pool, so the demo doubles as a side-by-side race between the four algorithms.

Maze "hello, world!" [--seed N] [--randomness F] [--binomial F] [-w N] [-h N]

Building the maze

A maze is exactly the case LatticeGraph exists for: a regular grid whose edges are always just its cardinal neighbours. Rather than the general-purpose Graph (a forward-star edge store, built for arbitrary/explicit topology), the maze uses LatticeGraph, which derives edges from index math and each node’s blocked flag on every call instead of storing them — no edges to allocate when the grid is built, and no forward-star fixup cost when isolate walls a cell off during carving.

The node type is a small custom struct, MazeNode, rather than the library’s NodeDefault:

struct MazeNode {
    MazeNode() = default;
    MazeNode(JsonBox::Object o) : /* ... */ {}
    JsonBox::Value toJson() const { /* ... */ }
    // data
    std::size_t index = 0;
    bool blocked = false;
    int x = 0;
    int y = 0;
};

using GraphT = EvoAI::LatticeGraph<MazeNode>;

The x/y fields are the only reason this example doesn’t just use NodeDefault: DefaultTraversalPolicy detects them at compile time and switches its heuristic from an always-0.0 stub to real Euclidean distance. Without them, A* silently degrades into plain Dijkstra and GBFS has no ranking signal to search by at all — neither would actually be searching toward the goal, which would defeat the point of racing four algorithms with visibly different behaviour.

The maze itself is grown from a fully-connected lattice (LatticeGraph’s constructor is that lattice — there’s no separate factory call), then carved by GrowingTree starting from the cell at the center of the grid. GrowingTree is templated on the graph type and only needs forEachOutgoingEdge/isolate, so it runs unmodified on LatticeGraph exactly as it does on Graph:

GraphT buildMaze(const SimConfig& cfg) {
    GraphT g(cfg.rows, cfg.cols, false);
    for (std::size_t i = 0; i < g.size(); ++i) {
        g[i].x = static_cast<int>(i % cfg.cols);
        g[i].y = static_cast<int>(i / cfg.cols);
    }
    MazeAlg::GrowingTree<GraphT> growingTree;
    growingTree(g, g[cfg.startIdx], cfg.randomness, cfg.binomial);
    return g;
}

randomness and binomial tune the character of the generated maze — left unset on the command line, they default to two draws from the seeded RNG, so a given --seed always reproduces the same maze, the same algorithm assignment, and the same race.

Opening up the start and the targets

Growing Tree can wall off the exact cell it started from, and the bottom row will not have a clear opening anywhere by construction, so the demo manually carves room for both. Unlike Graph, LatticeGraph has no connectToX()/connect() to call: since every forEachOutgoingEdge call derives edges from .blocked and index math fresh, unblocking a cell is the whole operation — connectivity to any already-open neighbour comes back on its own, in both directions, with nothing left to reconnect by hand:

void clearCenter(GraphT& g, const SimConfig& cfg) {
    const int rows = static_cast<int>(cfg.rows);
    const int cols = static_cast<int>(cfg.cols);
    for (int dy = -cfg.clearRY; dy <= cfg.clearRY; ++dy) {
        for (int dx = -cfg.clearRX; dx <= cfg.clearRX; ++dx) {
            int r = static_cast<int>(cfg.centerRow) + dy;
            int c = static_cast<int>(cfg.centerCol) + dx;
            if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
            std::size_t idx = static_cast<std::size_t>(r) * cfg.cols
                            + static_cast<std::size_t>(c);
            g[idx].blocked = false;
        }
    }
}

One target cell per letter is opened the same way along the bottom row, spaced out and centered under the maze, along with the cell directly above it so a search can actually arrive into the target from the rest of the maze:

std::vector<std::size_t> setupTargets(
    GraphT& g, const SimConfig& cfg, const std::string& text)
{
    const int cols = static_cast<int>(cfg.cols);
    const int bottomRow = static_cast<int>(cfg.rows) - 1;
    int firstCol = static_cast<int>(cfg.centerCol) - static_cast<int>(text.size()) / 2;
    if (firstCol < 1) firstCol = 1;

    std::vector<std::size_t> targets;
    for (std::size_t i = 0; i < text.size(); ++i) {
        int c = firstCol + static_cast<int>(i);
        if (c >= cols - 1) c = cols - 2;
        std::size_t idx = static_cast<std::size_t>(bottomRow) * cfg.cols
                        + static_cast<std::size_t>(c);
        g[idx].blocked = false;

        if (bottomRow > 0) {
            std::size_t northIdx = static_cast<std::size_t>(bottomRow - 1) * cfg.cols
                                 + static_cast<std::size_t>(c);
            g[northIdx].blocked = false;
        }
        targets.push_back(idx);
    }
    return targets;
}

Assigning an algorithm to each letter

Every character of the input text gets its own LetterState: which target it is walking towards, and which of the four algorithms will compute its route. The algorithm is picked uniformly at random, independently per letter:

enum class Algorithm { DFS, BFS, GBFS, ASTAR };

static Algorithm pickRandomAlgorithm(std::mt19937& rng) {
    return static_cast<Algorithm>(std::uniform_int_distribution<int>(0, 3)(rng));
}

struct LetterState {
    char                     ch        = '\0';
    std::atomic<std::size_t> currentIdx{0};
    std::size_t              goalIdx   = 0;
    Algorithm                algo      = Algorithm::ASTAR;
    std::atomic<bool>        finished  {false};
};

Searching concurrently

A small thread pool pulls letters one at a time from a TaskQueue. Each worker owns a single SearchContext and DefaultTraversalPolicy, created once before the task loop and reused for every letter that worker processes, so every worker reads the shared maze through const references without needing any locking around the search itself:

// created once per worker thread, outside the task loop
PFA::SearchContext ctx;
PolicyT            policy;

while (taskQueue.pop(task)) {
    std::vector<const GraphT::Node_t*> path;

    const auto& startNode = graph[ls.currentIdx.load()];
    const auto& goalNode  = graph[ls.goalIdx];

    switch (ls.algo) {
        case Algorithm::DFS:  { PFA::DFS<GraphT,PolicyT>  a; path = a(graph,startNode,goalNode,ctx,policy); break; }
        case Algorithm::BFS:  { PFA::BFS<GraphT,PolicyT>  a; path = a(graph,startNode,goalNode,ctx,policy); break; }
        case Algorithm::GBFS: { PFA::GBFS<GraphT,PolicyT> a; path = a(graph,startNode,goalNode,ctx,policy); break; }
        case Algorithm::ASTAR:{ PFA::AStar<GraphT,PolicyT>a; path = a(graph,startNode,goalNode,ctx,policy); break; }
    }
    // ...
}

Each algorithm calls ctx.reset(graph.size()) internally before searching. Because SearchContext’s buffers only grow and reset() is just a generation-counter bump, reusing one ctx per worker means only the first search on each thread pays the cost of growing those buffers – every later search on that thread, including across different letters and different algorithms, reuses the same capacity for free. This is also why sharing one ctx across DFS/BFS/GBFS/AStar calls on the same worker is safe: nothing about the buffers is algorithm-specific.

Animating and rendering

Once a path is found, the worker walks it in a small number of evenly spaced frames, storing each step into the letter’s atomic currentIdx:

if (!path.empty()) {
    constexpr std::size_t maxFrames = 40;
    const std::size_t stride = std::max(std::size_t{1}, path.size() / maxFrames);
    for (std::size_t step = 0; step < path.size(); step += stride) {
        ls.currentIdx.store(path[step]->index, std::memory_order_relaxed);
        std::this_thread::sleep_for(std::chrono::milliseconds(30));
    }
}

A separate render loop on the main thread redraws the whole grid at a fixed rate, reading each letter’s currentIdx to place it on the grid and color it by its assigned algorithm (cyan for DFS, green for BFS, yellow for GBFS, magenta for A*), so the maze walls, the moving letters, and the still-empty targets are all visible at once while the searches race to finish.

The full code is here