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.

  1. Add position A to free-path-list 1.
  2. Set current free-path-list = 1.
  3. 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.
  4. 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.
  5. Repeat 3-4 until all free path's from current coordinate has been added to the free-path-list.
  6. Repeat 3-5 until all coordinates in current free-path-list has been evaluated.
  7. Change current free-path-list to the other list (Negate current list selection).
  8. Repeat 3-7 until the point B has been reached.
  9. 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.

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

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

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

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

john@lis.pitt.edu