algorithm - 为基于图 block 的 2D 游戏引擎存储 map

Question

我们有一个(可能很大的)横向滚动 2D 世界，其中有很多重复的图 block (例如地形、墙壁、水等)。例如，有可能非常高的大“山丘”，但使用同样的小块“岩石”纹理。

我想优化这个世界的存储和渲染(绘制一个大四边形并对其应用相同的重复纹理比分别绘制许多相邻的小四边形更好)。

这样做的好方法是什么？目前我看到了两种可能的解决方案:

1. 允许 map 设计者手动指定“ block ”(重复图 block 的大矩形)
2. 允许 map 设计者逐 block 设计 map ，然后自动计算 block (执行此操作的好算法是什么？)

如果您开发过类似的游戏，很想听听您的具体解决方案。

Answer 1

因为无论如何您都不会绘制矩形(而是三角形)，所以我建议选择第二个选项。此外，永远不要相信您的程序的用户。

第一个任务是将 map 划分为具有相同纹理的多边形。因为您的地形是基于网格的，所以这可以很容易地通过一种洪水填充结合标记算法来实现，例如运行像这样:

- n := 0 // will be the polygon numbers
- Iterate over each grid cell
    - If cell is marked, continue with next cell
    - mark cell with n
    - check adjacent cells for the same texture and mark them accordingly * 
    - n := n + 1

* 此步骤可以通过多种方式执行:FloodFill .此外，您应该为每个 block 存储一个边缘单元。 IE。具有至少一个具有不同纹理的相邻单元格的单元格。我们称其为种子细胞。

然后您的网格用多边形编号标记，n 等于多边形数。

下一步是提取多边形。这就是种子细胞可以提供帮助的地方。对于每个 block ，从种子单元格开始，沿着 block 的边缘运行，收集所有角点。这些角点将构成您的多边形。

之后你就有了一组多边形。最后一步是对多边形进行三角剖分以进行渲染。这可以实现，例如与 Ear Cutting / Clipping Algorithm或其他人。