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 );

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

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 );

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?

Beandog,

How dense is your environment?

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...
******************************

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 );

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

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 );

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

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



cheers,
muffin