Cauldron2D.Sectors.Bsp (Cauldron2D v0.2.2)

Copy Markdown View Source

A binary space partition of a sector map: the order to draw it in from any point, front to back, and the convex piece any point is in.

{segs, subsectors, nodes} = Cauldron2D.Sectors.Bsp.build(map)
Cauldron2D.Sectors.Bsp.locate(map, {x, y})

The level is cut by lines into convex subsectors, each a run of segs — pieces of the map's lines — in one sector. A node is a cutting line {x, y, dx, dy} with a child on each side and the bounding box of each child; the last node is the root.

  • a seg is %{from: {x, y}, to: {x, y}, line: index, side: 0 | 1, offset: distance}, where side is the side of its line it shows and offset how far along that side it starts

  • a subsector is %{first: index, count: n, sector: index}, its segs being first..first + count - 1
  • a node is %{x:, y:, dx:, dy:, boxes: {front_box, back_box}, children: {front, back}}, a box {top, bottom, left, right} and a child {:node, index} or {:leaf, index}; the front is the right of the cutting line, as Cauldron2D.Sectors.Map.point_side/2 reckons it

build/2 builds one from a map's lines. A level that carries its own BSP is read into the same shapes and used as it is.

Summary

Types

box()
child()

Functions

build(map, opts \\ [])

A BSP for map built from its lines: {segs, subsectors, nodes} as tuples.

locate(map, point)

The subsector point is in.

root(map)

The root of the map's BSP.

walk(map, point, acc, leaf, far?)

Visit the subsectors front to back as seen from point.

Types

box()

@type box() :: {float(), float(), float(), float()}

child()

@type child() :: {:node, non_neg_integer()} | {:leaf, non_neg_integer()}

Functions

build(map, opts \\ [])

@spec build(Cauldron2D.Sectors.Map.t(), keyword()) :: {tuple(), tuple(), tuple()}

A BSP for map built from its lines: {segs, subsectors, nodes} as tuples.

Cutting lines are chosen among the segs' own lines, weighing how many segs a cut would split against how unevenly it divides them. Options: :split_cost, the weight of one split against one seg of imbalance, default 8; :candidates, how many cutting lines are tried at each step, default 48.

locate(map, point)

@spec locate(Cauldron2D.Sectors.Map.t(), Cauldron2D.Sectors.Map.point()) ::
  non_neg_integer()

The subsector point is in.

root(map)

@spec root(Cauldron2D.Sectors.Map.t()) :: child()

The root of the map's BSP.

walk(map, point, acc, leaf, far?)

@spec walk(
  Cauldron2D.Sectors.Map.t(),
  Cauldron2D.Sectors.Map.point(),
  acc,
  (non_neg_integer(), acc -> acc),
  (box(), acc -> boolean())
) :: acc
when acc: term()

Visit the subsectors front to back as seen from point.

leaf is called leaf.(subsector_index, acc) and returns the new acc. Before going into the far side of a node, far?.(box, acc) is asked whether anything in that box can still be seen; returning false skips it.