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)
- demo.gif (10.06 MiB) Viewed 3303 times
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
