Hi all, I can see a lot of new game based on 2D map (ie: all the rts new games). Anyway, though they might use terrain, I was wondering about ways to optimize without terrain.
So if some has some link to some optimized algorythm of a (x,y) map. Sure I thought of showing only some tiles depending on where the camera was, but still, there must be other ways.
thanks a lot.
This is a very general question and so I’m sorry if my response too is general. Any space partitioning algorithm that works for 3D should have an equivalent in 2D. For example, you could use a quadtree to partition your map into smaller and smaller subsections and then display visible one’s based on view. If you’re using Xith, some of this stuff should be taken care of for you.
Ok, let me explain this with an example (oh and by the way the “zone” partitionning is a good idea!)
What I want to do is a terrain like my subdivided with tiles. Let’s define what a tile is:
A tile is a square subdivided into small triangle making little square. So, a tile has about 10x10 small pane into it. So, that’s about 200 polys (triangle). I can modify the poly coords to make terrain effects in it. A tile is also as large as a character in the screen, so it is not big like a terrain.
Now, let’s define map:
A map is made of tiles aligned to each other (with the height of each tiles) Making the map like a Warcraft 3 map. A map can have 64x64, 128x128, 100x50, etc. tiles. Though, I’m just showing what the camera is seeing, let’s say the camera is pointing the character like warcraft. So, I just want to show maybe 16x16 tiles.
Well, now that’s where the problem lies. The basic way to do this is surely a 2D array, containing the tiles informations.
tile[x][y]
and then getting the character position in the map, x and y, and limiting the vue to x + 8, x - 8, y + 8, y - 8.
now you can loop with 2 for loops like this:
for ( int y = charY - 8; y < charY + 8; y++ )
for ( int x = charX - 8; x < charX + 8; x++ )
if (we’re not outside the array && the tile isn’t null )
enable( tile[x][y] );
ok, it can be a bit long, I thought of another way that is making an array with one dimension like this:
tile[x * y]
// getting the top left 16x16 square depending on the character position
topleftSquare = ( mapSizeX * charY ) + charX;
// getting the bottom left 16x16 square depending on the character position
bottomleftSquare = ( mapSizeX * charY ) + charX;
for ( int i = topleftSquare; i < bottomleftSquare; i++ )
enable( tile[i] )
I don’t know if it’s really faster, but anyway.
Another way could be making different BranchGroup, called zone. And when I’m approching of one zone, I enable it. While this solution can be the fastest (perhaps) It can be a problem if I’m in a 40x40 tiles zone and I load up a 40x40 zone.
Or, I could load the map, and divid it into small 16x16 tile not caring of what the map is made of (a “room” could be cut in a half) but the user will not see this, since 16x16 is as large as the screen view.
Any thought is welcome, I’m a bit lost in all this
Hi
if u have relatively small map i think it doesnt matter how u find visible area. I mean ur way is good for small map - when u can store it in array. If u work with something really complex and large u just cant afford to store all tiles in array , so u have to use quadtree or BSP tree - as sad above. BSP tree have better algorithm for finding visible area. but again - for 64x64 it really doesnt matter.
BTW 2dimention array and 1dimension array is same in binary representation , so it doesnt matter what exactly u use 