Option 1:
// Class heavy approach. More function calls.
class cLayer {
char *data; // get data by using data[Column*Width+Row]
long texture;
}
class cMap {
cLayer* layer[3]; // or vector <cLayer*> layer;
}
Option 2:
// A middle thing. Not really that nice to work with...
typedef struct {
char tile;
} sTile;
class cMap {
sTile map[3][10][10];
}
Option 3:
// struct w/ height and layer info on each tile.
// Possible waste of memory?
typedef struct {
char num_tiles;
char height[10];
char tile[10];
char layer[10];
} sTile;
class cMap {
sTile map[10][10];
}
Option 4:
// Linked list
struct sTile {
struct sTile *next;
char tile;
};
Best map structure
Author
I've been messing around with an isometric tileengine and have been trying different ways of making the map. I began checking through the code in Jim Adam's Programming rpgs in directx. I later made most of the tilecode myself to get some practise and wrote the map structure in classes (Option 1).
I've later found out some shortcomings by checking the IsoMetrix engine and reading some articles on gamedev. If I were to make a height/layer array for each map coordinate I can stack things like walls on top of each other (Option 3).
What I'm really wondering is what would be the optimal way to go regarding memory use and speed of the game. Do I really have to worry much about it since the area won't be big enough to slow things down anyway? It seems like option 3 is the best way to go, or maybe a combination of options 3 and 4. It just seems like it will use a lot of memory because each coordinate has so many arrays.
These examples aren't complete, just to show what they would look like.
I wouldn't worry too much about optimizing this structure, I wouldn't expect it to have a big impact on your game's speed. It would be a good idea to keep the interface to cMap modular enough that you can come back later and tweak things if you need too.
Having said that, it doesn't hurt to think about this a little bit. I'd start by looking at how you are going to want to access the map data. There are probably 2 main types of operations which will use the structure: drawing the map (sequential access to all tiles) and collision / pathfinding (random access to a possibly large subset of the tiles). You may also be doing things like line of sight calculations, but that's going to have a similar access pattern to pathfinding.
The requirement for random access takes option 4 out, long linked lists aren't very good for non-sequential sorts of things. Options 1 and 2 will both work fine for random access, and there are only minor differences between them. I don't like that option 2 has a static size for them map, but you could make it dynamic like option 1 without any trouble. (map[layer * map_area + column * width + row]). The main difference is that you have a layer class in option 1. If layers are just a way to have a 3d grid of tiles then you probably don't need this, if you are going to do something more complex with them (independant scrolling, different sized layers, per layer attributes, etc.) then you may want a class for them. I don't understand what all the attributes of sTile in option 3 are for, but it looks like it will give you good random access.
In addition to random access you need sequential access every frame to draw the map. Arrays can be good for this to minimize cache misses, but you are going to want to avoid iterating through a sparsely populated array every frame. If some of your layers are mostly empty, you would rather not look at the empty tiles in the array when drawing. A linked list would actually work here, as long as it didn't contain entries for empty tiles. Since the map size probably isn't changing often (only at level load) you could use an array to hold the tile list as well, but each tile would need to know it's location in the world. Then you could iterate through the array and draw the tiles (you'll want them presorted).
The best option might be two structures: one to hold the map information for random access and one for sequential access. This would increase memory usage, but you wouldn't have to put the same information in both structures. The sequential map could simply have the information needed to draw the tiles, and the random access map could have pathing information. Or one structure could be an index for the other.
Whichever way you go I wouldn't but too much effort into optimizing this part yet. If you profile and find that you are spending a lot of time traversing the map then you can go back and fix it. I would avoid a linked list for random access though, that could be a problem when it comes time for pathing. Also if you come to a problem where you are wanting to use the same structure for two very unrelated tasks, consider spliting it into two structures more suited to the individual uses.
Having said that, it doesn't hurt to think about this a little bit. I'd start by looking at how you are going to want to access the map data. There are probably 2 main types of operations which will use the structure: drawing the map (sequential access to all tiles) and collision / pathfinding (random access to a possibly large subset of the tiles). You may also be doing things like line of sight calculations, but that's going to have a similar access pattern to pathfinding.
The requirement for random access takes option 4 out, long linked lists aren't very good for non-sequential sorts of things. Options 1 and 2 will both work fine for random access, and there are only minor differences between them. I don't like that option 2 has a static size for them map, but you could make it dynamic like option 1 without any trouble. (map[layer * map_area + column * width + row]). The main difference is that you have a layer class in option 1. If layers are just a way to have a 3d grid of tiles then you probably don't need this, if you are going to do something more complex with them (independant scrolling, different sized layers, per layer attributes, etc.) then you may want a class for them. I don't understand what all the attributes of sTile in option 3 are for, but it looks like it will give you good random access.
In addition to random access you need sequential access every frame to draw the map. Arrays can be good for this to minimize cache misses, but you are going to want to avoid iterating through a sparsely populated array every frame. If some of your layers are mostly empty, you would rather not look at the empty tiles in the array when drawing. A linked list would actually work here, as long as it didn't contain entries for empty tiles. Since the map size probably isn't changing often (only at level load) you could use an array to hold the tile list as well, but each tile would need to know it's location in the world. Then you could iterate through the array and draw the tiles (you'll want them presorted).
The best option might be two structures: one to hold the map information for random access and one for sequential access. This would increase memory usage, but you wouldn't have to put the same information in both structures. The sequential map could simply have the information needed to draw the tiles, and the random access map could have pathing information. Or one structure could be an index for the other.
Whichever way you go I wouldn't but too much effort into optimizing this part yet. If you profile and find that you are spending a lot of time traversing the map then you can go back and fix it. I would avoid a linked list for random access though, that could be a problem when it comes time for pathing. Also if you come to a problem where you are wanting to use the same structure for two very unrelated tasks, consider spliting it into two structures more suited to the individual uses.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
