Spanning the map - path race!
Let's say we want to go from A to B. It needs a direction map the same
size as the tilemap (with the
landscape). It also needs two free-path-lists with (X,Y) coordinates.
Number of elements depend on mapsize.
- Add position A to free-path-list 1.
- Set current free-path-list = 1.
- Around the current coordinate in the current free-path-list, search in a
special star pattern: Up, Right, Down, Left, Up-Left, Up-Right,
Down-Right and finally Down-Left.
- If you find a free tile, update the direction-map on the free tile with
the direction to to this tile. Add this coordinate to the current
free-path-list.
- Repeat 3-4 until all free path's from current coordinate has been
added to the free-path-list.
- Repeat 3-5 until all coordinates in current free-path-list has been
evaluated.
- Change current free-path-list to the other list (Negate current list
selection).
- Repeat 3-7 until the point B has been reached.
- Backtrack from B to A using the direction map to find the shortest
path.
The effect of this algorithm should be lots of branches expanding from
the staring point A. The one that reaches the goal B is the shortest
path. We know this because each branch is expanded by the length 1 for
each iteration.
There are a couple of problems however.
- Speed: It's a rather timeconsuming algorithm. Long distances will
take longer to evaluate. With no optimization a typlical path on
80 steps took 50ms on my 486dx2-66 CPU. There are three nested loops in
the routine. Optimization will speed it up quite a lot.
- Memory: Since you probably have to distribute the evaluation over time
in a real time strategy game (i.e. like evaluating one of the lists
explained earlier per game refresh, or frame if you call it that),
you have to have one direction-map (and two lists) per unit. This will
surely take a lot of memory depending on size of map. Optimizations
can be done to cut down the memory usage (i.e evaluating on smaller maps).
- Good looks: It follows the difference path between A and B. It first
moves across and then in a straight line. Not the correct "good looking"
lines. The routine can be made to optimize paths further so that a
more good looking path is chosen (without lengthening the path).
- Map changes: If changes is done to the map after evaluation has been
done and the
unit starts to move, it will choose the old shortest path. (I.e. blowing
a hole in a wall won't help if the movement have already been issued.
The unit will move around the wall instead.). It have to re-evaluate
if changes are done. Even if collitions with other units happen.
So you see it's limitations. Please try out this test program I have made
in pascal that includes a simple map editor to try out different maps.
SHORPATH.PAS - Shortest path program in Pascal.
MUS.PAS - A unit needed for the program to run.
Below you will see a picture of the program after a shortest path
evaluation. The gray lines are all the branches it expanded and the white
one is the one that reached the goal first.
Back to index page.