main.nim

import strutils
import random

import sdl2

import dadren.application
import dadren.scenes
import dadren.utils

template `as` (a, b: untyped): untyped = ((b)a)

type
  BSPNode[T] = ref object of RootObj
    parent: BSPNode[T]
    region: Region[T]
  ParentNode[T] = ref object of BSPNode[T]
    forward, backward: BSPNode[T]
    position: float
  Leaf[T]= ref object of BSPNode[T]
    content: T
  HSplit[T] = ref object of ParentNode[T]
  VSplit[T] = ref object of ParentNode[T]
  BSPTree[T] = ref object
    root: BSPNode[T]
    leaves: seq[Leaf[T]]

proc newLeaf[T](content: T, left, top, right, bottom: float, parent: BSPNode[T] = nil): Leaf[T] =
  result = new(Leaf[T])
  result.parent = parent
  result.content = content
  result.left = left
  result.top = top
  result.right = right
  result.bottom = bottom

proc newBSPTree[T](content: T, left, top, right, bottom: float): BSPTree[T] =
  result = new(BSPTree[T])
  result.root = newLeaf(content, left, top, right, bottom)
  let l = result.root as Leaf[T]
  result.leaves = @[l]

proc midpoint[T](self:VSplit[T], target: Leaf): float =
  let width = target.right - target.left
  result = target.left + self.position * width

proc midpoint[T](self:HSplit[T], target: Leaf): float =
  let height = target.bottom - target.top
  result = target.top + self.position * height

proc adjustSource[T](self: VSplit[T], target: Leaf, midpoint: float) =
  target.right = midpoint
  target.parent = self

proc adjustSource[T](self: HSplit[T], target: Leaf, midpoint: float) =
  target.bottom = midpoint
  target.parent = self

proc newSibling[T](self: VSplit[T], target: Leaf, midpoint: float): Leaf =
  newLeaf[T](nil, midpoint, target.top, target.right, target.bottom, self)

proc newSibling[T](self: HSplit[T], target: Leaf, midpoint: float): Leaf =
  newLeaf[T](nil, target.left, midpoint, target.right, target.bottom, self)

proc newParent[T, K](self: BSPTree[T], parent: BSPNode[T], position: float): K =
  result = new(K)
  result.parent = parent
  result.position = position

  if isNil(parent):
    self.root = result

proc split[T, K](self: BSPTree[T], target: Leaf, parent: K): Leaf[T] =
  let mp = parent.midpoint(target)
  parent.backward = target
  parent.forward = parent.newSibling(target, mp)
  parent.adjustSource(target, mp)
  self.leaves.add(parent.forward as Leaf)
  return (parent.forward as Leaf)

proc vsplit[T](self: BSPTree[T], target:Leaf, position: float): Leaf[T] =
  var parent = newParent[T, VSplit[T]](self, target.parent, position)
  return self.split(target, parent)

proc hsplit[T](self: BSPTree[T], target:Leaf, position: float): Leaf[T] =
  var parent = newParent[T, HSplit[T]](self, target.parent, position)
  return self.split(target, parent)

proc delete[T](self: BSPTree[T], target:Leaf): Leaf[T] =
  # return target if it is the root node
  if self.root == target:
    return target

  var parent = (target.parent as ParentNode[T])

  # determine correct sibling
  if target == (parent.forward as Leaf):
    result = (parent.backward as Leaf)
  else:
    result = (parent.forward as Leaf)

  # if target's parent is root
  if self.root == target.parent:
    self.root = result
    return result

  if isNil(parent.parent):
    return result

  var grandparent = (parent.parent as ParentNode[T])

  # if target's parent is a split
  if parent == grandparent:
    grandparent.forward = result
  else:
    grandparent.backward = result

type
  Color = ref object
    r,g,b: int
  GameScene = ref object of Scene
    app: App
    bsp: BSPTree[Color]

proc newGameScene(app: App): GameScene =
  new(result)
  result.app = app
  let size = app.getLogicalSize()
  result.bsp = newBSPTree(Color(), 0f, 0f, size.w, size.h)

converter scancode2uint8(x: Scancode): cint = cint(x)
converter uint82bool(x: uint8):bool  = bool(x)

proc contains[T](self: utils.Region[T], x, y: float): bool =
  echo $self
  return true
  # return  x > self.left and x < self.right and
  #         y > self.top and y < self.bottom

method update(self: GameScene, t, dt: float) =
  let keys = getKeyboardState()
  var x, y: cint
  getMouseState(addr x, addr y)
  for node in self.bsp.leaves:
    var r: Region[float]
    r.left = node.left
    r.top = node.top
    r.right = node.right
    r.bottom = node.bottom
    if r.contains(cint(x.float / 4.0), cint(y.float / 4.0)):
      node.content = Color(r:255)
    else:
      node.content = Color(g:255)
  # if keys[SDL_SCANCODE_H.cint]:
  #   self.camera.move(-1, 0)
  # elif keys[SDL_SCANCODE_V.cint]:
  #   self.camera.move(1, 0)
  # elif keys[SDL_SCANCODE_D.cint]:
  #   self.camera.move(0, -1)

method draw(self: GameScene) =
  self.app.clear(0, 0, 0)

  for leaf in self.bsp.leaves:
    let margin = 5
    let
      left = leaf.left + margin
      right = leaf.right - margin
      top = leaf.top + margin
      bottom = leaf.bottom - margin
      color = leaf.content
    # echo left, ", ", top, ", ", right, ",", bottom
    self.app.display.setDrawColor(color.r.uint8, color.g.uint8, color.b.uint8, 255.uint8)
    for y in top..bottom:
      for x in left..right:
        self.app.display.drawPoint(x.cint, y.cint);

let
  app = newApp("settings.json")
  scene = newGameScene(app)
  root = (scene.bsp.root as Leaf[Color])

root.content = Color(b:255)
randomize()
for i in 0..3:
  let y = random(scene.bsp.leaves.len)
  var leaf = scene.bsp.leaves[y]
  let r = random(2) + 1
  if r == 1:
    var newLeaf = scene.bsp.hsplit((leaf as Leaf[Color]), 0.5)
    newLeaf.content = Color(r:255)
  elif r == 2:
    var newLeaf = scene.bsp.vsplit((leaf as Leaf[Color]), 0.5)
    newLeaf.content = Color(g:255)

scene.draw()
app.run(scene)

test.nim

import unittest

include main

type
  sLeaf = Leaf[string]
  sHSplit = HSplit[string]
  sVSplit = VSplit[string]

suite "bsp tree":
  setup:
    var
      content = "Hello World"
      bsp = newBSPTree(content, 0, 0, 100, 100)
      root = (bsp.root as sLeaf)

  test "creation":
    check:
      bsp.root of sLeaf
      isNil(root.parent)
      root.left == 0
      root.top == 0
      root.right == 100
      root.bottom == 100
      root in bsp.leaves
      root.content == content

  test "horizontal split":
    var
      sib = bsp.hsplit(root, 0.5)
      split = (bsp.root as sHSplit)

    check:
      bsp.root == sib.parent
      sib.parent of sHSplit
      sib == (split.forward as sLeaf)
      root == (split.backward as sLeaf)
      root.top == 0
      root.bottom == 50
      sib.top == 50
      sib.bottom == 100
      sib in bsp.leaves
      root in bsp.leaves

  test "vertical split":
    var
      sib = bsp.vsplit(root, 0.5)
      split = (bsp.root as sVSplit)

    check:
      bsp.root == sib.parent
      sib.parent of sVSplit
      sib == (split.forward as sLeaf)
      root == (split.backward as sLeaf)
      root.left == 0
      root.right == 50
      sib.left == 50
      sib.right == 100
      sib in bsp.leaves
      root in bsp.leaves


  test "deletion":
    var
      sib = bsp.vsplit(root, 0.5)
      split = (bsp.root as sVSplit)
      newRoot = bsp.delete(root)

    check:
      bsp.root == newRoot