//18 July 2001 - COTD submitted by PREDATOR [predator.lair@gmx.co.uk] // // global stuff // #define MAX_FRAGM 256 // maximum number of objects fragments #define SECTOR_H 128 // sector width (crap name, I know :) #define SECTOR_V 96 // sector height // a very basic object class, // the real thing would have lots of additional data // typedef struct obj_s { float x, y; int width, height; void (*think)(obj_s* self); void (*collide)(obj_s* self, obj_s* other); } obj_t; // // the key : the object fragment... // typedef struct objfrag_s { obj_t* o; objfrag_s* next; objfrag_s* prev; } objfrag_t; // // global data // objfrag_t ** sectorlist; objfrag_t fraglist[MAX_FRAGM]; int numobjs, numfrags; // current number of objects & fragments int sectors_x, sectors_y; // number of sectors per width / hight int world_h, world_v; // some sort of world dimensions // all of the objects are stored in this imaginary linklist type :) linklist_t * obj_list; // // setting up the system... ( all of this can be, of course, put in a class ) // void word_init() { int count; numobjs = 0; numfrags = 0; sectors_x = world_h / SECTOR_H; sectors_y = world_v / SECTOR_V; count = sizeof(*sectorlist) * sectors_x * sectors_y; sectorlist = (objfrag_t**)malloc(count); } // // refresh the things a bit, called each frame... // void world_purge() { memset(sectorlist, 0, count); // isn't really necesary, the new fragments will be owerwritten... memset(fraglist, 0, sizeof(fraglist)); numfrags = 0; } // called each time an object needs to be updated, // it gets inserted in the collision grid at (sx, sy) // // you can spilt up an object between sectors like this: // for ( sy = (int)o->y / SECTOR_V; // sy <= ((int)o->y + o->height) / SECTOR_V; // sy++ ) // for ( sx = (int)o->x / SECTOR_H; // sx <= ((int)o->x + o->width) / SECTOR_H; // sx++ ) // world_sectorize(o, sx, sy); void world_sectorize(obj_t* o, int sx, int sy) { objfrag_t** link; objfrag_t* f; // grab a root fragment in this sector link = §orlist[sectors_x * sy + sx]; // the new fragment to be added f = &fraglist[numfrags]; numfrags++; if (numfrags > MAX_FRAGM ) return; // the tricky part: linking the fragment in f->o = o; f->prev = NULL; f->next = *link; if ( *link ) (*link)->prev = f; *link = f; } // // the really usefull stuff: checking for collisions per sector // void world_check_collisions() { obj_t* o; obj_t* oo; objfrag_t* f; objfrag_t* ff; int i; for ( i = 0; i < sectors_x * sectors_y; i++ ) { f = sectorlist[i]; // prepare an object while ( f ) { o = f->o; // grab the actual object ff = sectorlist[i]; while ( ff ) { // check for the others in the same sector oo = ff->o; if ( o != oo ) // can't collide with itself ! // user defined collision detection function, usually // a bounding box check, then a more pixel accurate one if ( SOME_SORT_OF_COLISION_DETECTION_MACRO() ) { // call the objects collide funcs. ( or do anything else...) // to be sure that the functions are call only once per object // cut out the second statement or keep a collision counter if ( o->collide ) o->collide(o, oo); if ( oo->collide ) oo->collide(oo, o); } ff = ff->next; // the remaining objects in this sector to be checked } f = f->next; // the next object } } }