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
Medals (Achievements)
2D turn-based strategy game
SDL 1 tutorials (outdated)

Latest Updates

SDL2 turn-based strategy tutorial
Thu, 14th April 2022

Water Closet ported to PlayStation Vita
Tue, 4th January 2022

The Legend of Edgar 1.35
Sat, 1st January 2022

Achievements tutorial
Thu, 2nd December 2021

SDL2 Rogue tutorial
Thu, 30th September 2021

All Updates »

Tags

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

Books


A North-South Divide

For over a hundred years, messenger Duncan has wandered the world, searching for the missing pieces of an amulet that will rid him of his curse; a curse that has burdened him with an extreme intolerance of the cold, an unnaturally long life, and the despair of watching all he knew and loved become lost to the ravages of time. But now, Duncan is close to the end of his long quest.

Click here to learn more and read an extract!

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
Mon, 26th April 2021

Lasagne Monsters source code
Tue, 20th April 2021

3 Guys Apocalypse source code
Sun, 11th April 2021

A Reddit Wallpaper download script
Fri, 27th May 2016

Scraping Amazon's Wishlist
Sat, 21st May 2016

Mobile site