Maze.lua

local Vector2 = {}

local argAssert = "'%s' must be a %s"
local floor = math.floor

local function assertType(value, label, expectedType)
    assert(type(value) == expectedType, argAssert:format(label, expectedType))
end

local function assertVector2(v2)
    if type(v2) == "number" then
        v2 = Vector2.new(v2, v2)
    end

    assertType(v2, "input", "table")
    assert(getmetatable(v2) == Vector2, argAssert:format("input", "Vector2"))

    return v2
end

function Vector2.new(x, y)
    local x = x or 0
    assertType(x, 'x', "number")

    local y = y or 0
    assertType(y, 'y', "number")

    local v2 = {}
    v2.X = x
    v2.Y = y

    return setmetatable(v2, Vector2)
end

function Vector2:__index(k)
    if k == "Magnitude" then
        return math.sqrt(self.X ^ 2 + self.Y ^ 2)
    elseif k == "Unit" then
        return self / self.Magnitude
    elseif k:sub(1, 2) ~= "__" then
        return rawget(self, k)
    end
end

function Vector2:__newindex(k,v)
    error("Vector2 is read-only")
end

function Vector2:__tostring()
    return self.X .. ", " .. self.Y
end

function Vector2:__add(other)
    self = assertVector2(self)
    other = assertVector2(other)

    return Vector2.new(self.X + other.X, self.Y + other.Y)
end

function Vector2:__sub(other)
    self = assertVector2(self)
    other = assertVector2(other)

    return Vector2.new(self.X - other.X, self.Y - other.Y)
end

function Vector2:__mul(other)
    self = assertVector2(self)
    other = assertVector2(other)

    return Vector2.new(self.X * other.X, self.Y * other.Y)
end

function Vector2:__div(other)
    self = assertVector2(self)
    other = assertVector2(other)

    return Vector2.new(self.X / other.X, self.Y / other.Y)
end

function Vector2:__eq(other)
    self = assertVector2(self)
    other = assertVector2(other)

    return self.X == other.X and self.Y == other.Y
end

---------------------------------------------------------------------------------------------------------------------

local Maze =
{
    Width = 119;
    Height = 19;

    Wall = utf8.char(0x2588);
    Open = ' ';

    Directions =
    {
        ['←'] = Vector2.new(-1,  0);
        ['→'] = Vector2.new( 1,  0);
        ['↑'] = Vector2.new( 0, -1);
        ['↓'] = Vector2.new( 0,  1);
    }
}

function Maze:Generate(seed)
    self.Grid = {}

    self.Width = (math.floor(self.Width / 2) * 2) + 1
    self.Height = (math.floor(self.Height / 2) * 2) + 1

    for y = 1, self.Height do
        self.Grid[y] = {}
        for x = 1, self.Width do
            self.Grid[y][x] = self.Wall
        end
    end

    if seed then
        math.randomseed(seed)
    end

    local function visit(from, to)
        local x, y = to.X, to.Y

        if x >= 1 and x <= self.Width then
            if y >= 1 and y <= self.Height then
                if self.Grid[y][x] == self.Wall then
                    local mid = (from + to) / 2
                    self.Grid[mid.Y][mid.X] = self.Open
                    self.Grid[y][x] = self.Open

                    local dirs = {}

                    for _, dir in pairs(self.Directions) do
                        table.insert(dirs, dir * 2)
                    end

                    while #dirs > 0 do
                        local index = math.random(1, #dirs)
                        local dir = table.remove(dirs, index)
                        visit(to, to + dir)
                    end
                end
            end
        end
    end

    local start = Vector2.new(2, 2)
    visit(start, start)
end

function Maze:Solve()
    local startPos = Vector2.new(1, 2)
    self.Grid[startPos.Y][startPos.X] = 'S'

    local endPos = Vector2.new(self.Width, self.Height - 1)
    self.Grid[endPos.Y][endPos.X] = 'E'

    local visited = {}
    local path = {}
    local g = 0

    for x = 1, self.Width do
        visited[x] = {}
        for y = 1, self.Height do
            visited[x][y] = (self.Grid[y][x] == self.Wall)
        end
    end

    local function aStar(pos)
        visited[pos.X][pos.Y] = true

        if pos == endPos then
            return true
        end

        while true do
            local lowestF, bestId = math.huge

            for id, dir in pairs(self.Directions) do
                local new = pos + dir
                if new.X >= 1 and new.X <= self.Width then
                    if new.Y >= 1 and new.Y <= self.Height then
                        if not visited[new.X][new.Y] then
                            local h = (endPos - new).Magnitude
                            local f = g + h

                            if f < lowestF then
                                lowestF = f
                                bestId = id
                            end
                        end
                    end
                end
            end

            if bestId then
                local bestDir = self.Directions[bestId]
                g = g + bestDir.Magnitude
                table.insert(path, bestId)

                local found = aStar(pos + bestDir)
                if found then
                    return true
                else
                    g = g - 1
                    table.remove(path)
                end
            else
                return false
            end
        end
    end

    aStar(startPos, startPos)

    local prev = startPos

    for i, nodeId in ipairs(path) do
        if nodeId ~= startPos then
            local node = prev + self.Directions[nodeId]
            if node ~= endPos then
                local nextId = path[i + 1]
                self.Grid[node.Y][node.X] = nextId
                prev = node
            end
        end
    end

    return path
end

function Maze:Render()
    for y = 1, self.Height do
        local row = ""
        for x = 1, self.Width do
            row = row .. self.Grid[y][x]
        end
        print(row)
    end
end

Maze:Generate()
Maze:Solve()
Maze:Render()