This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Blockmap Algorithm
  Submitted by



This is the classic blockmap algorithm ( objects are spread out on a grid of rectangular sectors, and for collisions you only check the surrounding sectors of an object ) with a feature that allows major spread gains. Instead of just checking one object's 8+1 neightbour sectors for intersections, detections are only done in the object's sector by using "object fragments" ! An objects can be composed of at least one fragment, depending on its size and position relative to the lines making up the blockmap grid. So it is enough only to check the fragments you find in one sector to be sure that two objects are colliding. Simple as that ! This code actually works, I've used it some time ago in a 2D engine, with spectacular results ! This can be easily expanded to 3D, with octrees, I think. Hope it's useful to somebody ! Predator 2001. PS. You can't just cut & paste the code and compile it !

Download Associated File: blockmap.txt (3,464 bytes)

//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 } } }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.