CODEWITHSUNDEEP
path-findinga-star
Tommynem
Tommynem

Reputation: 31

Pathfinding to a moving target

Working on a recent project I wondered how to find a good/perfect path to a target that is moving with a steady speed. I tried standart A* pathfinding but it failed, since the heuristic will be wrong the more the object moves and I just can´t find a way to make that work for me. Maybe you guys got another algorith that should work with just fine or some calculation tuning with A* that would work...

Thanks for your afford :)

Upvotes: 3

Views: 2649

Answers (2)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

A* should in general work, but then of course you need to recalculate every time the target moves. For 99% of cases, this is actually ok. For example, in video games you can get away with only recalculating the best path once every second or so, so it's generally not a huge performance hit.

However, if you really need something more powerful, check out Generalized Adaptive A*, an algorithm specifically designed to handle moving targets. And if you really want to be on the bleeding-edge, there are multiple adaptations of GAA* that are faster in certain cases - see this post (under "moving target points") for more details.

Upvotes: 3

Matthew Page
Matthew Page

Reputation: 756

Using A* with a moving target is ok, but you must recalculate the whole path again. I don't think A* likes just having it's destination / goal changed.

Your A* needs to be very well optimised to run in real time and recalculate the new path every time the target moves.

Remember to play with your H to get a balance between working out the shortest path and the quickest to calculate. All depends on your map and obstructions really.

However A* may not be the best path finder for your application, but I'd need to see your map and more info..

Upvotes: 0

Related Questions