I'm looking for an implementation of the Anytime Dynamic A* algorithm defined in this paper. I started implementing it but am short on time and am hoping that someone would be willing to let me see/use/modify theirs. Thanks!

After four years of working on a PhD thesis in motion planning I can tell you that you're very very unlikely to find a drop-in implementation of ADA*. There are a few reasons why:

- ADA* implies some degree of concurrency. That is, the planning 'Main' function of figure 5 runs in one thread, whilst your execution and sensing/obstacle code runs in other threads. A major question is then, 'how do I efficiently update my obstacle map, without using excessive memory and avoiding concurrency bugs?'

- Like most planners described in academic publications, the focus is on describing a generic concept. A specific implementation will involve a selection of concrete data structures (priority queues, open lists, sets) that are potentially hand tweaked to be suitable for a given application.

- Finally, the pseudo-code presented in the paper, coupled with the description of the algorithm is *the* reference implementation for this type of problem. Suck it up and write some code.

Quote: Original post by XXX_Andrew_XXX
After four years of working on a PhD thesis in motion planning I can tell you that you're very very unlikely to find a drop-in implementation of ADA*. There are a few reasons why:

- ADA* implies some degree of concurrency. That is, the planning 'Main' function of figure 5 runs in one thread, whilst your execution and sensing/obstacle code runs in other threads. A major question is then, 'how do I efficiently update my obstacle map, without using excessive memory and avoiding concurrency bugs?'

- Like most planners described in academic publications, the focus is on describing a generic concept. A specific implementation will involve a selection of concrete data structures (priority queues, open lists, sets) that are potentially hand tweaked to be suitable for a given application.

- Finally, the pseudo-code presented in the paper, coupled with the description of the algorithm is *the* reference implementation for this type of problem. Suck it up and write some code.

The code doesn't need to be in a thread. Say for example it worked like this:

Class ADAStar {
//members are anything needed between iterations.
public Path findPath(Tile[][] worldTileStates) {
if this is the first run, do the first run stuff and return the first iteration of Path
else just do the part that would normally be looping forever in its own thread which may return a better Path or do a new search from scratch, depending.
}
}

This makes tons of sense to plug directly in to a game because all the game has to do is update the obstacleMap based on the new state of the world after updating everything this tick. Basically it can do the same thing it did to create it in the first place but this time when it sees something that was open and is now closed, it marks it closed like it normally would and also marks it as changed. Same goes for previous closed that are now open. Now the ADA* alg can look at edge changes. A very simple scan of the changed flag on edges to the current path will indicate which tiles need to be added to the queue for evaluation.

I think this could be very generic to work under many scenarios. I have sucked much up and written tons of code, in fact, several games worth from scratch, but in order to actually finish my games, I have to stick to my project plan and I simply ran out of time for better AI. My hopes were that someone had implemented this algorithm in an efficient manner that I could adapt to my game without multiple days of work.

The pseudo code isn't necessarily that easy to follow. The inconsistency calculation didn't make sense to me. I kept doing the math and I wasn't able to see how a state could ever be anything but under or overconsistent. I think maybe I just didn't understand that part.

I also couldn't see exactly how the algorithm was going to handle a moving goal, which was my biggest concern. That alone put this at high enough risk of not working correctly that I am not willing to gamble several days of time messing with it only to find out that it only works well on static goals.

I believe you when you say you have years of experience in the field and that most implementations of such things are highly specialized, but I'm still positive that someone somewhere has written something like this for a game that could be easily adapted to another game. If it ever gets posted, I'll try it out. If it isn't and I find time to work on the idea some more, I'll implement it and see how it works for me.

Thanks