PATHFINDER

=====================================

PATHFINDER - SIDE A: ASSEMBLY LIBRARY

by Einar Saukas

=====================================



The PATHFINDER library is a small efficient Assembly implementation of the

"simplified Dijkstra" algorithm for finding shortest paths in small mazes, that

you can freely use in your own programs. It uses 512 bytes as temporary queue

(located at addresses 64768 to 65279) and only 90 bytes of code (located at

addresses 65280 to 65369 by default).



It requires a maze previously stored in memory as follows:

0 = wall/obstacle

1 = empty/passage



For instance, let's consider the following map:



#######

#..#..#

#.#..##

#.....#

#######



After removing one of the side walls (you don't need both), replacing each wall

position with 0 and empty position with 1, the result will be a maze that is 6

bytes wide (DELTA=6) represented as follows:



upper_wall:

db 0, 0, 0, 0, 0, 0

first_row:

db 1, 1, 0, 1, 1, 0

second_row:

db 1, 0, 1, 1, 0, 0

third_row:

db 1, 1, 1, 1, 1, 0

lower_wall:

db 0, 0, 0, 0, 0



This maze can be stored anywhere in memory. For using PATHFINDER, the first step

is setting the maze width (delta) as follows:



ld hl, 6 ; delta = 6

ld (65329), hl ; set delta



Then you can set one or more goals inside the maze, directly specifying their

memory addresses. For instance, to set a goal at the upper right corner in

previous example:



ld hl, first_row+4 ; upper right corner address

call 65280 ; set goal



Now you can execute PATHFINDER to solve the maze:



call 65297 ; execute PATHFINDER



After execution, empty/passage positions will be marked as follows:

2 = goal position

3 = 1 step away from closest goal

4 = 2 steps away from closest goal

5 = 3 steps away from closest goal

...



Afterwards, from anywhere in the maze you can easily follow a perfect path to

the closest goal by simply keep moving to any neighbor position marked as 1 step

closer than your current position. Also you will instantly know your exact

distance to the closest goal.



If a certain position is too far away from the goal, this algorithm will still

work, except a value greater than 255 will "overflow" back to 248. In practice,

if a certain position is marked as 248 or higher, you will only know it's far

from goal (at least 246 steps away) and, whenever a position marked as 248

doesn't have any neighbor marked as 247, you must walk to any neighbor marked as

255 instead.



If the goal position(s) changes, you can just reset the internal maze area (to

change PATHFINDER markers back to value 1), add new goal(s) then execute

PATHFINDER again. In previous example, resetting the internal maze area can be

done as follows:



ld hl, first_row

ld bc, lower_wall-first_row

call 65358





=========

ALGORITHM

=========



The PATHFINDER library implements a "simplified Dijkstra" algorithm that is

very efficient for small mazes. It's represented by the following pseudo-code:



// Solve MAZE such that MAZE[POS]=0 if wall, MAZE[POS]=1 otherwise



SetGoals() {

create empty QUEUE

for each GOAL

MAZE[GOAL] = 2

add GOAL to end of QUEUE

}



SolveMaze() {

while QUEUE is not empty

remove POSX from start of QUEUE

for each unmarked position POSY, that is neighbor of POSX

MAZE[POSY] = MAZE[POSX] + 1

add POSY to end of QUEUE

}



Further details and discussions about this concept are provided in section

"BASIC CONCEPTS".





======================

INCREMENTAL PATHFINDER

======================



Executing PATHFINDER in a large maze may take a couple frames. If you are

developing a fast-action game and cannot afford pausing too long for any

specific task, you can use the incremental variant of PATHFINDER instead.



The incremental PATHFINDER works exactly like the original full version, except

it will only solve a limited number of maze steps each time it's called, instead

of solving everything at once. Technically each algorithm execution can take at

most 617N+38 T-states in theory (without memory contention), where N is the

specified limit of steps per call. However in practice it will almost never

exceed 75% of the maximum time. Therefore the default limit of N=30 steps per

call will typically take at most 14K T-states per invocation.



This way, an action game that calls the incremental version only once every 3

frames (using the default configuration mentioned above) would be able to

recalculate all paths in a full screen maze about once per second. This should

work just fine for ghosts chasing a constantly moving player in a Pacman game,

for instance.



This incremental version has very little overhead in comparison to the original

full PATHFINDER. It uses 512 bytes as temporary queue (located at addresses

64768 to 65279) and only 93 bytes of code (located at addresses 65280 to 65372

by default).



After each PATHFINDER invocation, register A will return value 0 if the entire

maze has been solved, or 1 otherwise. So you just need to keep calling it

whenever you want, until it finishes processing. For instance:



loop:

... ; do something

call 65297 ; execute PATHFINDER incrementally

and a ; test register A

jr nz, loop ; repeat until entire maze is solved

...



Everything else works just like the original full version. There are just a few

different addresses between both versions, according to the following table:



+---------------+-------------+-------------+

| | FULL | INCREMENTAL |

+---------------+-------------+-------------+

| STEPS LIMIT | ----- | 65298 |

| DELTA (WIDTH) | 65329/65330 | 65337/65338 |

+---------------+-------------+-------------+

| SET GOAL | 65280 | 65280 |

| PATHFIND | 65297 | 65297 |

| RESET MAZE | 65358 | 65361 |

+---------------+-------------+-------------+





=======

LICENSE

=======



This utility can be used freely within your own ZX-Spectrum programs, even for

commercial releases. The only condition is that you indicate somehow in your

program or documentation that you have used it.





=======

CREDITS

=======



Designed and implemented by Einar Saukas.