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.