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.

Short-term future.

I’ve since updated the map algorithm to provide rivers and more “whole” landmasses. I’ve also now got mouse support included into this “roguelike”, as controls now are WASD for movement, and the little guy will face the mouse location.

I think one of the next directions is to begin dealing with AI. This will require (roughly in order of importance):

dynamic queue for entity processing
pathfinding
AI packages:
follow/go_to
attack
flee
wander
AI schedule implementation

as far as schedules, a first pass attempt will likely be a schedule consisting of sleep->work->eat->play, where each state consists of a location to go to (sleep = bed, work = behind an NPC shop table, etc), time spent at each state, maybe special anims for working, and get that running. This largely depends on the follow/go_to implementation, which underneath that requires a good fast pathfinding algorithm.

Rebuild incoming…

Code’s been moved over to http://code.google.com/p/pet-project-code/. Use TortoiseSVN to download the code. For now, Windows only.

I’ll be rebuilding this in C with allegro, and things are now moving quite a bit faster as I’ve already done a good chunk of this before. One significant halt on my development is that pygame (and SDL) use an event queue to handle keyboard inputs. Allegro handles input in a brute-force kind of way, sort of like a while(c = getchar() ) type of system, plus some flags that tell you when keys are pressed or not. I’ve got a rough idea of how to go about fixing that, and for now I’m happy with what I’ve got.

Time is a completely different matter. If anyone uses microcontrollers, time systems in allegro are handled like an interrupt. Every Xth time increment, a special function you write gets called that you can use to manipulate time.

What changes will come? Gameplay-wise, things are going to be partially turn-based – basically an evolution of moving this thing into real-time, without it being too different from the standard fare. There’s going to be some hand-built maps, and I’ll try porting in my old python level generators into this current project. I’ve already got a worldmap generator that suits my purposes.

Time-wise, I’m going to try to do short stabs at the code throughout the semester, and see how that goes.

I’d write a post about the level generator, but it’s just an application of the diamond-square algorithm. This explains it pretty simply especially the picture:
http://library.thinkquest.org/26242/full/types/ch10.html

Why C? I spent a summer playing with C, and in theory I can write code that runs faster/more efficiently, as I have a decent idea of how C operates ‘under the hood’, rather than python.

Ideas…

Mechs. Zombies. Survival. Dwarf Fortress. AI.

I have an idea…

Release 0.0.8C

Got a quick chunk of time to play around with this again.  The minimap is now working properly, and that memory fix I talked about is now in.  The tileset may also have been tweaked, I’m not sure on that one.  Grab it here!

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.

Map generation #4.5 – tidying up some ends

In my last post about this map-making process, I seemed to have left off at the part where the image itself is generated in its own separate program. Converting this image into a matrix for use in Graff was relatively straightforward. Pygame’s surfarray module allows one to access a surface (the screen) and treat it as a matrix of color values. From there I pulled out the color, used a dict datatype to convert that color into a tile type, and then write that into a matrix for use with the Graff; that wasn’t much of a problem.

However, one glitch I’ve noticed is that often the map would have some holes in it–it seemed like the algorithm would skip over a tile, perhaps because it couldn’t find a properly-fitting tile, so sometimes you get things that looked like this:

As it turns out, that was the case. I simply did not make enough tiles to cover each possible combination. After thinking that I’d have to make a mind-boggling number of additions to the 6×6 tile pieces I already have, I edited the code so that if the tile it needed could not be found, it should spit out that key combination and then I’d see where that would take me. Altogether, only about 30 “impossible” combinations of tiles ever seemed to come up, so I just added those extra ones onto the tileset.

After doing that, the results are much cleaner. Some glitches still remain (mainly I missed a few combinations, it seems), and I’ll probably adapt this to work with a smaller scale (say 3×3 instead of 6×6) or make changes to it to develop other areas, but I think I’ve just about exhausted the usefulness of posting about this process.

Oh, there is also the problem of the map not always being one complete piece. I still haven’t decided in what way I’ll solve that one yet, but there are some more interesting questions about Graff that I think I need to find an answer to first.

0.0.8

Release here!

This’ll probably be the last update for a few weeks. Trying to go back to Python after spending a few weeks of working with C++ feels so..different. I might switch this project over to C++ if I get equated well enough with it, or maybe I’ll just start working on a C++ project instead and keep this around too. Busy busy busy. Either way, more activity will come in December or so.

The only glitch I’ve noticed with this release is the minimap is a little screwy. I know why it doesn’t work, but if I hold off on this until I fix it, it’ll be even longer before this post comes up.

CHANGES:
   Added a (barebones) title screen.
   Custom keybindings via title screen.
   Added “Key” py file and an ini file for manual editing if need be.
   Digging function cleaned up somewhat.
   Integrated new map generator.
      A fully glitch-free version is finished, I just need to update it.
   Changed scrolling/grass behaviors for more natural movement.
   Automatic screenshots placed in the Screenshots directory. Use the SCROLL LOCK key.

Additionally on that page under Misc, I’ve added in a dialog.py / dialog.txt file to show how my dialogue system will hopefully work. Run it through the terminal

Brief update.

Got some feedback on how the player movement worked and so I decided to switch it to the original idea I had–when the player gets too close to the bounds of the screen, then the screen recenters itself on the player, as opposed to re-centering every single time the player moves. Likewise the grass is now drawn so that it looks “attached” to the tile, instead of before where the grass appeared to just float under the screen like an odd parallax effect (see image; night sky is what the grass looked like if anyone hasnt tried out this thing).

Also, I’ve worked in the map generator into the game itself. It looks a bit weird, to be sure:

But I feel like currently that’s due to tileset issues and not necessarily the code. Don’t mind the odd looking minimap, still have a few kinks to work out.

Also, now I’ve got a way to output screenshots (properly labelled to boot) into a ‘screenshots’ directory when you press the printscreen key. Saves time when I’m on Windows, thats for sure.

Map generation #4

#4? Where’d #3 go? Post #3 would be useless because, from where I finished at #2, I’ve completely rebuilt the code in a separate file. Refactoring, joy.

Last time I posted, I had an algorithm that was reasonably good at generating a network of hallways. I don’t think I have any screenshots, but with some edits to the tileset, you can get some really wacky maps generated out of it, one of which could work as a ruined set of roads that I might save later, though I don’t have a picture of it. I’ll probably stash away that code file for later.

Put simply, most of the previous code followed this basic pattern:
make a matrix, and randomly assign an index to it, with the index corresponding to a certain image of a predef.
afterwards, go through and check each matrix cell for connections between predefs that should be there, and connect them.

The important part about it was that each index was a binary number from 0001 -> 1111. When you introduce in rooms, however, that scheme needs to be so modified that my “randomly do it and fix it later” approach fell to the ground. Not only do you have connections for 0 and 1 (nothing and hallway), you’ve got 2, 3, and 4 (room lower, room upper, room filled), and so the numbers just get rather large when trying to do it the old way. What I’ve got now, looks like this:

make a matrix of zeros
set the corner tiles to something that does not leave the grid and has 2 connections going inside
for each tile in the top row:
  pick a tile whose connection type (0,1,2,3,4) on the left of the tile matches that of the left tile's right side
for each tile in the left column:
  [repeat, checking upper tile instead of left tile]
for each tile inside the bounds of the matrix:
  [again repeat, checking upper and left tile's connections so they match up]
for each tile on the bottom row:
  [repeat, checking left tile, upper tile]

and so on, until the matrix has been filled, then draw the appropriate tiles to the screen in the right positions. So, instead of doing it all and checking it later, we’re immediately putting in a tile that is known to fit the previously known connections. What really delayed me was that the corners, top, left, right, bottom, and inside all check for different things–the top tiles have to set themselves to be a good tile who’s top is a 0 and left matches the adjacent tile; the inside tiles have to check the left tile and the top tile; the bottom row has to have a bottom of 0, match the top, and match the left tile, and so forth. As a result there wasn’t a very easy way for me to take all four of those action and combine them into one thing.

What’s the result now? Here are some shots of the same code, but with edits to the tileset.png part:

Option 1: Plain tiles

Option 2: Walls

Option 3: Tile edit 1

Option 4: Tile edit 2

There’s a few glitches in part because sometimes, it’s impossible to connect the right tile–that combination just can’t exist, so you get a few gaps there when defining say, the walls in that second picture in the bottom right–optimally all the white should be outlined by red. Eventually I might fix that, either by adding in those “impossible tiles” into the set or something else, though that’ll be saved for later. I’ll also have to re-check the code once more to see if there isnt just a simple glitch that’s getting in the way, too.

Regardless, the results themselves look nice to me. I have coded in place a way to (somewhat painstakingly) add in additional tiles. Compared to the generator that gave me the idea, if you select only Dungeon 1 tiles, the results are pretty close. If I want to change the distribution and say, add more hallways than rooms to a map, I could always add in additional hallway predefs, so that the random.choice will be more inclined to pick hallway connections than room connections. Likewise, the pictures above show how altering a few of the ~40 or so tiles can make the map look significantly different.

Where will this little thing go next? I probably won’t bother spending a post writing about it, but pygame has a surfarray subsection to the module that lets me convert pixels on an image into a numpy matrix. From there it’s rather trivial to integrate what I’ve got into the standard Map.py set of code I’ve got and get it playable.

Code of this and the dialogue system will be up on my other site..eventually.