path-maker-d

index.html

<div class="container">
</div>

path-maker-d.markdown

path-maker-d

A Pen by Edward FauchonJones on CodePen.

License.

script.coffeescript

# Define global path charachteristics
num = 12
size = 25
width = 20

# Define node class
class Node
  constructor: (@x, @y, @nodes=[]) ->
  queryPathToEdge: (previousNodes=[]) ->

    # Check if this node lies on the edge
    return true if @x is 0 or
      @x is (num-1)*size or
      @y is 0 or
      @y is (num-1)*size
    
    # Check if any neighbour nodes lie on the edge 
    for node in @nodes
      return true if node.x is 0 or
      node.x is (num-1)*size or
      node.y is 0 or
      node.y is (num-1)*size
      
    # Check if any neighbour nodes lie on paths to the edge
    for node in @nodes
      # Only check neighbours that have not been previously visited
      return true if previousNodes.indexOf(node) is -1 and
      node.queryPathToEdge(previousNodes.concat(@))
    
    return false

# Construct grid of nodes
grid = ((new Node(i*size, j*size) for i in [0...num]) for j in [0...num] )

# Populate nodes with grid neighbours
for i in [0...num]
  for j in [0...num]
    grid[j][i].nodes.push(grid[j][i+1]) if i+1 < num
    grid[j][i].nodes.push(grid[j+1][i]) if j+1 < num
    grid[j][i].nodes.push(grid[j][i-1]) if i-1 >= 0
    grid[j][i].nodes.push(grid[j-1][i]) if j-1 >= 0

# Flatten grid, because flat data is always better than not      
grid = _.flatten grid
searchGrid = grid.slice()

# Remove random edges according to the following rules
#
# 1. A node must never have 0 edges
# 2. A node must have a path to an edge node
for i in [0..1000]
  
  # Get random node
  idx = Math.floor Math.random()*searchGrid.length
  node = searchGrid[idx]
  nodes = node.nodes
  
  # Do not attempt to remove last edge
  if nodes.length is 1
    searchGrid.splice idx, 1
    continue
  
  # Get random neighbour
  neighbourIdx = Math.floor Math.random()*nodes.length
  neighbour = nodes[neighbourIdx]
  neighbourNodes = neighbour.nodes

  # Do not attempt to remove last edge of neighbour
  if neighbourNodes.length is 1
    searchIdx = searchGrid.indexOf neighbour
    searchGrid.splice(searchIdx, 1) if searchIdx isnt -1
    continue
  
  # Do not remove edge if there is no other path to the edge from node
  noPathsCount = 0
  for n in nodes
    continue if n is neighbour 
    if n.queryPathToEdge([node, neighbour])
    then break
    else noPathsCount++
  if noPathsCount is nodes.length-1
    searchGrid.splice idx, 1
    continue
    
  # Do not remove edge if there is no other path to the edge from neighbour
  noPathsCount = 0
  for n in neighbourNodes
    continue if n is node 
    if n.queryPathToEdge([node, neighbour])
    then break
    else noPathsCount++
  if noPathsCount is neighbourNodes.length-1
    searchIdx = searchGrid.indexOf neighbour
    searchGrid.splice(searchIdx, 1) if searchIdx isnt -1
    continue
  
  # Remove edge by removing eachother from neighbour nodes
  nodes.splice nodes.indexOf(neighbour), 1
  neighbourNodes.splice neighbourNodes.indexOf(node), 1

# Generate list of edges
edges = []
for node in grid
  for neighbour in node.nodes
    edges.push [[node.x, node.y], [neighbour.x, neighbour.y]]

# Prepare SVG container
container = document.querySelectorAll(".container")[0]
draw = SVG(container).size((num-1)*size + width, (num-1)*size + width)

# Render edges
for edge in edges
  draw
  .line(edge)
  .fill('none')
  .stroke
    color: 'white'
    width: width
    linecap: 'square'
    linejoin: 'miter'
  .transform
    x: width/2
    y: width/2

scripts

<script src="https://cdnjs.cloudflare.com/ajax/libs/svg.js/2.6.3/svg.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>

style.scss

html, body {
  margin: 0;
  padding: 0;
  width: 100vw;
  height: 100vh;
}

.container {
  width: calc(100% - 200px);
  height: calc(100% - 200px);
  margin: 100px;
  background-color: #2196F3;
  display: flex;
  justify-content:center;
  align-items:center;
}