XNA Roguelike游戏：多值网格最少矩形划分算法需求

首先，非常理解你的痛点——500x500的地图逐个调用Draw确实会让GPU不堪重负，合并同值Tile为大矩形是降低绘制调用次数的绝佳方案。针对非二进制矩阵的最小矩形划分需求，这里给你一套实用的贪心扫描算法，既容易实现，又能满足游戏性能优化的要求。

核心思路：贪心扫描+动态扩展 #

不同于二进制矩阵的最大矩形算法，我们的目标是用最少的矩形覆盖所有同值Tile。贪心算法的核心逻辑是从左上角开始，逐个处理未标记的Tile，尽可能扩展出最大的同值矩形，标记后跳过已处理区域，直到遍历完成。这个方法虽然不一定能得到理论上的全局最优解，但在Tile地图场景下，结果足够接近最优，且实现简单、运行高效。

具体步骤 #

1. 遍历起点：从地图左上角(0,0)开始，逐个检查每个Tile，跳过已处理的Tile。
2. 横向扩展：以当前Tile为起点，向右扩展到最大连续同值列（需保证当前行的后续Tile未被处理且值相同）。
3. 纵向扩展：在横向确定的列范围内，向下扩展到最大连续同值行（需保证每一行的对应列范围都是同值且未被处理）。
4. 记录与标记：将这个矩形加入结果列表，并标记所有覆盖的Tile为已处理。
5. 重复遍历：继续处理下一个未标记的Tile，直到整个地图处理完成。

C#伪代码实现（适配XNA） #

using System.Collections.Generic;
using Microsoft.Xna.Framework;

// 存储矩形分组信息的辅助类
public class TileRectangle
{
    public Point StartPos { get; }
    public int Width { get; }
    public int Height { get; }
    public char TileValue { get; }
    public Texture2D TileTexture { get; }

    public TileRectangle(Point start, int width, int height, char value, Texture2D texture)
    {
        StartPos = start;
        Width = width;
        Height = height;
        TileValue = value;
        TileTexture = texture;
    }
}

public List<TileRectangle> GenerateMinimalTileRectangles(char[,] dungeonMap, Dictionary<char, Texture2D> tileTextures)
{
    int mapHeight = dungeonMap.GetLength(0);
    int mapWidth = dungeonMap.GetLength(1);
    bool[,] processedTiles = new bool[mapHeight, mapWidth];
    List<TileRectangle> rectGroups = new List<TileRectangle>();

    for (int y = 0; y < mapHeight; y++)
    {
        for (int x = 0; x < mapWidth; x++)
        {
            if (processedTiles[y, x]) continue;

            char currentTile = dungeonMap[y, x];
            // 第一步：横向扩展到最大列
            int maxX = x;
            while (maxX + 1 < mapWidth && !processedTiles[y, maxX + 1] && dungeonMap[y, maxX + 1] == currentTile)
            {
                maxX++;
            }

            // 第二步：纵向扩展到最大行
            int maxY = y;
            bool canExpandDown = true;
            while (canExpandDown && maxY + 1 < mapHeight)
            {
                int nextY = maxY + 1;
                // 检查下一行的整个横向范围是否都是同值且未处理
                for (int col = x; col <= maxX; col++)
                {
                    if (processedTiles[nextY, col] || dungeonMap[nextY, col] != currentTile)
                    {
                        canExpandDown = false;
                        break;
                    }
                }
                if (canExpandDown) maxY++;
            }

            // 第三步：创建矩形分组并加入结果
            rectGroups.Add(new TileRectangle(
                start: new Point(x, y),
                width: maxX - x + 1,
                height: maxY - y + 1,
                value: currentTile,
                texture: tileTextures[currentTile]
            ));

            // 标记当前矩形覆盖的所有Tile为已处理
            for (int ry = y; ry <= maxY; ry++)
            {
                for (int rx = x; rx <= maxX; rx++)
                {
                    processedTiles[ry, rx] = true;
                }
            }
        }
    }

    return rectGroups;
}

XNA绘制优化的具体应用 #

拿到矩形分组后，你可以在Draw方法中批量绘制：

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.Black);
    spriteBatch.Begin(samplerState: SamplerState.LinearWrap); // 开启纹理重复

    foreach (var rectGroup in _tileRectangles)
    {
        // 单个Tile的纹理区域（假设每个Tile大小是32x32）
        Rectangle sourceRect = new Rectangle(0, 0, 32, 32);
        // 屏幕上的目标矩形（根据Tile坐标转换为屏幕坐标，比如每个Tile32像素）
        Rectangle destRect = new Rectangle(
            rectGroup.StartPos.X * 32,
            rectGroup.StartPos.Y * 32,
            rectGroup.Width * 32,
            rectGroup.Height * 32
        );
        // 绘制整个矩形，纹理自动重复填充
        spriteBatch.Draw(rectGroup.TileTexture, destRect, sourceRect, Color.White);
    }

    spriteBatch.End();
    base.Draw(gameTime);
}

额外优化建议 #

• 动态地图处理：如果地图有动态变化（比如玩家破坏Tile），只需要重新计算变化区域及其周边的矩形，无需遍历整个地图。
• 纹理字典预加载：提前将所有Tile纹理按值存入字典，避免绘制时重复查找。
• 性能测试：对于500x500的地图，这个算法的时间复杂度是O(n*m)（n行m列），每个Tile仅被处理一次，完全不会成为性能瓶颈。

内容的提问来源于stack exchange，提问作者Seerramatutu