main.lua

function love.load()
    -- Setup necessary to make the screen have a pixelated look
    window_width, window_height = 1280, 720
    game_width, game_height = 480, 270
    love.window.setMode(window_width, window_height)
    love.graphics.setDefaultFilter('nearest')
    love.graphics.setLineStyle('rough')
    canvas = love.graphics.newCanvas(game_width, game_height)

    physics_step()
end

function physics_step()
    in_physics_step = true
    love.physics.setMeter(8)
    world = love.physics.newWorld(0, 0)

    -- Create physics circles and boundary
    circles = {}
    local function create_physics_circle(x, y, radius)
        local circle = {}
        circle.body = love.physics.newBody(world, x, y, 'dynamic')
        circle.shape = love.physics.newCircleShape(radius)
        circle.fixture = love.physics.newFixture(circle.body, circle.shape)
        circle.radius = radius
        table.insert(circles, circle)
    end

    boundary = {}
    boundary.x1, boundary.y1, boundary.x2, boundary.y2 = game_width/2 - 40, game_height/2 - 81, game_width/2 + 40, game_height/2 + 81
    boundary.body = love.physics.newBody(world, 0, 0)
    boundary.shape = love.physics.newChainShape(true, boundary.x1, boundary.y1, boundary.x2, boundary.y1, boundary.x2, boundary.y2, boundary.x1, boundary.y2)
    boundary.fixture = love.physics.newFixture(boundary.body, boundary.shape)

    radii = {}
    for i = 1, 32 do table.insert(radii, 6) end
    for i = 1, 18 do table.insert(radii, 8) end
    for i = 1, 12 do table.insert(radii, 10) end
    for i = 1, #radii do create_physics_circle(game_width/2 + 4*(2*love.math.random()-1), game_height/2 + 4*(2*love.math.random()-1), table.remove(radii, love.math.random(1, #radii))) end

    -- Simulate
    for i = 1, 500 do world:update(1/60) end

    -- Create graph data structure and destroy physics world
    graph = {}
    for _, circle in ipairs(circles) do 
        circle.x, circle.y = circle.body:getPosition()
        table.insert(graph, {x = circle.x, y = circle.y, radius = circle.radius}) -- Populate graph data structure with nodes
    end
    world:destroy()
    in_physics_step = false

    pathing_step()
end

function pathing_step()
    in_pathing_step = true
    table.sort(graph, function(a, b) return a.y < b.y end)

    -- Connect nodes
    local function distance(x1, y1, x2, y2) return math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) end

    for i, node_1 in ipairs(graph) do
        for j, node_2 in ipairs(graph) do
            if i ~= j and distance(node_1.x, node_1.y, node_2.x, node_2.y) < 1.1*(node_1.radius + node_2.radius) then
                if not node_1.neighbors then node_1.neighbors = {} end
                table.insert(node_1.neighbors, node_2)
            end
        end
    end

    -- Create 2 vertical paths from top to bottom
    local function get_random_top_node()
        local min_y, max_y = 10000, -10000
        for _, node in ipairs(graph) do
            if node.y < min_y then min_y = node.y end
            if node.y > max_y then max_y = node.y end
        end
        local h_cutoff = math.abs(max_y - min_y)/5
        local top_nodes = {}
        for _, node in ipairs(graph) do
            if node.y <= min_y + h_cutoff then 
                table.insert(top_nodes, node)
            end
        end
        return top_nodes[love.math.random(1, #top_nodes)]
    end

    local function get_random_neighbor_down(node)
        local neighbors_down = {}
        for _, neighbor_node in ipairs(node.neighbors) do
            if neighbor_node.y > node.y then table.insert(neighbors_down, neighbor_node) end
        end
        return neighbors_down[love.math.random(1, #neighbors_down)]
    end

    local function create_path_from_top_to_bottom(i)
        -- Pick a new node until one that isn't selected is picked
        local node = get_random_top_node()
        while node.selected do node = get_random_top_node() end
        node.selected = i

        -- Pick random neighbor down until no more random neighbors down can be picked
        local down = get_random_neighbor_down(node)
        while down do
            down.selected = i
            down = get_random_neighbor_down(down)
        end
    end

    create_path_from_top_to_bottom(1)
    create_path_from_top_to_bottom(2)

    -- Create 2 horizontal paths from previously selected nodes
    local function get_random_neighbor_right(node)
        local neighbors_right = {}
        for _, neighbor_node in ipairs(node.neighbors) do
            if neighbor_node.x > node.x then table.insert(neighbors_right, neighbor_node) end
        end
        return neighbors_right[love.math.random(1, #neighbors_right)]
    end

    local function get_random_neighbor_left(node)
        local neighbors_left = {}
        for _, neighbor_node in ipairs(node.neighbors) do
            if neighbor_node.x < node.x then table.insert(neighbors_left, neighbor_node) end
        end
        return neighbors_left[love.math.random(1, #neighbors_left)]
    end

    local function get_random_selected_node()
        local node = graph[love.math.random(1, #graph)]
        while not node.selected do node = graph[love.math.random(1, #graph)] end
        return node
    end

    local function create_path_from_selected_node_to_left_or_right(i)
        -- Find the minimum/maximum left/right node positions and pick a random previously selected node
        local min_x, max_x = 10000, -10000
        for _, node in ipairs(graph) do
            if node.x < min_x then min_x = node.x end
            if node.x > min_x then max_x = node.x end
        end
        local node = get_random_selected_node()
        node.selected = i

        -- Pick random neighbor left/right until no more random neighbors left/right can be picked
        local distance_to_min, distance_to_max = math.abs(min_x - node.x), math.abs(node.x - max_x)
        if distance_to_min < distance_to_max then -- This node is closer to the left than to the right, therefore find a path to the right
            local right = get_random_neighbor_right(node)
            while right do
                right.selected = i
                right = get_random_neighbor_right(right)
            end
        else -- Find a path to the left
            local left = get_random_neighbor_left(node)
            while left do
                left.selected = i
                left = get_random_neighbor_left(left)
            end
        end
    end

    create_path_from_selected_node_to_left_or_right(3)
    create_path_from_selected_node_to_left_or_right(3)
    in_pathing_step = false
    final_step()
end

function final_step()
    in_final_step = true

    -- Place nodes in their proper world positions
    local function remap(old_value, old_min, old_max, new_min, new_max)
        local new_min = new_min or 0
        local new_max = new_max or 1
        local new_value = 0
        local old_range = old_max - old_min
        if old_range == 0 then new_value = new_min
        else
            local new_range = new_max - new_min
            new_value = (((old_value - old_min)*new_range)/old_range) + new_min
        end
        return new_value
    end

    for _, node in ipairs(graph) do
        if node.selected then
            node.x = remap(node.x, game_width/2 - 40, game_width/2 + 40, 0, 400)
            node.y = remap(node.y, game_height/2 - 81, game_height/2 + 81, -540, 270)
        end
    end
end

function love.update(dt)

end

function love.draw()
    love.graphics.setCanvas(canvas) -- Draw everything to the 480x270 canvas
    love.graphics.clear()

    -- Physics step
    if in_physics_step then
        for _, circle in ipairs(circles) do 
            circle.x, circle.y = circle.body:getPosition()
            love.graphics.circle('line', circle.x, circle.y, circle.radius)
        end
        love.graphics.rectangle('line', boundary.x1, boundary.y1, boundary.x2 - boundary.x1, boundary.y2 - boundary.y1)
    end

    -- Pathing step
    if in_pathing_step then
        for _, node in ipairs(graph) do
            love.graphics.setColor(1, 1, 1)
            if node.selected then
                if node.selected == 1 then love.graphics.setColor(0, 1, 0)
                elseif node.selected == 2 then love.graphics.setColor(1, 0, 0)
                elseif node.selected == 3 then love.graphics.setColor(0, 0, 1) end
                love.graphics.circle('line', node.x, node.y, 0.6*node.radius)
                for _, neighbor_node in ipairs(node.neighbors) do
                    if neighbor_node.selected then
                        love.graphics.line(node.x, node.y, neighbor_node.x, neighbor_node.y)
                    end
                end
            else
                love.graphics.circle('line', node.x, node.y, 0.6*node.radius)
                for _, neighbor_node in ipairs(node.neighbors) do
                    love.graphics.line(node.x, node.y, neighbor_node.x, neighbor_node.y)
                end
            end
        end
    end

    -- Graphics step
    if in_final_step then
        for _, node in ipairs(graph) do
            if node.selected then
                for _, neighbor_node in ipairs(node.neighbors) do
                    if neighbor_node.selected then
                        love.graphics.setColor(1, 1, 1)
                        love.graphics.line(node.x, node.y, neighbor_node.x, neighbor_node.y)
                    end
                end
            end
        end

        for _, node in ipairs(graph) do
            if node.selected then
                love.graphics.setColor(0, 0, 0)
                love.graphics.circle('fill', node.x, node.y, node.radius)
                love.graphics.setColor(1, 1, 1)
                love.graphics.circle('line', node.x, node.y, node.radius)
            end
        end
    end

    love.graphics.setCanvas()

    -- Draw 480x270 canvas scaled up to match window's resolution
    love.graphics.setColor(1, 1, 1)
    love.graphics.setBlendMode('alpha', 'premultiplied')
    love.graphics.draw(canvas, 0, 0, 0, window_width/game_width, window_height/game_height)
    love.graphics.setBlendMode('alpha')
end