# core/resolvers/walk.resolver.ts

> 93 lines of code and 37 definitions.

Tree: GovLab Patterns
Language: typescript
Layer: infrastructure
Canonical: https://banes-lab.com/anatomy/patterns#file-patterns-core-resolvers-walk-resolver-ts
Source text: https://banes-lab.com/source/patterns/core/resolvers/walk.resolver.ts.txt

Listed in [core/resolvers](https://banes-lab.com/api/source/patterns/core/resolvers.md), after [core/resolvers/representation.resolver.ts](https://banes-lab.com/source/patterns/core/resolvers/representation.resolver.ts.md).

## Definitions

- `walkGrid` (lexical_declaration, line 86, exported)
- `key` (lexical_declaration, line 31)
- `add` (lexical_declaration, line 35)
- `spiralFree` (lexical_declaration, line 62)
- `ringCells` (lexical_declaration, line 50)
- `pickNext` (lexical_declaration, line 72)
- `CONTAIN_FACTOR` (lexical_declaration, line 5)
- `OVERFLOW_WEIGHT` (lexical_declaration, line 6)
- `RADIUS_MIN` (lexical_declaration, line 7)
- `SPIRAL_RINGS` (lexical_declaration, line 8)
- `N` (lexical_declaration, line 10)
- `S` (lexical_declaration, line 11)
- `NE` (lexical_declaration, line 12)
- `SE` (lexical_declaration, line 13)
- `SW` (lexical_declaration, line 14)
- `NW` (lexical_declaration, line 15)
- `ALL_DIRS` (lexical_declaration, line 16)
- `DOWN_PREF` (lexical_declaration, line 17)
- `UP_PREF` (lexical_declaration, line 18)
- `SIDE_PREF` (lexical_declaration, line 19)
- `Scored` (interface_declaration, line 21)
- `WalkBounds` (interface_declaration, line 26)
- `hexDist` (lexical_declaration, line 39)
- `prefsFor` (lexical_declaration, line 43)
- `cell` (lexical_declaration, line 52)
- `step` (lexical_declaration, line 54)
- `free` (lexical_declaration, line 73)
- `at` (lexical_declaration, line 75)
- `[head]` (lexical_declaration, line 79)
- `[first]` (lexical_declaration, line 87, exported)
- `radius` (lexical_declaration, line 91, exported)
- `origin` (lexical_declaration, line 92, exported)
- `visited` (lexical_declaration, line 93, exported)
- `cells` (lexical_declaration, line 94, exported)
- `cursor` (lexical_declaration, line 95, exported)
- `previous` (lexical_declaration, line 96, exported)
- `next` (lexical_declaration, line 98, exported)

## Contained in

- [core/resolvers](https://banes-lab.com/anatomy/patterns/folder-patterns-core-resolvers.md)

## Uses

- [core/classifiers/syntax.classifier.ts](https://banes-lab.com/source/patterns/core/classifiers/syntax.classifier.ts.md)

## Used by

- [core/converters/walk.converter.ts](https://banes-lab.com/source/patterns/core/converters/walk.converter.ts.md)

## Linked from

- [core/classifiers](https://banes-lab.com/anatomy/patterns/folder-patterns-core-classifiers.md)
- [core/converters](https://banes-lab.com/anatomy/patterns/folder-patterns-core-converters.md)
- [core/resolvers](https://banes-lab.com/anatomy/patterns/folder-patterns-core-resolvers.md)

## Source

```typescript
import type { Axial, Cell, WalkNode } from "#types/walk.types";
import { HALF } from "#configuration/constants/walk.constants";
import { stateOf } from "#core/classifiers/syntax.classifier";

const CONTAIN_FACTOR = 0.55;
const OVERFLOW_WEIGHT = 40;
const RADIUS_MIN = 2;
const SPIRAL_RINGS = 240;

const N: Axial = { q: 0, r: -1 };
const S: Axial = { q: 0, r: 1 };
const NE: Axial = { q: 1, r: -1 };
const SE: Axial = { q: 1, r: 0 };
const SW: Axial = { q: -1, r: 1 };
const NW: Axial = { q: -1, r: 0 };
const ALL_DIRS: readonly Axial[] = [N, S, NE, SE, SW, NW];
const DOWN_PREF: readonly Axial[] = [S, SE, SW, NE, NW, N];
const UP_PREF: readonly Axial[] = [N, NE, NW, SE, SW, S];
const SIDE_PREF: readonly Axial[] = [SE, NE, SW, NW, S, N];

interface Scored {
    at: Axial;
    score: number;
}

interface WalkBounds {
    visited: ReadonlySet<string>;
    radius: number;
}

const key = function key(cell: Axial): string {
    return `${cell.q},${cell.r}`;
};

const add = function add(a: Axial, b: Axial): Axial {
    return { q: a.q + b.q, r: a.r + b.r };
};

const hexDist = function hexDist(cell: Axial): number {
    return (Math.abs(cell.q) + Math.abs(cell.r) + Math.abs(cell.q + cell.r)) * HALF;
};

const prefsFor = function prefsFor(delta: number): readonly Axial[] {
    if (delta > 0) {
        return DOWN_PREF;
    }
    return delta < 0 ? UP_PREF : SIDE_PREF;
};

const ringCells = function ringCells(center: Axial, radius: number): Axial[] {
    const cells: Axial[] = [];
    let cell = { q: center.q + SW.q * radius, r: center.r + SW.r * radius };
    for (const dir of ALL_DIRS) {
        for (let step = 0; step < radius; step += 1) {
            cells.push(cell);
            cell = add(cell, dir);
        }
    }
    return cells;
};

const spiralFree = function spiralFree(cursor: Axial, visited: ReadonlySet<string>): Axial {
    for (let radius = 1; radius < SPIRAL_RINGS; radius += 1) {
        const free = ringCells(cursor, radius).find((cell) => !visited.has(key(cell)));
        if (free !== undefined) {
            return free;
        }
    }
    return cursor;
};

const pickNext = function pickNext(cursor: Axial, prefs: readonly Axial[], bounds: WalkBounds): Axial {
    const free: Scored[] = prefs
        .map((dir, rank) => {
            const at = add(cursor, dir);
            return { at, score: rank + Math.max(0, hexDist(at) - bounds.radius) * OVERFLOW_WEIGHT };
        })
        .filter((option) => !bounds.visited.has(key(option.at)));
    const [head] = free;
    if (!head) {
        return spiralFree(cursor, bounds.visited);
    }
    return free.reduce((best, option) => (option.score < best.score ? option : best), head).at;
};

export const walkGrid = function walkGrid(nodes: readonly WalkNode[]): Cell[] {
    const [first] = nodes;
    if (!first) {
        return [];
    }
    const radius = Math.max(RADIUS_MIN, Math.ceil(Math.sqrt(nodes.length) * CONTAIN_FACTOR));
    const origin: Axial = { q: 0, r: 0 };
    const visited = new Set<string>([key(origin)]);
    const cells: Cell[] = [{ at: origin, node: first, state: first.state ?? stateOf(first.label) }];
    let cursor = origin;
    let previous = first.depth;
    for (const node of nodes.slice(1)) {
        const next = pickNext(cursor, prefsFor(node.depth - previous), { radius, visited });
        visited.add(key(next));
        cells.push({ at: next, node, state: node.state ?? stateOf(node.label) });
        cursor = next;
        previous = node.depth;
    }
    return cells;
};
```