使用lua实现各种算法，先从快速傅里叶变换开始

萧山财神

接下来我们可以实现一种在2D游戏中常用的算法：快速傅里叶变换（Fast Fourier Transform, FFT）。FFT是一种高效计算离散傅里叶变换（DFT）的方法，广泛应用于信号处理、图像处理、音频分析等领域。

以下是用 Lua 实现的快速傅里叶变换算法：

-- 复数结构
Complex = {}
Complex.__index = Complex

function Complex:new(real, imag)
    local complex = {real = real, imag = imag}
    setmetatable(complex, Complex)
    return complex
end

function Complex:add(other)
    return Complex:new(self.real + other.real, self.imag + other.imag)
end

function Complex:subtract(other)
    return Complex:new(self.real - other.real, self.imag - other.imag)
end

function Complex:multiply(other)
    return Complex:new(
        self.real * other.real - self.imag * other.imag,
        self.real * other.imag + self.imag * other.real
    )
end

function Complex:exp()
    return Complex:new(math.cos(self.imag), math.sin(self.imag))
end

-- 快速傅里叶变换
function fft(input)
    local n = #input
    if n <= 1 then return input end

    -- 分离偶数和奇数索引
    local even = {}
    local odd = {}
    for i = 1, n // 2 do
        even[i] = input[2 * i - 1]
        odd[i] = input[2 * i]
    end

    -- 递归计算FFT
    local fftEven = fft(even)
    local fftOdd = fft(odd)

    -- 合并结果
    local result = {}
    for k = 1, n // 2 do
        local t = fftOdd[k]:multiply(Complex:new(0, -2 * math.pi * (k - 1) / n):exp())
        result[k] = fftEven[k]:add(t)
        result[k + n // 2] = fftEven[k]:subtract(t)
    end

    return result
end

-- 测试快速傅里叶变换
local input = {
    Complex:new(1, 0),
    Complex:new(1, 0),
    Complex:new(1, 0),
    Complex:new(1, 0),
    Complex:new(0, 0),
    Complex:new(0, 0),
    Complex:new(0, 0),
    Complex:new(0, 0)
}

local output = fft(input)

print("FFT 结果:")
for _, complex in ipairs(output) do
    print(string.format("(%f, %f)", complex.real, complex.imag))
end

在这个实现中：

1. Complex 结构表示一个复数，包含实部 real 和虚部 imag，并提供复数的加法、减法、乘法和指数运算。
2. fft 函数实现快速傅里叶变换算法，接受一个复数数组 input 作为输入，返回其傅里叶变换的结果。
3. 在 fft 函数中，通过递归分治法将输入数组分为偶数索引和奇数索引的子数组，分别计算其傅里叶变换，然后合并结果。
4. 测试代码定义了一个简单的输入信号，并调用 fft 函数进行傅里叶变换，输出结果。

快速傅里叶变换在2D游戏中的音频分析、图像处理、信号处理等方面有广泛应用。它能够高效地计算离散傅里叶变换，将时域信号转换为频域信号，从而进行频谱分析和滤波等操作。