Hey Jeremy, I'm currently trying to implement a collision prediction & resolution system in 2D, much like there [is/should be!] be for aeroplanes. Just to clarify, I'm not talking about collision detection to detect when things have already crashed into each other.. I'm trying to make something that will predict and avoid these crashes altogether :) Basically, given a few point objects that are flying through 2D space, I want an object to be able to look at its own velocity, and other object's velocities (and maybe their acceleration too), and be able to predict if they are about to collide, and then avoid a collision by changing velocity (ie speed or direction). The twist is that the other objects will be doing the same thing, so I have to avoid the case where both objects will swerve to avoid each other, but then crash on their new path. In reality my objects will preferably change speed rather than direction, but the principle's the same. I've been Googling for technical reports on aircraft systems to no avail. I know what a Markov chain is, if that's any help. If anybody has experience in this or even just has an idea to get me started, that'd be great. Sorry if my post is a bit long. Thanks!

Who is Jeremy?

It's probably not as difficult a problem as it might seem. Prediction is pretty trivial and then you can perform collision detection on those predictions. A 2D object moving in a straight line will have a roughly rectangular predicted path, its width based on the object and its length based on the object's velocity and the timescale.

When it comes to corrective behaviour, there are a few simple things you can do. You might try a quick search of several different evasion techniques to see which produces predicted paths with no collisions. Such techniques might simply come down to 'steer left', 'steer right', 'slow down', 'speed up', and the other 4 combinations of those. Maybe there are more formal solutions but I don't know if they are necessary for non-critical systems.

Think fast! Two cars are headed straight for a head on colision. They both swerve right. Do they still crash?

Some people's gut reaction tends to be "yes, they both turned the same way and hit each other" but if you think for a second, you realize that since they are facing opposite directions "Right" is also in opposite directions.

Ok, I know this example may seem very stupid and that very few people would have said "yes," but it helps to illistrate a very important point.. Even though a problem may seem complex, a simple solution using just a single, or couple small rules often solves the problem perfectly.

For the airplane problem, having them change altitude (randomly assigning which plane rises or falls) and possibly vearly slightly off course should work wonders and depending what exactly you are doing should also be a good approximation of real traffic control.

Quote: Original post by Drakonite
Think fast! Two cars are headed straight for a head on colision. They both swerve right. Do they still crash?

I know what you mean Drakonite. In an air traffic control situation this wouldn't really be a problem, as the decisions are centrally coordinated and both can be instructed with knowledge of what the other is doing.

However in the car situation, if one steers right and one steers left, then they probably will crash, and they don't have the time to phone each other up and ask which way the other one's about the swerve. Similarly, one car could slow down so that the other car passes over its future path, but if the other car slowed down in the same way they'd still crash, only slower. So one of them has to take the initiative, but there has to be some way of choosing the option with the least risk, when neither car knows what action the other is going to take.

PS I don't know what the "hey jeremy" was for, just messing around :)

Craig Raynolds' steering behaviours is pretty much tou are looking for: http://www.red3d.com/cwr/steer/

There's tons of other interesting stuff relating ot the issue on his site.

You should fallback to traditional geometric collisions, but instead of a bouding box arround the airplane, you should use an hemisphere, which changes size based on the airplane's altitude, attitude and speed.

An hemisphere because the airplane cant possbly collide with anything behind him, and he can change attitude in any XY axis, which multiplied by its speed, makes an hemisphere, if you can picture it.

The hemisphere will be large enough for the airplane to have 5 minutes to avoid collision with other hemispheres, so the radius can be calculated by the airplane's speed, multiplied by the amount of warning time we want, 5 minutes.

So, if the airplane travels at 600Km/h, and we want a 5 minute warning time, thats a 50Km radius for the hemisphere, which may seem large, but you are working in 3D, so you can instruct planes to go into higher/lower division planes.

You can also build "3D vapor structures" arround airports.

Imagine one of those buildings used to park cars, with multiple stories. The car has to navigate a certain path to get from ground floor to floor 10.

Thats what your airplanes have to do in an aproach vector. They have to go into a waiting stack, then into an aproach vector, and finally land. There are as much aproach vectors as there are runways, so...

That's what i could come up with from the top of my head...

Quote: Original post by memon
Craig Raynolds' steering behaviours is pretty much tou are looking for: http://www.red3d.com/cwr/steer/

There's tons of other interesting stuff relating ot the issue on his site.

That's a really good site and actually what gave me the original inspiration for this project :) I'll check it out again in case there's something handy I missed out.

Yes, these guys seem to be avoiding crashes pretty well.
http://www.red3d.com/cwr/steer/Unaligned.html

What you said was helpful, Prozak, some interesting ideas about the hemisphere and stuff.

Thanks all

With planes, you have a REALLY helpful attribute to make all these calculations much simpler: Location (from GPS or the like).

Using the location attribute, you can do something like make the 'lower left' plane slow down while the 'upper right' plane does not, and things like that. If you're using an actual globe, then instead of 'lower left' it might be 'southeastern most' or somesuch.

This way you automatically have a way to distinguish between planes in a deterministic way and always have one perform one action and the other do another action.

Also, you could do '1 pass' on all the planes to calculate the changes and instead of directly implementing them, have them run the tests again using the changes calculated from the first 'pass'. This could be acomplished in real life by having some kind of transmitter on each so that the planes themselves would be in constant communication (probably via radia. You'd need some good error correction and the like, and you'd have to allow for lack of communication in extreme circumstances).

Quote: Original post by Extrarius
you'd have to allow for lack of communication in extreme circumstances

In my system there is no communication between vehicles, so it's always an extreme circumstance! They're meant to be cars and the time to a potential collision will generally be in the range of 1 second or so. So I was wondering if there was some uncertainty algorithm, to at least maximise the chance of not crashing?

I just remembered that I learnt some stuff on Game Theory, can anybody else remember anything relevant to that? Like the Prisoner's Dilemma where neither prisoner knows whether the other one's going to confess and they have to choose a strategy to maximise their chance of getting set free.

Quote: Original post by memon
Craig Raynolds' steering behaviours is pretty much tou are looking for: http://www.red3d.com/cwr/steer/

There's tons of other interesting stuff relating ot the issue on his site.

I second this motion.