gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Game Design > Platform game architecture

#32097 - Steve++ - Sat Dec 18, 2004 3:49 am

I'm designing a platform game engine. I started with a simple tile engine (able to scroll very large tile maps with multiple layers). Then I saw a post by tepples; he said that instead of designing tilemaps, we should design maps of objects - objects being A tiles high and B tiles wide. A level would be rendered using a compositor that draws the objects on the screen.

This got me thinking very deeply about the architecture. I'm definitely going with this idea. The foreground layer - where everything happens - will be encoded as a list of objects. The problem is that, if there is just one single flat list of objects, every frame the compositor must traverse the entire list and draw any objects in display range. I've thought of a simple optimisation (which I'm sure I've seen before):

Each level will be divided into a grid. Each cell in a grid will have a size of, let's say, 16*16 tiles. Each cell will contain a list of objects which it contains. In ROM, there will still be a single list of objects for each level. The cells' lists will be generated as part of the level loading process.

This also works for moving objects (sprites). As they move around the level, they must register and deregister themselves with cells. This optimises collision detection. One approach is to say that an object belongs to a cell if its origin pixel (top-left) is in that cell. This means that to test for collision, we'd need to check against every object in the host-cell, then every object in all the surrounding cells. The other approach is to say that an object belongs to a cell if at least one of its pixels is inside the cell. Assuming that the maximum object size is the same as the cell size, each object will belong to one, two or four cells. That way, collision testing is minimised, but in the worst case scenario, four times the memory is used for linked lists.

On the topic of linked lists, I'm not using the STL list template. I'm designing an object pool template that uses a stack to allocate and deallocate an object. This results in zero memory fragmentation. The beauty of this is that all the cells' linked lists will draw from the same object pool, whereas the best the STL list template can do is create one pool per list instance. This is a topic for another forum...

I would like to know if my idea is a bit too extreme and could be simplified to make better use of memory without too much CPU overhead. In other words, is this a sledgehammer approach or am I on the right track? I welcome any suggestions, improvements, critiques, etc.

- Steve

#32174 - Lord Graga - Sun Dec 19, 2004 12:45 am

16x16 would take up a *huge* amount of ROM space. I would use 64x64 instead, since it would take up less ROM space and be faster to process.

#32179 - Steve++ - Sun Dec 19, 2004 2:29 am

Wouldn't that be RAM space? The ROM would just contain a list of objects and their absolute location in tile coordinates. The grid would be created in RAM. This is so other (moving) objects can be dynamically added to and removed from cells.

Thanks for the tip about cell size. It's all about balancing RAM and CPU. Each cell will have two linked lists (static and moving objects), each of which is just a pointer to the first node in the list. So that's 8 bytes per cell. Cells of size 64x64 will take 16 times less RAM than 16x16. I was also thinking of 32x32 because that's the closest to screen size. The screen could be just another moving object in the world. That way I could easily script collision actions with the screen, so that for example, off-screen enemies would stop moving.

I'm playing with the idea of having static and moving objects in the same linked list. Each cell would then only consume 4 bytes (one 32-bit pointer). The problem with that is collision testing would occur between static objects. That's easy enough to fix though.

You said 64x64 would not only take up less space, but be faster to process. I tend to disagree with that. Smaller cell sizes lead to less off-screen objects for the compositor to process and (typically) less collision detection tests.

Thanks for the suggestion.