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

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...