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.

Serious suggestion: why don't you ask Toady how he did it? I'm sure he'd share his approach.

I noticed that C uses manual memory management
Read K&R.

Also,
• Boehm-Demers-Weiser conservative garbage collector
this.

>>1
every NPC is a really small piece of data which does not contain any pointers

If NPCs don't hold pointers at each other it means you can move your data around freely. Which means that you can store all live NPCs in a contiguous array and whenever you delete one, you move the last one in its place.

>>2
$ ./df
Segmentation fault

>>3
Read K&R.
Sweeet, I found what I needed in section 8.7. Will start reading right away.

Are you suggesting I somehow combine the ideas in this code with the GC?

>>5
The BoehmGC is a piece of art and you should use it, it will make your life simpler.
If you don't like the idea of using a GC, you could do what >>4 said, mallocing a big chunk of memory and putting all your NPCs there, resizing it when it becomes too large/small.

>>4
This isn't a terrible idea, but do document the practice since code like this is a little unclear about intentions:

struct NPC { /* whatever */ };
void del_npc(NPC *npc) {
    int i;
   
    for(i=0; (int)npc[i +1] != 0; i++);
    if( i != 0 ) memcpy(npc, &npc[i], sizeof(struct NPC));
    memset(&npc[i], 0, sizeof(struct NPC));
}

The convention here is that NPC will deref to an int which evaluates to zero. It's better to use a struct member to indicate that it's the last item on the list but this code will work with whatever your struct looks like (assuming it works at all, I haven't tested it.)

This assumes a fixed size array, which may or may not have been malloc'd. Adding an NPC to the end works similarly, find the first entry on the list that derefs to 0 -- but you'll have to guard against exhausting the list. There's also a subtle bug: if you do not null terminate the list, it will continue searching past the end of the array whenever the list is full.

I'd sooner use a nonserial format for this kind of thing because of the possibility of errors above. Alternatively you could just mark individual NPCs as "free" when deleting and skip them when walking the list.

>>7
WTF is wrong with you?

Obviously you should just keep the number of active NPCs around.

Obviously assuming that live NPCs begin with a nonzero int is a very bad idea.

Obviously scanning the entire array to find its length is OUTRIGHT RETARDED.


I never thought I'd say that, but it looks like C causes brain damage sometimes.

Go find yourself a book on good C++ code style and never code in C again until you've mastered C++ and know how to write non-retarded code even in C.

>>8
Uh yeah. You might want to focus on reading comprehension before you give people programming advice. Here's what you didn't get from my post:

a) make sure you document it if you write code like this.
b) an alternative is better.
c) yet another alternative is better.

Obviously you didn't read much of the post, particularly the part immediately before the code and the part about the additional struct member.
Obviously this is in the context of >>7 and should be treated as such.
Obviously >>7 is not the way to do it if you're interested keeping around extra information around.

Anyway since I'm repeating myself: this was an example of what code might look like according to >>7's corner-cutting suggestion, nothing like code I'd ever write. I'm not sure where you got that idea, since I declaimed the design at least twice.

>>9
U MENA >>4, which, incidentally, was myself.

What I had in mind was basically an std::vector implementation in C.

Your insinuation that your shit is "an example of what code might look like according to" my suggestion is quite frankly insulting.

I did not praise your "advice" about documenting the code because it's fucking obvious, but OK, that's a good advice.

The code you wrote on the other hand is horrible. What's even more terrifying is that you don't understand this and are surprised at the reaction. Like, it's just a quick hack, why I'm so worked up about it?

Well, you see, it's as if you were hungry and decided to eat some feces, "it's just a quick snack, what's up?"

There's no amount of "quickness" that can excuse this shit.

I repeat, your brain is seriously damaged by C, the retarded "let's just pass a pointer, then scan ahead to find the end" attitude in particular. I forbid you to write any more C before you learn to express yourself in a less retarded manner in C++.

>>10
Yeah, I meant >>4.

The example code was posted because it only took 3 lines of meat to point out what kinds of problems >>1 would probably run into given such advice. And I've said 3 times now that this wasn't a submission but an example of a source of problems.  The comment about documenting it is important: you didn't say it yourself and it's a dirty solution.

This obsession you have with walking the list is particularly hilarious. If the advice in >>4 is to be useful it presumes the list will be walked at some point and the procedure can be folded in at that time.

If >>4 is how you recommend solving a problem you've got no grounds to criticize an implementation for being imperfect. Please do stick with C++ though. Linus and I will know to disregard your every opinion.

>>11
The example code was posted because it only took 3 lines of meat to point out what kinds of problems >>1 would probably run into given such advice.
All problems you've mentioned in >>7 stem from the brain-damaged idea of not using the list length. Reread it yourself, it's hilarious -- you've mentioned literally zero problems that could be present otherwise. Even the problem of unclear intentions pretty much doesn't exist if you write it correctly:
void delete_npc(struct NPC * npcs, int * length, int index)
{
    ASSERT(0 <= index && index < length);
    *length--;
    if (index < *length)
        memcpy(npcs[index], npcs[*length], sizeof(NPC));
}
If the advice in >>4 is to be useful it presumes the list will be walked at some point and the procedure can be folded in at that time.
No, you intend walk it each time you delete or add an NPC. That can't be "folded" into anything. Because if you store the length then you don't need to walk the list at all.
Please do stick with C++ though. Linus and I will know to disregard your every opinion.
Hahaha, "Linus and I", I'm afraid if Linus saw you he would seriously consider switching to C++. You really, really suck at programming. Like, no Indian sweatshop would hire you, you're that bad. Seriously. If you think about becoming a professional programmer, please reconsider, you are not cut for it, you'll waste a lot of time, energy and money, both your own and of the people who'd have to deal with you.

>>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...

>>12
How many times do I have to declaim that code? I did it in the first post I made which should make it clear. You can blather on all you like about "doing it properly" -- you didn't explain what that might be until after the fact, yet >>1 is explicitly asking for guidance in that area. Without more help than you've given he's likely to produce something buggy, unclear and downright wrong. Meanwhile, you're actually advocating using C++isms in C. That's what earned you the Linus remark.

As for me, in fact I've been employed as a programmer for more than 10 years now. I am paid well and I often earn compliments from my employer and coworkers regarding the quality of the code I write. So you can say what you like but it won't affect my self-image.

>>13
In regards to the "in-game coordinate" thing, keeping two lists might be useful, though may also be memory impractical.  One list contains the normal unsorting NPC data and the other contains minimal information about NPCs required to reorganize its contents based on some kind of criteria, e.g., coordinate location in regards to viewport proximity.  The latter list has index references to the former list and when an NPC is removed from an interior index of the first list thaqt index is "remembered" for new NPC purposes.

memcpy(npc, &npc[i], sizeof(struct NPC)
memcpy(npcs[index], npcs[*length], sizeof(NPC));

STOP DOING THIS, ``FAG/G/OTS''


npcs[a] = npcs[b];

Was it that hard? Was it? It wasn't. Now forget about memcpy.

>>4
Btw I always use this trick when I'm trying learn new language and want to implement BSD robots. Easy to implement. Reliable. Works like a charm.

>>13
Use hash tables then.
(x,y) -> ID. # where (x,y) is y * MAP_WIDTH + x
ID->struct NPC
generate ID either randomly or sequentially.

For lightweight C hash map, you might consider this

https://github.com/attractivechaos/klib/blob/9786b6570494bcb2c389d6e52355ec0b3b40cc19/khash.h

>>14
Without more help than you've given he's likely to produce something buggy, unclear and downright wrong.
And with your "help" he is guaranteed to produce something buggy, ugly and downright wrong. Because your code is based on the most retarded C-ism in existence. Try to apply your advices to my code. It is impossible. The problems simply don't exist.

Are you familiar with the term "net-negative producing programmer" (http://en.wikipedia.org/wiki/NNPP)? That's you my friend, and your "help" is the prime example of that, it has negative worth. OP would have been better off without it. So that entire "well at least I shown some code" thing you seem to be pushing is wrong, showing code that bad is worse than showing no code at all.

Meanwhile, you're actually advocating using C++isms in C. That's what earned you the Linus remark.
Yes. Doing so is good. There is a lot of good C++isms. Good C programmers use them all the time. Go look at the fucking Linux networking code. There's a lot of awful C-isms. Only learning C++ can save you from writing retarded C. Go do it and don't write a line of C before you are done, for the sake of humanity!

I am paid well and I often earn compliments from my employer and coworkers regarding the quality of the code I write.
That's why we can't have nice things.

I am amused at how someone can know what a Boehm-Demers-Weiser conservative garbage collector is but be unfamiliar with a pool.

Why not store monsters in the level map itself? You'd have to iterate over the entire map to find them for the AI phase, but considering you'd have to suck chunks of the map out of memory to do their AI anyway, that could be fine, assuming a certain monster density. If you were going to store a monster pointer (or less crazy, an array index) in the map anyway for easy lookup, you can probably pack a monster's info into less space than a reference to it would take.

Not sure what you want with so many monsters though. Not like you're going to encounter more than a screenful at once. Why not just fake it?

>>18
"well at least I shown some code"
I didn't say or imply that even once. Tell me, why do you think I posted that code? I've stated it explicitly numerous times, so you don't need to trouble yourself with finding subtext.

Yes. Doing so is good.
No, it's not. C++ broke away from being a mere C pre-proccesor for a reason. There's no way back, and even Bjarn will tell you that choosing to build on C was a difficult compromise. You can't write good C that way.

That's why we can't have nice things.
Speak for yourself. I have lots of nice things.

This thread is going downhill fast.

>>22
Try to look at it like this: at least it didnt start at the very bottom.

Anyone have any experiences with this?

http://ccan.ozlabs.org/info/talloc.html

>>21
Speak for yourself. I have lots of nice things.
Give them away. Property is a burden on your spirit.

>>23
AUTIST

>>26
*grabs dick

>>20
Not sure what you want with so many monsters though. Not like you're going to encounter more than a screenful at once. Why not just fake it?
A screenful is 1920 (80x24), and that is quite a lot.

>>28
A screenful is far fewer than that unless you're making the weirdest fucking game ever. A good chunk of the level is going to be walls and stuff, and plenty of empty space too. Even if you're trying to make the most crowded game ever, I'd be shocked if you really needed to worry about more than 100 monsters at once, and I doubt all of those would be visible at the same time.

Maybe if the screen is much larger than 80x24.

>>20
Why not store monsters in the level map itself? You'd have to iterate over the entire map to find them for the AI phase,

That would be too slow. Monsters with huge ranged attack like

    for(unit in all_monster_in_radius(my.pos, my.weapon.range)) //ok, not C
    {
       if(is_enemy(me, unit) && estimated_damage(me, enemy) > estimated_damage(me, best_target))
          best_target = unit;
    }
    attack(best_target)

will cripple game so hard that even original rogue on original hardware will run faster.

Why not just fake it?

I want to cast ｌｏｃｋ ｄｏｏｒ to lock monsters and I don't want them to disappear or jump across lava river randomly.

>>21
Tell me, why do you think I posted that code?
Because you came up with one of the most braindamaged ways to implement >>4, overcame a number of difficulties along the way and decided to share the experience.

Which would be a good and noble thing to do, if not for the fact that you are a very bad programmer, an intellectual cripple, a freak of nature produced by overexposure to C and underexposure to other system languages.

The code in >>12 doesn't have any of the difficulties that you advised about dealing with in >>7. None at all! Hard to believe, I know, but try to find a single advice of yours that applies to my code!

Which means that your post a) doesn't contain any useful advice, b) does contain horrible, misleading code, that can further spread the intellectual corruption and desolation that you are plagued with. It is worse than useless, it has negative worth.

You can't write good C that way.
I write code this way. My code is good. You write "idiomatic C" code. Your code is beyond terrible. But by all means, continue ignoring the reality in favor of your infallible logical proofs, you'll fit right in /autism/.

>>29
Maybe if the screen is much larger than 80x24.

You mean, like all modern screens?
My current terminal is 120x40 in linux, 153x46 in VirtualBoxed windows(it uses smaller font) and I'm too lazy to measure console in my dualbooted windows. But it's nowhere near 80x24

>>30
That would be too slow. Monsters with huge ranged attack like
Meh. I'm not sure I believe that. Particularly with the kind of monster density you seem to be planning on, iterating through nearby monsters will probably be as fast or faster when searching the map as it is when pointer chasing through a quadtree of monsters, or whatever it is you have in mind.

>>29
That example was from NetHack (I think it's 78x21), but I've encountered even greater monster counts in TOME2.

It doesn't matter how many are visible.

>>32
Thank you for this shocking new information.

>>34
It doesn't matter how many are visible.
Of course it does. Monsters that aren't visible and can't be visible soon are prime candidates for faking.

>>36
Would blinding yourself make all monsters disappear?

I can't implement normal structure for monsters
Therefore I will fake them

Don't listen to this guy, OP. He bad influences on you.

>>37
Wow. If it would make you disappear, I'd blind myself now.

>>39
U buttranged?