Re: Pathing
This is a multi-part message in MIME format.
------=_NextPart_000_0026_01C24BC9.B99BCB60
charset="iso-8859-1"
> I wrote this program which solves maze:
=20
YES, 10963508 !!! :)
=20
That is one solution! I call this the 'flood fill' approach:
=20
Search around while always keeping track of where you came from.
When you find...
=20
1. a branch, save it on a stack, (the to-do list)
2. the goal, backtrack the path to the start position
3. a terminating dead-end: see if stack is empty
3.2 if not, restore a saved position from the stack and go on
3.1 If it is, no path was found
=20
It may not give the shortest path to the goal, but it will always
guarantee you a path whenever a path is possible.
=20
Here is a tip on how you may modify the algorithm slightly if
you want the path to be shorter.
=20
At 3.2, when you pick a new position from the to-do list, you are
currently using the last element saved:
=20
> one_to_do_point =3D to_do_points [length (to_do_points)]
=20
This could be called an arbitrarily chosen point, as far as finding
a short path is concerned. Instead, you could try this:
=20
3.2.1 Loop through the to-do list to get all the xy positions
3.2.2 Measure the distance between each xy and the goal *
3.2.3 Use the to-do point which has the shortest distance.
=20
(* Note that you could use Manhattan distance here:=20
distance =3D delta x + delta y)
=20
See how this would make the search 'home in' on the goal?
I did not invent this of course, but I call it 'homing=20
flood fill'.
=20
You would still not be guaranteed an optimal path, however.=20
=20
Dijkstra published a path finder based on travel cost.
(I don't know if he 'discovered' it, nor do I care. I mean,
it's like with the 'discovery' of Australia: if the aborigines
hadn't found it, James Cook would surely have. :)
=20
Using Dijkstra (the algorithm is named after him), you always
get the shortest path, whenever a path can be found.
=20
To implement it, we must keep track of not only where we came
from, but how far we traveled to get here. Like with flood fill,
we also mark off all the squares that we have 'been to'.=20
=20
If we now store the accumulated 'cost' together with the xy=20
coordinates on the list, we can pick them back out in the=20
lowest cost order. I.e.: instead of reverting to the closest
branch, we revert to the lowest-cost branch whenever one=20
search thread hits a dead-end.=20
=20
This, I think is also called the 'marching ants' algorithm.
I'm a bit uncertain about all these names, but it may be that
it isn't Dijkstra unless you add the distance to the cost each
time you decide on what branch to revert to.
=20
So unless I'm much mistaken (I often am):
=20
1. Store the branches as {cost + distance, xy}
=20
2. Pop them back in the lowest order (lowest cost + distance)
=20
And then there is a-star... :)
=20
I'm too tired to write anything more tonight, but I have
written a simple, stupid, ignorant, ineffective, really,
really BAD a-star routine in euphoria (attached).=20
=20
How it became so bad? Well, first, I wrote the kludge in
QBASIC, some time in a previous millennia. Then, after=20
getting Euphoria some months ago, I converted it in an
awesome hurry, just to see how much faster it would run.
In it's horrible anything-but-optimal form it ran about
15 times faster. I haven't touched qbasic ever since... :)
=20
Just run it, play around with the maps and the cost=20
evaluation, see if you can figure it out.
For related sites on the net, search for 'a*', 'a-star',
'Dijkstra', 'short path' etc.
=20
=20
Yours Sincerely,
Barbarella
=20
------=_NextPart_000_0026_01C24BC9.B99BCB60
Content-Type: application/x-compressed;
name="astar.zip"
|
Not Categorized, Please Help
|
|
