Jump to content
  • Advertisement
Sign in to follow this  
Stephen R

Navigating in space

This topic is 4845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I have quite a question on my hands and very little experience with either AI or pathfinding outside of A*. I have an artibtrary 2d universe where space ships fly around objects like moons and planets under the influence of gravity. What I need is some way of letting the computer controlled ships make a path to their next waypoint, taking the effects of gravity into account (hopefully even using them to its advantage) and avoiding any obsticales that might be in their way. I'm quite lost as to where to start writing this. If anyone could recommend any techniques, or if there are any sites which would be usefull, I'd be really appreciative. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Hi,

I've never worked on such a project, so this is just a wild guess, but eh, it might help you :)

I guess if each "big objects" have a gravity that affects entities around them, A* won't be useful as you scene will change quite often... (I might not be visualizing your problem correctly though)

Since its in space, I guess you wont have any "dead ends", so having a pathfinder might not be necessary. You might want to try to write a custom steering behavior that uses gravity as an input, and have all your entities purely move with steering behaviors, avoiding other objects and using gravity as a "boost".

Craig W Reynolds has an example of following a flow field... this might be a starting point?

Hope this helps

Eric

Share this post


Link to post
Share on other sites
Thanks, I kind of figured that A* would be of little use to me in this situation, but the flow field is very interesting. A kind of flow field created from the gravity info would mean that the ships could move around, taking gravity into account. Then all I have to do is make a way of plotting a course between two points and the ships should be able to follow it relatively easilly. Take into account collision avoision and that should be most of their functionallity in place.

Thanks a million, thats just what I needed.

Share this post


Link to post
Share on other sites
Well, you could do what NASA does with their mission planning....

Basically, do gravity slingshots from one gravity point (planet) to another, until you get to the planet closest to your target. Of course, this is not considering that there may be obstacles in between planets, but its a start. Also, slingshoting from one planet to another in a greedy fashion may actually be more energy efficient in the long run, maybe.

If only I could do free hand drawinggs here, I'd draw you a picture, but basically, it involves alot of tangents and orbits.

Share this post


Link to post
Share on other sites
This is not quite a pathfinding problem in the traditional sense. Navigation in a solar system with real gravity is annoying. Google for "spacecraft launch windows", "transfer orbits", "Hohmann transfer orbit" and similar terms to get an idea of how it works in real life. Basically there's a strategy for minimizing the amount of energy used (by using "transfer orbits", but the tradeoff is that you can only launch during relatively short time periods (the "launch windows") that don't occur very often (they depend on the relative phases and periods of the planets involved).

Share this post


Link to post
Share on other sites
And if you're going to use real gravity, here's a system that isn't completely realistic but will probably make life simpler: when travelling within the immediate vicinity of one planet (ie between it and its moons), treat the planet as the only significant source of gravity (ignore its moons). When travelling between planets treat the central star as the the only signficant source (ignore the planets).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you dont want optimal, or close to optimal, but instead just want a method that WILL lead to the destination under realistic space physics then you can use a little predictive navigation. This doesnt include obstacle avoidance but thats actualy a minor issue (a special case)

Consider where the source ship will be after T seconds, where T is a unit of time that is larger than the ship would need to decelerate to a full stop. Fine tuning will be needed based on the thrusting capability of the ship.

Now, In the 1D case we can assume only two options for the ship. Accelerate (positive thrust) or Decelerate (negative thrust).

If after T seconds, the ship will blow past the destination, then it needs to decelerate. If it wont yet reach the destination after T seconds, then its free to accelerate (far away from target) or coast along (near the target.)

If you play around with this simple system in 1D, you will see that your ship in a 1D universe will very nicely cruise up to the destination and decelerate to a stop just as it reaches the desination and it doesnt matter how long it takes to decelerate as long as your predictive timestep T is as large or larger.

Taking this to the 2D case, now we also have to deal with angle of thrust. But we can apply the same princple to angles as well. We can apply the thrust in a bearing to the left or the right of the target in order to adjust the ships velocity bearing. By considering again where the ship will be at time T, we can tell if we are going too far left or too far right of the target and can act accordingly.

And for those seriously accurate physics, we might have to deal with how fast the ship can rotate. This too can apply the same predictive method. If after time T we will be blow past the desired angle, we can apply negative rotational thrust, otherwise we can apply positive rotational thrust or simply let the rotation continue as is.

In each case, the time unit T will need to be based off how long it would take the property we are predicting to come to a full stop given full thrusting. it doesnt have to be perfect, but it does have to be larger.

- Rockoon (Joseph Koss)


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!