Searching idea for Space Shortest path to target Algorithm

While on a earth, maze based game yu can always use a shortest way to node algorithm(A* , for a space game this obivously does not work, as a ship can fly everywhere except where are other objects.



If I would use a naive approach and just have every x mters a node in empty space, the resould would be a few millions nodes, so this is not the best idea.



Basically I need a way to navigate from one Vector3f to another Vector3f, for simlication lets assume all other objects are static and sphere shaped, we know the radius and the center of each.



My first approch here is that I do a rayceck to the destiantion from the start, and check if I intersect a sphere, if I do I add a midway point a bit outside of the sphere and do the way in two steps then. I repeat this untill I get a way without intersections.



While this does work pretty well for most simple cases, it does not always work out (There are cases where the corrected points always lead to a next collision no matter what I do) Also if it work and finds a way, it is sometimes not the best one possible. (There are clearely shorter path, but the correction points lead to (opposite of shortcut) (Can’t find a good english word)



Also this algorithm has the problem, that all data has t be calculated on demand, and cannot do any preprocessing and just use fast lookups later.



If anyone has ideas on how to improve this or knwos/finds a better algorithm to navigate in space It would really help me :slight_smile:

Don’t know if that may be useful, Potential Fields Pathfinding.

http://www.gamedev.net/reference/articles/article1125.asp

Interesting problem. Unfortunately i don’t have time to ponder about it right now, but there should be plenty of material on the net considering the amount of space games there are.



Just a quick idea to get rid of the detour (opposite of short cut :wink: ) problem:

If you use spheres for your collision check, you can get the delta vector from the center of the object to the collision point and place the midway point in the opposite direction from the object center.

You could still use “tiles” but you dont have to save them in memory. I’d do it similar to the way you proposed. When a ship is supposed to move to a position, you simply do the A* thing, but you create each “Tile” on the fly. Meaning for the first step you check every quadrant around you if its free and add “the best” to your list, then from that next quadrant you do the same. This way you only create data on the fly and dont have to save your whole space as a 2d array. I was doing the same for Scalaxy and it worked pretty well.