PC Games

Orb
Lasagne Monsters
Three Guys Apocalypse
Water Closet
Blob Wars : Attrition
The Legend of Edgar
TBFTSS: The Pandoran War
Three Guys
Blob Wars : Blob and Conquer
Blob Wars : Metal Blob Solid
Project: Starfighter
TANX Squadron

Android Games

DDDDD
Number Blocks
Match 3 Warriors

Tutorials

2D shoot 'em up
2D top-down shooter
2D platform game
Sprite atlas tutorial
Working with TTF fonts
2D adventure game
Widget tutorial
2D shoot 'em up sequel
2D run and gun
Roguelike
SDL 1 tutorials (outdated)

Latest Updates

SDL2 Rogue tutorial
Wed, 29th September 2021

SDL2 Gunner tutorial
Thu, 26th August 2021

SDL2 Shooter 2 tutorial
Tue, 13th July 2021

SDL2 Widget tutorial
Fri, 18th June 2021

SDL2 Adventure tutorial
Tue, 8th June 2021

All Updates »

Tags

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

Books

Resizing an array in C

Thu, 19th May 2016

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.

code 

Related News

Orb source code
Sun, 25th April 2021

Lasagne Monsters source code
Mon, 19th April 2021

3 Guys Apocalypse source code
Sat, 10th April 2021

A Reddit Wallpaper download script
Thu, 26th May 2016

Scraping Amazon's Wishlist
Fri, 20th May 2016

Comments

Share your comments and thoughts below. All comments are anonymous and cannot be edited.

 

Mobile site