If you’ve done data structures for any period of time, you would probably know about the binary tree. We use binary trees because of their efficiency: if I’m searching for a certain value, I can half the search space on each search iteration. This, is extremely useful, but not just in searching within an array. The binary tree can patch many problems that require an efficient search, so why not 2D space? This is where the BSP tree comes in.

What is BSP?

Binary Space Partitioning is, luckily, just as it sounds. It splits space into 2 parts recursively. In this post we’re only going to be looking at 2D space, however, the action of BSP can be used largely on any number of dimensions. Imagine we have an infinite plane, and a bunch of walls. Each of these walls are simply lines with a start point, and an end point. What BSP will do is take each line, and split the plane with it. In this way, every line on one side of the splitter goes on one side, and the opposite. We can then do this recursively until the tree is fully created, with each branch being a wall, and the leaf nodes of the tree being all the little pockets of space between them. With this thing now created, if we wanted to find an entity, we could search through the BSP tree, and reject half of the search space with each search 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, and we can now begin splitting our space.

Here we have chosen a line to split on, and we extend that line infinitely. However, we have to ensure we retain the actual finite bounds of this line, as they are still necessary for the real game logic.

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. Now we can perform our second split.

Here, we chose the yellow line to perform our split, and by this point you can imagine how the rest would go.

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

Everything is in a 2D world, so let’s start with a position data type.

type Pos struct {
x, y float64
}

We kind of want to have something we can insert into and query from the tree. For this case, we will make some simple entities. This way, when we test the BSP tree, we can see if our entities are ending up in the correct sections of space.

type Entity struct {
name string
pos  Pos
}

Now, the world will be split up by lines, so lets make that structure.

type Segment struct {
start, end Pos
}

Those are all the simple structures, hopefully those all make sense. It is also worth mentioning that when using a segment for splitting the plane, we will have to imagine it extending infinitely in both directions. This should make sense if you followed along with the diagrams I gave before. Furthermore, entities will usually have a radius or some bounding box, but in this example case, they will simply be points. Making them circles with a radius would not be too much extra work, and maybe a challenge for you at the end of this tutorial!

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
}

Just like a regular binary tree, we have two children. Notice that they are called front and back, rather than left and right. This is because walls usually have a front and back side, and when rendering the back side is usually skipped. Therefore, naming it this way will make it easier to remember which side not to draw (if used in a pseudo-3D context). Then, we have the segment that splits this BSP node in half, with all the lines on one side of this splitter ending up in the front child, and the opposite for the back. Lastly, since the leaf node of the BSP tree is the empty space rather than a splitter, we store all entities within that space in that leaf nodes. This way, we can say “get me all entities close to this point”, and it will be able to return one of these entity lists.

Now finally, just to wrap the data structure up nicely, we will have a BSP tree struct.

type BSPTree struct {
root *BSPNode
}

Having this structure may seem useless, but having a wrapper object will prove useful as the functionality get extended. It will be able to hide node creation logic, and also hide recursive function calls that may be dangerous for the outside to poke at.

What Methods?

Sadly, we can’t use a data structure if it doesn’t have any methods. Because of this, let us define them, as many as we can figure out beforehand.

func (segment *Segment) intersect(other Segment) (Pos, bool) {
// TODO: Gets the intersection point of two lines
return Pos{}, false
}

func (segment *Segment) intersectAsInfinite(other Segment) (Pos, bool) {
// TODO: Gets the intersection point of two lines
// it extends the first segment in both directions infinitely
return Pos{}, false
}

func (segment *Segment) pointInFront(pos Pos) bool {
// TODO: Returns true if the given position is in
// front of the segment
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 {
// TODO: Returns true if the line was successfully added
return false;
}

func (node *BSPNode) nodeAtPos(pos Pos) *BSPNode {
// TODO: Returns the leaf node that encapsulates the given point
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 {
// TODO: Returns true if the line was successfully added
return false;
}

func (tree *BSPTree) entitiesNearby(pos Pos) []*Entity {
// TODO: Returns a list of enemies that could possibly be nearby
return nil
}

All we’ve done differently here is return a list of entities rather than just the whole BSP node, since the outside code shouldn’t care what a BSP node is, they just want to find some entities!

Wrapper Implementation

The easiest thing to implement to start off will be the wrapper. This is because, well, there’s almost no logic to it. 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)
}

No extra logic needed here, so now let’s move on to some intersection code.

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, you may notice we have t and u, which will be floating point variables in our code. You may see these xs and ys with little numbers next to them. These are coordinates, such as our Pos struct we made before. x1 and y1 refers to the start position of the first line, and x2 and y2 is the end position of this line. The 3rd and 4th variants of these numbers are for the other line. So, now we have everything within the picture explained as data in our code, we should easily be able to translate it.

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)))

Yeah, pretty awful to look at. Luckily, if you look ahead, the denominator for both u and t are identical, so let’s move this to its own variable.

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

That’s a lot better, so now let’s make u.

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, and just assume the line is parallel but not coincident. So let’s add a little 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 <= 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 have one last thing to do. After this has run, we know that there must be an intersection, but we need to know the point of intersection. Even more fortunately, the Wikipedia blesses us again with a little 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. Also, when calculating the point of intersection, we use the second segment and u instead of the first segment and t. We could’ve done the same for the first method, but doing both will help us understand the relation between the 2 lines and these 2 magic values.

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, how do we figure out which child node to choose? Well, it’s simple! We just wrote a function to help us out here. We simply use the pointInFront method on this node’s splitter, and if it’s true, we pick the front child!

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. Furthermore, in DOOM, a lookup table would’ve been used for trigonometric functions such as sine and cosine, so this querying logic would’ve been extremely fast.

Building the BSP

All this will be useless, if we cannot build our BSP tree. So, let’s finally begin the most difficult task. Now, 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() {
// TODO: Propogate entities down to children
}

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.

1. The line is entirely in front of the splitter, so we move it to the front child
2. The line is entirely behind the splitter, so we move it to the back child
3. The line crosses the splitter, so we much split the line in two, and push both to each child.

There is actually a 4th case, which is the coincident case, but as I said before, we’re not going to worry about that right now.

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)
}

Notice that we only check if the other line’s start is in front of the splitter. We only need to check one, since if the other position wasn’t in front, we would’ve flagged the case as an intersection.

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
} else {
backLine = l2
}

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. In case that was tough to keep up with all these little code fragments, here is the entire method.

func (node *BSPNode) addLine(line *Segment) bool {
// Leaf case
if node.isLeaf() {
node.splitter = line
node.front = &BSPNode{}
node.back = &BSPNode{}
node.propogateChildren()
return true
}

// Branch case

// Point of intesection
poi, ok := node.splitter.intersectAsInfinite(*line)
if ok {
// Intersection case
l1 := &Segment{
line.start,
poi,
}

l2 := &Segment{
poi,
line.end,
}

var frontLine, backLine *Segment
if node.splitter.pointInFront(line.start) {
frontLine = l1
} else {
backLine = l2
}

added := true
added = added && node.front.addLine(frontLine)
added = added && node.back.addLine(backLine)
return added
}

// Entirely on one side case
if node.splitter.pointInFront(line.start) {
return node.front.addLine(line)
} else {
return node.back.addLine(line)
}
}

Coincident

Lastly, we have the coincident case, which will be interesting, but let’s give it a shot. 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 also have to make the change that the line intersection function will also have to return whether the lines were coincident.

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 (including the original splitter line). These lines won’t get in the way of any insertion or query logic, but the referencing must remain as they are 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.

1. 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).
2. Utilize this structure in one of your pre-existing games.
3. 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.
4. Create another query method but with a rectangle.
5. Make a program that takes in a list of lines, and will attempt to construct the most balanced BSP tree.
6. Maybe attempt to do some AVL tree style optimizations but for the BSP tree.
7. Write the tree to a file, and read it back.

The code for this implementation is available on GitHub.