Pathfinding through four dimensional data

Question

The problem is finding an optimal route for a plane through four dimensional winds (winds at differing heights and that change as you travel (predicative wind model)).

I've used the traditional A* search algorithm and hacked it to get it to work in 3 dimensions and with wind vectors.

It works in a lot the cases but is extremely slow (im dealing with huge amounts of data nodes) and doesnt work for some edge cases.

I feel like I've got it working "well" but its feels very hacked together.

Is there a better more efficient way for path finding through data like this (maybe a genetic algorithm or neural network), or something I havent even considered? Maybe fluid dynamics? I dont know?

Edit: further details.

Data is wind vectors (direction, magnitude). Data is spaced 15x15km at 25 different elevation levels.

By "doesnt always work" I mean it will pick a stupid path for an aircraft because the path weight is the same as another path. Its fine for path finding but sub-optimal for a plane.

I take many things into account for each node change:

• Cost of elevation over descending.
• Wind resistance.
• Ignoring nodes with too high of a resistance.
• Cost of diagonal tavel vs straight etc.

I use euclidean distance as my heuristic or H value. I use various factors for my weight or G value (the list above).

Thanks!

Answer 1

You can always have a trade off of time-optimilaity by using a weighted A*.

Weighted A* [or A* epsilon], is expected to find a path faster then A*, but the path won't be optimal [However, it gives you a bound on its optimality, as a paremeter of your epsilon/weight].

Answer 2

A* isn't advertised to be the fastest search algorithm; it does guarantee that the first solution it finds will be the best (assuming you provide an admissible heuristic). If yours isn't working for some cases, then something is wrong with some aspect of your implementation (maybe w/ the mechanics of A*, maybe the domain-specific stuff; given you haven't provided any details, can't say more than that).

If it is too slow, you might want to reconsider the heuristic you are using.

If you don't need an optimal solution, then some other technique might be more appropriate. Again, given how little you have provided about the problem, hard to say more than that.