============================ PATHFINDER - by Einar Saukas ============================ ZX-Spectrum games typically require finding shortest paths within a single screen, thus a 2D grid area smaller than 24x32. For such small maps, the overhead from using a fairly complex heuristics-based pathfinding algorithm (in terms of data structure management time and memory) is not worth it. Instead, these maps can be easily solved by the following "simplified Dijkstra" algorithm: * All positions that are neighbor to the target location must be marked with value "1", since they are 1 step away from this target; * All remaining positions that are neighbor to "1" must be marked with value "2", since they are 2 steps away from the target; * All remaining positions that are neighbor to "2" must be marked with value "3", since they are 3 steps away from the target; * ... Keep doing it until it reaches the initial position. Afterwards, if the initial position gets marked with value "9", it means it's 9 steps away from the target position. From there, you can move to a position that is 8 steps away from target, then to a position that is 7 steps away, and so on. Technically, this algorithm corresponds to the following pseudo-code: pathfind(position SOURCE, position TARGET) { create empty QUEUE clear array DISTANCE[] mark DISTANCE[TARGET] = 0 add TARGET to end of QUEUE while QUEUE is not empty remove POSX from start of QUEUE for each unmarked position POSY, that is neighbor of POSX if POSY is same as SOURCE then return "PATH FOUND" DISTANCE[POSY] = DISTANCE[POSX] + 1 add POSY to end of QUEUE return "THERE'S NO PATH" } The QUEUE mentioned above is just a small circular buffer, and DISTANCE is a temporary buffer area. ============ "SINGLEPATH" ============ Program "SINGLEPATH" is a BASIC implementation of this algorithm, provided to help explain how it works. It contains the following lines: * Lines 10-30: Generates a random map on screen. At this point, if you are not happy with the generated map, you can simply save the emulator screen, edit it, then import it again. You don't even need to use the same colors: every char position with a dark PAPER (colors 0,1,2,3 without BRIGHT) will be interpreted as obstacles, everything else as paths. * Lines 40-60: Asks for a source and target position. * Lines 70-210: Executes pathfinder. During execution, neighbor positions stored in the queue are shown in yellow, already processed positions in cyan. * Lines 220-280: Shows the shortest path (if the map has a valid solution). =========== "MULTIPATH" =========== Program "MULTIPATH" is another BASIC implementation of the same algorithm, but supporting multiple sources and targets. In practice, it only means calculating paths for the entire map, without bothering to check at every step if it has reached a SOURCE position. Pathfinding for multiple sources and/or targets is quite useful in practice. For instance, if a Pac-Man game takes the current player position as target, this algorithm will determine the best path for every computer-controlled enemy ghost at once. This program contains the following lines: * Lines 10-30: Generates a random map on screen. * Lines 40-60: Asks for multiple source and target positions. * Lines 70-120, 200-210: Executes pathfinder. Notice that the number of sources and targets won't make any difference in the map processing time. * Lines 130-190: Shows shortest path from each source to its closest target. ======== TO DO... ======== An Assembly implementation will be provided soon...