I'm a newbie to A* and I've read over a number of explanations and tutorials, and I was going to implement it in a small experiment but I've run into a problem. Most explanations deal with just A* and and one agent, but not A* within a program or multiple agents and multiple pathfinding at the same time. If I run one lengthly while loop in an A* function for each agent, clearly that'll not go well with the main game loop or any other agent in the program for that matter. So I would suppose that the solution is to break up the A* function into steps so that the game loop is able to continue normally and other agents also using the A* function don't have to wait. My problem is that I have no idea how to do this at all and I haven't found any A* tutorials that have dealt with how one implements A* with a gameloop, or how to break A* up (if that is the actual solution).

do it in a parallel thread? that way you won't have to break up or rework the algorithm..

There is a good article on this in Game Programming Wisdom. Run a short-and-cheap version at the beginning of the pathfinding, in the "main" loop, just to point you in the right direction so that the AI can start moving right now. At the same time, launch the lengthy, optimal A* loop in a parallel thread. When the A* loop finishes, just switch the paths.

Dont be afraid of multithreading, its invaluable in AI. But do learn to use it properly.

If you want to check out a program I wrote that has three vehicles heading towards one goal check out my webpage: http://www.adamwlarson.com/downloads3.html

It works really well and fast, what I did was step through one step of the A* at a time for each agent instead of waiting for a path to be found. So here is my main Find Path function.


What I did in my update part was this:


To search the path I use an OrderedLinkedList that I created for my Node structure. Then I use an STL stack to traverse back that way the path is stored in the correct order. Try out my program and use the map editor, by left and right clicking with the mouse. You shouldn't see any slow down at all and all enemies seem to move at the exact same time without bogging down the game loop.

I tried the separate thread methood, and I got great results!

Path objects have 3 modes: (waiting_for_path / has_path / idle),
so when you ask "it" for a path, it adds itselfe and the goal to a need_path queue, which is operated by a separate pathfinder thread. When the path is calculated, the mode is changed, and the unit starts to move in the next frame.
so ill guess you could call it an async A* :-)

I could do 50 searches in a 64*64 world whitout delaying longer then any regular RTS, but the best part is that the game dont slow down, and everything felt smooth... (most RTS wait up to 500ms from command is given until they start to walk, mostly because of network lag, if you start a "starting to move" animation right away, nobody will notice the real delay, playing an "afirmative"/"yes sir" sound clip is another common trick to hide the delay, and it realy works)

-Anders

p.s: 500ms is alot of time to calculate A*, 100ms should be ok for 50 paths... In large maps you optimize and add higher level nodes, so that no 512*512 search is needed.

uncutno;

How did you do your queue'ing?
I'm trying to implement what you speak of, but since I'm using stl::list objects I kinda puzzled...




Above is the code that somewhat works, but not quite.
Path's are calculated - but the final PathPackage->Path gets lost somewhere...

Any clues/tips?

Ok, you should not recreate a thread every time you want a new path to be found, have one thread running, and sleep/wait it if it got nothing to do...

My structure was like this:

Unit{    Coordinate position;    Coordinate nextnode;    Path path{        List nodes;        boolean hasNextNode();        Coordinate popNextNode();    }}

so whenever the position equals the nextnode, the unit tries to pop the next node from the Path object. If there is no next node it waits. This means that to move a unit the units path needs to contain nodes! (to keep it from moving, keep the list empty). By doing it this way, the Unit wil always end up at a node, even if the Path is recalculated when it is between....

whenever you want to give the unit a new path, you simply clear its path nodes, and then pass the Path object to the PathfinderThread. When the pathfinder thread has found the path, if delivers all the nodes to the path (with some mutex locking), and in the next frame, the unit will discover that it have a path, and will start to follow it.

By making the unit a slave to its Path, the only thing you need to touch is the path object, the unit movement is automatic...

Now the PathfinderThread:
I use a simple producer consumer pattern for this one. The PathfinderThread is running from start, and sleeps/waits if it got nothing to do. Whenever it gets a Path object into its queue (from the unit or the unit controller), it calculates the path, deliver all the nodes to the Path object, and then forgets about it. Since the Path object is owned by the Unit It just calculates it, and fills in the result which the unit discovers the next frame.

This could give you problems whenever you delete a Unit, while its path is calculated. To solve this, you could have a PathPool, where you store unused Paths. By having a pool, you dont need to realocate memory every time a new Path/Unit is created, and the Path object will never be deleted.

So what happend when you give a move command to a unit?
1.The Path nodes is deleted (so that the unit isnt going to move)
2.The Path is passed to the PathfinderThread
3.While the Path is calculated, the unit dont move since it dont have any new nodes in its Path
4.The PathfinderThread finished and delivers all nodes to Path object. The Pathfinder then forgets about the Path object and starts with its next task
5.Suddently the Unit got new nodes in its Path, and it starts to move in the next frame.

Since calculating a path dont take a long time, you dont need to handle special cases. Never try to cancel a Path beeing calculated in the middle. Let everything you give to the PathfinderThread be finished, and solve delay problems (like a new command before the old one is finished) by just adding the new command to the PathfinderThreads queue...
Also: Try to touch the Path object as little as possible so that the two threads dont wait for each other... Let the PathfinderThread calculate the new nodes in its own memory, and only use the popNode to get them...

Hope this helps :-) It got longer then planned

Hi!

I've implemented almost the exact thing that you described, it works great!
Right now I'm doing stress-tests with ~500 units on 6400 nodes and everything feels silky. Note that this is a grid-free solution so nodes should only define trouble-areas - it's overkill to use this many nodes. ;)

Problems:
I got one problem, it's that I havn't solved the "push-into-queue" problem yet, so I need a fixed array of units that want pathfinding - and I loop through these each frame. I only allow one pathfinding at a time thou.

Another problem is that when doing a LOT of pathfinding simultaniously something in my code produces short ( < 10 ms) stops every hundred unit or so - probably due to memory allocation or FindClosestNode... The first is easily solved by putting a Sleep(MaxTimeNeededForAPath) in between the different pathfind calls.
And the second could be solved by using octrees.

My biggest timeculprit is probably the CanSee(node) function... since this needs to loop through all nodes to find links between nodes. This can also be solved by using octrees.

No user complains about not having their units move at the EXACT same time, and if they do - simply begin moving in the target direction!

I'm quite happy with my current version thou:
Node-based, means true 3D and grid-free, pathfinding with an "endless" number of units at the same time. :D

Numerous optimizations remain thou, like: Not using sqrt for distance calc's, octree's for FindClosestNode.

If anyone want a peak at my rather messy, un-commented code, let me know!