Build Bounded Spatial Buckets on C64 | Pattern Library

Nearby objects are worth comparing; distant ones usually are not. A small bucket table can narrow that candidate list.

C64 shows the working diagnostic row 00 02 00 00 01 02 02 03. — A completed native caller displays 00 02 00 00 01 02 02 03. The public field order below identifies these bytes; the capture is a state diagnostic, not a recording of a finished game.

Use it in a project

Partition a 16×16 logical area into four 8×8 buckets. Each holds four byte item identifiers in S0..S15, with counts C0..C3. MODE=0 clears the table; MODE=1 inserts ITEM at INPUT_X/Y; MODE=2 queries that bucket. Out-of-range coordinates, modes or selected counts return VALID=0 without table writes. A full insertion returns INSERTED=0, FULL=1; successful insertion reports INSERTED=1. Query COUNT and BUCKET identify the active prefix at S[4*BUCKET].

Include component.inc once (MOS callers include the shared 6502 implementation through it). Reserve the public fields in this exact order: BUCKET, COUNT, INSERTED, FULL, VALID, MODE, INPUT_X, INPUT_Y, ITEM, C0, C1, C2, C3, S0, S1, S2, S3, S4, S5, S6, S7, S8, S9, S10, S11, S12, S13, S14, S15. They occupy 29 contiguous bytes. Also reserve the private workspace: T0, T1, T2, EXPR_SAVE (4 bytes). Array names in the explanation refer to the numbered consecutive bindings, such as C0, C1 and so on.

Call spatial_bucket_init once at the intended reset boundary. It clears inputs as well as outputs and workspace. Set your starting state and configuration afterwards, then call spatial_bucket_step whenever the described event occurs. The helper reads no device, waits for no frame and installs no interrupt handler.

Ownership	Fields
Retain between calls	C0..C3 and S0..S15
Supply before service	MODE, INPUT_X/Y and ITEM
Read after service	BUCKET, COUNT, INSERTED, FULL and VALID

Two coordinate high bits select a quadrant. Four fixed slots per bucket avoid allocation; the insertion count is checked before forming the destination index. This is a native bounded companion to the existing broader collision reference, not a replacement for its geometric tests.

Reusable initialisation and service

6502.inc

; SPDX-License-Identifier: MIT
; Build Bounded Spatial Buckets. See README.md for the byte interface and ownership.
; init clears the public fields and private workspace; set inputs afterwards.
spatial_bucket_init:
    lda #0
    sta BUCKET
    sta COUNT
    sta INSERTED
    sta FULL
    sta VALID
    sta MODE
    sta INPUT_X
    sta INPUT_Y
    sta ITEM
    sta C0
    sta C1
    sta C2
    sta C3
    sta S0
    sta S1
    sta S2
    sta S3
    sta S4
    sta S5
    sta S6
    sta S7
    sta S8
    sta S9
    sta S10
    sta S11
    sta S12
    sta S13
    sta S14
    sta S15
    sta T0
    sta T1
    sta T2
    sta EXPR_SAVE
    rts
spatial_bucket_step:
; BUCKET = 255
    lda #255
    sta BUCKET
; COUNT = 0
    lda #0
    sta COUNT
; INSERTED = 0
    lda #0
    sta INSERTED
; FULL = 0
    lda #0
    sta FULL
; VALID = 0
    lda #0
    sta VALID
; if MODE > 2:
    lda MODE
    cmp #2
    beq spatial_bucket_L5
    bcs spatial_bucket_L4
spatial_bucket_L5:
    jmp spatial_bucket_L2
spatial_bucket_L4:
    jmp spatial_bucket_L1
spatial_bucket_L1:
; return
    rts
    jmp spatial_bucket_L3
spatial_bucket_L2:
spatial_bucket_L3:
; if MODE == 0:
    lda MODE
    cmp #0
    beq spatial_bucket_L9
spatial_bucket_L10:
    jmp spatial_bucket_L7
spatial_bucket_L9:
    jmp spatial_bucket_L6
spatial_bucket_L6:
; T0 = 0
    lda #0
    sta T0
; while T0 < 4:
spatial_bucket_L11:
    lda T0
    cmp #4
    bcc spatial_bucket_L14
spatial_bucket_L15:
    jmp spatial_bucket_L13
spatial_bucket_L14:
    jmp spatial_bucket_L12
spatial_bucket_L12:
; C[T0] = 0
    lda #0
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta C0,x
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
    jmp spatial_bucket_L11
spatial_bucket_L13:
; T0 = 0
    lda #0
    sta T0
; while T0 < 16:
spatial_bucket_L16:
    lda T0
    cmp #16
    bcc spatial_bucket_L19
spatial_bucket_L20:
    jmp spatial_bucket_L18
spatial_bucket_L19:
    jmp spatial_bucket_L17
spatial_bucket_L17:
; S[T0] = 0
    lda #0
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta S0,x
; T0 = T0 + 1
    lda T0
    clc
    adc #1
    sta T0
    jmp spatial_bucket_L16
spatial_bucket_L18:
; VALID = 1
    lda #1
    sta VALID
; return
    rts
    jmp spatial_bucket_L8
spatial_bucket_L7:
spatial_bucket_L8:
; if INPUT_X >= 16:
    lda INPUT_X
    cmp #16
    bcs spatial_bucket_L24
spatial_bucket_L25:
    jmp spatial_bucket_L22
spatial_bucket_L24:
    jmp spatial_bucket_L21
spatial_bucket_L21:
; return
    rts
    jmp spatial_bucket_L23
spatial_bucket_L22:
spatial_bucket_L23:
; if INPUT_Y >= 16:
    lda INPUT_Y
    cmp #16
    bcs spatial_bucket_L29
spatial_bucket_L30:
    jmp spatial_bucket_L27
spatial_bucket_L29:
    jmp spatial_bucket_L26
spatial_bucket_L26:
; return
    rts
    jmp spatial_bucket_L28
spatial_bucket_L27:
spatial_bucket_L28:
; T0 = INPUT_X >> 3
    lda INPUT_X
    lsr
    lsr
    lsr
    sta T0
; T1 = INPUT_Y >> 3
    lda INPUT_Y
    lsr
    lsr
    lsr
    sta T1
; T1 = T1 << 1
    lda T1
    asl
    sta T1
; T0 = T0 + T1
    lda T0
    clc
    adc T1
    sta T0
; T1 = C[T0]
    ldx T0
    lda C0,x
    sta T1
; if T1 > 4:
    lda T1
    cmp #4
    beq spatial_bucket_L35
    bcs spatial_bucket_L34
spatial_bucket_L35:
    jmp spatial_bucket_L32
spatial_bucket_L34:
    jmp spatial_bucket_L31
spatial_bucket_L31:
; return
    rts
    jmp spatial_bucket_L33
spatial_bucket_L32:
spatial_bucket_L33:
; BUCKET = T0
    lda T0
    sta BUCKET
; COUNT = T1
    lda T1
    sta COUNT
; VALID = 1
    lda #1
    sta VALID
; if MODE == 1:
    lda MODE
    cmp #1
    beq spatial_bucket_L39
spatial_bucket_L40:
    jmp spatial_bucket_L37
spatial_bucket_L39:
    jmp spatial_bucket_L36
spatial_bucket_L36:
; if T1 < 4:
    lda T1
    cmp #4
    bcc spatial_bucket_L44
spatial_bucket_L45:
    jmp spatial_bucket_L42
spatial_bucket_L44:
    jmp spatial_bucket_L41
spatial_bucket_L41:
; T2 = T0 << 2
    lda T0
    asl
    asl
    sta T2
; T2 = T2 + T1
    lda T2
    clc
    adc T1
    sta T2
; S[T2] = ITEM
    lda ITEM
    sta EXPR_SAVE
    ldx T2
    lda EXPR_SAVE
    sta S0,x
; T1 = T1 + 1
    lda T1
    clc
    adc #1
    sta T1
; C[T0] = T1
    lda T1
    sta EXPR_SAVE
    ldx T0
    lda EXPR_SAVE
    sta C0,x
; COUNT = T1
    lda T1
    sta COUNT
; INSERTED = 1
    lda #1
    sta INSERTED
    jmp spatial_bucket_L43
spatial_bucket_L42:
spatial_bucket_L43:
    jmp spatial_bucket_L38
spatial_bucket_L37:
spatial_bucket_L38:
; if COUNT == 4:
    lda COUNT
    cmp #4
    beq spatial_bucket_L49
spatial_bucket_L50:
    jmp spatial_bucket_L47
spatial_bucket_L49:
    jmp spatial_bucket_L46
spatial_bucket_L46:
; FULL = 1
    lda #1
    sta FULL
    jmp spatial_bucket_L48
spatial_bucket_L47:
spatial_bucket_L48:
    rts
component_end:

Machine contract

A/X/status may change; Y and decimal mode are preserved. Use CLD for binary arithmetic. A direct JSR needs two return-address stack bytes. The helper makes no nested calls and adds no other stack use. Its named scratch is private workspace, not a pointer, a ROM variable or shared zero-page space that the game may borrow concurrently. The samples use fixed symbol bindings. Scope or rename every label and binding, including the component_end measurement marker, and allocate a separate block for each independent instance. Different helpers can also use common field names, so combining them needs separate namespaces or explicitly renamed bindings. Give each block one mutation owner.

The diagnostic PRG owns screen, font and colour RAM and disables interrupts; it does not return to BASIC. The reusable helper does none of those things.

Adapt the caller

demo.asm supplies the bindings and include order. exercise.inc first runs table cases, then a separate client retaining state between calls. A game can call the public step entry directly and remove the diagnostic packet and display. Do not copy the diagnostic’s hardware takeover into an existing game loop.

Build with make ASM198X=/path/to/asm198x. The Makefile produces normal, custom, deliberately wrong and repaired programs. Tools must already be installed; the sample downloads nothing.

Bindings and include order

demo.asm

BUCKET=$80
COUNT=$81
INSERTED=$82
FULL=$83
VALID=$84
MODE=$85
INPUT_X=$86
INPUT_Y=$87
ITEM=$88
C0=$89
C1=$8a
C2=$8b
C3=$8c
S0=$8d
S1=$8e
S2=$8f
S3=$90
S4=$91
S5=$92
S6=$93
S7=$94
S8=$95
S9=$96
S10=$97
S11=$98
S12=$99
S13=$9a
S14=$9b
S15=$9c
T0=$9d
T1=$9e
T2=$9f
EXPR_SAVE=$a0
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=0
BROKEN=0
COYOTE_STEPS=4
BUFFER_STEPS=4
TEXT_CAP=8
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=7
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

A client retaining state between calls

exercise.inc, excerpt

preview_rules:
!if CUSTOM {
; MODE = 1
    lda #1
    sta MODE
; INPUT_X = 15
    lda #15
    sta INPUT_X
; INPUT_Y = 15
    lda #15
    sta INPUT_Y
; ITEM = 255
    lda #255
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; ITEM = 1
    lda #1
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; ITEM = 2
    lda #2
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; ITEM = 3
    lda #3
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; ITEM = 4
    lda #4
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
    rts
} else {
; MODE = 1
    lda #1
    sta MODE
; INPUT_X = 2
    lda #2
    sta INPUT_X
; INPUT_Y = 3
    lda #3
    sta INPUT_Y
; ITEM = 7
    lda #7
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; ITEM = 8
    lda #8
    sta ITEM
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
; MODE = 2
    lda #2
    sta MODE
!if BROKEN {
; MODE = 0
    lda #0
    sta MODE
}
    jsr checked_step
    jsr emit_state
}
    rts

Customise it

Fill the bottom-right bucket, then attempt one overflow insertion. The maintained custom caller changes its inputs or client sequence rather than hiding a different implementation behind the same label. Compare every state of the two clients, not only their final display.

Custom client selection

custom.asm

BUCKET=$80
COUNT=$81
INSERTED=$82
FULL=$83
VALID=$84
MODE=$85
INPUT_X=$86
INPUT_Y=$87
ITEM=$88
C0=$89
C1=$8a
C2=$8b
C3=$8c
S0=$8d
S1=$8e
S2=$8f
S3=$90
S4=$91
S5=$92
S6=$93
S7=$94
S8=$95
S9=$96
S10=$97
S11=$98
S12=$99
S13=$9a
S14=$9b
S15=$9c
T0=$9d
T1=$9e
T2=$9f
EXPR_SAVE=$a0
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=1
BROKEN=0
COYOTE_STEPS=2
BUFFER_STEPS=2
TEXT_CAP=4
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=49
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

The custom diagnostic row is 03 04 00 01 01 01 0F 0F. The full client trace in the source explains how it gets there.

Mistake and repair

The wrong caller selects clear instead of insert/query. Counts remain zero and candidates disappear. Clear once at the intended rebuild boundary, then retain the populated buckets for all queries.

The BROKEN branch lives in the sequential client, not the reusable helper. wrong.asm selects it; repaired.asm restores the normal call sequence. The repaired executable matches the normal program (for Spectrum, compare loaded CODE rather than the tape filename).

Select the deliberately wrong client

wrong.asm

BUCKET=$80
COUNT=$81
INSERTED=$82
FULL=$83
VALID=$84
MODE=$85
INPUT_X=$86
INPUT_Y=$87
ITEM=$88
C0=$89
C1=$8a
C2=$8b
C3=$8c
S0=$8d
S1=$8e
S2=$8f
S3=$90
S4=$91
S5=$92
S6=$93
S7=$94
S8=$95
S9=$96
S10=$97
S11=$98
S12=$99
S13=$9a
S14=$9b
S15=$9c
T0=$9d
T1=$9e
T2=$9f
EXPR_SAVE=$a0
STATE=$80
input_ptr=$70
cases_left=$72
ptr=$74
saved_y=$76
OUTPUT=$c000
preview=OUTPUT+1400
ready=OUTPUT+1408
CUSTOM=0
BROKEN=1
COYOTE_STEPS=4
BUFFER_STEPS=4
TEXT_CAP=8
PROPERTY_COUNT=16
STREAM_BYTES=13
CRC_POLY=7
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.inc"
!source "data.inc"
!source "cases.inc"
hex_font:
    !byte 0,0,0,0,0,0,0,0,0,56,40,40,40,56,0,0,0,16,48,16,16,56,0,0,0,56,8,56,32,56,0,0,0,56,8,56,8,56,0,0,0,40,40,56,8,8,0,0,0,56,32,56,8,56,0,0,0,56,32,56,40,56,0,0,0,56,8,8,8,8,0,0,0,56,40,56,40,56,0,0,0,56,40,56,8,56,0,0,0,16,40,56,40,40,0,0,0,48,40,48,40,48,0,0,0,56,32,32,32,56,0,0,0,48,40,40,40,48,0,0,0,56,32,48,32,56,0,0,0,56,32,48,32,32,0,0
code_end:

C64 shows the deliberate error row FF 00 00 00 01 00 02 03. — The wrong client completes with FF 00 00 00 01 00 02 03; its changed inputs and state explain the result.

Cost and alternatives

The measured helper extent is 391 code bytes; public state is 29 bytes and private scratch is 4 bytes. There are no immutable helper tables. Caller data, the test cases, return-address stack, alignment and display buffers cost additional space. These are assembled sizes, not cycle measurements.

Clear touches twenty table bytes; insert/query takes bounded arithmetic and one selected count read. More buckets reduce candidate density but cost counts/storage, while larger bucket capacity increases worst-case pair testing.

This table stores point membership, not shape overlap. Objects spanning buckets require insertion into every covered bucket or neighbouring-bucket queries; otherwise broad-phase false negatives are possible. Duplicate identifiers are permitted, and a full bucket needs an explicit game policy rather than silently dropping possible collisions.

Execution evidence

Four variants run on PAL stock-ROM PRG, using Asm198x 0.0.72, Emu198x 0.44.2. Each executes 34 boundary/varied/error table cases, dirty initialisation and the separate retained-state client. An independent mathematical/container model checks every public byte after every call. This is bounded example coverage, not exhaustive correctness for every possible state.

The records retain loaded immutable code, completion, register sentinels, full packets, source/tool/firmware hashes and captures. The public gate validates these retained observations and rejects altered evidence; it does not run restricted firmware. No firmware is distributed. The eight displayed bytes are the first eight public fields, zero-padded when shorter; the packet includes every field.

Where it fits

Rectangle overlap: Use the bucket as a broad phase and apply an actual shape test to candidate pairs.

The Craft · Maths for Games · Source and native evidence.