========================================== PATHFINDER V2.0 - 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 89 bytes of code (located at addresses 65280 to 65368 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 (WIDTH=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 as follows: ld hl, 6 ; width = 6 ld (65328), hl ; set width add hl, hl ; calculate width*2 ld (65338), hl ; set width*2 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 65357 ========= 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 623N+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 92 bytes of code (located at addresses 65280 to 65371 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 | | WIDTH | 65328/65329 | 65336/65337 | | WIDTH*2 | 65338/65339 | 65346/65347 | +---------------+-------------+-------------+ | SET GOAL | 65280 | 65280 | | PATHFIND | 65297 | 65297 | | RESET MAZE | 65357 | 65360 | +---------------+-------------+-------------+ ======= 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.