将图块地图解析为高效的水平和垂直边界框

Question

我正在用 C++ 开发一个简单的平台游戏，一切都很好，除了我想将图块分组到边界框中，以便减少物理函数的传递（我的目标是 PC 和嵌入式设备，所以一切都与速度有关）。

以下函数的作用是加载一个简单的地图格式： “[char * header] [char bytesize] [bytesize w] [bytesize h] [char tw] [char th] [char *map]” 然后，它将数组读取为二维地图，并在可能的情况下对垂直线进行分组。

问题是...有人可以告诉我如何将这些图块分组为垂直轴和水平轴上的有效边界框吗？

这是一张图片来帮助解释，我知道我的语法和拼写很糟糕： http://thetooth.name/dev /blocks_bic.png

    void Environment::load_map(char* mapPath){
        cl("Loading Map: %s ", mapPath);

        FILE* mapFile = fopen(mapPath, "rb");
        FILE* mapInfoFile = fopen(strcat(substr(mapPath, 0, strlen(mapPath)-3), "bmd"), "rb");

        if (mapFile == NULL || mapInfoFile == NULL)
        {
            cl("[ERROR]\n");
            throw KLGLException("Error loading map file!");
            return;
        }

        size_t wordSize;
        char tBuffer[8] = {};
        int w = 0;
        int h = 0;
        int tileWidth = 0;
        int tileHeight = 0;

        fread(tBuffer, 1, 7, mapFile);
        if (strcmp(tBuffer, "STME1.0"))
        {
            cl("[BADHEADER]");
        }

        fill_n(tBuffer, 8, NULL);
        fread(tBuffer, 1, 1, mapFile);
        if (!strcmp(tBuffer, "B"))
        {
            wordSize = sizeof(char);
        }else{
            wordSize = sizeof(int);
        }

        fseek(mapFile, 8, SEEK_SET);
        fread(&w, wordSize, 1, mapFile);
        fread(&h, wordSize, 1, mapFile);
        fread(&tileWidth, 1, 1, mapFile);
        fread(&tileHeight, 1, 1, mapFile);

#define lvLookup y*w+x
        fill_n(mapData, (w*h)+1, '\0');
        fill_n(mapMask, (w*h)+1, '\0');

        // Read files into memory... back to front and inside out...
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                fread(&mapData[lvLookup], 1, 1, mapFile);
                fread(&mapMask[lvLookup], 1, 1, mapInfoFile);
            }
        }

        fclose(mapFile);
        fclose(mapInfoFile);

        // Parse map data into are geometry vectors
        for(int x = 0; x < w; x++){
            for(int y = 0; y < h; y++){
                if(mapData[lvLookup] > 0){
                    int xl = x;
                    int yl = y;
                    while(mapData[yl*w+x] != 0/* && mapMask[yl*w+x] == 0*/){
                        yl++;
                    }
                    platforms->push_back(Platform(x*tileWidth, y*tileHeight, 1*tileWidth, (yl-y)*tileHeight, lvLookup, mapData, mapMask));
                    y = yl-1;
                }
            }
        }
        cl("[OK]\n");
    }

提前致谢！

Answer 1

这有点难看，但我认为它应该作为一个起点。它的工作原理是从左到右、从上到下扫描，寻找相似的整列。具有挑战性的部分是跟踪连续的完整垂直块并正确输出“部分”运行。

void find_bounds()
{
    int startx = 0;
    char last = mapData[0];
    for (int x = 0; x < w; x++) {
        int starty = 0;
        for (int y = 0; y < h; y++) {
            char c = mapData[x+y*w];
            if (c != last) {
                if (starty == 0) {
                    // finish last run of complete vertical blocks
                    if(startx != x) { 
                        // it ran more than one column, output those first
                        span(last, startx, 0, x-1, h-1);
                        startx = x;
                    }
                    // and a run from the start of this column
                    span(last, x, 0, x, y);
                } else {
                    // a run within a column
                    span(last, x, starty, x, y);
                }
                last = c;
                starty = y;
            }
        }
        // had a run withing this column or processing last column, finish it up
        if (starty || x == w-1) {
            span(last, x, starty, x, h-1);
            startx= x + 1;
        }
    }
}

测试套件（前两个应对应于插图中的第二个和第三个案例）：

#include <iostream>
#include <vector>
using namespace std;

const int w = 8, h = 8;
char mapData[w*h+1] = 
#if 1
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
" xxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
#elif 0
"xxxxxxxx"
"xxxxxxxx"
"xxx xxxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
#else
"xxxxxxxx"
"xx xxxxx"
"xxxxxxxx"
"xx xxxxx"
"xxxx xxx"
"xxxxxxxx"
"xxxxxxxx"
"xxxxxxxx"
#endif
;

void span(char type, int x0, int y0, int x1, int y1)
{
    if (!(x0 == x1 && y0 == y1))
        cout << type << " " << x0 << ", " << y0 << " ->  " << x1 << ", " << y1 << "\n";
}

int main()
{
    find_bounds();
}