• Advertisement

Archived

This topic is now archived and is closed to further replies.

pathfinding in space problem

This topic is 5093 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

I''m currently programming a game involving ships moving through space, with variables for motion including rotational acceleration and velocity, as well as normal acceleration and velocity. I haven''t been able to figure out the math involved with charting a path between two points involving these factors. Since I''m going for more realistic physics, the ship will also have to turn around and accelerate in the opposite direction of its current velocity in order to stop. Since that turning around also involves accelerating (and then stopping) rotation, the equation seems to get pretty complicated pretty quickly. can anyone think of a reasonable way to figure this out?

Share this post


Link to post
Share on other sites
Advertisement
i know what youre talking about, and it seems to me the solution isnt easy indeed. that is, if youre looking for the very shortest path. i think doing some sort of feedback system would give pretty nice results aswell, ie just evalute the current conditions each frame and apply a somewhat reasonable reaction to it. this shoud give not too shabby results, since its basicly what humans do aswell.

Share this post


Link to post
Share on other sites
Have a look at Rapidly-exploring Random Trees (RRTs). They allow taking into account differential constraints like what you need.

http://citeseer.nj.nec.com/rd/65862727%2C407332%2C1%2C0.25%2CDownload/http://citeseer.nj.nec.com/cache/papers/cs/19942/http:zSzzSzgerms.cs.iastate.eduzSzpaperszSzwafr00.pdf/lavalle00rapidlyexploring.pdf

Share this post


Link to post
Share on other sites
i think there was a contest with a situation similiar to this in 2D recently.

One of the winners used A* with some obscure hacks to try to solve the puzzles. Unfortunately, he had some big iron dual Xenon machines running the algo and they took awhile to do it. However, these were also complicated courses. something simple with wide open spaces like space should be faster, especially if you don''t care too much about getting the BEST route possible, just good enough.

Ah, here it is I was talking about the first prize winner. Basically each pixel point was a node, and the possible branches from that node were not the adjacent pixels, like you would with a normal A* algorithm, but instead the possible actions you could take, like rotate left/right/down/up, and accelerate. You can make the algorithm faster by making the space between "pixels" bigger.

Share this post


Link to post
Share on other sites

  • Advertisement