Find a Grid Path and Reachable Cells in Spectrum BASIC | Pattern Library

An enemy needs to get around a wall. A turn-based unit needs to show where it can move. Both begin with the same question: which cells can I reach, and how many steps will it take? This breadth-first search returns that information without deciding how your characters move or how the map is drawn.

Spectrum BASIC shows both retained behaviour checks passing. — The working caller completes with both saved checks equal to one.

Include and initialise

Reserve arrays M(16), D(16), R(16), Q(16), public scalars W/H/S/T/P/F/O/E/C and private scratch I/N/J/V/X/Y/A. Reserve lines 3000–3720 and combine the numbered helper with your caller using build.py. Put END, STOP or a jump before it. Use GOSUB on C64/BBC, GO SUB on Spectrum. Avoid the private globals in surrounding caller loops.

W and H are integral logical dimensions from one to four, with at most sixteen cells. Cells are zero-based, laid out row by row. For cell n, x=n-W*INT(n/W) and y=INT(n/W). Store its map value in M(n+1): zero means walkable, one means blocked. S is the start cell; T is the requested target. Calling 3000 clears results/work arrays, retaining W/H/S/T/M. Calling 3100 does that reset itself before every query, so callers do not need a separate initialisation each time.

Read the result

When O=1, P is the shortest number of four-neighbour steps and F is the first cell to move into. For S=T, P=0 and F=S. When O=0, no route exists and P/F remain 255. Check O before using F as an index. E=1 rejects bad dimensions or endpoints; E=2 rejects a non-binary map value in the active rectangle. Invalid calls clear work/results without changing the map or supplied dimensions/endpoints. Unused map cells outside W*H are ignored.

D(n+1) is a shortest distance or 255 for an unreachable/blocked cell. R(n+1) is its parent cell, or 255 for the start/unvisited cells. C counts reachable cells. Q(1)..Q(C) lists discovery order; unused queue entries are zero. Zero is also a valid queued cell, so use C rather than searching for a zero terminator.

The reusable routine

Reusable numbered routines

routines.bas

3000 LET P=255: LET F=255: LET O=0: LET E=0: LET C=0
3010 FOR I=1 TO 16: LET D(I)=255: LET R(I)=255: LET Q(I)=0: NEXT I: RETURN
3100 GO SUB 3000: LET E=1
3110 IF W<1 OR W>4 OR W<>INT (W) THEN RETURN
3120 IF H<1 OR H>4 OR H<>INT (H) THEN RETURN
3130 LET N=W*H
3140 IF S<0 OR S>=N OR S<>INT (S) THEN RETURN
3150 IF T<0 OR T>=N OR T<>INT (T) THEN RETURN
3160 FOR I=1 TO N
3170 IF M(I)<>0 AND M(I)<>1 THEN LET E=2: RETURN
3180 NEXT I
3190 LET E=0
3200 IF M(S+1)=1 THEN RETURN
3210 LET D(S+1)=0: LET Q(1)=S: LET J=0: LET C=1
3300 IF J>=C THEN GO TO 3500
3310 LET V=Q(J+1): LET J=J+1
3320 LET X=V-W*INT (V/W): LET Y=INT (V/W)
3330 IF Y>0 THEN LET A=V-W: GO SUB 3700
3340 IF X<W-1 THEN LET A=V+1: GO SUB 3700
3350 IF Y<H-1 THEN LET A=V+W: GO SUB 3700
3360 IF X>0 THEN LET A=V-1: GO SUB 3700
3370 GO TO 3300
3500 IF D(T+1)=255 THEN RETURN
3510 LET O=1: LET P=D(T+1)
3520 IF T=S THEN LET F=S: RETURN
3530 LET A=T
3540 IF R(A+1)=S THEN LET F=A: RETURN
3550 LET A=R(A+1): GO TO 3540
3700 IF M(A+1)=1 OR D(A+1)<>255 THEN RETURN
3710 LET D(A+1)=D(V+1)+1: LET R(A+1)=V
3720 LET Q(C+1)=A: LET C=C+1: RETURN

The queue visits neighbours up, right, down, left. That makes ties predictable. Cells are marked when discovered, before they enter the queue, so each enters at most once. A parent points to a cell exactly one step closer to the start. Following parents backwards finds F without allocating a second path array.

Customise it

The custom caller uses a three-column rectangle instead of four. The map and all work arrays retain sixteen allocated elements: this changes the logical world and scan, not the declared allocation. Increase capacity only by changing DIM, bounds, validation, sentinels and tests together. This routine intentionally caps dimensions at four to keep the complete example small. It is a reusable small-region component, not a claim to navigate a whole commercial game’s world at this scale.

Move an actor into F only when O=1 and the game permits that move; recompute after obstacles change. Static maps can cache distance fields, while many moving enemies may share a field grown from a common target. A reversed/shared field needs its own direction and tie policy. Weighted terrain needs Dijkstra’s algorithm or another cost-aware search; plain BFS assumes every permitted step has equal cost. Diagonals, corner cutting and actor footprints also change the neighbour rules.

Mistake and repair

The wrong caller erases the wall before querying. It obtains a shorter path through what the game intended to be solid ground; both saved detour checks become zero. The pathfinder is following the supplied map. The repair preserves that wall, with source and loaded tokenised program identical to the working version.

Spectrum BASIC shows two failed checks from the deliberate caller mistake. — The wrong caller runs to completion, but both saved behaviour checks are zero.

Cost and Maths for Games

The search visits at most WH cells and tests at most four neighbours each. Validation scans the active map first; parent reconstruction adds up to one path’s length. Four sixteen-element numeric arrays cost far more than 64 machine-code bytes in an interpreter. BFS spends storage on predictable shortest paths. Greedy movement uses less memory but can become trapped behind walls; A can reduce explored cells on larger maps at the cost of an ordered frontier and heuristic rules.

Maths for Games supplies row-major coordinates, graph distance and the Manhattan lower bound on an empty four-neighbour grid. The Craft helps decide whether an enemy should take the shortest route at all. The returned arrays are data: drawing reachable cells or animating movement belongs to a caller.

Machine and measured size

Spectrum FOR variables must be single letters: this diagnostic uses Z/Q instead of the other callers’ JJ/KK. Numeric arrays start at one. AND/OR in these listings join comparisons; neither is being used as a bitwise operator. The diagnostic reserves its mailbox above CLEAR 59999.

The numbered helper occupies 1009 tokenised program bytes on this interpreter, including line headers. This excludes the caller, test tables, numeric scalar/array storage, interpreter stacks and ROM. Tokenised size is not machine-code size or a hardware-cycle count. No real-time or whole-game performance budget is inferred from the diagnostic. The caller’s AA/BB, Z/Q and RAM mailbox are observation machinery, not required game state.

Execution evidence

Working, custom, deliberately wrong and exact repaired callers executed through Spectrum’s stock BASIC interpreter under Emu198x 0.44.2. Build198x 0.2.9 tokenises C64 PRG and Spectrum TAP programs. C64 enters stock RUN, Spectrum uses ROM tape loading, and BBC enters every numbered source line through MOS/BASIC. Actual loaded program bytes, complete state packets, positive completion/count/guards and visible result pixels are checked. After the positive completion marker, the observer advances two complete display frames before capturing, so a partially scanned final character cannot masquerade as a finished picture. Firmware is not distributed.

An independent mathematical/order model checks the trace and rejects altered source, configuration, loaded program, state, completion and image evidence. Host exhaustive checks complement the native boundary/sequential examples; those host ranges are not claimed as natively exhaustive. The wrong caller prints 0,0 and the normal/custom/repaired callers print 1,1.

Public CI checks retained evidence; it does not execute restricted firmware. Refresh with python3 scripts/verify-basic-world.py bounded-grid-path sinclair-zx-spectrum --tools /path/to/extracted/releases and inspect with python3 scripts/check-basic-world.py bounded-grid-path.

Explore further

Compare the assembly technique. The BASIC game-flow routine makes session boundaries explicit. Complete source and native evidence.