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:
- 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.
- 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:
- In addition to the map coordinate in Plist (in FindTheWay),
you need to keep track of how far you have walked so far.
- 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).
- 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).
- 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:
- Speed: This algorithm gives higher priority to paths that
get closer to the goal, so other ``dumb'' paths are
not examined.
- 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'.
- 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.
- 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.