Collision Detection

So I’ve been thinking some more about the Worms-like game contest for gamedev next time. I’ve got a damn sweet model for deformable terrain up my sleve, which I think could make a very strategic ballistics game. Not to mention, it’s deformable terrain, which is cool in its own right.

There are two problems I’m facing at the moment. The first is that the deformable terrain model is a very stiff differential system, making for computationally intense integration. As an example, do a simple Euler integration on x’ = -Kx, with K = 10,000 and x0 = 1. You’ll note that if you use a step-size any greater than 10-4, things start looking very different from the correct e-Kx.

Another is collision detection, as usual. The Game Language I spoke of earlier is going to need a solid generic collision detection algorithm built-in (and it needs to be overridable), so it’s time I gave this some thought. I was thinking of using the OpenGL stencil buffer in combination with selection to do the detection for me, but it has a couple serious problems, the main one being that it only works for objects that are on-screen. So that basically rules that one out.

So I might fall back on a quad-tree implementation, using the embedded list pattern (I’ll post on that in a minute), so I don’t have to allocate any memory in the process. Doing lines is a bit of a challenge in the tree environment, but I might be able to come up with an efficient and elegant recursive algorithm. Actually, I can think of it right now. Cool. I think I’ll do another demo and see how it measures up in terms of speed.

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