Bugg

import math, options

const
  MAX_ITEMS = 16
  MAX_SPLIT = byte(4)

type
  Bounds*   = tuple[x, y, w, h: float32]

  Region = object
    bounds:   Bounds
    regions:  array[4, int]
    nodes:    int
    size:     int
    grade:    byte

  Node[T]   = object
    case big: bool:
    of false: sNodes: array[MAX_ITEMS, (Bounds, T)]
    of true:  bNodes: seq[(Bounds, T)]

  QT* [T] = object
    bounds:       Bounds
    regions:      seq[Region]
    nodes:        seq[Node[T]]
    freeRegions:  seq[int]
    freeNodes:    seq[int]

    itSeq:        seq[(Bounds, T)]

proc collides*(r1, r2: Bounds): bool =
  r1.x < r2.x + r2.w and
    r1.x + r1.w > r2.x and
    r1.y < r2.y + r2.h and
    r1.h + r1.y > r2.y

proc emptyRegions(region: Region): bool = region.regions[0] == -1
proc emptyNodes(region: Region): bool = region.nodes == -1

iterator intersect(qt: QT, region: Region, b: Bounds): int =
  if not emptyRegions(region):
    for regionIndex in region.regions:
      try:
        if collides(qt.regions[regionIndex].bounds, b):
          yield regionIndex
      except:
        quit "This would not happen generating garbage inside this iterator, Try appending 'let rrr = $regionIndex'"

proc newRegion(bounds: Bounds, grade: byte): Region =
  Region(bounds: bounds, nodes: -1, regions: [-1, -1, -1, -1], grade: grade)

proc nextRegionsIndex(qt: var QT): array[4, int] =
  if len(qt.freeRegions) > 0:
    let firstRegion = qt.freeRegions[0]
    del qt.freeRegions, 0
    for i in 0..<4:
      result[i] = firstRegion + i
  else:
    let i = len(qt.regions)
    result = [i, i + 1, i + 2, i + 3]
    setLen(qt.regions, i + 4)

proc nextNodeIndex(qt: var QT): int =
  if len(qt.freeNodes) > 0:
    result = qt.freeNodes[^1]
    delete qt.freeNodes, len(qt.freeNodes) - 1
  else:
    result = len(qt.nodes)
    setLen(qt.nodes, len(qt.nodes) + 1)

proc removeNode(qt: var QT, regionIndex: int, nodeIndex: int) =
  add qt.freeNodes, nodeIndex
  qt.regions[regionIndex].nodes = -1

proc splitRegion(qt: var QT, regionIndex: int, bA, bB, bC, bD: Bounds) =
  let
    grade = qt.regions[regionIndex].grade + 1
    regions = nextRegionsIndex(qt)

  for i, bounds in [bA, bB, bC, bD]:
    qt.regions[regions[i]] = newRegion(bounds, grade)

  qt.regions[regionIndex].regions = regions
  qt.regions[regionIndex].size = 0

proc newNode[T](qt: var QT, regionIndex: int, node: Node[T]) =
  let nodeIndex = nextNodeIndex(qt)
  qt.nodes[nodeIndex] = node
  qt.regions[regionIndex].nodes = nodeIndex

proc insert[T](qt: var QT[T], regionIdx: int, element: T, bounds: Bounds): bool =
  let r = qt.regions[regionIdx]

  if r.nodes == -1:
    newNode(qt, regionIdx, Node[T](big: false))
    return insert(qt, regionIdx, element, bounds)

  let
    nodesIndex  = qt.regions[regionIdx].nodes
    size        = r.size

  template cNode(): auto = qt.nodes[nodesIndex]

  if size >= MAX_ITEMS and not cNode().big:
    qt.nodes[nodesIndex] = Node[T](big: true, bNodes: @(cNode().sNodes))
    return insert(qt, regionIdx, element, bounds)

  if cNode().big: add qt.nodes[nodesIndex].bNodes, (bounds, element)
  else: cNode().sNodes[size] = (bounds, element)

  inc qt.regions[regionIdx].size
  return true

proc createQuadTree*[T](bounds: Bounds): QT[T] =
  QT[T](bounds: bounds, regions: @[newRegion(bounds, 0)], nodes: @[],
    freeRegions: @[], freeNodes: @[])

proc add[T](qt: var QT[T], regionIndex: int, element: T, bounds: Bounds): bool =
  let
    region          = qt.regions[regionIndex]
    hasRegions      = not emptyRegions(region)
    full            = not hasRegions and region.size >= MAX_ITEMS
    smallestRegion  = region.grade >= MAX_SPLIT
    collision       = collides(bounds, region.bounds)

  # NOT HERE
  if not collision: return false

  # CONTINUE INSERTING
  if hasRegions:
    for rIdx in intersect(qt, region, bounds):
      if add(qt, rIdx, element, bounds): result = true
    return

  # INSERT HERE
  if smallestRegion or not full:
    return insert(qt, regionIndex, element, bounds)

  # ADD MORE SPACE
  let
    nodesIdx          = region.nodes
    nB                = region.bounds
    (nW, nH, nX, nY)  = (nB.w / 2, nB.h / 2, nB.x, nB. y)

    bA = (nX      , nY      , nW, nH)
    bB = (nX + nW , nY + nH , nW, nH)
    bC = (nX      , nY + nH , nW, nH)
    bD = (nX + nW , nY      , nW, nH)

  splitRegion qt, regionIndex, bA, bB, bC, bD

  ## Insert elements in new nodes
  template cNode(): auto = qt.nodes[nodesIdx]

  for rIdx in qt.regions[regionIndex].regions:
    if add(qt, rIdx, element, bounds): result = true
    if cNode().big:
      for n in cNode().bNodes:
        discard add(qt, rIdx, n[1], n[0])
    else:
      for i, n in cNode().sNodes:
        if i == region.size: break
        discard add(qt, rIdx, n[1], n[0])

  removeNode qt, regionIndex, nodesIdx

proc add*[T](qt: var QT[T], bounds: Bounds, element: T): bool =
  add(qt, 0, element, bounds)

#################################################
###############     TEST    #####################
#################################################

block:
  randomize(1234)
  var qt = createQuadTree[string]((0f, 0f, 256f, 256f))

  # Split Regions
  echo "INSERT MANY"
  const TOTAL_INSERT = 64
  for i in 1..TOTAL_INSERT:
    let x, y = float32(random(256))
    let (w, h) = (20f, 20f)

    doAssert add(qt, (x, y, w, h), $i)

  # >>> WITHOUT TOUCHING ANYTHING I GET
  #
  # # INSERT MANY
  # # Traceback (most recent call last)
  # # test2.nim(212)           test2
  # # test2.nim(170)           add
  # # test2.nim(45)            add
  # # system.nim(2525)         sysFatal
  # # Error: unhandled exception: index out of bounds [IndexError]

  # >>> NOW, MODIFY LINE 45 AND ADD 'let rrr = $regionIndex':
  #
  # # iterator intersect(qt: QT, region: Region, b: Bounds): int =
    # # if not emptyRegions(region):
      # # for regionIndex in region.regions:
        # # let rrr = $regionIndex  # <<<------------------------------ LINE 43
        # # if collides(qt.regions[regionIndex].bounds, b):
          # # yield regionIndex

  # NO PROBLEM!!!