Modification of the spanning algorthim
Evaluating closest paths - A* spinoff?

I got some great feedback from Amit Patel (amitp@CS.Stanford.EDU) which came with the following suggestions to optimize the selection of which path to expand in the spanning algorithm. The changes will make it quite like the A* according to feedback I've gotten. Here it is:

-----------
The main difference between your algorithm and A-star (I think) is that A* will prioritize the path-list.

Either:

  1. When you insert a new path into the list, make sure it is in the right place instead of just at the beginning or end.
  2. When you pick a path out of the list, find the best one.
The value to use at any map position P is the cost of going from Start to P plus an estimated cost of going from P to End. For an estimate, you can just use the straight-line distance.

I don't know if you have the time to modify your program, but if you do, I think it could help find a really good algorithm. #2 above is easier to program, so what you'd have to do is:

  1. In addition to the map coordinate in Plist (in FindTheWay), you need to keep track of how far you have walked so far.
  2. Instead of going through all elements of PList and `expanding' them, go through them all to find the one that has the lowest (Plist[AI].DistanceSoFar + DistanceToEnd(PList[AI].Location)) Where DistanceToEnd is just sqrt((x1-x2)^2 + (y1-y2)^2).
  3. After you find the best element of PList, remove it (put the last element of PList in this element's position, and decrement the count).
  4. Examine the neighbors of this best element of PList. Each of the new elements will have a DistanceSoFar one higher than the best element's. (This will be different if you have terrain on your map, of course.)
Once you find the goal, you are reasonably sure your path was "good", beause you always picked the best of the current paths. (A* is a little bit more complicated because it handles the case where you find a new point that's already on your path list.)

As for your list of limitations:

  1. Speed: This algorithm gives higher priority to paths that get closer to the goal, so other ``dumb'' paths are not examined.
  2. Memory: I think the number of paths you need will be shorter because you look at the important ones first, and the others are not `expanded'.
  3. Good looks: I don't know if this is any better than what you have now. I think it would give you a good looking line if you made diagonal paths 1.4 in DistanceSoFar and straight paths 1.0, but I haven't tried this.
  4. Map Changes: Hopefully, if the new algorithm is fast enough, it can be re-evaluated several times while walking, so that if something comes up, it can change the path. I think one way of knowing whether you should do this is to compare the distance you have to go with the "best" distance (straight line). If you are close to the best, it's unlikely new paths will open up. (Of course, it's possible that your path will be blocked ..)
I have not yet tried to implement this. I really like your program! I may have misunderstood your algorithm, though. :( I should take a closer look ..

Amit

----------------

Amit have understood it quite alright. His additions are of great value, because you will probably get a better looking path and a possibility to stop expanding paths that are not especially good and eventually pick them up again if the closer ones didn't get far. In the case where we have to go in the opposite direction (esp. the U-map example) one of the other paths will eventually be closer and expand further.

I have now implemented a version of this, and it is quite fast. You will see how it only evaluate the nearest path. A comment though: You don't have to calculate the SQRT as we are not really interested in the real distance but rather which summed sqares are the smallest. (You really don't have to square them either, but this will make the paths look a bit strange). Try the code below and see how it works:

NPATHPRO.PAS - Implementation of above algorithm..
MUS.PAS - A unit needed for the program to run.

Here is an example of the evaluation it goes through. Look how it ignores the path's that are not neccesary to expand. Remember though, it does not find the shortest path. This is because correct backtracking from B to A is not always found.

Here you can see a close-up on one of the evaluations and see how it expands (gray lines) and cuts through on the backtracking to find the smallest step values. In this case its pretty good:

But in this case there are problems. This is because there are several equal distance step values around one tile. The backtracking will fail to find the best path and choose the long path where the original branch expanded.

Take a look at the page about direct line pathfinding for a solution to this problem.


Back to index page.

john@lis.pitt.edu