C memory management

Hey /prog, I'm teaching myself C by writing a roguelike and I noticed that C uses manual memory management for creating objects in the heap. I was wondering if the C-gods could lend me some advice on how to proceed with this:

I want to write a roguelike with thousands of NPCs, every NPC is a really small piece of data which does not contain any pointers (position, stats, behavior... probably ends up being a few bytes). NPCs would spawn and die constantly. How would I go about managing the memory for this?

• malloc and free individual NPCs
• Boehm-Demers-Weiser conservative garbage collector
• malloc a big chunk of memory and build some kind of memory manager on top of it (are there techniques for this?)

Please advice.

>>3
I was hoping section 8.2 contained the code to do >>4, but it turns out it was just an explanation of how malloc etc... work.

Reading through it, it seems malloc is designed to work in very general cases and does a lot more than I need; so I'm thinking a separate malloc call for every npc is probably out of the question, even with GC.

I've thus implemented the idea suggested by >>4:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MEM_SIZE 1024
#define MEM_TYPE int

MEM_TYPE* mem = NULL;
int mem_chunks = 1;
int mem_index = 0;

// init()
// key = store(data)
// mem[key] = other data
// unstore(key)

void init()
{
    // printf( "chunks: %d\n", mem_chunks);
    mem = realloc(mem,mem_chunks * MEM_SIZE * sizeof(MEM_TYPE));
    if(mem == NULL)
    {
       fprintf(stderr, "Out of memory, exiting\n");
       exit(1);
    }
}

int store(MEM_TYPE data)
{
    mem[mem_index++] = data;
    if ( mem_index == mem_chunks * MEM_SIZE)
    {
        mem_chunks++;
        init();
    }
    return (mem_index-1);
}

void unstore(idx)
{
    mem[idx] = mem[--mem_index];   
    if ( mem_index + MEM_SIZE < (mem_chunks-1) * MEM_SIZE)
    {
        mem_chunks--;
        init();
    }
}

int main()
{
    init();
    int i;
    for ( i = 0; i < MEM_SIZE * 300; i++) store(i);
    for ( i = 0; i < MEM_SIZE * 295; i++) unstore(0);
    for ( i = 0; i < mem_index; i++)
    {
        // printf("%d ", (MEM_TYPE) mem[i]);
    }
    exit(0);
}

Looking at it though, I'm not sure this is the correct approach to store a list of NPCs (or game objects) for a roguelike. I like that there's not much alloc-ing going on, but there are some problems:

• Every object has an in-game position. I completely overlooked this very common access pattern. Getting the objects in a certain area requires looping over all objects.

• unstore() moves memory around, so there's no reliable way to keep references to game objects. The more I think about it, the more I begin to believe this is a major drawback. Pointers to objects are out of the question due to the realloc calls, but it would be nice if the index of an object never changed.

So it seems I'll need something slightly more complicated than originally intended...