Infinite 2D map data ?

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Infinite 2D map data ?

Post by binbinhfr » 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 ?

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Infinite 2D map data ?

Post by albinopapa » 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.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

binbinhfr
Posts: 78
Joined: May 9th, 2019, 10:57 pm

Re: Infinite 2D map data ?

Post by binbinhfr » June 8th, 2019, 2:04 pm

Hi, thx for your answer.
I'm not using Chili framework anymore, but it was very helpful from training. Now I use SDL2.0 library, with GPU acceleration. Quite effective for 2D stuff as far as I tested it. I set up a timing monitor to measure time spent into update and into drawing. The bottleneck is really update. And especially using this map/chunks storage. Because I have the same version of my program using a finite map of 1000x1000 cells stored in a simple Cell[1000*1000] array, and the result is really quicker, under the 1/60s refresh rate. The problem is really the access time to data.

But as I wrote before, I will probably surrender on trying to update the whole logic on a 1/60s rate. I will try to use another thread in parallel or a simple trick to give regularly the hand to the drawing routine.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Infinite 2D map data ?

Post by albinopapa » June 9th, 2019, 4:47 am

As I stated, depending on how you are accessing your data, it could be the use of std::map over something like std::vector or the use of pointer chasing and/or lack of data locallity or cache coherence.

You already seen a speed up using a C style array. This leads me to believe it's more than likely the last two, pointer chasing or lack of cache coherence. Being able to lookup data in constant time and access neighboring data that is still in CPU cache is going to give you most of your speed, but depending on how much you have going on, you may need the extra threads.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply