# Mathematically predicting object motion

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

## 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 on other sites
http://www.realtimecollisiondetection.net/

That's the companion site for the excellent book of the same name.

##### Share on other sites
I would greatly recommend Ian Millington's book in AI: Artificial Intelligence for Games.

Hope this helps!

Atef Hashem

##### 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 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 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

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633695
• Total Posts
3013375
×