Sign in to follow this  

Mathematically predicting object motion

This topic is 3724 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'm currently researching, for a university project, current collision detection and AI pathing algorithms and thinking about developing an engine that will calculate paths for objects so that they dont collide (if they dont have to) and only test for collision between paths on creation. My questions are: - Could anyone redirect me to any sites that talk about collision detection/AI pathing algorithms, similar to the above if possible. - Would there be any advantages or use to the above method. Thanks for any replies.

Share this post


Link to post
Share on other sites
I think I have already taken that book out from the library, and it has a lot of useful information.

I was just wondering whether or not there is any documentation on creating paths for each object, and on creation of the path it is tested for collision, and this is the only test done for that object until it creates a new path.

Share this post


Link to post
Share on other sites
Well, that's pretty much how all classical pathfinding works. You find a path which doesn't intersect any obstacles, and then you use that path. You wouldn't really call it "collision detection", because you are producing a collision-free path as opposed to producing a path, checking for collisions along the way, and resolving them. Of course, this "only look for obstacles at the beginning" strategy fails in worlds where obstacles change.

Share this post


Link to post
Share on other sites
I've recently implemented such a system. It's pretty straightforward; the hardest part is simply designing the right data structures to make it work and make it work fast. I took some basic inspiration from a paper you can find on the net that describes "cooperative pathfinding," although my system ended up being quite a bit more sophisticated.

First and foremost, you need a robust method for determining the answer to this question: "Will object A, in motion, ever collide with another object during specific time interval X?". As long as you keep track of each object's path, velocity, etc., you should be able to predict precisely where an object will be at any given time in the future. Given that information, you can then determine if two objects will collide and the moment in time that they do so (if at all).

Next, when formulating a new path, you need to consider all other existing paths using the system described above, and reject nodes that cause collisions. This can easily be done with something like A*, for instance, by implementing a custom predicate that determines whether or not an edge can be taken between 2 nodes. As new paths are formed or old paths expire (or are canceled), they need to be registered/unregistered with the code that predicts the collisions. Once all that is done, you get objects that pathfind nicely while avoiding each other.

EDIT: I forgot to mention that you probably want to treat your objects as something simple like circles/spheres, as this really simplifies the collision detection.

EDIT EDIT: Just found a link to another "cooperative pathfinding" paper that I had never read before: http://www.cs.ualberta.ca/~silver/research/publications/files/cooperative-aiwisdom.pdf

Share this post


Link to post
Share on other sites

This topic is 3724 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this