13 replies to this topic

[Chris Burrows]

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

[Ashaman73]

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

[Chris Burrows]

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?

[serumas]

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)

[Krohm]

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.

But your world representation does not have to be an array.
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.


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.

Edited by Krohm, 19 September 2012 - 12:48 AM.

[FLeBlanc]

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.

[Chris Burrows]

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

[Ashaman73]

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.

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

[nox_pp]

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;

[FLeBlanc]

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.

Edited by FLeBlanc, 20 September 2012 - 09:10 AM.

[alnite]

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.

Why don't you limit the camera viewport? Yes, you are basically only allowing players to see half of the map, and the other half is just empty.

If you don't want to store empty spaces, you can go with the Starcraft's fake isometric idea. Everything underneath is just a rectangular grid, but the artwork are isometric.

[Krohm]

I write this to elaborate on what FLeBlanc is writing, to make sure this staggered grid abomination is eradicated.
I also include some elaborations on the (0,0) method I proposed above. I guess it was mine?

What other choices do I have? Hash table? My pathfinding code is pretty dependant on arrays, but I'm always open to suggestions...

My fault here. Your world representation does not have to be a plain array. It can be an array + index remapping function. More below.

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)

• Staggering the grid does not save anything in general. It does save something in this specific example. Everyone can see that: the staggered grid takes half the surface. No wonder it takes less memory. But again, this is not a problem unless you have at least 256k2 maps (and even this it would be something in the order of hundreds of megs).
• The implication of (1) is that the content is diamond-shaped. It is unclear this is true in general.
• Here's the index remapping function for the array.
  

  	// Assume we have a AABB structure holding the mincoord, maxcoord for the maze.	// xy is ground plane, z is up (not relevant here)	// levelCellSize is the dimension, in world space, of a cell.	single2 worldPos = GetPlayerPosition();	worldPos -= levelAABB.mincoord;	worldPos /= levelCellSize;	int row = int(worldPos.x);	int col = int(worldPos.y);

  This is the index remapping function. It maps world position to an array index [row][col] to use to access the tile resource being used.
  Player position is (row, col) - origin.

[Heaven]

I've always thunk like FleBlanc said: in WORLD SPACE the map is an array. Nothing else matters, ultimately. I mean, whether you want to display that array top-down, or if you want to rotate it 30 degrees for an isometric viewpoint is really just a matter of drawing. This simplifies so many things, and in all honesty it took me re-reading this thread a couple times before I finally figured out what you were asking. I couldn't understand why you were coming from a SCREEN SPACE perspective when things make so much more sense if everything is a square array and you manipulate it however you want to get it to display how you want. That may just be me....

With that said, making it so you limit the viewport so you never see "the void" without wasting tons of map cells...there are creative ways to get around it I'm sure but as someone else also already mentioned: why bother? We've got so much memory nowadays does it really matter if, as in your worst case scenario you illustrated above, you're wasting 50% of the array? I doubt it, and in reality you're probably going to be wasting lots less since your viewport is going to be smaller than what you've illustrated unless you zoom out really far.

Interesting perspective, regardless! Best of luck in finding a satisfying solution!

Take care.

[uglybdavis]

What you are looking for:
http://tonypa.pri.ee/tbw/tut16.html

If you read the whole series, he represents everything in a 2D array

Edited by uglybdavis, 24 September 2012 - 12:19 PM.