collision detect theory...

[Z!re]

I just came to think of this, while messing with the MOoRPG collision layer...


Let's say you are making a game, with a few hundred objects, that needs to be checked for collision.

First thing that comes to mind:

Code:

For a=0 To NumObjects
If Object.Location = OtherObject(a).Location Then Collide
Next

Which would evolve into:

Code:

For b = 0 To NumObjects
For a=0 To NumObjects
  If a <> b Then
   If Object(b).Location = OtherObject(a).Location Then Collide
  End If
Next
Next

Now, let's assume 10 objects.. this would mean ~100 checks.

Pretty fast... definitely acceptable...


Now, let's assume 1000 objects.. that's 1 000 000 checks.. one million...

Try this:

Code:

For a& = 0 To 999999
Next

Takes a while, sure, might only take 0.1 seconds on your 1044GHz machine ( ), but think about it.. 0.1sec... maximum you could possibly get in your game would be 10FPS... ever played a game at 10FPS?


"I'll just use a collision layer then, and make the objects update it"
Sure.. This works for small maps, and when each object only take a small amount of memory.

Consider:
A world of 5120 x 3200 tiles, where each tile is 64x64 pixels, and you want pixel perfect collision (you do want pixel perfect collision) and p*p scrolling.

A collision layer would take 67108864000 bytes (5120*64 * 3200*64) or ~64GB

Ofcourse, this assumes 8bits per pixel, which might not be needed, you might only need passable, or not passable, and in that case a simple bitmap will suffice, and you'll end up with a colission layer of ONLY ~8GB

A bit inefficient, dont you think?


So we can't use a colission layer, nor can we scan through all the objects every frame (read: everytime you move)

So what to do..

The first thing I thought of, was:
"I'll just divide each tile, and not use pixel perfect colissions"
So, I went ahead with dividing each tile into areas of 4x4, instead of 64x64, thus I could only get colissions down to an accuracy of 16 pixels (which sucks BIG TIME, esp in mode 13h.. 16 pixels is 'half-way across the screen' )

But I went ahead with it.

The new formula would then be: 5120*4 * 3200*4

Which means 262 144 000 bytes, or 250MB
"Wow... from 64GB down to 250MB, that's quite good"

Tested it, and DAMN it sucks... "OMFG!, I wasnt even near that cliff!, WTF!, Why cant I enter the door!?!?!?!"

Ya.... So that was a crappy idea...


Then I realized...

When will the ENTIRE world be filled with objects? Or even if you shrink it to 4x4 possibe locations per tile, when?

Never... unless I plan on having 16 384 000 objects, at the same time, in the world. Which I dont (Nor do you, you hear me.. that's a shitload of objects.. don't even think about it.. dont... Or I'll beat you up... damit!)

So... How about I store all the objects in a database, with their X, Y values?

DOH!, Back to square one... but wait...


How about a combination?

A database of, lets say, the X locations, with N number of slots for location data?


Like this:
You have a map, let's say it's 10x10. You decide to have a maximum of 25 objects in total on the map at any given time.
You also decide that there can only be 7 objects on the same Y axis.

The database file now looks something like:

Code:

0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000
0000000

Great, but that doesent help us at all...

Nope... but wait.. what if, for each X position in the file we store the EXACT X and Y position, as well as any other data we might want for that object?

Ok, so the map is 10x10...

Let's say we create an Array:

Code:

Dim MapCollision(10) As String * 56

"Why As String * 56?"
Hang on...

Now, to store a object, we first find out where the object is on the X axis..

Let's say this is our object:

Code:

Obj.X = 5
Obj.Y = 3
Obj.Name = "Hans"
Obj.Health = 100

To store it we do:

Code:

Flag = 0
For i = 1 To 7 '7 objects max per Y axis, remember

'8 bytes per object
If Mid$(MapCollision(Obj.X), i*8, 8) = String$(8, 0) Then
  Flag = 1
  Exit For
End If

Next
If Flag = 0 Then
'No free slot found, Hans cannot be on that Y axis, sorry Hans.
Print "ERROR: Aaaw,";Obj.Name;"couldn't play with the other objects."
End
End If

'So, now we got a free index slot, in out map data array collision wannabe thingy
'It is stored in i
'Now let's store Hans on the map, so he can play with himself :P

Mid$(MapCollision(Obj.X), i*8, 2) = MKI$(Obj.Y)
Mid$(MapCollision(Obj.X), i*8, 4) = MKI$(Obj.Name)
Mid$(MapCollision(Obj.X), i*8, 2) = MKI$(Obj.Health)

And there you go, Hans is stored, along with some data for him.


For a 10x10 map this is kind of a bad idea, but it works.

But think about the 5120x3200 world I'm using

Using the above technique, and storing:
X, Y, ID (all take 4 bytes, totaling at 12)

I need to store the exact X possition too, as I only used it tilewise, or I would end up with 327 680 X axis positions, each taking MaxObjsPerYAxis*8 bytes... a bit large, ey?

Anyways...

Storing that, and assuming 2000 objects max per Y axis, and X tile axis (not pixel axis)

I got a collision file at 117MB (5120 * 12 * 2000)

Over 100MB less then the crappy non-pixel perfect version!

And it's fast!


Think about it... To see if you have collided, you just read the X axis in your database file

A For Next loop of only 2000 objects MAX... and read their X and Y position and compare it to whatever you want...


It's fast, really really fast.. and this enables me to use up to 10240000 objects... :o




Anyways... Break it... Find the flaws and holes in it... Doooo it!.. You know you want to! If you don't I'll brag forever! *muahahaha*




Note: The code blocks are untested, and provided for better visualization only, I didn't know how to explain stuff so... Sorry about that =)