A classic fundamental data structure is the binary tree, which allows us to half a given search space on each search iteration. Usually, this is used on a sorted array, so why not 2D space? Enter, the BSP tree.
What is BSP?
Binary Space Partitioning take 2D space and splits it into 2 parts recursively. In an infinite 2D world, we could use all the walls, split the plane with each of them, and placing each other line in either the left or right children of the tree. We do this recursively until we have each branch as a wall, and each leaf as a pocket of space. Then, if we wanted to find an entity within space, we could reject half of the search space with each iteration!
Visually Explained
That was a bit wordy, so it'll probably be better to go through with a visual example.
We start off with our basic walls as we talked about before.
Here we have chosen a line to split on, and we extend that line infinitely.
Now, everything to one side is going to be the left child of this binary tree, while the other side will be the right child. This is color coded in the image above.
Here, we chose the yellow line to perform our second split.
Now that image is after the final two splits.
Looking at this, we have all these little pockets of space that can be queried by walking down the tree.
Perfect, now we should start defining our structures.
Defining our Structures
Let's start with our basic data types.
type Pos struct {
x, y float64
}
type Entity struct {
name string
pos Pos
}
type Segment struct {
start, end Pos
}
It is worth mentioning that when using a segment for splitting the plane, we will extend it infinitely in both directions. We will be coming back to these structures later when we need to write methods for them, but for now, they are finished.
The BSP Node
This will be the main complicated data structure, the node for the BSP tree.
type BSPNode struct {
// Children
front, back *BSPNode
// If a branch node
splitter *Segment
// If a leaf node
entities []*Entity
}
And to wrap it, a BSP Tree struct.
type BSPTree struct {
root *BSPNode
}
What Methods?
Let's try to figure out as many methods as we can before we start coding.
func (segment *Segment) intersect(other Segment) (Pos, bool) {
return Pos{}, false
}
func (segment *Segment) intersectAsInfinite(other Segment) (Pos, bool) {
return Pos{}, false
}
func (segment *Segment) pointInFront(pos Pos) bool {
return false
}
These two will be useful, as we're going to need to decide whether a line intersects another in almost every step of the BSP tree creation. Then, we will also need to figure out whether a line should go to the front or back of a node, so we have made the pointInFront method specifically for this purpose.
Then we have the methods given for the BSP node.
func (node *BSPNode) addLine(line *Segment) bool {
return false;
}
func (node *BSPNode) nodeAtPos(pos Pos) *BSPNode {
return nil
}
First one is used when constructing the tree, it will either push the line to the left, right, or even split the line in half and push it to both. We also want to know if an error occurred, so it will return true if it was able to find a space for the line. Then, we want to be able to grab the node that will encompass a given position. From this, we will be able to grab nearby entities.
Then, we will provide wrapper functions on the BSP tree.
func (tree *BSPTree) addLine(line *Segment) bool {
return false;
}
func (tree *BSPTree) entitiesNearby(pos Pos) []*Entity {
return nil
}
All we've done differently here is return a list of entities rather than just the whole BSP node.
Wrapper Implementation
The easiest thing to implement to start off will be the wrapper. We're going to start with a constructor for this structure.
func (tree *BSPTree) init() {
tree.root = &BSPNode{
front: nil,
back: nil,
splitter: nil,
entities: nil,
}
}
The reason we do this is because there should always be at least the root node. If there are no lines, this root node simply encompasses everything, and is an infinite plane with no bounds. Currently, however, this node has no front, back, splitter, or entities.
Now we have that figured out, let's do the entitiesNearby method.
func (tree *BSPTree) entitiesNearby(pos Pos) []*Entity {
// Find the node that encompasses this area
node := tree.root.nodeAtPos(pos)
// No node found (should practically never happen),
// simply give back no entities
if node == nil {
return nil
}
return node.entities
}
Looks good, just calls the node's version of this method, with a little guard in case something goes wrong.
Now for the really short function of addLine.
func (tree *BSPTree) addLine(line *Segment) bool {
return tree.root.addLine(line)
}
Line Intersections
Let's start with our finite intersection, then we will very easily modify this for the infinite version. From Wikipedia, we are given a great formula to find out whether two line segments have intersected.
Looks like a lot of random letters everywhere, but we're going to go piece by piece to convert this into code.
Firstly, t and u appear to be floating point variables. Then, the x and y's are coordinates. Subscript 1 denotes the first line's start position, all the way to 4 being the other line's end position. With this in mind, we should be able to perform the code translation.
t := (
(
(segment.start.x-other.start.x) * (other.start.y-other.end.y) -
(segment.start.y-other.start.y) * (other.start.x-other.end.x)) /
(
(segment.start.x-segment.end.x) * (other.start.y-other.end.y) -
(segment.start.y-segment.end.y) * (other.start.x-other.end.y)))
Awful, let's take out the denominator, since it will be used for both u and t.
d := (
(segment.start.x - segment.end.x) *
(other.start.y - other.end.y) -
(segment.start.y - segment.end.y) *
(other.start.x - other.end.y))
t := (
(segment.start.x - other.start.x) *
(other.start.y - other.end.y) -
(segment.start.y - other.start.y) *
(other.start.x - other.end.x)) / d
u := -(
(segment.start.x - segment.end.x) *
(segment.start.y - other.start.y) -
(segment.start.y - segment.end.y) *
(segment.start.x - other.start.x)) / d
So easy! Except, we have one thing we missed, and that's the case where d is 0! If this is the case, two things are true, either that the lines are parallel, or perfectly laid on top of one another (coincident). We're going to ignore coincident cases right now. So let's add a guard to avoid the division by 0 error.
// Parallel
if d == 0 {
// FIX: Deal with coincident case
return Pos{}, false
}
Right, now everything is valid, we can decide whether the lines intersected. From the Wikipedia, we know the lines have intersected if 0 <= t <= 1 and 0 <= u <= 1. So let's simply calculate this.
hasIntersected := 0 <= t && t <= 1 && 0 <= u && u <= 1
if !hasIntersected {
return Pos{}, false
}
We're so close now! We just need to find the point of intersection. Even more fortunately, the Wikipedia blesses us again with a line just before the last paragraph. This line defines Px and Py. These are the coordinates of the intersection. Let's calculate these values as described.
intersection := Pos{
segment.start.x + t * (segment.end.x - segment.start.x),
segment.start.y + t * (segment.end.y - segment.start.y),
}
return intersection, true
And there it is! We've found the intersection between two finite lines, but what about an infinite line and a finite line? Well, the Wikipedia gives us the knowledge that if t is in the range we checked, then the intersection point is within the first line segment's range, while u says the same for the second line segment. Therefore, if u is true, it doesn't matter if t is true. This is because we don't need an intersection within the first line's range, since we're extending it towards infinity. As long as there is an intersection on the second line, we're good.
func (segment *Segment) intersectAsInfinite(other Segment) (Pos, bool) {
d := (
(segment.start.x - segment.end.x) *
(other.start.y - other.end.y) -
(segment.start.y - segment.end.y) *
(other.start.x - other.end.y))
// Parallel
if d == 0 {
// FIX: Deal with coincident case
return Pos{}, false
}
u := -(
(segment.start.x - segment.end.x) *
(segment.start.y - other.start.y) -
(segment.start.y - segment.end.y) *
(segment.start.x - other.start.x)) / d
hasIntersected := 0 <= u && u <= 1
if !hasIntersected {
return Pos{}, false
}
intersection := Pos{
other.start.x + u * (other.end.x - other.start.x),
other.start.y + u * (other.end.y - other.start.y),
}
return intersection, true
}
Looks pretty similar, but now we don't even need to calculate t.
Now for the last segment method, is a point in front of this segment? Well, interestingly, we first have to define what "in front" even means. We're going to define this as the face that points in a counter-clockwise direction, if we were to define the start as the center of a circle, and end a point on the circumference.
Very good, so now it should be relatively easy to calculate this. We can calculate whether a point is in front of a segment by first getting the angle from the segment's start to the segment's end. Then, we do the same for the segment's start to the query point. If the second angle is greater than the first, then it is in front. So let's start by getting those two angles.
dx := segment.end.x - segment.start.x
dy := segment.end.y - segment.start.y
dis := math.Sqrt(dx*dx + dy*dy)
a1 := math.Acos(dx/dis)
if dy < 0 {
a1 = -a1
}
dx = pos.x - segment.start.x
dy = pos.y - segment.end.y
dis = math.Sqrt(dx*dx + dy*dy)
a2 := math.Acos(dx/dis)
if dy < 0 {
a2 = -a2
}
Since this is a very simple duplication of logic, why don't we move this to its own method?
func (pos *Pos) angleTo(other Pos) float64 {
dx := other.x - pos.x
dy := other.y - pos.y
dis := math.Sqrt(dx*dx + dy*dy)
// Avoid division by 0
if dis == 0 {
return 0
}
a := math.Acos(dx/dis)
if dy < 0 {
a = -a
}
return a
}
Much easier. Now, since we're comparing angles, it's always much easier to simply subtract them, then compare with 0. This way, a positive angle is a front face, and a negative angle is a back face. No angle means it fits perfectly on the line (which is annoying). To make this a much simpler task, rather than fiddling with whether the value is over 360, we're just going to consider the sine of the angle for our calculation.
func (segment *Segment) pointInFront(pos Pos) bool {
a1 := segment.start.angleTo(segment.end)
a2 := segment.start.angleTo(pos)
s := math.Sin(a2-a1)
return s >= 0
}
I mean, you couldn't ask for nicer looking code.
And that's all for the logic of lines, for now.
At this point, we can start working on the BSP node!
Query?
Because we never like doing things in the correct order, let's do the nodeAtPos method first. Our first case is that if we're a leaf node, we return the current node. If it's not, we find which side this point belongs on, then recurse into the correct child node.
func (node *BSPNode) isLeaf() bool {
return node.front == nil && node.back == nil
}
func (node *BSPNode) nodeAtPos(pos Pos) *BSPNode {
// Leaf case
if node.isLeaf() {
return node
}
// Branch case
return nil
}
Now we can use the pointInFront method to decide which child to chose in the branch case.
func (node *BSPNode) nodeAtPos(pos Pos) *BSPNode {
// Leaf case
if node.isLeaf() {
return node
}
// Branch case
if node.splitter.pointInFront(pos) {
return node.front.nodeAtPos(pos)
} else {
return node.back.nodeAtPos(pos)
}
}
And that's literally it! So simple! Now you can probably imagine just how efficient this data structure really is.
Building the BSP
Now to building the BSP tree. A BSP node is given a line, and what that node does with the line depends on many things, the first being whether it is a leaf node. Let's start with the leaf node case.
func (node *BSPNode) propogateChildren() {
}
func (node *BSPNode) addLine(line *Segment) bool {
if node.isLeaf() {
node.splitter = line
node.front = &BSPNode{}
node.back = &BSPNode{}
node.propogateChildren()
return true
}
return false
}
Note that we have to go through all the entities in this node, and move them to either the front or back child. Let's write that function now.
func (node *BSPNode) addEntity(e *Entity) {
// Leaf case
if node.isLeaf() {
node.entities = append(node.entities, e)
return
}
// Branch case
if node.splitter.pointInFront(e.pos) {
node.front.addEntity(e)
} else {
node.back.addEntity(e)
}
}
func (node *BSPNode) propogateChildren() {
// Go through each entity, attempting
// to pass it on to a child
for i := range len(node.entities) {
e := node.entities[i]
if node.splitter.pointInFront(e.pos) {
node.front.addEntity(e)
} else {
node.back.addEntity(e)
}
}
}
Perfect, now let's get back to what we were doing, inserting lines. There are three cases that we have to be weary about at this point. We're trying to decide whether a line should be pushed to the back or front child.
- The line is entirely in front of the splitter, so we move it to the front child
- The line is entirely behind the splitter, so we move it to the back child
- The line crosses the splitter, so we much split the line in two, and push both to each child.
First, let's check if the lines intersect, and if they don't, we can do the first two cases.
// Point of intesection
poi, ok := node.splitter.intersectAsInfinite(*line)
if ok {
// Intersection case
_ = poi
return false
}
// Entirely on one side case
if node.splitter.pointInFront(line.start) {
return node.front.addLine(line)
} else {
return node.back.addLine(line)
}
So all we have to do now is create the two new lines, and give them to the front and back children.
l1 := &Segment{
line.start,
poi,
}
l2 := &Segment{
poi,
line.end,
}
This creates our two lines.
var frontLine, backLine *Segment
if node.splitter.pointInFront(line.start) {
frontLine = l1
backLine = l2
} else {
backLine = l2
frontLine = l1
}
This chooses which line will be used for which child.
added := true
added = added && node.front.addLine(frontLine)
added = added && node.back.addLine(backLine)
return added
And there we go, we've now completed the insertion of a line into the BSP tree.
Coincident
Lastly, we have the coincident case. First, it would be helpful to know if a point lays exactly on top of another line, and is therefore not in front or behind.
func (segment *Segment) pointOnLine(pos Pos) bool {
a1 := segment.start.angleTo(segment.end)
a2 := segment.start.angleTo(pos)
s := math.Sin(a2-a1)
return s == 0
}
Then, during intersection checks, if we find parallel lines, and one of the points on the second line lies on the first line, we have coincident lines. We must also make the intersection's return more robust.
type LineIntersection byte
const (
LI_NONE LineIntersection = iota
LI_INTERSECT
LI_COINCIDENT
)
This is just an enum to tell us what type of intersection occurred.
// Parallel
if d == 0 {
if segment.pointOnLine(other.start) {
return Pos{}, LI_COINCIDENT
}
return Pos{}, LI_NONE
}
Nice, now we can use this value meaningfully in the rest of our code.
case LI_COINCIDENT:
// Keep a reference, but don't use
// as a splitter
node.lines = append(node.lines, line)
return true
Here we've added a property to the BSP node that is just a list of lines. This way, any coincident lines can be kept in this list. These lines won't get in the way of any insertion or query logic, but the reference must remain as it is important to level structure.
Testing
Now the scary bit, is our code correct? Really, we should be proud at this moment. We've written a lot of code, with a lot of it being complicated and dealing with trigonometry. All the more reason to ensure its legitimacy with some testing!
func main() {
// Create a new BSP tree
bsp := &BSPTree{}
bsp.init()
fmt.Println("Attempting to add first line")
fmt.Println(bsp.addLine(&Segment{
Pos{0, -100},
Pos{0, 100},
}))
fmt.Println("Testing the 'line in front' case")
fmt.Println(bsp.addLine(&Segment{
Pos{10, -100},
Pos{20, 100},
}))
fmt.Println("Testing the 'line behind' case")
fmt.Println(bsp.addLine(&Segment{
Pos{-10, -100},
Pos{-20, 100},
}))
fmt.Println("Testing the 'line split' case")
fmt.Println(bsp.addLine(&Segment{
Pos{10, 0},
Pos{100, 0},
}))
fmt.Println("Testing the 'line coincident' case")
fmt.Println(bsp.addLine(&Segment{
Pos{0, 200},
Pos{0, 300},
}))
}
Sure, it's not the most exhaustive testing, but that shall do for now. For your testing, maybe add a method to add entities, then test whether you can retrieve those entities back.
Challenge
That was a lot of work, but now we have a fully operational BSP tree that can be used in many applications. As per usual, we won't end at this post, here are your challenges for using this BSP tree.
- Visualize the BSP tree, by showing each line that is in it. Furthermore, it would be nice to be able to see which side of a line is the front, and coloring of the empty space (as in my example images).
- Utilize this structure in one of your pre-existing games.
- Create a method to query the BSP tree for entities where the query parameter is a circle, and it will return every entity within that circle.
- Create another query method but with a rectangle.
- Make a program that takes in a list of lines, and will attempt to construct the most balanced BSP tree.
- Maybe attempt to do some AVL tree style optimizations but for the BSP tree.
- Write the tree to a file, and read it back.
The code for this implementation is available on GitHub.