Manhattan Distance on C64 | Pattern Library

On a four-way grid, distance is the horizontal gap plus the vertical gap. That makes a useful cheap measure for a guard choosing a nearby target, or a turn-based game showing a movement budget. Two byte coordinates can produce a result larger than a byte.

C64 shows the working result 00 00 FF FF FE 01 00 00. — The completed native caller shows hexadecimal state bytes. The field order below explains the result; the full verification packet retains every call.

Include, initialise and call

Bind AX, AY, BX, BY, DIST_LO, DIST_HI as 6 contiguous private bytes in that order. Include the helper once. Call manhattan_distance_init at the deliberate reset boundary: it clears all named bytes, including inputs. Set your starting values afterwards. Call manhattan_distance_step when this service is needed.

Fill both coordinate pairs and call step when the decision needs the distance. Compare both result bytes when selecting a threshold or nearest target. Ties need a separate stable rule. Reusing one scratch block for successive independent queries is safe under a single owner.

AX/AY and BX/BY are unsigned coordinates from 0–255. Step preserves all four inputs and writes DIST_LO/DIST_HI as a little-endian result |AX − BX| + |AY − BY|, from 0–510. A wider result is needed even though each coordinate fits in one byte.

Reusable initialisation and service

6502.inc

; SPDX-License-Identifier: MIT
; Manhattan Distance. Bind these contiguous private bytes: AX, AY, BX, BY, DIST_LO, DIST_HI.
; init clears the whole block; step uses current inputs. No I/O, waits or IRQ owner.
; A/X/flags may change; Y and decimal mode survive. Binary arithmetic requires D=0.
manhattan_distance_init:
    lda #0
    sta AX
    sta AY
    sta BX
    sta BY
    sta DIST_LO
    sta DIST_HI
    rts
manhattan_distance_step:
    lda #0
    sta DIST_HI
    lda AX
    cmp BX
    bcs distance_x
    lda BX
    sec
    sbc AX
    jmp distance_save
 distance_x:
    sec
    sbc BX
distance_save:
    sta DIST_LO
    lda AY
    cmp BY
    bcs distance_y
    lda BY
    sec
    sbc AY
    jmp distance_add
 distance_y:
    sec
    sbc BY
distance_add:
    clc
    adc DIST_LO
    sta DIST_LO
    bcc distance_done
    inc DIST_HI
distance_done:
    rts
component_end:

State and ownership

Four input bytes and a two-byte output. There is no map, actor state or movement inside this helper. Byte order is explicit on every target, including 68000.

A/X/flags may change; Y and decimal mode survive. Clear decimal mode before binary arithmetic; the standalone caller uses CLD. A direct call pushes a two-byte return address.

This implementation has fixed symbol bindings and one mutation owner. Independent users need distinct state blocks and scoped/renamed bindings; including another copy with the same global labels is not sufficient. Sequential queries may reuse a scratch block only after the previous result has been consumed. Do not let an interrupt and the main loop mutate the same block without a separately designed ownership policy.

The standalone PRG takes over screen/font/colour RAM, disables IRQ sources and does not return to BASIC. Its private diagnostic workspace is $70–$89; its packet starts at $C000.

A small caller you can adapt

The standalone program includes the helper and a separate client. Its read-only table exercises 96 valid inputs, then this client initialises once and retains state between calls. Replace the supplied input changes with your own game values; the display and packet machinery are diagnostics rather than dependencies of the component.

Buildable caller, bindings and include order

demo.asm

AX=$80
AY=$81
BX=$82
BY=$83
DIST_LO=$84
DIST_HI=$85
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
SCORE_CAP=65535
QUEUE_CAP=4
REPEAT_DELAY=4
REPEAT_RATE=2
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.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 separate client retaining state between calls

exercise.inc, excerpt

preview_rules:
!if CUSTOM {
    lda #0
    sta AX
    lda #0
    sta AY
    lda #200
    sta BX
    lda #255
    sta BY
!if BROKEN {
    jsr checked_step
    lda #0
    sta DIST_HI
} else {
    jsr checked_step
}
    jsr emit_state
} else {
    lda #0
    sta AX
    lda #0
    sta AY
    lda #255
    sta BX
    lda #255
    sta BY
!if BROKEN {
    jsr checked_step
    lda #0
    sta DIST_HI
} else {
    jsr checked_step
}
    jsr emit_state
}
    rts

The eight display fields follow AX, AY, BX, BY, DIST_LO, DIST_HI; unused display fields are zero. Each field is a hexadecimal byte. The working row is 00 00 FF FF FE 01 00 00. The output is a completed diagnostic state, not a recording of movement, input or sound hardware.

Make it your own

The custom query moves BX from 255 to 200 while BY stays 255 and A remains at the origin. The result is 455, encoded C7 01, rather than 510, encoded FE 01.

Maintained custom configuration or caller

custom.asm

AX=$80
AY=$81
BX=$82
BY=$83
DIST_LO=$84
DIST_HI=$85
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
SCORE_CAP=999
QUEUE_CAP=2
REPEAT_DELAY=6
REPEAT_RATE=3
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.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 observed custom row is 00 00 C8 FF C7 01 00 00. The retained records qualify these named configurations; a new input domain or larger layout needs its own bounds and fresh execution checks.

Common mistake and repair

The wrong client discards DIST_HI after computing the distance. The opposite corners now look 254 units apart rather than 510. Keep the carry byte through both the storage and comparison paths.

Deliberately wrong client selection

wrong.asm

AX=$80
AY=$81
BX=$82
BY=$83
DIST_LO=$84
DIST_HI=$85
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
SCORE_CAP=65535
QUEUE_CAP=4
REPEAT_DELAY=4
REPEAT_RATE=2
!source "caller.inc"
!source "exercise.inc"
component_start:
!source "component.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 fault result 00 00 FF FF FE 00 00 00. — The wrong client completes and records 00 00 FF FF FE 00 00 00. Compare its state with the working row and the explained failure.

The wrong branch is in the displayed client above, selected by BROKEN. repaired.asm selects the original client again. Its executable matches demo exactly; Spectrum tape filenames can differ while loaded CODE is identical. The bad caller is a labelled experiment, not an alternative recommended implementation.

Cost and verification

The measured helper occupies 65 code bytes plus 6 named state bytes in this layout. Return addresses, alignment, tables and display diagnostics are additional. The sizes cover init and step together, not the whole standalone program.

Two absolute differences and one wide sum, with no multiply or square root. That makes the result cheap for grid decisions, but it does not make it an interchangeable estimate for every movement model.

This is the shortest distance on an unobstructed four-way grid. Walls can make the actual route longer or unreachable. Eight-way movement may call for Chebyshev or octile distance; Euclidean movement needs a different metric. Wider or signed coordinates need wider differences before taking absolute values.

Four native runs use PAL C64 with stock BASIC/KERNAL PRG startup and RUN; Asm198x 0.0.72 and Emu198x 0.44.2. Every run checks 96 table results, dirty initialisation and every state in a separate sequential trace against an independent integer model. This is boundary/varied-input qualification, not exhaustive coverage of every byte combination. Source/tool/firmware hashes, native startup and completion, preserved-register sentinels, immutable loaded code, actual helper extent, capture bytes and pixels, and exact repair are checked. Deliberately changed observations must fail. Firmware is hashed, never distributed.

Source and native evidence.