Proposal: spatial queries & pathfinding — Query.nearest/within, Grid.*, Path.a_star #24

New issue

Closed

opened 2026-08-29 23:39:27 +02:00 by orkun · 1 comment

orkun commented

2026-08-29 23:39:27 +02:00

Owner

Follow-up to #2. ECS-native spatial helpers plus grid/path algorithms, deterministic fixed-point.

Proposed surface

Query.count([Prop]), Query.first([Prop]) -> entity, Query.nearest(from, [Prop]) -> entity, Query.within(center, radius, [Prop]) -> list
Grid.line(a, b) (Bresenham — the rt_line primitive from #2 already exists), Grid.flood_fill(x, y), Grid.line_of_sight(a, b) over the tilemap
Path.a_star(cost_map, from, to) -> list

Work required

Query.nearest/within want a runtime spatial index to be efficient; Grid.*/Path.* need Map access wiring and the A* implementation.

Blocked on: a runtime spatial index (for Query) + Map/pathfinding plumbing.

Follow-up to #2. ECS-native spatial helpers plus grid/path algorithms, deterministic fixed-point. ## Proposed surface - `Query.count([Prop])`, `Query.first([Prop]) -> entity`, `Query.nearest(from, [Prop]) -> entity`, `Query.within(center, radius, [Prop]) -> list` - `Grid.line(a, b)` (Bresenham — the `rt_line` primitive from #2 already exists), `Grid.flood_fill(x, y)`, `Grid.line_of_sight(a, b)` over the tilemap - `Path.a_star(cost_map, from, to) -> list` ## Work required `Query.nearest`/`within` want a runtime **spatial index** to be efficient; `Grid.*`/`Path.*` need Map access wiring and the A* implementation. **Blocked on:** a runtime spatial index (for Query) + Map/pathfinding plumbing.

orkun added the

proposal

priority:medium

area:stdlib

labels 2026-08-29 23:39:27 +02:00

orkun referenced this issue

2026-08-29 23:39:27 +02:00

Proposal: a namespaced standard library — Math (trig/lerp), Text, List, Time, Audio, and namespacing the bare builtins (World/Net/Sys/Save/Mem) #2

orkun referenced this issue from a commit

2026-08-31 11:36:14 +02:00

feat(stdlib): add Grid.* — tile geometry + A* pathfinding over the tilemap (#24)

orkun referenced this issue

2026-08-31 11:36:56 +02:00

Proposal: ECS spatial queries — Query.count/first/nearest/within (needs a runtime spatial index) #42

orkun commented

2026-08-31 11:37:16 +02:00

Author

Owner

Shipped the grid geometry + pathfinding half in 07e5a20 — the part that isn't blocked. It's a new Grid.* namespace over the Map tilemap (runtime/native/grid.ludic, ~150 lines of Ludic, C-free, spliced via core.ludic):

Grid.line(x0,y0,x1,y1) -> []Cell — Bresenham line cells (the primitive #24 noted rt_line already had; this returns the cells rather than drawing them)
Grid.blocked(x,y,wall) -> bool — the shared passability test
Grid.line_of_sight(x0,y0,x1,y1,wall) -> bool — unobstructed straight line over the tilemap
Grid.flood(x,y,wall) -> []Cell — 4-connected reachable region (BFS)
Grid.a_star(x0,y0,x1,y1,wall) -> []Cell — shortest 4-connected path (A*, Manhattan heuristic), empty if unreachable

A cell is passable unless it's out of bounds or holds the caller's wall tile (a char code, e.g. '#'), so any impassable glyph works — and it's all integer/deterministic. Returned Cell slices are ordinary Ludic slices (len / [i], each cell has .x/.y). Pathfinding lives under Grid rather than a Path namespace, since Path is already the filesystem-paths library (#10).

Verified against Python references — a 1500-case fuzzer over random maps agrees exactly on A* path length (optimal, == BFS), flood-fill count, and line-of-sight. examples/library/grid.ludic asserts it and is wired into x test (now 61 passed, 0 failed); a Grid docs section + 5 per-symbol pages; coverage/vocabulary/fence checks green; seed reseeded and the C-free bootstrap fixpoint holds.

What's covered vs deferred

Grid.line (Bresenham), Grid.flood_fill, Grid.line_of_sight over the tilemap
Path.a_star — as Grid.a_star (the Path name is taken)
Query.count/first/nearest/within — the ECS spatial-query side, which #24 itself flagged as blocked on a runtime spatial index

Closing this as the grid/pathfinding deliverable; the blocked ECS-query half is tracked in #42.

Shipped the **grid geometry + pathfinding** half in 07e5a20 — the part that isn't blocked. It's a new `Grid.*` namespace over the `Map` tilemap (`runtime/native/grid.ludic`, ~150 lines of Ludic, C-free, spliced via core.ludic): - `Grid.line(x0,y0,x1,y1) -> []Cell` — Bresenham line cells (the primitive #24 noted `rt_line` already had; this returns the cells rather than drawing them) - `Grid.blocked(x,y,wall) -> bool` — the shared passability test - `Grid.line_of_sight(x0,y0,x1,y1,wall) -> bool` — unobstructed straight line over the tilemap - `Grid.flood(x,y,wall) -> []Cell` — 4-connected reachable region (BFS) - `Grid.a_star(x0,y0,x1,y1,wall) -> []Cell` — shortest 4-connected path (**A***, Manhattan heuristic), empty if unreachable A cell is passable unless it's out of bounds or holds the caller's `wall` tile (a char code, e.g. `'#'`), so any impassable glyph works — and it's all integer/deterministic. Returned `Cell` slices are ordinary Ludic slices (`len` / `[i]`, each cell has `.x`/`.y`). Pathfinding lives under `Grid` rather than a `Path` namespace, since `Path` is already the filesystem-paths library (#10). **Verified** against Python references — a 1500-case fuzzer over random maps agrees exactly on A* path length (optimal, == BFS), flood-fill count, and line-of-sight. `examples/library/grid.ludic` asserts it and is wired into `x test` (now 61 passed, 0 failed); a Grid docs section + 5 per-symbol pages; coverage/vocabulary/fence checks green; seed reseeded and the C-free bootstrap fixpoint holds. ### What's covered vs deferred - [x] `Grid.line` (Bresenham), `Grid.flood_fill`, `Grid.line_of_sight` over the tilemap - [x] `Path.a_star` — as **`Grid.a_star`** (the `Path` name is taken) - [ ] `Query.count/first/nearest/within` — the ECS spatial-query side, which #24 itself flagged as **blocked on a runtime spatial index** Closing this as the grid/pathfinding deliverable; the blocked ECS-query half is tracked in #42.

orkun closed this issue

2026-08-31 11:37:17 +02:00

orkun referenced this issue from a commit

2026-08-31 12:19:27 +02:00

feat(stdlib): add Query.* — ECS spatial queries over the reflection ABI (#42)

orkun referenced this issue

2026-08-31 12:19:42 +02:00

Proposal: ECS spatial queries — Query.count/first/nearest/within (needs a runtime spatial index) #42

orkun referenced this issue

2026-08-31 17:51:59 +02:00

Types phase 4: containers — map / set + fixed arrays [T; N] #54