Sign in to follow this  
AoS

Loading Data For 2D Game Map

Recommended Posts

So I'm currently working on a project that requires me to have a map with provinces. I am currently having a map drawn in GIMP2.0 and loading the map with the standard SFML image loading function. This works fine. The place where I have an issue is reading the image file color data to determine what part of the map is what province. The map has each province colored in a unique color. Borders are added and then a new image without province colors is generated. So the new map has land one color, inland sea another color, and oceans another color. Borders are a lighter color than the land. The color map is kept so that it reads the mouse position when you click checks the color and says, oh you clicked on province X.
 
This is all great except I feel like the loading time is excessive. There are currently 2860 land provinces and there will probably be many more, plus inland sea, and ocean provinces. When the colored map is loaded a function goes through and checks the color of each pixel and adds the pixel to the appropriate province as an owned pixel of that province.
 
This data is used by other functions such as drawing the country map. So the program checks the country of a province and colors every pixel of each province the appropriate country color on the country map. The country map is a specific filter; there are many others. pixelsOwned is just a list of coordinates for each pixel, x,y.
 
My profiler tells me that the functions that generates each province's list of owned pixels is the most time consuming of the loading functions. Although many of the functions that involve coloring the map take quite a bit of time. It takes about 4 seconds to load up just if I comment out all the map coloring functions.
 
Is there some superior way to reading the data from every pixel?
 
Here is the function below:


void MapManager::loadMapPixelData(sf::Image *image) {
    sf::Vector2u pixelSize = image->getSize();
    int width = pixelSize.x;
    int height = pixelSize.y;
    for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j) {
            sf::Color color = image->getPixel(i, j);
            int red = color.r;
            int green = color.g;
            int blue =  color.b;
            for (int k = 0; k < provinces.size(); ++k) {
                if (red == mapProvinceValues[k].red && green == mapProvinceValues[k].green && blue == mapProvinceValues[k].blue) {
                     getProvinceById(k+1)->pixelsOwned.push_back({i, j});
                     break;
                 }
             }
             provincePixels.push_back({i, j, red, green, blue});
         }

     }

}

Edited by AltarofScience

Share this post


Link to post
Share on other sites

There are a number of issues with your code that can be addressed without changing what data you're storing:

 for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j) {

Generally it's faster to iterate through a 2d image's pixels in the order that they exist in memory. So swapping these two lines (assuming pixels are stored scanline by scanline) might speed things up. However, the slowness of what's going on inside of your loop will probably dominate your performance, I so doubt you'll see anything noticeable by making this change.

            for (int k = 0; k < provinces.size(); ++k) {

You're potentially iterating through 2860 provinces for every pixel. That's kind of ridiculous. Store them in an unordered_map and use the color as a key.

                     getProvinceById(k+1)->pixelsOwned.push_back({i, j});

You're adding to a pixelsOwned vector incrementally. Do you pre-size it to a reasonable capacity beforehand? If not, you're going to be hitting a ton of a reallocations as the vector grows.

 

Have you profiled your code to see where your actual bottleneck is? This should help determine what the best first course of action is.

 

Anyway, I would question the need to store these "pixel lists" at all. I don't know exactly how you're doing your drawing, but I'm sure there is a cheaper way. For instance, instead of a list of pixels for each country, just store a bounding rectangle, and compare each location against the original data.

Edited by phil_t

Share this post


Link to post
Share on other sites

There are a number of issues with your code that can be addressed without changing what data you're storing:

 for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j) {

Generally it's faster to iterate through a 2d image's pixels in the order that they exist in memory. So swapping these two lines (assuming pixels are stored scanline by scanline) might speed things up. However, the slowness of what's going on inside of your loop will probably dominate your performance, I so doubt you'll see anything noticeable by making this change.

            for (int k = 0; k < provinces.size(); ++k) {

You're potentially iterating through 2860 provinces for every pixel. That's kind of ridiculous. Store them in an unordered_map and use the color as a key.

                     getProvinceById(k+1)->pixelsOwned.push_back({i, j});

You're adding to a pixelsOwned vector incrementally. Do you pre-size it to a reasonable capacity beforehand? If not, you're going to be hitting a ton of a reallocations as the vector grows.

 

Have you profiled your code to see where your actual bottleneck is? This should help determine what the best first course of action is.

 

Anyway, I would question the need to store these "pixel lists" at all. I don't know exactly how you're doing your drawing, but I'm sure there is a cheaper way. For instance, instead of a list of pixels for each country, just store a bounding rectangle, and compare each location against the original data.

The profiler I used told me that that function, and similar functions, suck up the majority of the load time. I don't think it can get much more specific. Well it did say that some thing with the word allocate in it and the [] operator were the parts eating up the time within that function. I suspect that was the reallocation thing you mentioned.

Share this post


Link to post
Share on other sites

What youre doing:

1. Iterate over all provinces and for each

2. Iterate over all pixels in province and for each

3. Color corresponding pixel in output based on province

 

You should be doing:

1. Iterate over all output pixels and for each

2. Find province using corresponding pixel in province index image (make an image that directly contains province index instead of converting color->index in a loop) and

3. Color the output pixel based on province

 

Even if you use the first method, you should still get rid of the color -> province index for loop and replace it with a direct lookup (so the image directly stores the province indices instead of colors) or at the very least an unordered_map as mentioned.

 

The second method mainly differs in using less memory, because instead of storing pixels in the form x,y you store them as a single index to the province list (1/2 memory use?)

+ youll avoid having 3000 dynamically sized vectors dumped all around the heap and instead just have the contiguously laid out province index image which is much neater.

 

I dont know if you need the per province pixel vectors for some other operation though, so I dont know if my suggestion makes sense for those operations. But it should speed up the full-map operations you described and reduce load times since you dont need to create the vectors anymore if you dont need them.

Share this post


Link to post
Share on other sites

Maybe this is just stupid, but why store the pixel data at all?  Why not, when a user clicks on the map, you check that pixel against your color-coded map, and find the color there and look up the province then.  The only looping done is through the provinces, but that can be alleviated by putting the provinces in an unordered_map (as phil_t suggested) and just reference the province via ProvinceMap[ColorClicked];

 

The overhead is you keep the color-coded map loaded in memory.  Is that going to be a deal breaker?  If so, you can reduce the size of the color-coded map x16 by reducing the size of your color-coded map by 4 each axis, and, when checking for where a user clicked, divide the world-X click position and world-y client position by 4 and then check the color-coded map.

 

Just a thought.

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