How Accurate?

Today I am going to write about something that I noticed when working on AI for a game:

Almost nothing needs to be accurate in games.  Take collision detection as a example.  Wikipedia says in regard to collision detection in video games:

Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, he might be simply moved back to his last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow him to move that far.

I find something similar:  Al least 90% of your collision detection will be (Or can be) AABB (A rectangle that cannot be rotated).  The exceptions are, of course, circles and complex shapes.
For circles, one can just check if the objects are more then the sum of their radii (Plural of radius) apart.  This is called distance based collision.

Complex shapes will usually fall in the 10% that I talked about that cannot have AABB collision detection.  But thinking about it, we can still use AABB for complex objects, to prune down the amount of checks we need to do.  All you need to do is only check collisions for the objects that are colliding with the complex object’s AABB.  The big question after that is how to find if the objects are colliding.  There are 2 methods:

  1. Use many different AABB’s and distance collisions for the same object.
  2. Splice the image of the object into a grid.  If more than, say 50% of one of the squares is non-transparent then it is solid (generally this step will be done only once, at the beginning of the program).  You then loop through all the grid squares, checking if the objects collide with them.

Both of these methods are good, but they will still use large amounts of memory when any object is inside it’s AABB.  At this point it becomes “how much more accurate can I make the collision detection without having the game be to slow?”

That brings me back to one of my first points:

There is no silver bullet.  Everything you do in programming games will be a trade off:  How much processing time will it take vs. how good does it look.

The best thing you can do for yourself is get a good collection of functions to use in all your games.  Two that seem to find their way into any game I write are a AABB function, and a distance based collision function, both written in löve2d, although they would be easy to port into any language.

Advertisements

2 thoughts on “How Accurate?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s