Tilemaps: 2D-Array vs. Vector

2D array for clarity and the vector's algorithms aren't really needed with tile storing.

Depends on the game. One of my current project's requirements was a malleable map [otherwise, it should allow play in hex or square mode (ie, 6 neighbors, or 4|8 neighbors) as well as non-contiguous (think islands in space) maps], so fixed 2D was out.

The ony thing you want to avoid, is large maps using this type of implementation...

Tile tiles[600][600];

Such an implementation requires a large contiguous block of RAM that the target PC may not have availible.

A somewhat better solution is this...

Tile* tiles[600][600];

While this still requires a large contiguous block of RAM, you are only using 4 bytes per tile (the pointer to the tile data) instead of having the actual tile data required to be contiguous.

An even better solution (providing that you are not doing random access seeking on the array) is to use a linked list of tiles.

Either by having a 'link container' link to a Tile pointer, or having your tiles contain next links (and prev links if applicable).

Usualy when drawing a map you will be using sequential access on the list. But, if I remember correctly, certain pathfinding algorythms require random access to the list, linked lists do not provide very fast random access, and as such your random access speed will suffer.

So depending on your implementation, either method 2 or method 3 , AFAIK is the best choice.

Another thing you could do is to structure your data:

Consider a zone as a collection of rectangular subzones. The renderer doesn't need to know, just hide the complexities away behind a simple interface:

Tile Zone.getTile(int row, int col) 

(or something like that) should take care of finding out what subzone (2d array) the coordinate belongs to, calculate index into subzone and return the tile to the renderer. If the coordinate isn't contained by any subzones then return null;

That way you can have islands of data, or large holes in the map without wasting space on pointless null-pointers (No pun intended :)

You can store the subzones in a vector, array, linked list or other and get linear time lookups.

A tree based storage structure (perhaps a quad-tree, or double tree index on both rows and columns) would give log(n) time lookup, but the added overhead might make it slower than linear unless the number of subzones is "large".

I'll be implementing something like that myself, so I can't tell you how large yet.

Personally, for a 2D side-scrolling platformer I fiddled with once, I used the 2D array of pointers like EDI suggested.

The technical name for this is a Sparse Array.

It worked like a treat:

Relevant Screenshot (117KB)

Only the array entries that aren't null are drawn, thus everything else lets the sky gradient show through...

What about a 2D vector?

vector <vector<int> > map_vector;

Same time complexity as using a 2D Array, plus its malleable so you can resize your map dynamically. I don't see any reason not to use a vector, although I'll hold my breath on that one.

A 2D will allow fast lookups but at the cost of space (if the coverage is not complete). A 1D array will be a smaller coverage but will cost in lookups. A classic space vs. speed problem.

If you have complete coverage a 2D structure is reasonable. If however, you have a non-rectangle coverage area I suggest something like a kd-tree. This structure will allow fast lookups and be light on memory. This structure is common in GIS (city maps) which is basically the same problem.

That's my two cents. Hope it helps.

-R

Quote:

Original post by reccles A 2D will allow fast lookups but at the cost of space (if the coverage is not complete). A 1D array will be a smaller coverage but will cost in lookups. A classic space vs. speed problem.

If I'm not mistaken, a 2D array takes just as much lookup time as a 1D array that simulates a 2D array. The only difference is that with the 2D array, the compiler does the multiply and add behind the scenes, whereas with a 1D array, you have to do the multiply and add yourself. Either way, a multiply and add gets calculated.

I'd personally suggest a single 1D std::vector<> myself, and just do all the (x,y)->index calculations manually. Or consider boost::multi_array (which I have not used, but have heard plenty about).

Quote:

Original post by EDI The ony thing you want to avoid, is large maps using this type of implementation... Tile tiles[600][600]; Such an implementation requires a large contiguous block of RAM that the target PC may not have availible. A somewhat better solution is this... Tile* tiles[600][600]; While this still requires a large contiguous block of RAM, you are only using 4 bytes per tile (the pointer to the tile data) instead of having the actual tile data required to be contiguous.

i got a brain freeze. if each tile was 8 bytes then the first implementation would be 360000 * 8 bytes. but using the second implementation it will be 360000 * 4 bytes. that i get. what i don't understand is that you would still have to load the 360000 * 8 bytes of tile data anyway. wouldn't you? so how would the second implementation be a better solution?

Quote:

If I'm not mistaken, a 2D array takes just as much lookup time as a 1D array that simulates a 2D array.

Right, 1D and 2D are the same lookup time. My mistake. I was thinking of linked lists for some odd reason.

Quote:

Original post by reccles Quote: If I'm not mistaken, a 2D array takes just as much lookup time as a 1D array that simulates a 2D array. Right, 1D and 2D are the same lookup time. My mistake. I was thinking of linked lists for some odd reason.

This thread covers this topic, with the point being it really matters how the map is accessed, random or sequential. (sorry, forgot all my html code)

http://www.gamedev.net/community/forums/topic.asp?topic_id=269530

EDIT: For a world tile-map I would use the vector.

there are ALOT of thread covering this topic but ill give my imput any how
i would go with vector becasue you can dinamicly size even 2d vectors not so with arrays also when sorting and orginizing your data vectors built in functions become a big help

Quote:

Original post by Alpha_ProgDes Original post by EDI ommited for space... i got a brain freeze. if each tile was 8 bytes then the first implementation would be 360000 * 8 bytes. but using the second implementation it will be 360000 * 4 bytes. that i get. what i don't understand is that you would still have to load the 360000 * 8 bytes of tile data anyway. wouldn't you? so how would the second implementation be a better solution?

The first option creates an array of tile objects. When you create an array of objects, you grab a large block of memmory that will fit ALL of the objects. The problem with this is that if the amount of RAM required for the array is not available in one chunk from system RAM, it will use virtual RAM from the hard drive. As you may already know, this is a huge performance hit.

Another problem with this method is that in many cases you do not use all of the available space in the map causing a waste of resources because the objects are created for that space regardless of if they are needed or not.

The second option does require a large block of memmory BUT the array indexes contain pointers to tiles. There some benefits and drawbacks to this.

A possible benefit is that you only create the tile objects that you need instead of creating a bunch of wasted tiles.

A possible drawback is that you need to allocate memmory for the array of pointers AND all of the tile objects you will use. In many cases the memmory overhead here is less than that of using an array of objects.

A possible benefit/drawback depending on how you look at it is that you can utilize a list for quick object creation/deletion and an array for quick random access at the same time. The benefit being getting the best of both worlds, the drawback being that you have to manage a list as well as an array.

[edit]
Sorry, to answer the original question (cus I kind of rambled there) of how is option 2 a better solution, the answer would be that you do not need as large a block of contigious memmory for the array lessening the chances of having to use virtual memmory from the hard drive which is much slower as well as some of the reasons explained above.
[/edit]

Hope that helped