LÖVE

Code: Select all

function love.load()
  points = {}
  hostPoints = {}
  connections = {}
  
  minDistance = 30
  maxDistance = 60
  -- Number of times for host point to try to place a point near it
  hostTries = 3
  -- Maximum number of additional connections for newly placed point
  connectTries = 3
  -- When generating new hosts, this is the maximum number of connections a point can have
  hostGenMaxConnections = 3
  
  -- Adding first point
  screenWidth, screenHeight = love.graphics.getDimensions()
  local point = newPoint((screenWidth-40) / 2 + 20, (screenHeight-40) / 2 + 20)
  points[1] = point
  table.insert(hostPoints, newHost(point, hostTries))

  showNumbers = false
  zoomFactor = 1
  zoom = 1
  amount = 10000
end

function intersects (firstPointA, firstPointB, secondPointA, secondPointB)
  local firstPointSame = firstPointA == secondPointA or firstPointA == secondPointB
  local secondPointSame = firstPointB == secondPointA or firstPointB == secondPointB
  if firstPointSame or secondPointSame then
    return firstPointSame and secondPointSame
  end

  local k1 = (firstPointA.y - firstPointB.y)/(firstPointA.x - firstPointB.x)
  local c1 = firstPointA.y - (k1 * firstPointA.x)
  local k2 = (secondPointA.y - secondPointB.y)/(secondPointA.x - secondPointB.x)
  local c2 = secondPointA.y - (k2 * secondPointA.x)
  if k1 == k2 then
    return c1 == c2
  end
  local x = (c2-c1)/(k1-k2)
  local minX = math.min(firstPointA.x, firstPointB.x)
  local maxX = math.max(firstPointA.x, firstPointB.x)
  if x < minX or x > maxX then return false end
  minX = math.min(secondPointA.x, secondPointB.x)
  maxX = math.max(secondPointA.x, secondPointB.x)
  if x < minX or x > maxX then return false end
  return true
end

function distance(pointA, pointB)
  return math.sqrt((pointA.x - pointB.x)^2+(pointA.y - pointB.y)^2)
end

function generateGraphStep()
  if #hostPoints == 0 then return end
  local index = love.math.random(#hostPoints)
  host = hostPoints[index]
  host.times = host.times - 1
  if host.times == 0 then
    table.remove(hostPoints, index)
  end
  local degree = love.math.random() * math.pi * 2
  local length = love.math.random() * (maxDistance - minDistance) + minDistance
  local diffX = math.cos(degree) * length
  local diffY = math.sin(degree) * length
  local point = newPoint(host.point.x + diffX, host.point.y + diffY)

  local found = true
  local possibleConnections = {}
  local checkedPoints = {}
  for j=1,#points do
    dist = distance(points[j], point)
    if dist < minDistance then
      found = false
      break
    elseif dist <= maxDistance * 2 then
      if dist <= maxDistance and points[j] ~= host.point then
        table.insert(possibleConnections, points[j])
      end
      table.insert(checkedPoints, points[j])
    end
  end

  local vertices = {}
  if found then
    for i=1,#checkedPoints do
      local connPoint = checkedPoints[i]
      for j=1,#connections do
        local vertex = connections[j]
        if vertex.a == connPoint or vertex.b == connPoint then
          table.insert(vertices, vertex)
          if intersects(host.point, point, vertex.a, vertex.b) then
            found = false
            break
          end
        end
      end
    end
  end

  if found then
    points[#points+1] = point
    table.insert(hostPoints, newHost(point, hostTries))
    connections[#connections+1] = newGraph(host.point, point)

    shuffleTable(possibleConnections)
    connectCount = connectTries
    for i=1,#possibleConnections do
      if connectCount == 0 then
        break
      end
      local connPoint = possibleConnections[i]
      local canConnect = true

      for j=1,#vertices do
        local vertex = vertices[j]
        if intersects(connPoint, point, vertex.a, vertex.b) then
          canConnect = false
          break
        end
      end

      if canConnect then
        connections[#connections+1] = newGraph(connPoint, point)
        connectCount = connectCount - 1
      end
    end
  end
end

function newGraph(pointA, pointB)
  return { a = pointA, b = pointB }
end

function newHost(point, tries)
 return { point = point, times = tries }
end

function newPoint(x, y)
  return { x = x, y = y }
end

function love.update(dt)
  zoom = zoom + dt/20 * zoomFactor
  local timeToSpare = dt * 0.5
  local time = love.timer.getTime()
  while love.timer.getTime() < time + timeToSpare and #points < amount do
    if #points < amount then
      if #hostPoints == 0 then
        generateHosts(hostGenMaxConnections)
      end
      generateGraphStep()
    end
  end
end

function generateHosts(maxConnections)
  -- Generating with some hosts still existing can cause several same hosts in the list
  -- Skipping
  if #hostPoints > 0 then return end
  local counts = {}
  for i=1,#points do
    counts[i] = {point = points[i], count = 0}
  end
  for i=1,#connections do
    local graph = connections[i]
    local index = indexOf(points, graph.a)
    counts[index].count = counts[index].count + 1
    index = indexOf(points, graph.b)
    counts[index].count = counts[index].count + 1
  end
  for i=1,#counts do
    if counts[i].count <= maxConnections then
      table.insert(hostPoints, newHost(counts[i].point, hostTries))
    end
  end
end

function shuffleTable( t )
    local rand = love.math.random
    assert( t, "shuffleTable() expected a table, got nil" )
    local iterations = #t
    local j

    for i = iterations, 2, -1 do
        j = rand(i)
        t[i], t[j] = t[j], t[i]
    end
end

function love.draw()
  love.graphics.scale(1/zoom, 1/zoom)
  local dx = (screenWidth * zoom - screenWidth)/2
  local dy = (screenHeight * zoom - screenHeight)/2

  love.graphics.translate(dx, dy)

  love.graphics.setColor(100, 100, 100)
  for i=1,#connections do
    love.graphics.line(connections[i].a.x, connections[i].a.y, connections[i].b.x, connections[i].b.y)
  end

  for i=1,#hostPoints do
    love.graphics.setColor(255, 0, 255, 200)
    love.graphics.circle("fill", hostPoints[i].point.x, hostPoints[i].point.y, 5)
  end

  for i=1,#points do
    love.graphics.setColor(0, 150, 100, 200)
    love.graphics.circle("fill", points[i].x, points[i].y, 5)
    if showNumbers then
      love.graphics.setColor(255, 255, 255)
      love.graphics.print(i, points[i].x, points[i].y)
    end
  end
end

function indexOf(table, obj)
  for i=1,#table do
    if table[i] == obj then
      return i
    end
  end
  return nil
end

function love.keypressed( key, scancode, isrepeat )
  if scancode == "n" and not isrepeat then
    showNumbers = not showNumbers
  elseif scancode == "z" and not isrepeat then
    zoomFactor = zoomFactor + 1
  elseif scancode == "x" and not isrepeat then
    zoomFactor = zoomFactor - 1
  elseif scancode == "g" and not isrepeat then
    generateHosts()
  end
end