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