Planar graph generation
Posted: Sun Dec 18, 2016 8:06 pm
Hey, everyone!
I've worked on generating some planar graph, thought it might be useful for someone else.
Hope you'll find it useful.
Demo (filmed 10fps, that's why it's laggy)
I've worked on generating some planar graph, thought it might be useful for someone else.

Hope you'll find it useful.
Demo (filmed 10fps, that's why it's laggy)
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