More shortest pathing
Martijn Faassen
Hi everybody,
I've not followed the various shortest path algorithm threads in this
newsgroup very closely, but today I thought I'd have a go at it.
My first version works quite nicely, and since I'm so pleased with it,
I thought I'd post the algorithm here. It's probably not spectacular or
new, but I like it, anyway.
I was inspired mainly by reading a few lines here and there on pathing
algorithms in this newsgroup.
The field is a grid of squares, for example 60 by 60. A square can be set
to 'empty', 'obstacle', 'start', 'goal', and 'path'.
The 'obstacles' are obstacles the path can't go through.
The start square is simply point A where we start searching. The
goal square is point B where we want to know the shortest path to.
'path' is a special marker. More on this later.
The algorithm starts by placing a single entity which I call 'ant' (also
inspired by some newsgroup lines I read) on the start square.
This ant has a 'stack', which initially is empty. The stack will contain
moves. A path is defined by moves (north, south, west, east). So, the
stack contains the path, for example: nnwwssse.
The ant marks the area it is on with the 'path' marker.
Then the following rules are applied to the ant:
- If the ant is blocked, that is, if it is surrounded in n, s, w, e directions
by either obstacles or path markers, the ant dies. That's the end of the ant.
- if the ant is not blocked, it will move itself into the empty square.
(for example, to the north).
- if there were multiple empty squares, the ant will reproduce,
moving copies into the other empty squares. (for example, if the ant
moved to an empty square to the north, and the w and s squares are empty too,
copies of the 'parent' ant will be moved into those squares.
Each time an ant moves, it will push the direction into which it moved (for
example, n), onto its stack. Therefore, the stack will contain the entire
path the ant travelled.
Reproduction:
Children will have copies of the stacks of their parent ant.
So, they will share the same path history. The subsequent
different moves will make the paths different though (for example, the
parent went n from here, and a child went w, and another child went s).
So, each ant will contain on its stack a path that started in the start
square, as the original ancestor ant started there as well.
There is a circular list of ants. If an ant is born, it will be inserted
previous to its parent in the list. The program goes through the list,
from ant to next ant, each executing it one step (which is executing the
rules as stated above).
Now, there's one other rule. If an ant moves onto the goal square, the entire
algorithm stops. The path of that ant is the shortest path from start to goal.
If you watch it, the path markings look like a floodfill algorithm.
The surviving ants are on the edge of the 'wave', as any ant that gets
caught in the middle is surrounded by the paths of other ants (and its
own path), and therefore dies. This way the amount of ants stays fairly
limited. (depends on the map)
I've done some *very preliminary speed tests with this system. This gave a
search time (on a 60x60 map) of about .06 seconds. Pretty nice for a first
try. This will probably vary hugely with different types of maps.
The code wasn't very optimized, and the speed test not very thorough, so don't
read too much into this. The code does find the shortest path, but contains
a few bugs still, too. (currently it'll crash if a path *can't* be found :)
Did I make sense? Any reactions will be appreciated!
The source is in generic C++ (the graphics front end uses
svgalib in Linux, but you can also compile for meager text output).
I'm not done with the code yet, but if people mail me that they want it,
I will probably create nice 'publishable' version of the code.
Martijn
--
Martijn Faassen email:faa...@phil.ruu.nl
Pessimist's Definition of Optimism : Failing to learn from life.
Optimist's Definition of Pessimism : Failing to learn to live.
Steven Woodcock
Martijn Faassen (faa...@phil.ruu.nl) opined thusly:
: Hi everybody,
:
: <Interesting description of an ant shortest-pathing algorithm deleted>
:
This sounds rather like a classic Djikstra's to me. You're
not really doing anything to prioritize which ants you examine (other than
to push the children into the list ahead of the parents), and so it
works out to non-heuristic Djikstra's. I think.
: I've done some *very preliminary speed tests with this system. This gave a
: search time (on a 60x60 map) of about .06 seconds. Pretty nice for a first
: try.
:
This is decent timing, although you didn't say how widely your
terrain costs varied. You'll find that your solution time will get
larger depending on how varied the terrain is; if it's relatively flat
you'll find quicker solutions.
By way of comparison, I've been getting solution times of 2-3ms,
or .002 - .003 seconds, on 50x50 "flat" maps (all terrain equal costs, no
obstacles), and on the order of 12-14ms (.012 - .014 seconds) with randomly
generated terrain. This is on a P-133 in a pure "test bed" mode, so I'm not
doing anything other than fighting the standard Win-95 overhead. You
didn't mention what you're running on.
: Did I make sense? Any reactions will be appreciated!
Sounds like solid solution to me. I'd be interested to know what your
memory requirements might be with this approach.
: The source is in generic C++ (the graphics front end uses
: svgalib in Linux, but you can also compile for meager text output).
: I'm not done with the code yet, but if people mail me that they want it,
: I will probably create nice 'publishable' version of the code.
I urge you to allow me to post it on my AI Software Solutions Page
(see address below). Pathing algorithms appear to be by far the most
popular type of post! ;)
Steven
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Real3D <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: wood...@escmail.orl.mmc.com (Work), swoo...@cris.com (Home) |
| Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) |
| http://www.cris.com/~swoodcoc/ai.html (Game AI page) |
| http://www.cris.com/~swoodcoc/software.html (AI Software page) |
| Disclaimer: My opinions in NO way reflect the opinions of |
| the Lockheed Martin Information Real3D |
+=============================================================================+
Martijn Faassen
In article <4o5vgr$f...@tribune.concentric.net>,
Steven Woodcock <Swoo...@cris.com> wrote:
>Martijn Faassen (faa...@phil.ruu.nl) opined thusly:
>: Hi everybody,
>
>:
>: <Interesting description of an ant shortest-pathing algorithm deleted>
>:
>
>
> This sounds rather like a classic Djikstra's to me. You're
>not really doing anything to prioritize which ants you examine (other than
>to push the children into the list ahead of the parents), and so it
>works out to non-heuristic Djikstra's. I think.
It's not heuristic at all, indeed. Like I said, it's probably done
long before I did it (by Dijkstra), but it's interesting trying to figure
this out for myself.
How does one apply heuristics to path finding on a random map? I've been
wondering about this one. I can imagine something like: move toward the
goal faster than you move away from the goal, but many maps exist that
look like this:
---
S| G
---
Does this heuristic still improve performance on maps like this?
I can see how it could.. I suppose it depends a lot on the map.
However, the game I might be this type of routine to in the (far off) future
has very dynamic maps. Structures evolve on the map during play, but it's
hard to say which structures, and they can change all the time.
But that's why I'm looking into this anyway. And because this is fun,
of course. Plus I wanted to have something to delurk in this
most interesting newsgroup. :)
>: I've done some *very preliminary speed tests with this system. This gave a
>: search time (on a 60x60 map) of about .06 seconds. Pretty nice for a first
>: try.
>:
> This is decent timing, although you didn't say how widely your
>terrain costs varied. You'll find that your solution time will get
>larger depending on how varied the terrain is; if it's relatively flat
>you'll find quicker solutions.
>
> By way of comparison, I've been getting solution times of 2-3ms,
>or .002 - .003 seconds, on 50x50 "flat" maps (all terrain equal costs, no
>obstacles), and on the order of 12-14ms (.012 - .014 seconds) with randomly
>generated terrain. This is on a P-133 in a pure "test bed" mode, so I'm not
>doing anything other than fighting the standard Win-95 overhead. You
>didn't mention what you're running on.
I'm running on an (AMD)486DX4/100. Linux. The (very basic) test was without
X. How much after is a P-133 relative to my machine? I'm curious how
close I get to your values. At least now I have some 'benchmarks' to
compare my algorithm against. :)
Although real benchmarks need more detail, of course. 50x50, randomly
generated start and goal locations, averaged?
What about 'not being able to find' (all ants die in my case :), do you
factor that in?
>: Did I make sense? Any reactions will be appreciated!
>
> Sounds like solid solution to me. I'd be interested to know what your
>memory requirements might be with this approach.
Currently probably quite a lot. I'll track that, too. I've only been
working on this for a single day! :) There's quite a few optimisations,
both memory and CPU wise, which I can make. I've been using 'chars' to
store what only needs 2 bits (directions), for instance. And that can
of course be compressed further. I think I can find a way to get rid of
a lot of copying operations as well.
>: The source is in generic C++ (the graphics front end uses
>: svgalib in Linux, but you can also compile for meager text output).
>: I'm not done with the code yet, but if people mail me that they want it,
>: I will probably create nice 'publishable' version of the code.
>
> I urge you to allow me to post it on my AI Software Solutions Page
>(see address below). Pathing algorithms appear to be by far the most
>popular type of post! ;)
Coincidentally enough :), I checked it out today. Sure, I'd love to have
it posted there.
I'll work on non-pathing algorithms next. Any things which are in
particularly high demand?
Steven Woodcock
: Steven Woodcock <Swoo...@cris.com> wrote:
: How does one apply heuristics to path finding on a random map? I've been
: wondering about this one. I can imagine something like: move toward the
: goal faster than you move away from the goal, but many maps exist that
: look like this:
: ---
: S| G
: ---
: Does this heuristic still improve performance on maps like this?
You've hit upong the big bugaboo in pathing, the Evil U-Shaped Obstacle.
It can really hose you.
One very clean heuristic is to weight your ants so that you examine
the ones closest to the destination first. That is, use a heuristic
function h where
h(currow, curcol, destrow, destcol) {
return max(abs(currow - destrow), abs(curcol - destcol));
}
This way, ants farther away from the destination get saddled with
a huge "weight" and thus get a lower priority for solution finding.
Ants closer have a lighter "weight" and hence you'll look at them first.
If there aren't any impassable obstacles, that means you tend to examine
ants towards the destination first and find the solution faster.
But, of course, there's the Evil U. Using this heuristic, you
could cheerfully run down the map into the U and then "thrash" a bit as
the algorithm examines nearly every single point around the area to try
to get around it. It will eventually exhaust all of those possibilities
and fall back to more circumspect routes, and find the solution, but it
will take longer in that case.
There are several ways around this. You could build a secondary
heuristic to try to track if you're stuck. You could randomly switch
heuristics every 10th path (something I've not tried, but which might
be interesting to play with). You could play around with your selection
criteria when you're picking which ants to look at next. (Normally you
find the closest guy, then the next closest, then the next. You could
instead pick the closest, then the *third* closest, etc.). You could
start ants at both the starting point and the destination and run until
they meet in the middle; the Evil U might not be a factor coming from
the other direction. Etc.
: > By way of comparison, I've been getting solution times of 2-3ms,
: >or .002 - .003 seconds, on 50x50 "flat" maps (all terrain equal costs, no
: >obstacles), and on the order of 12-14ms (.012 - .014 seconds) with randomly
: >generated terrain. This is on a P-133 in a pure "test bed" mode, so I'm not
: >doing anything other than fighting the standard Win-95 overhead. You
: >didn't mention what you're running on.
: I'm running on an (AMD)486DX4/100. Linux. The (very basic) test was without
: X. How much after is a P-133 relative to my machine? I'm curious how
: close I get to your values. At least now I have some 'benchmarks' to
: compare my algorithm against. :)
I would presume the Pentium's floating point performance is superior,
but in this case that probably doesn't make a difference...my algorithm is
using all ints and shorts right now. I'd have to check the Official
Intel Propoganda sheet to figure out how the two compare.
: Although real benchmarks need more detail, of course. 50x50, randomly
: generated start and goal locations, averaged?
For testing I always start in the upper left-hand corner (1,1) and
run down to the lower right-hand corner (50,50). The terrain was
randomly generated with the rand() function, scaled down to return values
from 0-10. Anything 0 or 10 was set to INFINITY (i.e., impassable).
: What about 'not being able to find' (all ants die in my case :), do you
: factor that in?
That just returns a -1 for the weight, so I can test it and go
"darn" and do something else.
: > I urge you to allow me to post it on my AI Software Solutions Page
: >(see address below). Pathing algorithms appear to be by far the most
: >popular type of post! ;)
: Coincidentally enough :), I checked it out today. Sure, I'd love to have
: it posted there.
Cool! I look forward to seeing it.
: I'll work on non-pathing algorithms next. Any things which are in
: particularly high demand?
I haven't had any good line-of-sight algorithms submitted yet.
That could be useful.
I.G.Badcoe
Hi guys,
Steven Woodcock (Swoo...@cris.com) wrote:
: Martijn Faassen (faa...@phil.ruu.nl) opined thusly:
: You've hit upong the big bugaboo in pathing, the Evil U-Shaped Obstacle.
: It can really hose you.
: One very clean heuristic is to weight your ants so that you examine
: the ones closest to the destination first. That is, use a heuristic
: function h where
: h(currow, curcol, destrow, destcol) {
: return max(abs(currow - destrow), abs(curcol - destcol));
: }
This begins to look like the A* search that so many folk have already
told us about. If you were to put it in the ants algorithm it would
overcome another limitation that I think you (martijn) have which is
that you can only (at present) treat terrain as open or blocked. You
cannot, for example, have a partially blocked type (say swamp) because
an ant is either on the list or it is not. If the list were sorted,
however, you could include the cost of the terran crossed so far as well
as estimated distance from the goal in the sort criterion. In which case
I think you would have a pure A* algorith (I think).
: This way, ants farther away from the destination get saddled with
: a huge "weight" and thus get a lower priority for solution finding.
: Ants closer have a lighter "weight" and hence you'll look at them first.
: If there aren't any impassable obstacles, that means you tend to examine
: ants towards the destination first and find the solution faster.
: But, of course, there's the Evil U. Using this heuristic, you
: could cheerfully run down the map into the U and then "thrash" a bit as
: the algorithm examines nearly every single point around the area to try
: to get around it. It will eventually exhaust all of those possibilities
: and fall back to more circumspect routes, and find the solution, but it
: will take longer in that case.
: There are several ways around this. You could build a secondary
: heuristic to try to track if you're stuck.
Or you could only sort the list in a 'probabilistic manner' so that the
closest ants get some priority but not a total monopoly. This way if there
was a reasonably easy way around you'd have a good chance of evaluating one
of the ants near to it and letting it take over the head of the list.
On a different note, isn't all this talk of optimal and fastest path-finding
algorithms a little bit besides the point ? Two reasons:
Real beings don't use them ! They use simpler approaches like
assessing the locality and picking the direction that is most 'down hill' or
heading in the right direction until they get stuck and then trying to go
around the obstacle.
However good your algorithm it will always be possible to construct
a terrain that it finds 'difficult'. As an absolute proof visit Hampton-Court
Maze and try out your on-board software.
Thus it might be 'more realistic' to accept that some terrains are hard
to cross and construct the game such that units getting stuck (or going the long
way around when it wasn't strictly necessary) is an expected occurence.
Badders
Richard Wesson
['ant races']
Gee, that sounds like a pretty nice algorithm.
Here's a couple of modifications for doing it better.
Getting rid of the stack carried with every ant:
Keep track of the time tick and every time an ant steps on a new square,
'stamp' that square with the current time tick. When one ant reaches
the destination, you can find the shortest path back to the start by
starting at the end and always going to the square with the smallest
time stamp.
For terrain which has a variable cost of entry (squares may cost different
number of ticks to enter, like swamp or forest or whatever):
Keep a queue of ant lists. The current ant list is all the ants arriving
at their destination squares this tick. New ants which will arrive at
now+n time ticks are put in list currentListIndex+n. Do all the ants for
the current turn and then go to the next ant list at currentListIndex+1.
See the description of this algorithm on Steven Woodcock's web page.
As he's noted, this is a modified breadth-first search (like Dijkstra?)
We can't do much better than this -- you have to inspect up to N
squares V times, where N is the number of squares on the board and
V is the number of ways to get from one square to another (usually 4
or 8). Maybe you can reduce V, but it's always possible that you have
to inspect N squares.
C++/DOS gave me ~15 msec for a 100x100 board on a 486/80. It's good,
but not good enough for a real-time game. For a reasonable size board,
any algorithm which has to look at every square will not be fast enough
for real-time. Personally I think such a board should be reduced to
polygons and some geometric path-finder used, as somebody already
mentioned. I haven't seen any real-time games with variable terrain
(beyond passable/impassable) so this should work.
-- Richard Wesson
Martijn Faassen
In article <4o7bqb$4...@tribune.concentric.net>,
Steven Woodcock <Swoo...@cris.com> wrote:
>Martijn Faassen (faa...@phil.ruu.nl) opined thusly:
>: In article <4o5vgr$f...@tribune.concentric.net>,
>: Steven Woodcock <Swoo...@cris.com> wrote:
>: How does one apply heuristics to path finding on a random map? I've been
>: wondering about this one. I can imagine something like: move toward the
>: goal faster than you move away from the goal, but many maps exist that
>: look like this:
>
>: ---
>: S| G
>: ---
>
>: Does this heuristic still improve performance on maps like this?
>
>
> You've hit upong the big bugaboo in pathing, the Evil U-Shaped Obstacle.
>It can really hose you.
*grin* Okay.
> One very clean heuristic is to weight your ants so that you examine
>the ones closest to the destination first.
Yes, I thought about something like that, too.
[heuristics snipped]
>: > By way of comparison, I've been getting solution times of 2-3ms,
>: >or .002 - .003 seconds, on 50x50 "flat" maps (all terrain equal costs, no
>: >obstacles), and on the order of 12-14ms (.012 - .014 seconds) with randomly
>: >generated terrain. This is on a P-133 in a pure "test bed" mode, so I'm not
>: >doing anything other than fighting the standard Win-95 overhead. You
>: >didn't mention what you're running on.
>
> For testing I always start in the upper left-hand corner (1,1) and
>run down to the lower right-hand corner (50,50). The terrain was
>randomly generated with the rand() function, scaled down to return values
>from 0-10. Anything 0 or 10 was set to INFINITY (i.e., impassable).
Okay. I've been fiddling with my ants a bit more. They're still buggy,
so I am not releasing any code just net.
As some other poster mentioned, one way to optimize them was not to have
them all copying their ancestors stack, which means copying your parent's
stack when you are created (a time consuming operation), but instead to
keep a pointer to your parent and the location in the parent stack
(which stores the path the parent travelled), and remember where in the
stack you 'branched off' the parent.
This works, but involves some tricky reference counting, and it's not
perfect yet. I get times between 0.01 and 0.02 seconds (I can't seem
to time more accurate than a microsecond in linux) now, quite decent.
(this on a 50x50 map, start and goal randomly selected).
Memory use is 5-7 K to store all the ants now, though, I think.
This all still on my 486/100Mhz.
I also came up with an alternative solution, which is also still not
perfect. :)
But, as mentioned before, strange bugs still exist. Also, the weird
phenomenon resulting from my decision to limit steps to N, S, W, E occurs:
S-
|
-
|
G
(path of length 4 between S and G) is as long as:
S - -
|
|
G
This leads to counter intuitive results.
If I had included NE, NW, SE and SW as steps too, more natural paths would
occur..
>: > I urge you to allow me to post it on my AI Software Solutions Page
>: >(see address below). Pathing algorithms appear to be by far the most
>: >popular type of post! ;)
>
>: Coincidentally enough :), I checked it out today. Sure, I'd love to have
>: it posted there.
>
>
> Cool! I look forward to seeing it.
Okay, it might take a week or two, as I should be doing other stuff..
>: I'll work on non-pathing algorithms next. Any things which are in
>: particularly high demand?
>
>
> I haven't had any good line-of-sight algorithms submitted yet.
>That could be useful.
Okay. Hey, ants could do that too! :)
DrmWeaver2
In article <4ofdv7$3...@laurel.stud.phil.ruu.nl>, faa...@phil.ruu.nl
(Martijn Faassen) writes:
>In article <4o7bqb$4...@tribune.concentric.net>,
>Steven Woodcock <Swoo...@cris.com> wrote:
>>Martijn Faassen (faa...@phil.ruu.nl) opined thusly:
>>: In article <4o5vgr$f...@tribune.concentric.net>,
>>: Steven Woodcock <Swoo...@cris.com> wrote:
looks like "he said, she said" to me.....
just a laugh.. sorry
Bjorn Reese
Richard Wesson wrote:
>
> Keep track of the time tick and every time an ant steps on a new square,
> 'stamp' that square with the current time tick. When one ant reaches
> the destination, you can find the shortest path back to the start by
> starting at the end and always going to the square with the smallest
> time stamp.
This is (almost) the "Wavefront expansion" described in "Robot Motion
Planning" by Jean-Clauede Latombe (ISBN: 0-7923-9129-2)
--
Bjorn Reese Email: bre...@imada.ou.dk
Odense University, Denmark URL: http://www.imada.ou.dk/~breese
"It's getting late in the game to show any pride or shame" - Marillion
Bjorn Reese
Martijn Faassen wrote:
>
> It's not heuristic at all, indeed. Like I said, it's probably done
> long before I did it (by Dijkstra), but it's interesting trying to figure
> this out for myself.
I definitely agree. I've also been reinventing this wheel. While
designing the framework for a distributed strategy game, I was trying
to find the shortest path between two servers in a complex web of
servers. So I ended up with a kind of dammed flooding routing, and
ants (although I called them "pathfinder") to record the "road".
Jeff
Hi,
I am writing a Cluedo program for my coursework. I am looking for an
algorithm for my computer players to win the game. Can anyone suggest a
good algorithm to me or is there anywhere I can look for one?
Thanx a lot!
Glen Barnett
US readers note that in the US Cluedo is called "Clue".
Jeff, why not post a basic outline of how the game works; I last played
it a quarter of a century ago, when I was about 8.
Glen