I had been struggling for a few weeks with some strange behavior I was getting from my dissertation project. I developed my software using the GPL'd Quake 2 engine, and I was surprised when it started crashing unexpectedly and displaying all sorts of weird artifacts. John Carmack and his cohorts are great programmers, and I knew there weren't bugs like this in the commercial game... but I also knew that I hadn't touched any of the code that was throwing me memory violations.
So I spent a few weeks debugging, and didn't get anywhere. I excised the entire collision system and reduced the frequency of fatal errors, but the system still wasn't stable enough to run for more than a few hours. Plus, I really want to use the collision system.
Most of my changes were to the standard data structures, particularly edict_s (which I use to represent my animats -- my artificial creatures). I added a three-dimensional array to keep track of each animat's world knowledge -- one dimension holds the "layers" of knowledge (like food locations, enemy locations, unexplored territory, &c.), and the other two dimensions represent the XY coordinate plane of the world. The world is a square 2048 units per side, and I didn't want the arrays to be that large, so I collapsed the XY plane into a 32x32 grid of "sectors", with each sector being 64x64 units in size; my knowledge array could then have 32x32 entries per layer (0 - 31 in each dimension), rather than 2048x2048.
Because of this granulation, however, I needed a routine to translate an animat's real coordinates into its sector coordinates, so I wrote the following:
#define GRIDX(x) ((int)x->s.origin/C_GRIDSIZE)
#define GRIDY(x) ((int)x->s.origin/C_GRIDSIZE)
Those macros take the X or Y coordinate of animat x and then divide it by C_GRIDSIZE, which is 64. No problem! Except... near the edges of the map it's possible for an animat to nudge itself slightly past 0 or 2047! The knowledge array in the animat structure only goes from 0 to 31, but occasionally these macros would return -1 or 32, or even worse! When I would then try to write to the array, I wasn't writing into the knowledge map at all, I wrote to other locations in the animat structure!
Sorry for all the exclamation points, but it's no wonder I was seeing strange behavior. I just changed the macros as such:
#define MIN(a, b) (a<b?a:b)
#define MAX(a, b) (a>b?a:b)
#define GRIDX(x) MIN(MAX(((int)x->s.origin/C_GRIDSIZE),0),C_XMAX-1)
#define GRIDY(x) MIN(MAX(((int)x->s.origin/C_GRIDSIZE),0),C_YMAX-1)
Everything seems to be quite stable now, and I'm going to leave it running overnight just to be sure. The lesson is: always bounds-check your arrays!