• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Chris Burrows

Representing an iso map in a 2d array?

13 posts in this topic

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.

[img]http://imageshack.us/a/img221/7870/mapiso.gif[/img]

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.

[img]http://imageshack.us/a/img27/7569/negativem.jpg[/img]

I'm open to all suggestions. Thank you for your time.

- Chris
0

Share this post


Link to post
Share on other sites
[quote name='Chris Burrows' timestamp='1348031148' post='4981542']
but that leaves a huge amount of empty array cells
[/quote]
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 [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
0

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
[quote name='Chris Burrows' timestamp='1348031148' post='4981542']
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.[/quote]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.
[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. Edited by Krohm
1

Share this post


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

Share this post


Link to post
Share on other sites
[quote name='FLeBlanc' timestamp='1348064577' post='4981685']
no need for negative array indices; not sure where you got that idea
[/quote]

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.

[img]http://imageshack.us/a/img138/4294/negative2i.jpg[/img]

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.

[img]http://imageshack.us/a/img100/4223/arrayh.jpg[/img]

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 ([url="http://www.diybandits.com.au/Random/Update.zip"]here[/url] 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.

[quote name='Krohm' timestamp='1348037153' post='4981568']
But your world representation does not have to be an array.
[/quote]

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

Share this post


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

[CODE]

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

[/CODE]
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.
0

Share this post


Link to post
Share on other sites
[quote name='Chris Burrows' timestamp='1348133810' post='4981971']
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.
[/quote]

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.

[CODE]
std::map<std::pair<int, int>, Tile> tiled_map;
//or
std::map<int, std::map<int, Tile>> tiled_map;
[/CODE]
2

Share this post


Link to post
Share on other sites
[quote name='Chris Burrows' timestamp='1348133810' post='4981971']
[quote name='FLeBlanc' timestamp='1348064577' post='4981685']
no need for negative array indices; not sure where you got that idea
[/quote]

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.
[/quote]

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

Share this post


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

[quote name='Chris Burrows' timestamp='1348133810' post='4981971']What other choices do I have? Hash table? My pathfinding code is pretty dependant on arrays, but I'm always open to suggestions...[/quote]My fault here. Your world representation does not have to be a [i]plain[/i] array. It can be an array + index remapping function. More below.

[quote name='Chris Burrows' timestamp='1348133810' post='4981971']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)
[/quote][list=1]
[*]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.
[CODE]
// 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);
[/CODE]
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.
[/list]
0

Share this post


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

Share this post


Link to post
Share on other sites
What you are looking for:
[url="http://tonypa.pri.ee/tbw/tut16.html"]http://tonypa.pri.ee/tbw/tut16.html[/url]

If you read the whole series, he represents everything in a 2D array Edited by uglybdavis
0

Share this post


Link to post
Share on other sites

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  
Followers 0