best datastructure for tile-based 2D map.
Author
hello,
i was wondering if a two-dimensional-array is still the best choice as datastructure for a tile-based map.
each tile should be able to store several states as well as have information about the object on it.
states could be:
_ispassable
_triggers event
...
objects could be:
_houses
_plants
_tile texture
...
you could use 2d array of clas, like:
CTileClass myClass[100][100];
where
class CTileClass
{
public:
bool bPassable;
CTriger myTriger;
CTileObject myObject;
//etc...
};
CTileClass myClass[100][100];
where
class CTileClass
{
public:
bool bPassable;
CTriger myTriger;
CTileObject myObject;
//etc...
};
This is my personal opinion, but I don't think that there is a "best" data structure to represent a tile-based map. Choosing a good data structure is dependant on what you want your tile engine to be capable of, and if you're including low-end machines into your target audience then you need to think more about the performance/memory/capability trade-off. Since I'm feeling curiously verbose this morning, let me describe to you how I decided on the preliminary design for our tile-based engine.
Requirements
- Low-end PCs (1980s/90s) are included in my game's target audience
- Emphasis is on good performance, with a secondary emphasis on minimizing memory usage
- I want tremendous flexibility so that we can create virtually any animated sequence on the map
Design
After some initial design discussions with members of my team and experimentation, we came up with this preliminary design. This design (along with scripting support) allows us the flexibility to do pre
Tile Layers (3)
1. Lower Tile Layer
used for tiles that represent the ground, or tiles that should always be drawn below map objects
2. Middle Tile Layer
tiles used to put variation and detail on top of lower layer tiles. Also used for map lighting.
3. Upper Tile Layer
tiles for effects such as smoke, or for the top of large walls that sprites may walk behind. Upper layer tiles will always be drawn over map objects on the ground.
Sprite/Object Layers (3)
1. Ground Object Layer
used for objects that are affixed to the ground.
2. Pass Object Layer
special objects which may be drawn above or below ground objects, such as bridges.
3. Sky Objects
objects that are positioned in the sky and are drawn over all other objects and tiles. (birds, clouds, gryphon riders, etc)
Drawing Order
1. Lower Tile Layer
2. Middle Tile Layer
3. Ground Object Layer (first pass)
4. Pass Object Layer
5. Ground Object Layer (second pass)
6. Upper Tile Layer
7. Sky Object Layer
This allows us enough flexibility in our design that we can do pretty much anything we have planned for a scripted map sequence. So now lets get into how these are represented in code (C++ engine, Lua scripting)
Code
This source code is available here under the GPL license. At the link below. Browse to "src/modes/map/" for map-related code and "dat/maps/" for some sample map scripts. I'll post the relevant snippets here
Allacrost SVN repository
So to represent a map tile, we have this class. It contains 3 16-bit integers (one for each layer) that refer to tile images stored in a vector. We also have a mechanism here for determining tile properties such as walkability, but I don't want to get into that discussion because we use a somewhat abstract concept called "map contexts", where a tile may have different properties in each context.
For checking if a tile triggers an event, in the past I did have members in this class that contain pointers to map events to execute on certain conditions (such as the player walks onto the tile). However we have decided to move this event checking into the map script rather than the map engine.
(I'm not going to post my MapSprite class because its not as easy to understand, so just assume that I have a class that represents sprites)
Now here is the class that manages the entire map. Notice first that I store all of the tile images in a single 1D vector (the ImageDescriptor class is a base class for both still and animated images, but I'm not going to get into the details of the video engine). Next, you'll see that we have a 2D vector of MapTile class objects. All of the objects in here contain multiple indeces into the _tile_images vector.
Not all the tiles for each later need to be defined (ie, they don't need to refer to a tile image). Rather than do a list or another data structure, we stuck with a vector because we wanted linear access times. In the draw code all you have to do is check "does this tile point to a valid image on this layer?" and draw the tile if the answer is yes.
Our map objects (== map sprites), right now we just store them in simple 1D vectors, but I may change that in the future. When its time to draw an object layer, first we make sure that the objects are sorted in the proper order so that they are drawn in the correct way (ie, one is not drawn over the other in an incorrect way).
I hope that gives you some ideas. I wish I could talk about this more, but I've been really busy at work lately and haven't found the time to really put together a final design for my map engine. Good luck. [smile]
Requirements
- Low-end PCs (1980s/90s) are included in my game's target audience
- Emphasis is on good performance, with a secondary emphasis on minimizing memory usage
- I want tremendous flexibility so that we can create virtually any animated sequence on the map
Design
After some initial design discussions with members of my team and experimentation, we came up with this preliminary design. This design (along with scripting support) allows us the flexibility to do pre
Tile Layers (3)
1. Lower Tile Layer
used for tiles that represent the ground, or tiles that should always be drawn below map objects
2. Middle Tile Layer
tiles used to put variation and detail on top of lower layer tiles. Also used for map lighting.
3. Upper Tile Layer
tiles for effects such as smoke, or for the top of large walls that sprites may walk behind. Upper layer tiles will always be drawn over map objects on the ground.
Sprite/Object Layers (3)
1. Ground Object Layer
used for objects that are affixed to the ground.
2. Pass Object Layer
special objects which may be drawn above or below ground objects, such as bridges.
3. Sky Objects
objects that are positioned in the sky and are drawn over all other objects and tiles. (birds, clouds, gryphon riders, etc)
Drawing Order
1. Lower Tile Layer
2. Middle Tile Layer
3. Ground Object Layer (first pass)
4. Pass Object Layer
5. Ground Object Layer (second pass)
6. Upper Tile Layer
7. Sky Object Layer
This allows us enough flexibility in our design that we can do pretty much anything we have planned for a scripted map sequence. So now lets get into how these are represented in code (C++ engine, Lua scripting)
Code
This source code is available here under the GPL license. At the link below. Browse to "src/modes/map/" for map-related code and "dat/maps/" for some sample map scripts. I'll post the relevant snippets here
Allacrost SVN repository
So to represent a map tile, we have this class. It contains 3 16-bit integers (one for each layer) that refer to tile images stored in a vector. We also have a mechanism here for determining tile properties such as walkability, but I don't want to get into that discussion because we use a somewhat abstract concept called "map contexts", where a tile may have different properties in each context.
For checking if a tile triggers an event, in the past I did have members in this class that contain pointers to map events to execute on certain conditions (such as the player walks onto the tile). However we have decided to move this event checking into the map script rather than the map engine.
class MapTile {public: //! \name Tile Layer Indeces //! \brief Indeces to MapMode#_tile_images, mapping to the three tile layers. //! \note A value less than zero means that no image is registered to that tile layer. //@{ int16 lower_layer; int16 middle_layer; int16 upper_layer;}; // class MapTile(I'm not going to post my MapSprite class because its not as easy to understand, so just assume that I have a class that represents sprites)
Now here is the class that manages the entire map. Notice first that I store all of the tile images in a single 1D vector (the ImageDescriptor class is a base class for both still and animated images, but I'm not going to get into the details of the video engine). Next, you'll see that we have a 2D vector of MapTile class objects. All of the objects in here contain multiple indeces into the _tile_images vector.
Not all the tiles for each later need to be defined (ie, they don't need to refer to a tile image). Rather than do a list or another data structure, we stuck with a vector because we wanted linear access times. In the draw code all you have to do is check "does this tile point to a valid image on this layer?" and draw the tile if the answer is yes.
Our map objects (== map sprites), right now we just store them in simple 1D vectors, but I may change that in the future. When its time to draw an object layer, first we make sure that the objects are sorted in the proper order so that they are drawn in the correct way (ie, one is not drawn over the other in an incorrect way).
class MapMode { //! A vector containing the image for each map tile, both still and animate. std::vector<hoa_video::ImageDescriptor*> _tile_images; //! A 2D vector that represents all of the map tiles. std::vector<std::vector<MapTile> > _tile_layers; //! The set of ground map objects. std::vector<private_map::MapObject*> _ground_objects; //! Objects that can be both walked under and above on (like bridges). std::vector<private_map::MapObject*> _pass_objects; //! Objects that are drawn in the sky above everything else. std::vector<private_map::MapObject*> _sky_objects;}; // class MapModeI hope that gives you some ideas. I wish I could talk about this more, but I've been really busy at work lately and haven't found the time to really put together a final design for my map engine. Good luck. [smile]
For huge maps with lots of empty spaces in it, a quadtree is a good solution. You should definitely give it a try, as this concept is widely used and can be extrapolated to 3D sceneries too. It's also a good excercise in writing recursive routines :)
Agreed. That would make things like tile collision and rendering far easier, and a lot faster than traversing lists etc...
Remember though not to store blank tiles. In your CTileMap class, have each tile have a 'visible' property. If this property is false, then don't even have a CTile or whatever in that slot. Memory is still a very important factor to an applicaiton, just like speed is.
Even better would be to have a list of all tiles that are used in the current map. The CTileMap class would simply store the tile indexes to use. Then when it comes to accessing a tile for collision, rendering etc... you would simply access your tile array. This method is a very good method because you will only ever have one instance of a certian tile. If though, you need to same tile to have seperate properties, such as decals, events etc..., then store these along with the tile indexes in the CTileMap class. How you would store these properties would depend purely upon what they are.
Remember though not to store blank tiles. In your CTileMap class, have each tile have a 'visible' property. If this property is false, then don't even have a CTile or whatever in that slot. Memory is still a very important factor to an applicaiton, just like speed is.
Even better would be to have a list of all tiles that are used in the current map. The CTileMap class would simply store the tile indexes to use. Then when it comes to accessing a tile for collision, rendering etc... you would simply access your tile array. This method is a very good method because you will only ever have one instance of a certian tile. If though, you need to same tile to have seperate properties, such as decals, events etc..., then store these along with the tile indexes in the CTileMap class. How you would store these properties would depend purely upon what they are.
Directly indexing a 2d array of tiles would likely be faster than a quad tree for a 2d game, and certainly easier. Quad tree is overkill for a 2d tile based game imo. Depends on the game I suppose.
Quote:Original post by DrEvil
Directly indexing a 2d array of tiles would likely be faster than a quad tree for a 2d game, and certainly easier. Quad tree is overkill for a 2d tile based game imo. Depends on the game I suppose.
It depends on the type of map the game will use. For small maps that only span a couple of screens this may be true, but consider an L-shaped map which goes 5000 tiles down and then 5000 tiles to the right. Using a regular 2D array you would have to allocate 25 million tiles, and use only 0.04% of the allocated memory. Not very efficient, especially if you're aiming at less-capable hardware (archaic PC's, handhelds etc). With a quadtree, you get free compression while the mapsize is virtually unlimited. You can also have quadtrees of quadtrees, and swap them in/out on the fly to create maps bigger than the universe.
But again, it totally depends on what you're after. However, once you have written a good quadtree solution, you will find it will work equally well on even single-screen maps without considerable overhead. The code is also highly reusable as most 2D games are tile-based anyway. Of course quadtrees aren't the only solution to the problem but in my experience they work very well.
Author
thank you all!
when using a quadtree, how is it possible to determine the neighbouring tiles?
like when i want to define a path: go north twice, then east, then south three times, ...
if the map is rectangular, what about the possibility to store it as a one dimensional array? and index it using multiplication and modulo. is that a good idea, since one dimensional arrays are usually faster?
thanks!
when using a quadtree, how is it possible to determine the neighbouring tiles?
like when i want to define a path: go north twice, then east, then south three times, ...
if the map is rectangular, what about the possibility to store it as a one dimensional array? and index it using multiplication and modulo. is that a good idea, since one dimensional arrays are usually faster?
thanks!
I agree that for most cases, quad trees are overkill. However for very large maps (such as a RPG world map), I believe that they should be used. Again, choosing the best data structure really depends on your target platforms and design criteria (== how complex/flexible do you want your maps to be).
Short answer
No, it wouldn't make it faster and its not a good idea.
Longer answer
No it wouldn't make it faster (or if it does, it wouldn't be by much). You are assuming that you will be accessing that 1D array in a linear fashion, but in almost all cases you're going to: (1) read a group of elements in the array, (2) "skip over" many more elements to find the next one you're interested in (either a tile's neighboor, or a new row of columns to draw on the screen). Because of step (2), the processor won't have the next elements already loaded into its cache when you request to access it (because you're not taking advantage of data locality anymore).
There might be some special cases, for example if you access tiles in a very consistent and repetitive pattern and the processor your game is running has decent data prefetching in the architecture, but then you'd be relying on a mechanism that is not as prevalent across processor architectures like basic data caching is.
If you don't understand what I just said, you should study up on computer architecture if you're really this concerned about performance (or just a pedantic perfectionist such as myself. [wink]). IMO (and experience): don't try to squeeze every last drop of performance out of your design if it requires an extensive amount of work compared to an almost-as-good and simpler design. It's too costly and not worth the effort.
ehmdjii said:
if the map is rectangular, what about the possibility to store it as a one dimensional array? and index it using multiplication and modulo. is that a good idea, since one dimensional arrays are usually faster?
Short answer
No, it wouldn't make it faster and its not a good idea.
Longer answer
No it wouldn't make it faster (or if it does, it wouldn't be by much). You are assuming that you will be accessing that 1D array in a linear fashion, but in almost all cases you're going to: (1) read a group of elements in the array, (2) "skip over" many more elements to find the next one you're interested in (either a tile's neighboor, or a new row of columns to draw on the screen). Because of step (2), the processor won't have the next elements already loaded into its cache when you request to access it (because you're not taking advantage of data locality anymore).
There might be some special cases, for example if you access tiles in a very consistent and repetitive pattern and the processor your game is running has decent data prefetching in the architecture, but then you'd be relying on a mechanism that is not as prevalent across processor architectures like basic data caching is.
If you don't understand what I just said, you should study up on computer architecture if you're really this concerned about performance (or just a pedantic perfectionist such as myself. [wink]). IMO (and experience): don't try to squeeze every last drop of performance out of your design if it requires an extensive amount of work compared to an almost-as-good and simpler design. It's too costly and not worth the effort.
Author
thank you for your idea.
i still would like to clear that one thing up: :)
"when using a quadtree, how is it possible to determine the neighbouring tiles?
like when i want to define a path: go north twice, then east, then south three times, ..."
thanks!
i still would like to clear that one thing up: :)
"when using a quadtree, how is it possible to determine the neighbouring tiles?
like when i want to define a path: go north twice, then east, then south three times, ..."
thanks!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
