时间戳

首页 > 技术文章 > 由我的世界水生成机制引发的思考

由我的世界水生成机制引发的思考

chantmee 2021-10-01 17:11 原文

前言

在我的世界中，如果一个方块在相同高度的有两个或两个以上的水方块与它相邻,并且这个方块是空气，那么这个方块就会生成一个新的水方块，而新生成的这个水方块也可以以同样的方法帮助其他方块生成水方块。

举个例子，这里假设'*' 为水源，'.'为空气，‘-’为土方块，给定下面的地图：

-----
-*.*-
-*..-
-----

那么第一秒地图就变成了：

-----
-***-
-*..-
-----

第二秒地图变成：

-----
-***-
-**.-
-----

第三秒地图变成：

-----
-***-
-***-
-----

在这种初始条件下，水方块充满了整个地图。而如果原来的地图中少了任何一个水方块，水方块就不能充满整个地图了，因为会有一些方块的周围永远也不可能出现两个或两个以上的水方块。

问题

现在假设所有方块都在同一高度上，给定一个初始地图，如何判断水方块能否充满整个地图呢？如果不能充满整个地图那又有哪些方块不能被填充为水方块呢？

解决

对于给定的地图，我们可以扫描整个地图看一下哪些方块可以被填充为水方块，也就是那些在第一秒能够被填充为水方块的位置，将这些方块放入队列中。

之后是一个类似于BFS的过程，从队列中取出第一个位置，然后判断一下他能能否被填充为水方块，如果可以的话就在地图中标记这个方块被填充为水源，然后将这个新生成的水源周围的非土、非水方块并且不再队列中的方块加入到队列中。重复上面过程直到对列为空，此时地图就是最终的地图形态。

解释

如果一个方块能被填充为水方块，那么它周围必定有两个或两个以上的水方块。但是最一开始我们将能被填充为水方块的方块都添加到队列了，其他的空气方块的周围附近兜只有小于两个的水方块。

那么什么时候这些原本不能被填充为水方块的空气方块能够被填充为水方块呢？那一定是这些方块的周围出现了新的水方块时才有可能被填充为水方块。那如何判断哪些方块有可能被重新填充为水方块了呢？很明显，当我们合成水方块的时候，他周围的没有被填充为水的空气方块可能被填充为水方块。

这样就解释了上面的解决方法，每次都将可能被填充为水方块的空气方块加到队列中，检查队列中的方块能不能被填充为水方块，能的话再将这个新生成的水方块周围的空气方块加入到队列中...

c++解决

输入格式

第一行有两个数字n、m分别表示地图的行数和列数。

之后n行，每行有m个数字，数字与数字之间用空格隔开，数字表示方块的种类，0为土方快，1位水方块，2为空气方块。

代码

#include <cstdio>
#include <queue>

#define pii pair<int, int>
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

constexpr int Maxn = 505;
constexpr int dir[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int a[Maxn][Maxn]; // 0:方块   1:水源   2:空
bool inQueue[Maxn][Maxn];
int n, m;

bool canTurnIntoWater(int x, int y) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] == 1) {
            cnt++;
        }
    }
    return cnt >= 2 && a[x][y] == 2;
}

bool posIsValid(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] == 2 && !inQueue[x][y];
}

void solve() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    std::queue<std::pii>q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (canTurnIntoWater(i, j)) {
                q.push(std::mp(i, j));
                inQueue[i][j] = true;
            }
        }
    }
    for (; !q.empty(); q.pop()) {
        std::pii f = q.front();
        int x = f.fr, y = f.sc;
        inQueue[x][y] = false;
        if (canTurnIntoWater(x, y)) {
            a[x][y] = 1;
            for (int i = 0; i < 4; i++) {
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];
                if (posIsValid(xx, yy)) {
                    inQueue[xx][yy] = true;
                    q.push(std::mp(xx, yy));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%d%c", a[i][j], " \n"[j == m]);
        }
    }
    printf("\n");
}

int main() {
    solve();
    return 0;
}

/*
5 5
1 1 2 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
 */

推荐阅读