• android (3)
• battle-for-the-solar-system (10)
• blob-wars (10)
• brexit (1)
• code (6)
• edgar (9)
• games (43)
• lasagne-monsters (1)
• making-of (5)
• match3 (1)
• numberblocksonline (1)
• orb (2)
• site (1)
• tanx (4)
• three-guys (3)
• three-guys-apocalypse (3)
• tutorials (17)
• water-closet (4)

This questions comes up from time to time: how do you resize an array in C? The answer is simple: you can't. In fact, in most programming languages you can't. Or, if it does allow a method of doing so, there will be some behind-the-scenes magic that is doing something different.

Consider the following:

MyStruct data[10];

We want to expand data from 10 elements to 15. The only way we can do that is by creating another array of MyStructs and copying the existing 10 elements into it:

MyStruct newData[15];

for (i = 0 ; i < 10 ; i++)
{
	newData[i] = data[i];
}

Or, more easily:

MyStruct newData[15];

memcpy(newData, data, sizeof(MyStruct) * 10);

While this works, it still has problems, including the fact that newData has been created on the stack and could be lost at some later point. While working on The Pandoran War, I encountered the same problem. At any time during the game there can be hundreds of particles in existence: engine trails, explosions, etc. These are all tracked using a linked list, which is fine for processing, but drawing is a different matter. I didn't want to loop through the list again and draw only those effects that were currently on screen; it could lead to a dip in performance which I would rather avoid.

For technically reasons, another linked list was out of the question; one particle points to another, and playing around with that relationship could have unexpected results. I could've created a wrapper struct, a linked list with a reference to the particle to be drawn, but that seemed like the wrong approach.

Initially, I used a fixed-size array of a reasonable size (2000 elements), and pushed the particles that were onscreen into that for drawing later. While this was good on paper, every now and again the array would reach maximum capacity and would not accept any more additions.

I looked into how to dynamically resize an array, and, after a lot of head banging, I found a workable solution:

static Effect **effectsToDraw;
static int drawCapacity;

drawCapacity = 100;

effectsToDraw = malloc(sizeof(Effect*) * drawCapacity);
memset(effectsToDraw, 0, sizeof(Effect*) * drawCapacity);

The code above will create an array of Effects (a struct that holds particle effect data), with a size of 100. The drawCapacity variable is important here for tracking the size of the array. effectsToDraw is a standard array, that can be accessed is the usual way:

effectsToDraw[0]->x = 100;
effectsToDraw[0]->y = 100;

...

effectsToDraw[65]->x = 40;
effectsToDraw[65]->y = 20;

...

etc.

All good so far. But what about resizing it? To achieve this, I created a resize() function that takes the existing array, the size of the array, and the desired new size (either larger or smaller). It creates a new array of the desired size, copies the data out of the old array, deletes the old array, and finally returns the new one:

void *resize(void *array, int oldSize, int newSize)
{
	void **newArray;
	int copySize;
	
	copySize = newSize > oldSize ? oldSize : newSize;
	
	newArray = malloc(newSize);
	memset(newArray, 0, newSize);
	memcpy(newArray, array, copySize);
	free(array);
	
	return newArray;
}

This can be used harnessed very easily:

int n = drawCapacity + 100;

effectsToDraw = resize(effectsToDraw, sizeof(Effect*) * drawCapacity, sizeof(Effect*) * n);

drawCapacity = n;

Note how it's very important that we update drawCapacity with the new size. This will be needed to test to see if the array is full and needs to be resized. You can see this in action in the effects.c code in The Pandoran War:

https://github.com/stephenjsweeney/tbftss/blob/master/src/battle/effects.c#L98

(also shown in part below)

void doEffects(void)
{
	Effect *e;
	int i, onScreen;

	for (e = battle.effectHead.next ; e != NULL ; e = e->next)
	{
		...
		
		if (onScreen)
		{
			effectsToDraw[i++] = e;

			if (i == drawCapacity)
			{
				resizeDrawList();
			}
		}
	}
}

static void resizeDrawList(void)
{
	int n;

	n = drawCapacity + INITIAL_EFFECT_DRAW_CAPACITY;

	effectsToDraw = resize(effectsToDraw, sizeof(Effect*) * drawCapacity, sizeof(Effect*) * n);
	
	drawCapacity = n;
}

With all that working, I expanded the resizing to a lot of other parts of the code, including the quadtree. The effect on the quadtree was the largest, as it reduced the memory overhead significantly (down from something like 2MB to 100kb). It also allowed the quadtree's nodes to grow as needed (as they should).

In case you're wondering why I didn't simply use realloc() instead of rolling my own resize(), it simply comes down to realloc() not zeroing the allocated memory. Zeroing memory using memset() is a (good) habit that I've fallen into, and saves me a lot of headaches when it comes to working with C. I'd also read (probably incorrectly) somewhere that realloc() can cause issues. I imagine that this is due to a programmer error, rather than anything else, though. Also, I wanted to learn something.

Hopefully, you'll have found this useful.