3D Pathfinding AI algorithm recommendation and analysis

Question

I am trying to solve the following problem: I have a 2D tiled game which consists in airplanes flying in the airspace, trying to land in the nearest airport (there can be 'n' goals). The idea is making the planes search for the best path by themselves, avoiding colisions.

So I was going to try the A* algorithm, but then I found this other restriction: The planes can change their altitude if they need to. So I had the idea to implement the same philosophy of A*, but in 3D (of expanding nodes to the possible moves, letting the plane move also up, down, down-north, up-east, etc., making an abstract 3D to handle a relative altitude, and thus letting the algorithm find the best path with 3D moves).

About the heuristics, I discarded the manhattan dinstance because I wanted the algorithm to be more efficient (because you know a good heuristic makes a more efficient search, manhattan overstimates the cost, and I am using diagonal moves), so I decided to implement the diagonal distance (which combines aspects from both manhattan and euclidean), recommended to 8-adjacencies (expanding nodes also in diagonal moves). But I have a lot more adjacencies, so I was trying to adapt the diagonal distance formulas to 16-adjacencies (excluding the up and down diagonals like up-northeast, down-sowthwest, and so on), so the manhattan estimate for every 'diagonal move' (except those I mention) has the same cost value (1 diagonal move = 2 ortogonal moves, not 3 as it'd be in the "up and down diagonals" I have excluded), and with that the formulas for this heuristic were generalized like this:

Let node A be the start, and B the goal, and their respective locations be (xa,ya,za) and (xb,yb,zb)

numberOfDiagonalSteps = min{|xa-xb|,|ya-yb|,|za-zb|}

manhattanDistance = |xa-xb| + |ya-yb| + |za-zb|

numberOfStraightSteps = manhattanDistance - 2*numberOfDiagonalSteps

And assuming diagonal steps cost sqrt(3) (you know, Pythagoras, having ortogonal costing 1):

The heuristic is: h(n) = numberOfStraightSteps + sqrt(3)*numberOfDiagonalSteps

Well... one of my questions is that, as planes are moving ("obstacle nodes"), the algorithm has to be refreshing, re-executing, so, what do you recommend me to do best? I mean... is it better to try it like that, or better try to implement the D*-Lite?

And my other question is about time complexity. It is clear that the worst case for these algorithms is exponential, but it can be really improved from a good heuristic. But I don't find how the algorithm in my problem can be precisely analyzed. What time complexity can I give to that algorithm, or what do you suggest me to do in my case?

Thank you for your attention.

Answer 1

I would use simple map filling see:

• http://en.wikipedia.org/wiki/Dijkstra's_algorithm
• https://www.allegro.cc/forums/thread/599046

but the map will have more layers (flight altitudes). There can be just few of them (to limit time/memory wasting) for example 8 layers should be enough for up to 128 airplanes.

Of course it depends on 2D map area size and also after filling the map just take the shortest path from it. In filling the map consider any plane as obstacle (with some border around for safety). In this algorithm you can very simply add fuel consumption criteria or any other.

Also airfield selection can be very simple by this (first wants first gets the closest one). You have to have map for each airplane in time of decision (or refiling the same one for each plane separately). Do not need to be the whole map ... just the area between destination and plane

If you have to obey air traffic regulations then you need to apply flight plans + ad hoc scheduling instead. That is not an easy task (took me almost half a year to code it) and also the air traffic control is a bit complex especially the waiting ques in air and field sharing on the ground. All must by dynamically changeable (weather,waits,technical/political or security issues,...) but I strongly doubt this is the case so simple map filling above should do :)