Alternative to 2D array in a tiled-map structure

Raveline
  • Alternative to 2D array in a tiled-map structure Raveline

    After searching for a long time, I'm surprised this question was not asked yet. In a 2D, tiled-map game, how do you handle the map ? I'd be glad to have your point of view in any languages, though I'm more interested in C++ implementations.

    A 2D array, a 2D vector, a class handling a linked-list with ad hoc computing to handle coordinates, a boost::matrix... ? What solution do you use and why ?

  • It would depend on the style of game and map honestly. For a relatively small rectangular tile map, I'd probably just stick with a 2d array. If the map was very irregularly shaped (lots of empty gaps), a wrapper around linked lists that provides O(1) indexing would probably be my choice.

    An integer indexed array gives you a 2147483647^2 2d array. That's pretty big, but exceeds what you'd what to load into memory. If the map was to be large scale, another thing to look at is dividing the map into chunks. Each chunk is fixed size and contains a sub-array of tiles that could be loaded/unloaded as needed to keep memory lower.

  • I'll explain what I do for a specific case of tiled maps: this is for effectively infinite maps, ones where the world is generated on demand but you need to save modifications to it:

    I define some cell size "N" and split the world up into squares/cubes "NxN" or "NxNxN"

    A cell will have a unique key. I generate mine by hashing or using directly the formatted string:"%i,%i,%i",x,y,z (where x,y,z are the world coordinates of the start of the cell divided by N)

    Storing the tiles indices in arrays is straightforward as you know you have NxN tiles or NxNxN tiles. You also know how many bits your tile type takes up. Just use a linear array. It makes loading and saving/releasing the cells simpler to handle too.

    Any accessor merely needs to generate the key for the cell (to make sure it's loaded/generated, then get the pointer to it), then use a sub index to look inside that cell. to find the tile value at that specific point.

    Extracting the cell by its key, I currently use a map/dictionary as generally I process whole cells at once (wouldn't want to know how bad a hit it would be to do a dictionary lookup per tile, eek).

    Another point, I don't keep mobs / players in the cell data. The actively dynamic stuff needs its own system.

  • The question probably wasn't asked because you don't need an alternative. For me, it's:

    Tile tiles[MAP_HEIGHT][MAP_WIDTH]; if the size is fixed.

    std::vector<Tile> tiles(MAP_HEIGHT*MAP_WIDTH); otherwise.

  • One thing I've done for an RPG style map - that is, houses you can enter, dungeons, etc is have 4 main structures: a Map, an Area, a Zone, and a Tile.

    A Tile is obviously a tile.
    A Zone, or a chunk, or whatever, is an area of X by Y tiles. This has a 2D array.
    An Area is a collection of Zones. Each Area can have different Zone sizes - the overworld may use a 32x32 Zone, whereas a house may have one 10x20 Zone. These are stored in dictionaries (so I can have Zone (-3, -2)).
    A Map is a collection of Areas, all of which are linked to each other.

    I felt this allowed me greater flexibility rather than having one huge map.

  • I am toying with a 3D engine where the world is a mesh.

    I am importing some 2D maps+tilesets that have previously been made.

    And when I do, I convert it to a 3D mesh and put all the tiles into a single texture.

    This draws substantially faster.

    I would perhaps keep the map around in a 1D array of w*h if I had to keep it's tile concept, but my answer is that its liberating to move beyond the 2Dness.

    And, if you have performance problems whilst using GPU drawing, keeping the graphical representation as a single texture - with a mesh if its got variable heights - can really speed it up compared to drawing each tile individually.

Tags
c++ tiles data-structure maps
Related questions and answers
  • I'm writing a game engine which is going very fine. However, I'm now posed with handling textures. My Engine is in 2D, for simplicity reasons mostly to get a good idea of how to work with OpenGL. I do this in C++, and I have a hierarchical set-up when it comes to classes. There's a base class and some other classes derive from that. So now I'm onto the part where I want to load up some textures..., but simply put: SceneManager loads the file resources/maps/dungeon3Interor.msf (msf being a custom map format (MSF stands for M age S cene F ile ). The MSF file refers to a tilset. SceneManager loads

  • I'm using vertex array to draw 2d geometry, but I can't achieve smoothness. This is the code I'm using: glEnableClientState(GL_COLOR_ARRAY); glEnableClientState(GL_VERTEX_ARRAY); glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA); glColorPointer(4, GL_UNSIGNED_BYTE, 0, shared_colors); glVertexPointer(3, GL_FLOAT, 0, shared_vertex); glDrawArrays(GL_LINES, 0, shared_counter); glDisableClientState(GL_VERTEX_ARRAY); glDisableClientState(GL_COLOR_ARRAY); glDisable(GL_BLEND); Some advice?

  • ((char*)new_map[r].c_str());} // make sure this works later // Insert Time if(command== ALL || command== TIME){ enum{ time_loc_y= 22, time_loc_x= 38...Alright so i'm making a vertical side scroller where you are an '8' character traveling downward while avoiding my randomly generated walls (the "generation" function) on the left and right sides... until you pop out into an open space, known as a ' ' (space) character. You lose one life for each INITIAL collision with the X wall, and do not lose another until you have popped out and been freed

  • I'm writing a generic ShaderProgram class that compiles a set of Shader objects, passes args to the shader (like vertex position, vertex normal, tex coords etc), then links the shader components...: float m_Position[3]; // x, y, z // offset 0, size = 3*sizeof(float) float m_TexCoords[2]; // u, v // offset 3*sizeof(float), size = 2*sizeof(float) float m_Normal[3]; // nx, ny, nz; float colour[4]; // r, g, b, a float padding[20]; // padded for performance }; I've already written a working VertexBufferObject class that creates a vertex buffer

  • I know that if you want to display a sprite on screen (in 2D) you can use glOrtho and essentially make 1 gl unit equal to 1 pixel, so when I plot out the vertices for say a 128x128 image (on a quad), I can define the vertices as -64/64, -64-64, etc and then when I map my texture coords to that quad, the image is displayed at a 1:1 ratio. However, lets say I wanted to not use glOrtho and wanted to have a perspective view, so I can combine 2D sprites with 3D models and whatnot? I'm at a loss on how to convert/set up the coordinates for the planes/quads I want to draw images to, in a way

  • related to the graphics library I'm using, but is more of a conceptual thing. In C#, I coupled graphics in with alot of my classes which i know is a terrible idea. Wanting to do it decoupled... question about it is, is this a worthwhile approach at all? If it's a bad design I want to know now before I invest too much more time making all the screens I'm going to need. How do you build up... ago, decided to switch to C++. I wanted to get a good handle on C++ since it's been awhile since I used it heavily, and figured an interesting project like this would be a good motivator. I've been

  • , could be added to levels. Whether I do this hinges on whether I can get the fov routine I'm using working with the layers. Note that I don't care that it doesn't make sense to some of you that I'm trying to have a 3d field of view routine for a 2d roguelike. The roguelike does have a 3d space, and I want to determine what the player can see, even if what the player can see can't logically be displayed. Let me worry about how to handle that problem. I would be grateful for some advice in how to approach this problem. Perhaps this is utterly crazy, and I should just make a 2d roguelike... Update

  • I'm looking into designing and implementing an online RPG (or more accurately, redesigning an existing piece of server software). One of the problems is that of managing visibility. Update data for other players should only be sent to a game client if their player is near the other players (i.e. you shouldn't get health updates for people you can't see on the other side of the map). The main problem is that if you had to compare all the players every time an update is sent, it would just take way too long as the number of players scales (think up to a few thousand players per map and each

  • I have a 2D tile map, where each tile is marked as blocking or non-blocking. Each tile is 16x16 pixels and sub-tile movement is possible. I'm attempting to generate a navigation mesh from this data, at run-time, using C++. Is there any well known library that can be used to generate a navigation mesh, given a 2D tile map? Alternatively, is there any algorithm that can be used to intelligently generate a navigation mesh from the tile data? As far as I can tell, all of the popular solutions are aimed at 3D maps and don't perform well when given the simplified case of a 2D map.