Page 1 of 1

### Infinite 2D map data ?

Posted: June 4th, 2019, 9:35 pm
Hi,

I'm planning a game with an potentially infinite 2D map, made out of Cells. Each cell is an object with numerous members.
Class Cell
{
....
}

The goal is to access very quickly any of these Cells by its coordinate (x,y).

So I'm thinking about dividing the map into "chunks" which would be a fixed sized array of WxH Cells.

I'm thinking about storing chunks into a std::map. I first tried this :
Class Chunk
{
Cell* cells; // pointer to a [CHUNK_SIZE*CHUNK_SIZE] array
}

typedef std::pair<int, int> Point; // x,y coordinates of a Cell

Class Map
{
std::map<Point, Chunk*> chunks;
Cell* GetCell(int x, int y);
}

The GetCell member will be used to read of write the Cell.

But after some testings, it's quite slow because I need of lot of access to the map contents. I guess the (x,y)-key is not optimal.

So I'm thinking about a map<int, map<int, Chunk> > (a list of "rows" of "columns" of Cells)

Or maybe using pointers, like
map<int, (map<int,*Chunk>)* >
...so that copying/moving a "column" of Chunk would avoid duplicating any data, but only pointers...

What do you think ?
-----------------------------------------

My other idea is that, to enlighten computation work, I do not have to compute the logic of the game every graphical tick : I do not need to be so precise time-speaking.
So I was thinking about using a thread for the sync timed graphic loop, and another thread, more relaxed, that would constantly calculate the logic of the game, at its own rythm, only passing "generic" orders to the graphic engine, like "entity N moves from x1,y1 to x2,y2 in S seconds".

Do you think about another solution ?

### Re: Infinite 2D map data ?

Posted: June 5th, 2019, 1:44 am
The concept is similar to how I had my maze setup. I had a Maze that stored 25x25 Room objects and each Room object stored 25x25 tiles.

I personally just used vectors for each. If I wanted tile ( 3, 2 ) from room ( 12, 12 ) I'd just flatten each point into an index:

Code: Select all

``````auto& room = maze.GetRoom( 12 + ( 12 * numRoomsWide ) );
auto& tile = room.GetTile( 3 + ( 2 * numTilesWide ) );
``````
Ultimately, I found this code to be too verbose and wound up just storing a vector of tiles in a tilemap. I still have access to the rooms stuff, it just interacts with the tilemap. Each room stores it's beginning ( left, top ) tile offset.

Now, to access a tile:

Code: Select all

``````auto& tile = tilemap.GetTile( ( roomX * numTilesWide ) + 3 ), ( roomY * numTilesHeigh ) + 2 );
// In actuality, I rarely need to access them in this manner.  I mostly use the position of whatever I'm observing:
auto& tile = tilemap.GetTile( heroX / tileWidth, heroY / tileHeight );
// I have helper functions that do this for me though: static Vec2i Tilemap::world_to_tile( Vec2f const& pos );
auto& tile = tilemap.GetTile( Tilemap::world_to_tile( hero.GetPosition() ) );
``````
Though, now that I'm switching to 3D coordinates and changing the coordinate system so that Y is positive going UP the screen, I'm having to rethink how these functions work.

As far as performance, you are going to have to see what is causing the bottleneck. Is it the lookup? or is it the pixel pushing? Are you using the 3D Fundamentals framework? or the HW3D framework? or the regular chili framework 2016?

If not using hardware, then pushing pixels to fill the window can be a huge bottleneck especially if you have to do any calculations for each pixel. If it's running slow for just lookup, then consider using a vector where lookup is constant time. The only time required would be flattening the 2D coordinates into a 1D index.

Using pointers can actually slow things down in some cases because the processor has to chase down that data and it can't know what to cache for later use. However, if you aren't accessing the chunks and cells sequentially anyway, then it shouldn't even really matter.

### Re: Infinite 2D map data ?

Posted: June 8th, 2019, 2:04 pm