• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Alternative Collisions

T

Toxicosis

Guest
Currently, I'm using instance collision. But with only 300 objects in the room, about 44 of which are walls, things are already tight.

Someone mentioned to me a ds_grid collision. How would that work?

I mean, again, I'm trying to make hideously big levels, so my first impulse was to replace the instances called in the with obj_walls by calls to a ds_grid, 32k x 32k, where each value was either 0 or 1, to determine whether every px was occupied or not. It didn't take me long to realize that was beyond stupid.

My second thought was to buffer all solid instance positions and use an iterative check to skip as many blocks as possible. Here's a pseudocode.
Code:
CREATE EVENT:
ds_grid [32k,5]
with wall
 ds_grid[i,0] = instance_number
 ds_grid[i,1] = bbox_left;
 ds_grid[i,2] = bbox_top;
 ds_grid[i,3] = bbox_right;
 ds_grid[i,4] = bbox_bottom;
 i++;
 sort_by_column_1();
[0,0] = i;
[0,3] = max[3]

COLISSION_CODE:
var j, k, xmax;
j=ds_grid[0,0]/2;
skip = j/2;
while skip > 1
 if ds_grid[j,3] > bbox_right j=j-skip;
 else j=j-skip;
 skip=skip/2;
xmax = j;
//A loop of some sort until we reach the first object that doesn't start past the right edge. Once we got there, use ds_grid [0,3] to determine how broad a swath of the list to check.

skip = j/2;
while skip < 1
 if ds_grid[j,2] < bbox_left j=j+skip;
 else j= j+skip;
 skip = skip/2;
 xmin = j;
//As collision_rectangle needs to check n times,
//this one would only need to check x=log(n,2) times on the first check,
//then instead of checking n-m times the second check,
//it'd check only y = log(n-m,2) times the second check.

//We move from linear to logarhytmic time for the first two checks;
//for a mostly horizontal level, that reduces the load for the first check
//from 2048 instances to the same load you'd have from barely 11.
//Of course,
//it could turn out you've got 2048 instances spread only one pixel from the center of mass
//horizontally, but if that happens, you've got no one to blame but yourself.

for (j=xmin;j<=xmax;j++)
 if place_meeting(x,y,ds_grid[j,0])
//Well, something to that effect,
//now that we've narrowed it down to a hair-thin slice of the level.
//The checks on x and y cannot be handled the same, 
//but they'd be handled pretty good by that effect.
  return true;

return false;

That's my first impulse. However, every instance, even without code, has a load involved. I was wondering...
How about tile collision?

The only function I can think of that does this is tile_layer_find. I've been thinking, I could simply set some layers as things you can stand on, and that'd reduce most of my objects to tiles. So long as I can make another object take care of them and run all their logic, tiles can do things just fine.

In this version, I'd simply have to pick a resolution, and use tile_layer_find on the edge of every object that needs to know where it stands, checking every resolution pixels. To operate with multiple tiles as one object, I'd require a tile to check for other tiles around it, and so on. However, larger checks would scale with the area checked, rather than with the number of tiles, which would render it pretty useless for both.


It could be sped up even more dramatically through a hybrid of both, as tiles run no code and the grid would allow for a swift global check, but said hybrid would handle at most 32k tiles (barring multiple grids? Maybe, one grid per depth?).


Any advice?
 

TheouAegis

Member
Your grid doesn't necessarily have to be a one-to-one ratio. It will be faster if you do that but it will also take up much more space. You can store, say, 32 tiles in each cell of the grid. The more tiles you store in each cell of the grid, the longer it will take to find the information for a tile. Personally I would go with 8 tiles to a cell. This gives you also enough leeway to be able to include multiple solidity values. So instead of just solid and non solid, you could have empty, solid, mud, snow, water, lava, spikes, whatever.
 
T

Toxicosis

Guest
Like in the application surface example, Theou? That was complex, but it should not be impossible to reverse-engineer.
 
Top