21
\$\begingroup\$

I'm an absolute beginner with game development and all I know about collision avoidance/resolution, I learnt it on or through this site in the past week... so don't hesitate to correct me if what I'm asking here is based on wrong assumptions / misunderstanding. I tried of my best to be clear, but that said, the subject is still novel to me.

Vehicles

In my game, I have vehicles that move autonomously. They are placed in a 3D space, and their motion is governed by a number of variables which are different for each vehicles. The one of interest here are primarily:

  • Only forward motion.
  • A speed that can vary between min & max, but whose min is not (even close to) zero.
  • A steering radius that is dependent from the speed (the higher speed, the larger radius)
  • Two maximum accelerations (for decreasing and increasing speed)

Goal

My goal is to implement some sort of AI that will a 100% accurate collision avoidance (i.e. I will be sure that the vehicles will never ever collide).

Design

  • Although I would prefer more the idea of having the AI "onboard" (i.e. each vehicle having it's own "collision avoidance AI", eventually querying and/or sending messages to other vehicles) it is also possible for me to implement the CA AI at a central level (dispatching commands to the vehicles).
  • In most of the cases, the vehicle will simply have to steer clear of each other in any direction, but under certain circumstances, they will have to avoid collision and going towards the same target

What I found so far and where I got stuck

Within the many many links I found in other questions on this very site, I found of particular use these ones:

  1. Collision between pool balls
  2. Unalligned collision avoidance
  3. Queuing

While these three links "opened my eyes" in many ways, it is not immediately clear to me how to use that information in my case. In particular article #2 only "tries" to prevent collision (but collisions do happens time to time). While article #3 needs to stop vehicles sometimes to prevent collisions.

What I also noticed, is that the collision avoidance algorithms linked above use a "instant projection" of linear speed to check if something is on the way of the vehicle. I was wondering if this is enough in my case or if I had to project my position in a more realistic way (e.g.: If I am 60° into a steering 90° to the right, I should calculate my position for the rest of the 30° of the curve, and then assuming linear motion).

Finally, I am particularly afraid of deadlocks. In other words: although the density of vehicles in the world will be fairly low, I am worried that given a certain numbers of vehicles converging towards the same point, once they will realise they are on a collision course, any evasive manoeuvres will be impossible as it would bring the vehicle on a collision path with some other ones.

Question

How can I reach my "goal"? An in depth-explanation is of course very much appreciated, but links to external resources would also be of great help (I'm sure I'm not the first with this problem, but probably I used the wrong keywords to search the web?)

Thank you in advance for your help!

Improve this question
\$\endgroup\$
19
  • 20
    \$\begingroup\$ Have every vehicle stop. 100% avoidance achieved. \$\endgroup\$
    – Martin Sojka
    Jul 20, 2011 at 11:29
  • 2
    \$\begingroup\$ It's enough if they stop relative to each other. That is, all of them move in the exactly same direction, at exactly same speed. The bigger problem is that it's (provably) IMPOSSIBLE to achieve any algorithm which does it at 100% rate for every possible configuration. For example, consider two vehicles with very large turning radii at the minimum distance not equal to zero from each other, flying at each other with max speed. \$\endgroup\$
    – Martin Sojka
    Jul 20, 2011 at 12:37
  • 12
    \$\begingroup\$ @mac - One thing to keep in mind as you develop this algorithm is that It's A Game. If you're spending too much time trying to solve this problem, maybe you're trying to solve the wrong problem. You can cheat - move vehicles or violate their handling rules if you detect a difficult situation, especially if the player can't see it. Make sure whatever vehicle handling rules you come up with don't end up looking boring, it's more important to be entertaining than to be right. \$\endgroup\$
    – Flip
    Jul 20, 2011 at 13:16
  • 3
    \$\begingroup\$ @mac Well I would probably use a global controller with A*. I know you wanted to stay away from this solution, but it makes more sense as it has a global view of the vehicles and it can pre-calculate paths. You may also want to put a priority on vehicles (the one closest to the target gets a higher priority, so it's path remains unchanged and others re-route around it). \$\endgroup\$
    – Jonathan Connell
    Jul 20, 2011 at 13:23
  • 6
    \$\begingroup\$ @Flip A flight simulator is still considered a game, yet if you 'cheated', it would break the game for any player that realized this. \$\endgroup\$
    – Jonathan Connell
    Jul 20, 2011 at 14:17

6 Answers 6

Reset to default
5
\$\begingroup\$

Have you looked into flocking algorithms? When I look at your description that's what comes to mind for me. There's lots of articles around for this, here's one I like. Likely you won't be using all the aspects of flocking, like cohesion. Most of the aspects would be useful for what you're trying to do, like alignment and separation, both of which would help in avoiding collisions. You'd end up with something a bit different than flocking, but it should help you get started.

Good luck!

Improve this answer
\$\endgroup\$
4
  • 2
    \$\begingroup\$ The relevent search-term here is Boids. However, I don't think this is what OP was looking for - it sounds more like he wants cars going every-which way. \$\endgroup\$
    – BlueRaja - Danny Pflughoeft
    Jul 26, 2011 at 3:49
  • \$\begingroup\$ Flocking is still about the AI avoiding collision with eachother. \$\endgroup\$
    – Matt Jensen
    Jan 24, 2012 at 8:53
  • \$\begingroup\$ OP asks for reliable collision avoidance. Flocking poses no guarantees, as the force based model does not incorporate hard constraints. Although flocking is surely a good entry point to get into the topic, the answer is thus missplaced. I suggest the OP to look for "velocity obstacles" instead. \$\endgroup\$
    – Tobias Gurdan
    Jun 10, 2016 at 13:29
  • \$\begingroup\$ @TobiasGurdan If you have an answer that's more appropriate (and I agree that you do), you should create an answer. \$\endgroup\$
    – House ♦
    Jun 10, 2016 at 15:30
3
\$\begingroup\$

Here is an approach: Every vehicle has a short projected path where the vehicle in the end slows down and enters a loop, these paths may not overlap. Whenever a vehicle comes to the point where it is set to slow down you try to generate a new path that does not overlap any of the existing. If that is not found to be possible the vehicle continues on it's given path and retries making a new path periodically.

The method could be improved to allow tighter traffic by letting paths leading to loops overlap each other and loops where it can be determined that this will not cause a collision.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Have a method in each vehicle where it performs a radial search around itself, if there are any other vehicles inside this radius, move away in a fashion suitable to your liking: 1) Move in the opposite vector, 2) slow down, 3) speed up, etc.

You can even do combinations: If the other vehicle's vector is not straight ahead or directly behind: move away; else if it is straight ahead: slow down; else: speed up.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

My goal is to implement some sort of AI that will a 100% accurate collision avoidance (i.e. I will be sure that the vehicles will never ever collide).

If this were possible, it would have been put into all the world's aircraft by now.

I suggest relaxing the 'autonomous' aspect and having a function that resolves predicted collisions between 2 (or more) vehicles. It can be as naive as picking random new directions to travel in and seeing if that resolves the problem, but the important thing is that the function only returns when it's reached an agreement that suits both vehicles.

I also suggest that any vehicle that is predicted to collide in the near future reduces its speed while maintaining the same look-ahead distance - this will give your vehicles more opportunity to avoid collisions, just as in real life.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Since he's designing the rules of the universe, it's absolutely possible. The real world is obviously more complicated, but I'm sure real-world aircraft do use a ton of collision-avoidance techniques... \$\endgroup\$
    – BlueRaja - Danny Pflughoeft
    Apr 20, 2019 at 18:19
0
\$\begingroup\$

It sounds to me that crowd simulation might be the topic most relevant to what you're trying to achieve. The GAMMA group at UNC has a large body of work on the subject that might be worth looking through. Their description:

Crowd and multi-agent simulation is the process of simulating large numbers of people, creatures, or other characters, each interacting in one environment. These actors are expected to move to their goals, interact with their environment, and respond to each other. Crowd simulations have many uses, including improving architectural planning, enhancing training environments and virtual realties, and driving artificially-intelligent (AI) characters in games and movies. Our group has worked on many problems in crowd simulation, including fast, guaranteed, collision avoidance, real-time path and motion planning, crowd flows, and directed behaviors.

http://gamma.cs.unc.edu/research/crowds/

Improve this answer
\$\endgroup\$
0
-1
\$\begingroup\$

I don't think there is a 100% avoidance method, but if you vehicles possess full world informations, you could encase each vehicle into a box whose length depend on its speed, and perform collision check on those boxes. If there is indeed a collision, steer away, with a strength depending on the imminence of impact (or area of the collision between the two boxes), and slow dow (but keep your box the same length during the avoidance operation).

Obviously this won't work if the vehicles does not posses full informations, but in this case nothing will garanty a 100% avoidance (except, as already said, parallel movement)

some methods described here would probably be useful, notably this one :Unaligned Collision Avoidance steering behavior

regards

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Did you read the original question? That link you recommended is already in the question... \$\endgroup\$
    – bummzack
    Jul 26, 2011 at 14:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .