Entities and linked lists…

The overall system of the game is going to be built roughly similar to the pygame version. However, with switching to a language where memory is actually important, managing a dynamic number of entities requires managing a dynamic chunk of memory. Not having linux/being too lazy at the moment to get a linux worksetup going means I dont have valgrind to profile the memory usage either. 😦

Ah well, at the moment, a basic linked list is in place for entity management. Put simply, the plan is that anything declared to be “on screen” or, very close to the screen (within a z level, or two adjacent maps, X number of tiles away from the border, what have you) will be processed using this list.

You can find plenty of linked list tutorials out there, so I won’t go into too much detail, but put simply a linked list is a list (or array) of objects/items that are linked via pointers. To iterate through them, you can simply make a pointer (called ptr), and traverse through the list by setting ptr equal to some root or head node, and then repeatedly calling ptr = ptr->next, where “next” is itself a pointer to the next item in the list.

Pointers (and linked lists…or some form thereof) are necessary because arrays require you to know how many elements you want. With a list and dynamic memory, you can (efficiently) make an arbitrarily sized array, at the cost of some mental complexity in juggling around pointers.

On the actual game end, I’ll end up using this list to handle entity processing, as already said. For each entity determined to be on screen, change their location according to their AI package.

In addition to this, I want to add in some basic collision detection – which is tricky. Currently “collision” is handled via checking the heightmap, but that’s obviously not going to work when you’re wandering around a city.

I could have another 2d array that is populated with ints corresponding to tiles (and collision information by extension), like the pygame project had. But, I could make perhaps a 2d array of pointers, each of those pointing to a linked list representing everything on that tile.

Even when I get collision in, eventually I’m going to have a dynamic array of monster-entities floating around the map, item-entities taking up cells, and tiletype definitions. Having multiple arrays for each would be aggravating, but so might be juggling around pointers to handle movement… Pointers seem like the most logical solution, though.

Game design itself is going to be rewritten away from fantasy, at least for now. Zombies might be quicker to implement. But I’m still just getting the ‘machine’ itself running, so I dont have to worry about that too much at the moment.

Memory, Python, and You.

Rather recently I learned about a handy little program called Valgrind. I get to use it to debug some C++ code that works with dynamic memory to fix any leaks that occurred. As it turns out, this program can do a lot more.

Something I’ve noticed for a while now is that Graff takes up a pretty significant amount of memory–around 40 megabytes of RAM. I never really thought about it too hard until now, but I discovered that with the command:

valgrind --tool=massif python Start.py
ms_print massif.out.** > output

it takes snapshots of Graff’s memory usage. The first time running this and opening up “output” gives this result:


So currently I get ~43MB usage of the heap (or in python terms, plain memory) by just opening up the program and running around. Later in that output file, I notice a lot of calls to “SDL_CreateRGBSurface (in /usr/lib/libSDL-1.2.so.0.11.2)” seem to be eating up the most memory percentage-wise.

Doing some digging, I find out pygame converts images into a .RAW format for fast blitting–unfortunately, the file size is pretty hefty. Looking through my code, I notice that within Entity.py, when an entity is initialized, it loads up a file called “tiles.png” to pull the entity’s picture out of that and use it. After that, that loaded image is just kept there, permanently until the program quits. Tiles.png is only 42.3KB, though, which seems a little weird.

I decide to see just how many times entity loads up this image and stores it away forever. It turns out that this file is being loaded around 200 times, and is then saved as a member variable “self.sheet”. Since we don’t need it anymore once the entity’s image is ripped out of that sprite sheet, I decide to add one extra line to my code:

delete self.sheet

, after the entity’s image is set. What does that memory chart look like now?


15.64 MB is now used. By adding one extra line of code to delete an unused part of the code, I cut memory usage by 2/3!

Tinkering around some more, I find the pygame init routines take up a total of about 5MB, which means the code portion that I wrote takes up about 10MB of RAM. Perhaps now I’ll start paying attention to where memory ends up in Graff.