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?)
>>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.
>>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.
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.
>>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.
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++.
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.
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.
>>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.
Name:
Anonymous2011-02-12 14:16
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.
>>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.
Name:
Anonymous2011-02-12 14:46
>>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.
>>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/.
Name:
Anonymous2011-02-12 14:52
>>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
Name:
Anonymous2011-02-12 14:53
>>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.
Name:
Anonymous2011-02-12 14:53
>>29
That example was from NetHack (I think it's 78x21), but I've encountered even greater monster counts in TOME2.
>>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.
Name:
Anonymous2011-02-12 14:59
>>36
Would blinding yourself make all monsters disappear?
>>38
No, really. Starcraft(1st one, I never played 2nd) can calculate at least thousand of units in real time without faking. You are doing turn based game.
Name:
Anonymous2011-02-12 15:13
>>41
OP asked for "thousands of". Not "a thousand".
>>31 does contain horrible, misleading code,
How many times have we been over this? The whole point of the post was that misleading code is a problem, of course it contains an example of exactly that. I've explained that a few times already, including the very same post the code appears in.
>>42
FWIW, I had a simulator running ~300,000 object simulations/sec., executing transcendental computations on about 16 different attributes plus branching code running on an ARM chip clocked at 66MHz with no FPU. Unless you plan to do something obscene like solve path finding completely each frame for each entity or get into very high numbers of entities I don't see a problem brewing if you are targeting desktop typical systems with 1920x1080 displays.
• while it's true that you can only ever see a screenful at a time, i'm going for a DWARF FORTRESS-like game (or simulation), where you command multiple hundreds of @'s. i want to see how far i can take this without faking things.
• the terrain will be saved as a two dimensional array and accessed through a map_(x,y) macro so that later on we can add support for an infinite world.
• a tile is a single byte, and holds all information necessary for path-finding: 4 bits for terrain type, 1 bit for walkable, etc...
• i can update the code in >>12 to use a bona fide memory pool that allows indices to data (as per >>19 and wikipedia).
• i'll write a quadtree for a mapping of position -> game object index. i'll probably end up using another memory pool for the nodes inside the tree.
Name:
Anonymous2011-02-12 16:53
>>45 The whole point of the post was that misleading code is a problem, of course it contains an example of exactly that. I've explained that a few times already, including the very same post the code appears in.
You still don't get it.
The code itself is not the problem. It is a consequence.
The moment you decide to pass a pointer to some kind of nul-terminated array because that's "C style", you get horrible code ridden with problems that you can heroically overcome and discuss with other brain damaged people.
The moment you decide to pass a proper array with length and an index, you are practically destined to write good code. At least you are guaranteed to avoid every problem of the documented in >>7.
Look: since code like this is a little unclear about intentions
Miss.
It's better to use a struct member to indicate that it's the last item
Miss.
but you'll have to guard against exhausting the list.
Miss.
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.
Miss.
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.
I can't imagine what did you mean by "nonserial format", but it's a miss anyway.
When I say that you are an awful programmer I mean "programmer", not "coder". As a coder you did a good job: wrote some code, then demonstrated its various flaws. No questions about that.
Your brain damage manifested itself and doomed your efforts before even one line of code was written. And it seems that not only you are a terrible braindamaged programmer, but what's even worse, you don't realize there are decisions to be made before coding, which could produce all the difference in the world!
it seem the problem here is the * sizeof(union mem_block) part from the definition of offset. if i remove it, the code suddenly appears to work. at first i didn't understand this at all, but now i think it is because pointer arithmetic in C works like this:
int main()
{
grow_pool();
int i;
for ( i = 0; i < CHUNK_SIZE * 30; i++) store(i*2);
for ( i = 0; i < CHUNK_SIZE * 30; i++) unstore(i);
for ( i = 0; i < CHUNK_SIZE * 30; i++) store(i*2);
int d = store(123);
printf( "%d\n", mem_(d));
exit(1);
}
funny to see your own dead threads resurrected... who the fuck is >>58? also, here's the lastest version of the code:
[#]
struct mem_pool
{
unsigned int slot_size; // the size of each object in the pool
unsigned int pool_size; // the number of objects in the pool
unsigned int slots_left; // space left in the pool
void* pool;
void* ptr;
};
In pooled memory management, each allocation specifies a pool of memory from which it should be allocated. Each pool has a different lifespan. In Apache, there is a pool that lasts the lifetime of the server, one that lasts the lifetime of the connection, one that lasts the lifetime of the requests, and others as well. Therefore, if I have a series of functions that will not generate any data that lasts longer than the connection, I can just allocate it all from the connection pool, knowing that at the end of the connection, it will be freed automatically. Additionally, some implementations allow registering cleanup functions, which get called right before the memory pool is cleared, to do any additional tasks that need to be performed before the memory is cleared (similar to destructors, for you object-oriented folks).
To use pools in your own programs, you can either use GNU libc's obstack implementation or Apache's Apache Portable Runtime. GNU obstacks are nice, because they are included by default in GNU-based Linux distributions. The Apache Portable Runtime is nice because it has a lot of other utilities to handle all aspects of writing multiplatform server software. To learn more about GNU obstacks and Apache's pooled memory implementation, see the links to their documentation in the Resources section.
it seems no true c wizards exist on /prog/
i guess i'll become the first
>>67 Apache Also Subversion uses that shit, and it didn't help it any: it's as bloated enterprise as possible, and then some.
I can't comprehend how you came to the conclusion that Apache-style memory pools are appropriate for a "roguelike with thousands of NPCs". Then again, I stopped reading the thread midway because it was physically hurting me.
>>69
i'm not going to use those after all, i think i'll stick with my >>60. thanks for the valuable input though, i'll be sure to include you as a character in my game: i've decided to make my dwarf fortress auschwitz themed.
you'll be in control of nazi camp guards (soldiers technicians etc...) and you have to build barracks, gaschambers, ovens, gallows, prisons, etc.... and kill and burn all the J's (and j's). there will also be pink J's.
first the j's arrive in trucks but after awhile you get to build a trainstation to continually ship 'em in. you also get to have higher nazi commanders in your camp. the game ends when you've killed all the jews.
A free list is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next. It's most suitable for allocating from a memory pool, where all objects have the same size.
Free lists make the allocation and deallocation operations very simple. To free a region, one would just add it to the free list. To allocate a region, one would simply remove a single region from the end of the free list and use it. If the regions are variable-sized, one may have to search for a region of large enough size, which can be expensive.
Free lists have the disadvantage, inherited from linked lists, of poor locality of reference and so poor data cache utilization, and they provide no way of consolidating adjacent regions to fulfill allocation requests for large regions, unlike the buddy allocation system. Nevertheless, they're still useful in a variety of simple applications where a full-blown memory allocator is unnecessary or requires too much overhead.