Collision Avoidance with polygons

Quote:

I am working on a spaceship game where the environment and most objects(asteroids) are destructible. As they become damaged their geometry changes and so I need a collision avoidance method that takes into account the new polygon/shape of the object as to avoid it in the best/most efficient manner. Is anyone familiar with this sort of thing?

What first comes to mind is steering behaviors, but it's hard to say whether this would be an appropriate solution in this case without knowing more about the simulation. How are the agents represented exactly? Is movement physics-based? Is the simulation 2-d or 3-d? Can you post an example screenshot?

Sorry. Sure I can. The game is 2d, the movement is physics based(Box2D in case you're familiar with it). You apply force with a vector on a point in the object's body and that moves it, if it's on the center of mass the object will move in the vector's direction if it's not then some torque might be generated. To rotate an object you apply torque(a float).


The physical body is made up of convex polygons(In this case triangles, shown in green). This are generated from an original polygon that outlines the entire object.

http://img401.imageshack.us/img401/342/ship.jpg

Quote:

Original post by Antonym Sorry. Sure I can. The game is 2d, the movement is physics based(Box2D in case you're familiar with it). You apply force with a vector on a point in the object's body and that moves it, if it's on the center of mass the object will move in the vector's direction if it's not then some torque might be generated. To rotate an object you apply torque(a float). The physical body is made up of convex polygons(In this case triangles, shown in green). This are generated from an original polygon that outlines the entire object. http://img401.imageshack.us/img401/342/ship.jpg

Got it. Based on what you've posted, I can think of three techniques that you could use here:

1. Potential functions

Potential functions can be used for simple attractive or repulsive behaviors (it'd be the latter you'd want in this case). PFs aren't so great for helping an agent steer *around* an obstacle, but are good for simple avoidance of obstacles.

2. Steering behaviors

Steering behaviors are a commonly used and well documented means of controlling the motion of an autonomous agent. There are a few variations on the 'obstacle avoidance' steering behavior that you might be able to use here. Which approach would be best depends somewhat on the nature of the obstacles (for example, you might use a different approach for avoiding an obstacle like the one in your image than you would, say, a moving asteroid).

3. Pathfinding

A 'local' obstacle avoidance algorithm won't always behave intelligently when presented with the type of environment shown in your screenshot. If you need agents to not only be able to avoid obstacles, but also to be able to navigate this type of environment in a convincing manner, you may need to use a pathfinding algorithm instead. (That said, there are 'local' behaviors, such as wall following, that can be used to navigate in this type of environment with some success.)

Pathfinding in a dynamic environment can be tricky, but there are ways to update a search space representation to reflect dynamic changes such as walls that have been destroyed or what have you. This would be more applicable to obstacles like those in the screenshot; pathfinding won't be of much use when dealing with moving obstacles such as, say, an asteroid.

Anyway, that's what comes to mind. Maybe others will offer additional suggestions.

Potential functions. Hadn't heard of them before, a quick search returned 'AI for game developers by David M. Bourg & Glenn Seemann' Chapter 5. Gonna see what it's about.


Steering behaviors. I've tried them twice before but both attempts ended in failure. My conclusion is that they don't blend well with the physics library I am using right now, but then again maybe I am doing things wrong. By the version I came across(Craig W. Reynolds, OpenSteer) steering behaviors depend on the manipulation of your current velocity's vector(Unless I am missing something). The problem this presents is that I have no way of knowing where my ship is actually facing, just where it's moving towards. Taking my current facing from that vector would cause some weird instantaneous facing results. I was given a solution that was: Instead of changing my object's current velocity with the steering behaviours I should turn the steering vector into a force and apply it on the front of the ship. This worked but turning was slow and there was seemingly no way of making it go faster without ending up with a weird pendulum effect.
I made a thread regarding the problem on the Box2D forums in case you want to read the whole thing.
http://www.box2d.org/forum/viewtopic.php?f=3&t=3316

Pathfinding. Well if pathfinding isn't very helpful with moving obstacles then I have a problem since most of the objects in my game will be moving :S.

Quote:

Potential functions. Hadn't heard of them before, a quick search returned 'AI for game developers by David M. Bourg & Glenn Seemann' Chapter 5. Gonna see what it's about.

That particular book has received a fair amount of criticism, I think, but if you know that going in I don't know that it would hurt to check it out. (If nothing else, it does explain the basic concepts behind potential functions and a few other useful AI-related concepts.)

Quote:

Steering behaviors. I've tried them twice before but both attempts ended in failure. My conclusion is that they don't blend well with the physics library I am using right now, but then again maybe I am doing things wrong.

As long as you're able to apply forces to rigid bodies (which you can do with Box2D), you should be able to use steering behaviors. Maybe it was just a flaw in your implementation?

Quote:

By the version I came across(Craig W. Reynolds, OpenSteer) steering behaviors depend on the manipulation of your current velocity's vector(Unless I am missing something).

Most of the literature discusses the behaviors in terms of directly modifying the velocity vector, but it shouldn't be hard to adapt the techniques to work with force and momentum instead. (I understand your confusion though, as most of the examples I've seen appear to derive a force directly from the desired velocity.)

Quote:

The problem this presents is that I have no way of knowing where my ship is actually facing, just where it's moving towards.

You must have access to the ship's transform, right (for rendering purposes if nothing else)? If so, then you have access to the 'facing' vector.

Quote:

Taking my current facing from that vector would cause some weird instantaneous facing results.

If you're talking about adjusting the agent's orientation to align with the velocity, that doesn't have to be done instantaneously (or at all, for that matter).

Quote:

I was given a solution that was: Instead of changing my object's current velocity with the steering behaviours I should turn the steering vector into a force and apply it on the front of the ship. This worked but turning was slow and there was seemingly no way of making it go faster without ending up with a weird pendulum effect.

I'm not sure how well the steering behaviors work when the force is applied somewhere other than the center of mass (I haven't tried it).

Quote:

Pathfinding. Well if pathfinding isn't very helpful with moving obstacles then I have a problem since most of the objects in my game will be moving :S.

Yeah, if you don't have a specific need for pathfinding, I wouldn't worry about it for now.

Although these techniques (steering behaviors and potential functions) are fairly straightforward to implement, it can be tricky to get the behaviors the way you want them; sometimes it takes some persistence. (Also, if you're looking for other references on the subject, check out 'Programming Game AI by Example', which covers steering behaviors in detail, and has accompanying downloadable demos that demonstrate the techniques.)

Alright, I decided to give steering behaviors another go. I am trying to implement a simple seek behavior.

This works though setting my object's/sprite's facing like this brings up the problem I mentioned before. If there is a sudden change in velocity, say a collision propels the object back, then the object will automatically(Or the sprite for that matter) face backwards instead of just being sent back but still face its current direction. Am I doing something wrong? I don't see a way around this with steering behaviors.

The orientation problem you mention isn't really a shortcoming of steering behaviors; it's just that the issue is sort of tangential to the topic of the steering behaviors themselves, and so it usually isn't given more than passing mention in the literature. It's really something that has to be solved on a case-by-case basis (the problem is necessarily context-dependent - what works for one game might not work for another).

Now, on to possible solutions. The first thing to note is that you're snapping the orientation instantaneously to the new orientation, which will only look natural when the change in orientation is small. Alternatives would be to gradually turn towards the new orientation, or to use a sample buffer or other smoothing method to smooth out the turns.

As for the problem of getting 'knocked back', one alternative would be to have the agent orient towards the target 'seek' position rather than towards the direction of motion. This way, in the case you describe the agent would most likely continue to face in more or less the same direction after getting knocked back.

There are plenty of other solutions as well, of course - it's just a matter of 'thinking outside the box', as it were. There's no 'rule' with steering behaviors that the agent's orientation always has to align with the velocity vector; it's just a convenient way to address the issue of orientation when presenting the algorithms.

Alright I was able to figure out a pretty satisfactory solution, gonna post it here in case someone else runs into the same problem. Suggestions on how to improve it are certainly welcome.

Now that I think about it, this is a solution to the locomotion problem of controlling AI agents that can only move in the direction they are facing which has little if anything to do with the thread, oh well, I saw it was causing trouble to some other people aswell so I'll go ahead and post it anyway.

The code is a little bit messy.



[Edited by - Antonym on June 25, 2009 9:37:36 AM]

First, use Spacial Partitioning methods to make the search for collisions more efficient by making the subsets (considered as candidates) much smaller.

Next, have each object maintain a 'bounding box' which is large enough to contain the object no matter what its orientation (you could also do a bounding sphere) and use that geometry to cull out objects from the more detailed collision calculations. Radius to radius intersection is fairly cheap.

Then apply the much more costly collision full detail tests on the smaller number of objects.