Jump to content
  • Advertisement
Sign in to follow this  

Fast automatic path prediction/visibility validation in an arbitrarily complex force-driven environment

This topic is 1093 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 know the topic is a mouthful, but so is the problem.


First off, I'd like to mention that I'm just fishing for ideas. So far I haven't been able to come up with any worthwhile method to tackle this - at least not on my own. That being said, this really is an optional problem, but it's one of those nice features I'd love to have. I only need to solve this in 2D, but I do need to do it in realtime or very close to realtime (~10 FPS would be okay) and I need it to be robust (eg no performance spikes).


The problem: suppose you have an environment with a static set of force emitters. For simplicity's sake suppose they're all spherical (circular, that is) and uniformly attractive. In short, suppose you have a bunch of planets. You also have an arbitrary starting point A and an end point B, and you need to automatically orient a nozzle at A so that if you fire a projectile from it traveling at uniform speed (the projectile's velocity cannot change), it will hit B.




In addition to that, I also need to determine if no such orientation exists (essentially turning this into a kind of a "visibility" test, which does ideally need to be more responsive than 10 FPS).


Since both  the number of planets and A-B pairs can be arbitrary (the pairs are not dependent on each other), I reckon the term that applies here is a form of N-body simulation. In reality the number of planets is up to 4 and the number of A-B pairs is generally less than 5. I'm very  vague on the related math, but I don't think there's any form of generic analytical solution for what I need.


I've therefore been thinking about out of the box methods, like floodfilling and pathfinding. However, I haven't been able think of a way that would give me usable results, which can be extracted to trace the actual path from A to B in a reasonable amount of time. With floodfilling, I'd be okay with certain constraints, like limiting the size of the environment or running the test at something like quarter resolution. I couldn't imagine pathfinding being fast enough, though, as even at a lowered resolution the scene can be as large as 2000-4000 nodes square. Also, my current limitation is GL3.3, so I don't think I could offload anything to the GPU.


My gut tells me planetary mechanics should have something for this. Gravity assist comes to mind (I'm not sure about the term, though), although in my case I need to apply forces from several planets at a time.


Can anyone guide me in a meaningful direction? Or just tell me this can't be done the way I want so could get over it and move on? smile.png

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!