#55279 - ChronicImpact - Tue Sep 27, 2005 11:48 am
Okay, I'm building my first serious game for the GBA, I've done some moderate games for the PC before, but now I'm really stuck on something. I know it's probably a very simple thing to do, but I just don't get it.
The game I've designed is a simple platformer, jump around, get to the goal. It works on a 16x16 grid, the player is 16x16, and each solid object is 16x16.
I realised that to display a portion of the screen I just track the position of what part of the room should be on screen and draw the sprites up, etc. I've got a simple class for each solid object, x and y values and if it's on screen or not. But I just don't have enough memory to store all the data.
Some of the rooms are 40x40 cells wide; so I'd have to have an array of around 10600 classes to cover all that data, and that doesn't even cover the full possibilities.
I've read up about methods of reducing the amount of space used, but everything seems involve grouping objects into sections that are repeated mutiple times... but my levels aren't as simple as to repeat sections. (I've already designed 50+ levels using a pre-built game engine on PC)
Is there some amazing way to make this easier, or a library I could be using? I'm coding in C++, and using Hamdev to compile. Please help me! *sob*
#55285 - APL - Tue Sep 27, 2005 1:37 pm
I'm not entirely sure I understand you, but Perhaps some sort of tree structure would speed up your searches significantly.
_________________
-Andy L
http://www.depthchasers.com
#55286 - ChronicImpact - Tue Sep 27, 2005 1:40 pm
My problem isn't with searching, my problem is arranging all the information for what goes where, and fitting it into memory. I can't just declare an array of classes with 1000+ elements, it chokes up the GBA. I need an easy way to set out the information.
#55290 - Touchstone - Tue Sep 27, 2005 2:13 pm
If each class only contain 3 elements, x, y and if it's on screen or not, then you could probably fit it into one short, given that you give the x and y values 7 bits, 1 bit for if it's hidden or not, and you'd have a spare bit for something else, that way you could get close to 21200 bytes of memory to store all that, obviously depending on memory allocation scheme and such.
What you basically need to do is:
1, Pack your elements as tight as possible (reduce the memory usage for each object)
2, Avoid virtual classes (each object of a virtual class contain a v-table of, I think, 4 bytes)
3, Allocate as many objects as possible at once (reducing memory allocation overhead)
If you pack all your object data into one short and allocate it ine one big chunk of memory you shouldn't have any problems with 10600 objects in memory at once.
_________________
You can't beat our meat
#55304 - poslundc - Tue Sep 27, 2005 4:43 pm
| ChronicImpact wrote: |
| My problem isn't with searching, my problem is arranging all the information for what goes where, and fitting it into memory. I can't just declare an array of classes with 1000+ elements, it chokes up the GBA. I need an easy way to set out the information. |
Put your data in EWRAM. You have 256K of that. Say you left your values unpacked as 8 bits x, 8 bits y, and 8 bits of flags, then 1600 elements would consume 38K... not so bad.
That said, is there any reason you need to track the state of every cell of every object that's not onscreen? Maybe you need an "immutable" cell type for the 95% of cell data (in a platformer like Mario, anyway) that can just be loaded out of the ROM when it happens to be displaying on the screen, and won't ever change because of player actions.
Dan.
#55319 - ScottLininger - Tue Sep 27, 2005 6:47 pm
You shouldn't have any problem declaring 1000+ cells worth of data, so long as they are declared as static. Then they'll be stored on the cart instead of memory.
I'm not an OOP programmer on the GBA, so I simply don't know whether class instances can be declared this way. I would *think* so, but I could be wrong. The key question is whether your cell data needs to change dring play. If so, then static data won't work for you, since you can't change cart data at run time. (At least, not without some hairy, slow, and cart-specific register writes.)
I think most platformers use "flat" tile data for the tile maps, with a separate meta-data array that records properties of a given tile. (i.e. all "Wooden Block" tiles (say, tiles 31-45) are solid, so the characters won't fall through them.) Then your map data doubles as your world data, if that makes sense. For anything that changes in such a world during play, use RAM meta tiles or sprites or both.
Of course, with your OO code, it's probably very compartmentalized and easy to understand, but even with flat arrays of data, you can accomplish some of the same elegance with well-designed functions.
If you want to keep your class structure the way it is, would a linked list save you some entries? I presume that a large portion of your cells and/or tile entities would be empty, so you could save some RAM by only storing the data for your active entities, such as platforms and characters and such.
Hope any of that rambling helps in some way. :)
If you post a demo of a small level, it might help us understand better what you're trying to accomplish.
Cheers,
Scott
#55320 - poslundc - Tue Sep 27, 2005 6:50 pm
| ScottLininger wrote: |
| You shouldn't have any problem declaring 1000+ cells worth of data, so long as they are declared as static. Then they'll be stored on the cart instead of memory. |
Const?
Dan.
#57458 - phirewind - Sun Oct 16, 2005 3:23 am
I use a 2d array of bytes for the collision info used in my current test project: http://www.codesmiths.net/stuff/09_invasion_begins.gba (it's pure AI driven, just press ENTER and watch the one alien eventually take over all humans).
My tile information is very simple. I have an array that stores a list of my AI, up to 127 of them. I then have an array that stores up to 127 objects, such as power-ups, switches, keys, etc. Then each tile contains the type and array index of whatever occupies it in 8 bits, like this:
0 0 0 0 0 0 0 0 = Empty.
1 0 0 0 0 0 0 0 = Wall
0 n n n n n n n = Object, referenced by index (n) in the object array (n is greater than 0)
1 n n n n n n n = AI, referenced by index (n) in the AI array (nis greater than 0)
Example...
Tile location 22,15 is checked and stores the following bits: 1 0 1 1 0 1 0 1
This means that the tile contains an AI, which is number 53 in the AI storage array. I can then access "ai[53]" and check it's properties to see what kind of AI it is, what it's "mental state" is, etc. and make a decision based on that information. For a 40x40 room, this array would need 1600 bytes, or 1.6 KB.
I may eventually dump my 2d array for a virtual map and pixel-line pings for sight to increase intelligence and mobility, but for a tile-based game like you describe it should be fine.
If you needed to apply more detail, you could use 16-bit values to allow for more bits to denote the object type and index a larger array, perhaps the first 4 bits to denote up to 16 types of objects and 12 bits to support 4096 individual objects per type. However, that would be freaking insane to require that many intelligent objects at once. A combination might be this: use a 16-bit number, with the first 8 bits to denote a type of tile (up to 256 types), and use standard background tiling and scrolling methods to create the background and move it via global scroll amount variables. Then use the second 8 bits the way I do to track whether or not something can move into that space, and what's in there. That would only take 3200 bytes (3.2KB), and should be plenty since you can only have 128 sprites onscreen at once anyway, and you shouldn't be using sprites to create the background, so that means 128 moving objects onscreen at once.
If you need more than 128 "thinking" objects to be "alive" then use a 32-bit value per location, but still just use a 2d array like "tileinfo[x][y]" to keep the referencing simple, then you'll have to have your own managment sytem in the object structure to determine what's onscreen and actually needs a sprite dedicated to it, and be sure and clear unneeded sprites so you don't flood the memory.
Also, if I understand correctly you're using a different struct for each tile. Don't. Use 1 struct for each object type, i.e. 1 struct for tiles, 1 struct for AI's, etc. The struct for AI's and player units could contain an x, y, location, as well as an indicator for what type it is, what data each instance should store, etc. Tile struct could just be a pointer to the bitmap it uses, whatever game-altering properties it might have, etc. Making a "re-usable" struct means you can make a single array that can be indexed to use the method I described as a quick-reference system so you do little to no looping to find the information you need, and store as little duplicate information as possible.
#57617 - sgeos - Mon Oct 17, 2005 12:02 pm
Put as much as you can in ROM. You might want to consider the fly weight design pattern. You'll probably want a class heirarchy that allows certain objects to be lighter that others. (C++ does have interfaces, right?)
-Brendan
#57668 - poslundc - Mon Oct 17, 2005 6:29 pm
| sgeos wrote: |
| Put as much as you can in ROM. You might want to consider the fly weight design pattern. You'll probably want a class heirarchy that allows certain objects to be lighter that others. (C++ does have interfaces, right?) |
It sort of does... it allows you to specify class methods as being pure virtual, which is the essence of what an interface is, but beyond that it doesn't make a distinction between classes and interfaces.
I think a full Flyweight system might be overengineering for most GBA tasks, although the basic principle of lightweight classes is sound.
Dan.