Hello,
I'm working on an iso RTS and I'm using the staggered approach to store my map data in an array. This means that each X co-ordinate represents 2 different X tiles, depending whether or not the Y co-ordinate is odd or even, in which case the tile is offset, shown below.
This works fine, however it does add an extra layer of complexity to every calculation, pathfinding, movement, etc.
I am curious, what are the alternatives? I require the whole map to be filled with tiles, so simply tilting a traditional square grid will not work, because many tills will have negative co-ordinates, and arrays do not have negative cells, shown below. Unless (0,0) is far, far off in the top left somewhere, but that leaves a huge amount of empty array cells and a seemingly unnecessary giant array. My maps are 256x512.
I'm open to all suggestions. Thank you for your time.
- Chris
Representing an iso map in a 2d array?
but that leaves a huge amount of empty array cells
Huge is relative. Might be, that a single 1024x1024 texture consumes more than your whole map. That is, keep it simple and stupid und use the latter approach to ease your developer life
Hmmm, interesting. Is that the general consensus?
I know in Starcraft 1, although it appears iso, it actually uses a square grid with square tiles. The Blizzard artists simply faked the iso. But in games that are "true" iso, with rhombus tiles, are you saying they use an extra large tilted array with thousands of unused cells?
I know in Starcraft 1, although it appears iso, it actually uses a square grid with square tiles. The Blizzard artists simply faked the iso. But in games that are "true" iso, with rhombus tiles, are you saying they use an extra large tilted array with thousands of unused cells?
i have never worked on iso projet, but i think your aprouch is too complicated.
as you drawed pic 2m its cearly visible array[8,8], and i would thread map as simple array. i wouldnt do 2 tiles on 1 x coordinate. i would make serie functions to convert rect coordinate to iso and backword, so all usual algorithms like path finding will be as usual for rect array.
about cells with negative coords: i would make bigger map, but would limit camera movement freedom, map(200,200), camera moves frealy in space (40...160,40..160)
as you drawed pic 2m its cearly visible array[8,8], and i would thread map as simple array. i wouldnt do 2 tiles on 1 x coordinate. i would make serie functions to convert rect coordinate to iso and backword, so all usual algorithms like path finding will be as usual for rect array.
about cells with negative coords: i would make bigger map, but would limit camera movement freedom, map(200,200), camera moves frealy in space (40...160,40..160)
But your world representation does not have to be an array.
I require the whole map to be filled with tiles, so simply tilting a traditional square grid will not work, because many tills will have negative co-ordinates, and arrays do not have negative cells, shown below.
So we have this grid where x goes down-left and y goes up-left. I take for granted this is equivalent to a regular grid minus some perspective.
[attachment=11347:Rot.png]
[attachment=11348:Shear.png]
For the purpose of this discussion, x goes right, y goes down.
Suppose we have a small set of rooms such as
(7,0)(7,2)(6,2)
Do we still have to save everything? Of course not! Just save as many cells as required to hold the populated cells! In this case, a 2x3 map would be sufficient.
Then write a function which maps world coordinate to array indices. This typically involves to subtract the minimum world coordinate used (which will end up being array index 0).
Additionally, you might want to mark a cell as "world origin" for the current plane, so if you have a positioning system, it reports (0,0) when in this cell instead of some value with no real information to the user.
A 2D tile map is not going to represent a very large use of memory. You can make a mind bogglingly huge map and still not worry about running out of RAM. So right there, that cuts out the "waste" argument behind using a staggered tile approach. 2D tile games stopped being computer-intensive about 10 years ago. So that leaves you with other, more important considerations. The biggest concern I have with the staggered maps is that they significantly complicate the process of pathfinding and movement cost calculation. Just use a rectangular array, rotate the camera so you get the diamond shape (no need for negative array indices; not sure where you got that idea), and designate border tiles beyond which the camera point of view can not pass, in order to prevent the camera being able to view the edge of the map. The border zones won't represent a significant amount of waste, and you don't have to worry about stupid and god-awful hackish solutions to the pathfinding cost dilemma once you get to that stage. Everything is just a straight, simple grid.
It's interesting how everyone seems so intent on holding on to the optimizations of the past, without regard to the amazing advances in technology that render such optimizations moot.
It's interesting how everyone seems so intent on holding on to the optimizations of the past, without regard to the amazing advances in technology that render such optimizations moot.
no need for negative array indices; not sure where you got that idea
As I said originally, I require the entire visible map to be covered with tiles. Using a traditional square grid on a tilted on a 30 degree angle means that there are going to be tiles with negative array indices, shown in black.
Unless however, the (0,0) index is far off to the left somewhere, seemingly the preferred method. In the image below, the green rectangle depicts the desired visible map, it also shows the array co-ordinates within the map using the staggered approach. The giant blue rhombus, demonstrates the size of a tilted array required to cover the same size map with tiles.
As you can see, using the staggered approach cuts the size of the array in half, but as FLeBlanc mentioned, this is unlikely to have any impact on performance. Personally, I prefer the staggered approach for it's elegance. Positioning the tiles on screen is simple:
X co-ordinate: (X index * Tile width) + ((Y index mod 2) * ( Tile width / 2))
Y co-ordinate: Y index * (Tile height / 2)
I've already coded the pathfinding and movement with a staggered grid (here is a demo if anybody is interested), but I haven't come much further than that. I think I'll head the advice and re-write with the (0,0) offset method. Thanks for the help.
But your world representation does not have to be an array.
What other choices do I have? Hash table? My pathfinding code is pretty dependant on arrays, but I'm always open to suggestions...
It doubles the amount of memory, but the real trick is, not to make a huge array of complex objects, but to create an huge array of pointers or indicies.
Simple example if you really like to save memory.
That is, you have 256*256/2 * 2 = 65k bytes wasted. Even if you have a uint32 index or even a pointer will not hurt.
Simple example if you really like to save memory.
// map 256x256, only half is filled
TileObject* tileArray = new TileObject[256*256/2];
// tile map of size 256x256
uint16 tileMap = new uint16[256][256];
// tile at index 0 is a dummy tile
... init tile map with tile index 0
.. map real tile indicies to point into the tile array
That is, you have 256*256/2 * 2 = 65k bytes wasted. Even if you have a uint32 index or even a pointer will not hurt.
As I said originally, I require the entire visible map to be covered with tiles. Using a traditional square grid on a tilted on a 30 degree angle means that there are going to be tiles with negative array indices, shown in black.
How about storing the active area in one array, and the inactive area in another? Store the active area in a square grid that is later rotated, using whatever coordinates you want. Store the inactive but visible area in another array that has a hole cut out of its middle (where the active area fits.) Superimpose them...now you have 2 sets of coordinates, none of them are negative, and as long as you aren't pathfinding between the two areas, it's OK.
If you weren't stuck on using an array, this wouldn't be a problem at all. I don't know what language you're using, but in C++ you could use an std::map in any number of ways.
std::map<std::pair<int, int>, Tile> tiled_map;
//or
std::map<int, std::map<int, Tile>> tiled_map;
Something like what nox_pp just suggested is what I normally use. With a hash map you can have negative coordinates, arbitrarily sized areas, etc...
Also, if I do want to use a normal rectangular array, I just use something like this:
The green shows the viewport, and the darker tiles show border tiles where the camera is not allowed to go in order to prevent showing black. Adjacent to those could possibly be special tiles which trigger the streaming code to load in the adjacent map chunk if the camera enters the area, in order to prepare the next region (if streaming is enabled). Of course, going this route means that the screen-space of the map isn't a neat squarish region. However, I've personally never understood the desire to use a staggered map, to be honest, even back in the day. Sure, the map is a sort-of rectangular shape on screen, but in world space it isn't, and since all the game action happens in world space (screen space is only used to draw) it always made sense to me to simplify the world space handling even at the expense of slightly greater complexity in screen-space handling. If you use a representation as above, then adjacent maps lie neatly next to one another on the over-grid, so you can have large streaming worlds where the chunks are just sub-arrays of the larger world array.
Also, if I do want to use a normal rectangular array, I just use something like this:
The green shows the viewport, and the darker tiles show border tiles where the camera is not allowed to go in order to prevent showing black. Adjacent to those could possibly be special tiles which trigger the streaming code to load in the adjacent map chunk if the camera enters the area, in order to prepare the next region (if streaming is enabled). Of course, going this route means that the screen-space of the map isn't a neat squarish region. However, I've personally never understood the desire to use a staggered map, to be honest, even back in the day. Sure, the map is a sort-of rectangular shape on screen, but in world space it isn't, and since all the game action happens in world space (screen space is only used to draw) it always made sense to me to simplify the world space handling even at the expense of slightly greater complexity in screen-space handling. If you use a representation as above, then adjacent maps lie neatly next to one another on the over-grid, so you can have large streaming worlds where the chunks are just sub-arrays of the larger world array.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement