使用lua实现各种算法，先从Flood Fill算法开始

萧山财神

接下来我们可以实现一种在2D游戏中常用的算法：Flood Fill算法。Flood Fill算法是一种用于区域填充的算法，广泛应用于图像处理、游戏开发中的区域填充、迷宫求解等场景。

Flood Fill算法简介

Flood Fill算法的基本思想是从一个起始点开始，递归或迭代地填充与起始点相连的所有相同颜色的区域，直到整个区域都被填充。

示例代码

以下是用 Lua 实现的Flood Fill算法：

-- 定义方向向量
local directions = {
    {x = 0, y = 1},  -- 上
    {x = 1, y = 0},  -- 右
    {x = 0, y = -1}, -- 下
    {x = -1, y = 0}  -- 左
}

-- 检查坐标是否在图像范围内
local function inBounds(image, x, y)
    return x >= 1 and x <= #image and y >= 1 and y <= #image[1]
end

-- Flood Fill算法（递归实现）
local function floodFill(image, x, y, targetColor, replacementColor)
    if not inBounds(image, x, y) or image[x][y] ~= targetColor or image[x][y] == replacementColor then
        return
    end

    image[x][y] = replacementColor

    for _, dir in ipairs(directions) do
        floodFill(image, x + dir.x, y + dir.y, targetColor, replacementColor)
    end
end

-- 测试Flood Fill算法
local image = {
    {1, 1, 1, 2, 2},
    {1, 1, 0, 2, 2},
    {1, 0, 0, 2, 2},
    {1, 1, 0, 0, 0},
    {1, 1, 1, 1, 0}
}

local startX, startY = 3, 3
local targetColor = 0
local replacementColor = 3

print("填充前的图像:")
for _, row in ipairs(image) do
    for _, pixel in ipairs(row) do
        io.write(pixel .. " ")
    end
    print()
end

floodFill(image, startX, startY, targetColor, replacementColor)

print("填充后的图像:")
for _, row in ipairs(image) do
    for _, pixel in ipairs(row) do
        io.write(pixel .. " ")
    end
    print()
end

在这个实现中：

1. directions 表示四个方向的向量（上、右、下、左），用于在图像中移动。
2. inBounds 函数检查给定的坐标是否在图像范围内。
3. floodFill 函数实现Flood Fill算法，接受图像 image、起始坐标 x 和 y、目标颜色 targetColor 和替换颜色 replacementColor 作为输入，递归地填充与起始点相连的所有相同颜色的区域。
4. 测试代码定义了一个简单的图像，并调用 floodFill 函数进行区域填充，输出填充前后的图像。

Flood Fill算法在2D游戏中的区域填充、迷宫求解、图像处理等方面有广泛应用。它能够高效地填充与起始点相连的所有相同颜色的区域，适用于各种需要区域填充的场景。