Sign in to follow this  

best datastructure for tile-based 2D map.

This topic is 4213 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 ...

Share this post


Link to post
Share on other sites
you could use 2d array of clas, like:

CTileClass myClass[100][100];

where
class CTileClass
{
public:
bool bPassable;
CTriger myTriger;
CTileObject myObject;

//etc...
};

Share this post


Link to post
Share on other sites
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.

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 MapMode





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]

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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).

[quote="ehmdjii"]
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?
[/quote]


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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
for layers that are completely full i chose a 2d array of objects

for layers that are not full and dont need to maintain a matrix like structure i chose a B-Tree. (red black implementation)

this has worked fairly well since the btree layers are very fast to order nodes....when a sprite moves...i just modify his position, remove him from the tree and add him back. btree is always ordered on x,y location, ordered first by y then by x.

Share this post


Link to post
Share on other sites
In regards to whether you should use a quadtree or grid array or what...

The best way to choose the structure of any data is to first determine how you'll be accessing the data, in other words, what algorithms you'll be running against it.

In the case of a 2D, tile-based game, the most common query usually is "give me all the tiles on the screen," or "give me all the tiles within this rectangle" more generically. This is what leads folks to choose a quadtree: quadtrees are incredibly efficient at doing bounding box queries against a 2D spatial data set.

But more accurately, quadtrees are best suited for doing bounding box queries against a *sparse* or *irregular* 2D spatial data set, like scatter graphs. For a tile-based game, this is both appropriate and inappropriate.

It's appropriate for the objects in the game as the ratio of objects to tiles (tiles == ground/environment, usually static) is usually pretty low (1:100, 1:1000 depending on the gameplay). It's inappropriate for the tiles, as their ratio to tiles is (suprise, suprise) 1:1.

If your tiles are laid out on a regular grid, and the tiles are basically continous (including things like l-shaped or arbitrary-shaped worlds, but still continous like Diablo), then a quadtree is "dumb" for the task of doing bounding box queries. Since the tiles are laid out on a regular grid, it's much faster (and requires less space in memory) to simply "do the math" to get offsets into your array.

But, you say, that L-shaped world is going to have a huge amount of wasted space! That's when you get a bit smarter: you break your world up into sections, where each section is a rectangular grid, and each section is linked to other sections (think of it like a 2D portal system). Now you can have arbitrarily-sized worlds without slowing down any of your queries. You simply keep a list of currently visible sections, then perform a grid-based query against each section to determine which tiles in it are visible.

How do you know which sections are visible? Well, you *do* know which section is the first one visible. And every section does know which sections it links to. In fact, each section will likely only link to a handful of other sections. So, when you do the bounding box query you check and see if it goes outside of the bounds of the current section. If it does, you then check the query against the connected sections. If it passes on the connected sections, then you add those sections (whichever ones it passed on) to the list of current sections. If you find that your sections have lots of connecting sections, then you may want to be a bit more clever in how you structure list of connecting sections (such as separating it into north, south, east and west sections, etc.).

A lot of good techniques have been developed to prune down 3D geometry for 3D games... nearly all of them apply equally well (or even better!) to 2D games! ;)

Share this post


Link to post
Share on other sites
thank you for your elaboration, but my original question is still not answered and this still keeps me from choosing a quadtree:

"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!

Share this post


Link to post
Share on other sites
AFAIK the only way is to store references to neighbouring tiles. I would also point out that partitioning down to individual tiles, is a _very_ bad idea from a memory and cache utilization standpoint (trust me, I've tried doing down to pixel size - it's not pretty bringing a 2.5GHz machine to its knees!)

What I would suggest is going for a hybrid solution: a quadtree that stores 2d arrays of tiles in its leaves. This method combines easy navigation within a leaf with the adavantages of using a quadtree. Inter-leaf navigation is a bit more complicated (or rather, quite complicated), but it should not be necessary for most games (strategy games being a notable exception). It can be done (for example by using references to neighbouring leaves), but it probably is not worth the added complexity unless absolutely necessary. A good compromise would be making the array size for leaves bigger.

Share this post


Link to post
Share on other sites
Quote:
Original post by ehmdjii
"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!


With quadtrees, you usually don't work with individual tiles. You feed it your screen rectangle which will automatically yield everything visible. What I personally do to optimize the whole process is to store those visible tiles in a screen-sized 2D array so other objects can quickly do lookups too without traversing the tree over and over. This way you can do neighbour-lookups easily too.

Hope this helps.

Share this post


Link to post
Share on other sites
If you are still a beginner, make it a 2D array (encapsulated in a class). Finish the game and everything. See what algorithms you need then change the nature of the class that implements the tilemap.

Share this post


Link to post
Share on other sites

This topic is 4213 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this