• Create Account

## Simple (not really) Pathfinding (yes, again)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

30 replies to this topic

### #1BeanDog  Members

1065
Like
Likes
Like

Posted 14 June 2000 - 12:16 PM

OK, I''ve been working on it, but now that I actually time the beast, I find that my method takes over 1/20 of a second per execution for about a 50-square move! This is totally unreasonable. I''ve downloaded someone''s A* demo, but it took a few seconds to do the same job. Precalculated paths would work best, but what about moving obstacles? I really like the region search idea (thanks to whoever had that one). Problem is, once again, moving obstacles. Man, I pray someone has an idea. Just out of curiosity, how do the pros do it? Does anyone know? Maybe a StarCraft or C&C programmer will read this. HEY GUYS, HOW DID YOU MAKE IT WORK THAT FAST??? For goodness sake, this wasn''t even a problem on my 486 playing WarCraft II! I REALLY wish I were on the inside with Blizzard or something ~BenDilts( void );

### #2 Anonymous Poster_Anonymous Poster_*   Guests

Likes

Posted 14 June 2000 - 12:20 PM

What sort of data structures are you using? Your numbers seem extraordinarily bad... how big is your search space?

### #3BeanDog  Members

1065
Like
Likes
Like

Posted 14 June 2000 - 02:37 PM

I am using a 256x256 grid.
It takes one function call, and about 6 data lookups and 2 small (less than 6 iterations) nested loops to see if a unit can move onto a square.
For those of you who haven''t read my other thread, my search goes straight toward the goal, and when it hits an obstacle it splits into 2, going opposite directions (clockwise vs. counterclockwise) around that and each following obstacle. After a certain # of iterations, whichever search is the closest or hits it first wins, and I save the path into my creature''s class.

~BenDilts( void );

### #4Kylotan  Moderators

6408
Like
Likes
Like

Posted 14 June 2000 - 11:12 PM

I still think A* would be better until you have a good idea of what you''re doing. If the version you used took 2 seconds, it wasn''t programmed very well. A* is used by many professionals and is not that slow.

What happens if one of your split paths hits another obstacle? Does it split again? How does it decide to stop going (counter)clockwise around an obstacle? How many separate paths do you usually end up creating each time you search?

### #5StrategicAlliance  Members

122
Like
Likes
Like

Posted 14 June 2000 - 11:36 PM

Beandog,

I mean are we talking a desert with the occasional cactus to avoid or are we talking cities with cars moving everywhere?

This can be a decisive factor in which way to go.

If there are few objects to avoid your algorithm is good, but I would consider doing this : reduce the complexity of your environment by setting waypoints. Set a waypoint on every corner of an obstacle and when the waypoints are in a direct line of sight you KNOW you can move from one point to the other. That way you won''t have to do a calculation in each grid. You can simply say when you have to get past a rectangle moving from south to north : Go to the southwest corner of the rect., then to the northwest corner, then to my goal and you''re past the object in 3 calculations instead of at least the pixelsize of the rectangle.

If you work in a dense environment, try setting random waypoints and calculate the easiest way through using Dijkstra or something. Your algorithm will then stop as soon as it finds one way, instead of trying to find the best way, speeding things up.

All the best,

******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************

### #6BeanDog  Members

1065
Like
Likes
Like

Posted 14 June 2000 - 11:38 PM

Yes, it would split again at every obstacle. Which means, for one large block, it could split over 100 times, because any time it can''t move directly toward the target, it is seen as a new obstacle. However, I keep a grid that tells me which areas have been searched through already and any search hitting it will be stopped.

I usually end up with around 15 for a complicated map, I mean 15 existing when one of them hits the end or my total iteration limit runs out.

This actually works really fast if I set the max iterations to 20, it will find the best path for the next 20 spaces that will put it closest to the goal. However, when I tell it to go for, say, up to 100, or even take all the stops out and go ''till it gets to the end, it is really slow(1/20 sec.)

You must remember I am running on a P-233MMX with 128mb RAM. It''s not the fastest machine in the world.

~BenDilts( void );

### #7MikeD  Members

158
Like
Likes
Like

Posted 14 June 2000 - 11:40 PM

I can''t help with A* optimisation (except to say, get a 1000mhz machine) but for moving obstacles you should think of path-finding on two levels, planning and reactive.
The planning layer is what you have so far, a path from start to goal node in a grid. The reactive layer deals with moving from grid to grid or within a grid (all path finding is grid based, look at AoK or TA and the units seem to be moving on a pixel by pixel level but the world is broken up into grids for path-finding use). The reactive layer could then build small local paths around moving objects which is a lot quicker than it sounds as the number of paths across a grid increases exponentially with the grid size i.e. a 10x10 grid is more than twice as quick to path build for as a 14x14 grid, which contains twice as many blocks but far more potential paths. Reactive layers could also function with different forms of path finding such as wall crawling (bumping into objects and walking along their sides in whichever direction moves you closest to the goal position) or using areas of repulsion originating from the obstacle so that the path finder will tend to take a path around the it.

Actually, considering your A* speed problem you could deal with it by breaking up the processing over several frames, stopping each path plan after X nodes have been expanded or storing common paths / path segements (small CPU overhead for calculating what is common but worth it). Remember, the majority of units will be moving as part of a group from point A to point B, so they have to deal with their own individual reactive layer but their planning layer can, within reason, be identical.

Mike

### #8BeanDog  Members

1065
Like
Likes
Like

Posted 15 June 2000 - 12:01 AM

I think I''ve got it licked.

When I do pathfinding, I just search every 2 spaces, not each and every one in the path. Chances are this will avoid all the little obstacles, and if not, it will recalculate when it hits one. This process takes only a very small fraction of the time my other way did.

Thanks for the input, guys. Any more ideas are welcome, it''s not perfect.

~BenDilts( void );

### #9Geta  Members

136
Like
Likes
Like

Posted 15 June 2000 - 03:12 AM

quote:
Original post by BeanDog

I think I''ve got it licked.

When I do pathfinding, I just search every 2 spaces, not each and every one in the path. Chances are this will avoid all the little obstacles, and if not, it will recalculate when it hits one. This process takes only a very small fraction of the time my other way did.

Thanks for the input, guys. Any more ideas are welcome, it''s not perfect.

~BenDilts( void );

From your posts in this thread, I would suspect that your Astar''s poor performance is due to implementation.

I''ve seen 50 step paths found on a 1024x1024 map in 15ms (milliseconds) on a P90 using an Astar.

Here are some optimization suggestions:

1) Make sure the Open List is fast. If you use MSVC++ then consider using the STL priority queue container, and modify it so that you can use an iterator (very easy to do) and then derive your Open List from the new priority queue. It is lightning fast!

2) Use pointers and not the actual nodes. Store your Astar flags for Open/Closed status in the map itself, and then only process using a pointer to the map node.

3) Use the Manhatten Distance for the h() of f() = g() + h().

Starcraft, Age of Empires (and Kings) and virtually every commercial RTS game I can think of use the Astar (or a variant of it). Astar is the best pathfinding algorithm when discreet cells or nodes are available (ie. forming a graph), so before you dismiss it, you may want to make sure you have a good implementation of it. Amit Patel''s web page (available via a link from www.gameai.com is an outstanding source of Astar code).

Good luck,

Eric

### #10cornmuffin  Members

122
Like
Likes
Like

Posted 18 June 2000 - 04:49 AM

hey hey, what about dijkstra for shortest path? how well does it match up against A*?

cheers,
muffin

### #11Geta  Members

136
Like
Likes
Like

Posted 18 June 2000 - 04:57 AM

quote:
Original post by cornmuffin

hey hey, what about dijkstra for shortest path? how well does it match up against A*?

cheers,
muffin

My experience with Dijkstra''s algortithm is that it is not as fast as Astar, and it is not guaranteed to find the optimum path (as Astar is when using an admissible estimate - the h() in f() = g() + h()). YMMV.

In fact, an Astar with a zero value for h() is basically the same as a Dijksta''s algorithm.

Eric

### #12StrategicAlliance  Members

122
Like
Likes
Like

Posted 18 June 2000 - 05:41 AM

I think Dijkstra always finds the optimal path since it was originally constructed as a way to find the shortest path through a weighted graph.

If you use the corners of polynomal obstacles as nodes in your graph and the distance as the weight on a link, you''ll get the shortest path with Dijkstra.

******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************

### #13Geta  Members

136
Like
Likes
Like

Posted 19 June 2000 - 02:05 AM

quote:
Original post by StrategicAlliance

I think Dijkstra always finds the optimal path since it was originally constructed as a way to find the shortest path through a weighted graph.

If you use the corners of polynomal obstacles as nodes in your graph and the distance as the weight on a link, you''ll get the shortest path with Dijkstra.

I don''t think Dijkstra''s is guaranteed to find the optimal path (although I have been known to be wrong before). I agree it can find the shortest path, but shortest is not always optimum. Especially in an application like pathfinding on a computer game map with variable terrain costs (think of a road that goes around a mountain as opposed to the path over a mountain; the road path may have overall lower terrain costs - and hence be more optimal - than the overland route directly over the mountain).

Anyway, when one uses Astar, one can simply use the estimate h() as intended (and get Astar pathfinding) or set the h() to zero and get Dijksta as needed by the game.

Eric

### #14StrategicAlliance  Members

122
Like
Likes
Like

Posted 19 June 2000 - 03:19 AM

Geta,

I might be wrong as well, so I''m definitely not saying you are, I''m just telling what I think:

Since Dijkstra is a mathematical approach to find the shortest path through a weighted graph, it will always give you the shortest route based on what you use as weights on the interconnections in the graph. So you could use distance between nodes and you would find the shortest path.
You could use travelling speed and then you would find the quickest path. That''s how we saw it in our course of Discrete Math last year, but I don''t know A* well enough to be sure that Dijkstra would always match the result of A*.

Greetz,

******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************

### #15Geta  Members

136
Like
Likes
Like

Posted 19 June 2000 - 09:57 AM

quote:
Original post by StrategicAlliance

Geta,

I might be wrong as well, so I''m definitely not saying you are, I''m just telling what I think:

Since Dijkstra is a mathematical approach to find the shortest path through a weighted graph, it will always give you the shortest route based on what you use as weights on the interconnections in the graph. So you could use distance between nodes and you would find the shortest path.
You could use travelling speed and then you would find the quickest path. That''s how we saw it in our course of Discrete Math last year, but I don''t know A* well enough to be sure that Dijkstra would always match the result of A*.

Astar is the same type of search algorithm as Dijkstra, "a mathematical approach to find the shortest path through a weighted graph". Astar evolved from an algorithm called "A" which was almost identical to the Dijkstra algorithm. That is why, it is possible for Astar to function like a Dijkstra, by only setting h() to zero.

Possibly of interest to you, is a little tool written by Bryan Stout (called PathDemo), and available in the archieves of the Game Developer Magazine here in the web (sorry I don''t know the exact URL), that visually represents a path search process for a variety of pathfinding techniques. Bryan wrote it in Delphi (or Pascal??) several years ago to support his lecture on pathfinding at the Computer Game Developers Conference. If you can locate that tool, then you may want to experiment with Astar and Dijkstra pathfinding approaches (I think both are included) and you will visually see that Astar will find the optimum path with fewer expanded nodes (hence the fastest) and it is guaranteed to always find the optimum (if the h() is admissable). You can also tweak the parameters and run Astar with h() = 0, and then run a Dijkstra over the same map, and see that with h() == 0, both algorithms will search the same way.

Anyway, I think we have beaten this horse to death, so I will conclude my part of this discussion with a parting comment; that I like both algorithms, and have used them both (in their place) in commercial games.

Eric

### #16cornmuffin  Members

122
Like
Likes
Like

Posted 19 June 2000 - 11:06 AM

so in an RTS game like starcraft, dijkstra should do well? a path is a path, no weight difference, or else unmovable. also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra? thanks.

cheers,
muffin

### #17Kylotan  Moderators

6408
Like
Likes
Like

Posted 19 June 2000 - 10:50 PM

quote:
Original post by cornmuffin

also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra

The priority queue and the graph are not interchangable, as they aren''t referring to the same parts of your program. The graph,in this case, is your map, including any passability factors. The priority queue is the effective way of storing the nodes your algorithm generates with their cost, so that when you are generating the paths you can get the next node to examine more quickly.

You don''t -need- a heap implementation of a priority queue. You can just do a linear search through an array to find the next node to use, for example. But using a heap-style priority queue speeds up this process.

### #18StrategicAlliance  Members

122
Like
Likes
Like

Posted 19 June 2000 - 10:59 PM

Geta,

Thanks for your replies to my posts! I ran the demo by Bryan Stout and I see the difference indeed.
It''s been an interesting discussion, which shows this board is a great place to hang out and learn.
Thanks!

******************************
Stefan Baert

On the day we create intelligence and consciousness, mankind becomes God.
On the day we create intelligence and consciousness, mankind becomes obsolete...
******************************

### #19Geta  Members

136
Like
Likes
Like

Posted 20 June 2000 - 04:31 AM

quote:
Original post by StrategicAlliance

Thanks for your replies to my posts! I ran the demo by Bryan Stout and I see the difference indeed.
It''s been an interesting discussion, which shows this board is a great place to hang out and learn.
Thanks!

You are welcome, and learning goes ditto for me too.

Eric

### #20Geta  Members

136
Like
Likes
Like

Posted 20 June 2000 - 04:37 AM

quote:
Original post by Kylotan

[quote] Original post by cornmuffin

also, do i need a heap priority queue, how about just a simple weighted, connected graph, for dijkstra
(end Original post by cornmuffin)

The priority queue and the graph are not interchangable, as they aren't referring to the same parts of your program. The graph,in this case, is your map, including any passability factors. The priority queue is the effective way of storing the nodes your algorithm generates with their cost, so that when you are generating the paths you can get the next node to examine more quickly.

You don't -need- a heap implementation of a priority queue. You can just do a linear search through an array to find the next node to use, for example. But using a heap-style priority queue speeds up this process.

Kylotan is absolutely right on. And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric

Edited by - Geta on June 20, 2000 11:41:27 AM

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.