DEV Community: Chig Beef

Line by Line, Finding Walls for Rendering in a BSP Tree

Chig Beef — Tue, 11 Nov 2025 04:05:49 +0000

Recently we managed to grab all entities that a camera could hypothetically see from a BSP tree. Now, it's time for the similar job of finding all walls that should be rendered. The main idea here is that we want as few walls as possible, to minimize compute and overdraw. Although we won't be doing the actual rendering, this could be used by a game that would do the rendering.

Also, after the last post, I added functionality to find entities using a circle as the query object. I would suggest looking through the code for that one, and see if you can understand it. This functionality would be good for checking collision between the player and entities (if the player is a cylinder).

Using the View Frustum

When we were funding entities, we were able to use this thing called the view frustum to search for ones that were visible. This is exactly what we're going to do here.

func (node *BSPNode) querySegmentsByTriangle(triangle Triangle) []*Segment {
    // Finds all segments that are within this triangle
    return nil
}

func (tree *BSPTree) querySegmentsByTriangle(triangle Triangle) []*Segment {
    return tree.root.querySegmentsByTriangle(triangle)
}

// Queries the BSP tree using the
// view frustum for all viewable walls
func (camera *Camera) getWallsInView(world *BSPTree) []*Segment {
    return world.querySegmentsByTriangle(camera.createViewFrustum())
}

As per usual, we've defined the wrapper method on the tree, and call this from the camera using the view frustum.

How Do We Get The Lines?

With pretty much every query we've made so far, we've done the leaf node case first, which is exactly what we're going to do now. The thing is, the leaf nodes don't contain any lines, and therefore don't need checking. This means if we're at a leaf node, we do nothing!

if node.isLeaf() {
    return nil
}

Now we can start the interesting case, branch nodes. Just like querying entities with a triangle, we want to know if the triangle overlaps the splitter, or is entirely on one side. If it is entirely on one side, then we don't add any lines, but check the respective child node.

relation := node.splitter.triangleRelation(triangle)

switch relation {
case 1:
    return node.front.querySegmentsByTriangle(triangle)
case -1:
    return node.back.querySegmentsByTriangle(triangle)
default:
    // TODO: Triangle lies on splitter
    // (need to search through own lines)
    return append(
        node.front.querySegmentsByTriangle(triangle),
        node.back.querySegmentsByTriangle(triangle)...,
    )
}

If it's fully in front, only check the front. If it's fully behind, only check behind. If it's both, check both, and we also need to check the splitting lines. So now we need a method to check if a line intersects with a triangle. There are many cases to this, but there are 3 main ones.

The line intersects with one of the triangle's lines.
The line is fully within the triangle, and therefore no intersects trigger.
The line is outside of the triangle completely.

With these in mind, let's start writing!

func (triangle *Triangle) segmentIntersect(segment Segment) bool {
    // Find intersections between any lines
    _, i := (&Segment{triangle.p1, triangle.p2}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    _, i = (&Segment{triangle.p2, triangle.p3}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    _, i = (&Segment{triangle.p3, triangle.p1}).intersect(segment)
    if i != LI_NONE {
        return true
    }

    return false
}

Those are the line intersect cases, so we've done case 1 (and implicitly case 3 with the final return false). And case 2 should be easy, just check if one of the segment's points is within the triangle.

return triangle.pointWithin(segment.start)

As per usual, we only have to check one of the ends. This is because if only one point was within, an intersection would've occurred and be caught by an earlier case.

Getting ALL Intersecting Lines

So now we know how to check if a line is within a triangle, we can find all the intersecting lines from the node.

func (node *BSPNode) getLinesWithinTriangle(triangle Triangle) []*Segment {
    // Start with some capacity rather than
    // many grow calls
    marked := make([]*Segment, 0, len(node.lines))

    // Find all intersecting lines
    for i := range len(node.lines) {
        s := node.lines[i]
        if triangle.segmentIntersect(*s) {
            marked = append(marked, s)
        }
    }

    return marked
}

Then, we use this function in that recursive query we were writing before.

return append(
    node.getLinesWithinTriangle(triangle),
    append(
        node.front.querySegmentsByTriangle(triangle),
        node.back.querySegmentsByTriangle(triangle)...,
    )...
)

And that should get us all the intersecting lines!

First Tests

Using this:

walls := camera.getWallsInView(bsp)
fmt.Println("Found these walls from triangle")
for i := range len(walls) {
    fmt.Println(walls[i])
}

I get some walls! And the walls look correct after looking through the original level. What would be cool is to have a top down visualization of those walls that are marked for rendering.

Back-face Culling

We're not done yet, when finding walls to mark for rendering, we want as few as possible. A common way to cull lines is through the method of back-face culling. What this does is only render the lines that are facing towards the camera. Imagine the walls in your house, they are not a single segment, but rather 4 segments put together to give the physical wall depth. You can now imagine that the front-face of these segments all face outwards, and the back-face points inwards. In this way, all the back-faces are occluded by the front-faces, so they will never be drawn. Here is a diagram to help with this a bit.

As you can see, there is never a case where you can actually see the back-faces, and so we're going to cull them!

// Queries the BSP tree using the
// view frustum for all viewable walls
func (camera *Camera) getWallsInView(world *BSPTree) []*Segment {
    return camera.backfaceCull(
        world.querySegmentsByTriangle(
            camera.createViewFrustum(),
            ),
        )
}

// Deletes any walls that aren't
// facing the player
func (camera *Camera) backfaceCull(walls []*Segment) []*Segment {
    facing := make([]*Segment, 0, len(walls))

    for i := range len(walls) {
        w := walls[i]
        if w.pointInFront(camera.pos) {
            facing = append(facing, w)
        }
    }

    return facing
}

That was very easy, doesn't change the output for me since each line is facing the camera, but, looks good. Now we have an efficient way to find all segments the camera can see!

Challenge

The BSP tree is coming together quite nicely, but it's still far from being usable. Hence, here are some more vital functions you could add.

Hit-scan collision with walls to find closest point of contact.
Hit-scan collision with entities to find possible targets.
Player collision with walls.
Moving an entity through the BSP tree.

Line by Line, HOW do I query my BSP?

Chig Beef — Mon, 10 Nov 2025 05:51:11 +0000

Now, if you read my last post (sorry about the length...), you will remember we constructed a BSP tree. The BSP tree we created could hold these entities, but we never actually used this feature. Well, I was sitting and thinking about what someone might want to do with a BSP tree, and then it hit me, read from it! So, that's exactly what we're going to do, except, we're going to do it for a specific use case.

The View Frustum

Imagine you're playing a 3D game, where the walls are governed by a BSP tree. Now, looking from the top down, what would the player's view look like? A triangle! This is called the view frustum. What we're going to do, is apply the view frustum on the BSP tree, and in return we should get all entities that a hypothetical player could see. Our current function simply takes a point, and gets all entities in the node at that point, but that's practically useless. So now after all this, we should end up with some meaningful functionality.

The Camera

To start our programming, we want a camera object that we can move around the world. This way, we could easily move it around to get different results.

type Camera struct {
    pos     Pos
    angle   float64
    viewDis float64
    fov     float64
}

func (camera *Camera) createViewFrustum() int {
    // Generates a bounding triangle that
    // should encapsulate everything that
    // the camera can see
    // TODO: Return a triangle
    return 0
}

func (camera *Camera) getEntitiesInView(world *BSPTree) []*Entity {
    // Queries the BSP tree using the
    // view frustum for all viewable entities
    return nil
}

A position, an angle, the view distance, and the field of view, pretty simple. We also need to be able to create the view frustum based off of the camera, so we've got a method for that. We also need that method to get all the entities the camera can view. We're missing something, we need to define what a triangle is, otherwise we can't make that view frustum.

type Triangle struct {
    p1, p2, p3 Pos
}

Very simple, pretty much exactly how you would expect. Remember, lines have a front and a back side, so the order of p1, p2, and p3 will be important later.

Creating the View Frustum

Let's implement generating the view frustum. All we need is to create a triangle, and for that, we only need 3 points. The first point is obvious, the position of the camera, but the other two will require some trigonometry to figure out.

return Triangle{
    p1: camera.pos,
    p2: Pos{},
    p3: Pos{},
}

Well, it should be pretty easy to generate a point in the direction the player is facing. We would simply use sine and cosine to get the x and y coordinates of this point using the camera's angle as input. Then, we would scale by view distance. Well, we can do the exact same thing for the edges of our view. All we have to do is add or subtract half of the field of view before our calculations!

return Triangle{
    p1: camera.pos,
    p2: Pos{
        camera.pos.x + math.Cos(camera.angle-camera.fov/2)*camera.viewDis,
        camera.pos.y + math.Sin(camera.angle-camera.fov/2)*camera.viewDis,
    },
    p3: Pos{
        camera.pos.x + math.Cos(camera.angle+camera.fov/2)*camera.viewDis,
        camera.pos.y + math.Sin(camera.angle+camera.fov/2)*camera.viewDis,
    },
}

Looks like we've started to do some addition of positions and multiplication of magnitudes, so let's move those to their own functions.

func (pos Pos) add(other Pos) Pos {
    return Pos{
        pos.x + other.x,
        pos.y + other.y,
    }
}

func (pos Pos) scale(scale float64) Pos {
    return Pos{
        pos.x * scale,
        pos.y * scale,
    }
}

func (camera *Camera) createViewFrustum() Triangle {
    return Triangle{
        p1: camera.pos,
        p2: camera.pos.add(Pos{
            math.Cos(camera.angle-camera.fov/2),
            math.Sin(camera.angle-camera.fov/2),
        }.scale(camera.viewDis)),
        p3: camera.pos.add(Pos{
            math.Cos(camera.angle+camera.fov/2),
            math.Sin(camera.angle+camera.fov/2),
        }.scale(camera.viewDis)),
    }
}

That's a lot better, and will probably help in future, but with that, we have completed our view frustum.

Finishing the Camera

Before we can finish the camera, let's define our method on the BSP tree to run this code.

func (tree *BSPTree) queryEntitiesByTriangle(triangle Triangle) []*Entity {
    // Will find all entities within this triangle
    return nil
}

Nice, now we can call this in our camera code.

func (camera *Camera) getEntitiesInView(world *BSPTree) []*Entity {
    return world.queryEntitiesByTriangle(camera.createViewFrustum())
}

We just take that view frustum we made, and chuck it into the query logic. However, how do we know if an entity is within a triangle? Let's create a function for that, that decides whether a point is within. Luckily, the way we've defined everything makes this very simple.

Remember, lines have a front and a back, and they also have a method for determining whether a point is in front of the line or not. In the way we've defined our triangle, we are able to deduce that the point is within it if the point is in front of all the lines that make up the triangle. Make sense? Let's write the code, that might help.

func (triangle *Triangle) pointWithin(pos Pos) bool {
    return (
        (&Segment{triangle.p1, triangle.p2}).pointInFront(pos) &&
        (&Segment{triangle.p2, triangle.p3}).pointInFront(pos) &&
        (&Segment{triangle.p3, triangle.p1}).pointInFront(pos))
}

Bam, so now we can easily check if an entity is within the view frustum, since the view frustum is a triangle, and an entity is a point.

I think we're ready to get into the real code.

Querying the Node

As per usual, we have 2 cases, those being a leaf node, and a branch node. Let's start with the leaf node.

if node.isLeaf() {
    // Create the list of entities to
    // give back to query
    chosen := []*Entity{}

    // Find all entities within
    for i := range len(node.entities) {
        e := node.entities[i]
        if triangle.pointWithin(e.pos) {
            chosen = append(chosen, e)
        }
    }

    return chosen
}

This should make sense, just finding the entities that are within the triangle. However, we will now get to the more complicated case, branches. What we need to figure out is whether the triangle is entirely on one side of the splitter, or crosses it. If it is entirely on one side, then we only need to query one child, which is the efficient case we'd like. However, if the triangle lies over the splitter, then we need to query both children. From this, we want a method we can use to decide whether a triangle is in front, behind, or on top of a line.

// Positive if in front, negative if behind, 0 is on top
func (segment *Segment) triangleRelation(triangle Triangle) int {
    b1 := segment.pointInFront(triangle.p1)
    b2 := segment.pointInFront(triangle.p2)
    b3 := segment.pointInFront(triangle.p3)

    if b1 && b2 && b3 {
        // Fully in front
        return 1
    } else if !b1 && !b2 && !b3 {
        // Fully behind
        return -1
    } else {
        // Both
        return 0
    }
}

Having three cases does make this annoying, but hopefully this makes sense. From this, we can complete the branch case.

relation := node.splitter.triangleRelation(triangle)

switch relation {
case 1:
    return node.front.queryEntitiesByTriangle(triangle)
case -1:
    return node.back.queryEntitiesByTriangle(triangle)
default:
    return append(
        node.front.queryEntitiesByTriangle(triangle),
        node.back.queryEntitiesByTriangle(triangle)...,
        )
}

This should make the efficiency of the first two cases obvious, as we only have to do half the work.

Testing

// Get some entities?
camera := Camera{
    pos:     Pos{0, 0},
    angle:   0,
    viewDis: 200,
    fov:     math.Pi/2, // 90deg
}

fmt.Println(camera.getEntitiesInView(bsp))

Now obviously, we have no entities in the BSP, so this returns an empty list. So now we know it doesn't hallucinate! But let's test a real case, let's add some entities.

bsp.addEntity(&Entity{
    name: "John",
    pos:  Pos{50, 0},
})

bsp.addEntity(&Entity{
    name: "Mark",
    pos:  Pos{0, 50},
})

bsp.addEntity(&Entity{
    name: "Luke",
    pos:  Pos{-50, 0},
})

bsp.addEntity(&Entity{
    name: "Matthew",
    pos:  Pos{0, -50},
})

entities := camera.getEntitiesInView(bsp)
fmt.Println("Found these entities")
for i := range len(entities) {
    fmt.Println(entities[i].name)
}

Now, given the camera is looking towards the positive x-axis from origin, we should expect the entity with a positive x position to be shown, and this is exactly what I get, John. So with that, we've completed our work!

Challenge

Now we're able to imagine what entities might be shown if we were to view this from a first-person perspective, but what about some other useful queries? I already put rectangle and circle collision in the last post's challenges, so let's do something different.

Similar to this queryEntitiesByTriangle, can you write querySegmentsByTriangle.
Moving and turning the camera.
Having moving entities.
Could you disregard entities that are entirely obscured by a wall?
Visualize the view frustum and visible entities.

Note, for a little help, I've written lines to an external file, and the BSP tree is also written to a file. This way, you can easily modify the walls of the world, and see what BSP tree results.

Line by Line, But HOW Do I Construct A BSP Tree?

Chig Beef — Sat, 08 Nov 2025 05:34:38 +0000

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 <= 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 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.

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.

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

        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.

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.

Make In A Day: Hovertank One

Chig Beef — Sat, 16 Aug 2025 12:56:28 +0000

First question, what is Hovertank One? Remember DOOM, Quake, and Wolfenstein. Hovertank One was before them all, created by id software. This is probably going to be the only 3D game in this series. Even then, this game is not truly 3D, but will appear to be so.

If you don't know the challenge already, it's to make it in one day. Before we start coding, and start that timer, we fully design a spec. This way we don't feel cheated for forgetting something at the end. If our application adheres to our concrete design list, we've made Hovertank One!

It's been a while, and I felt this would be a big one to do as a comeback.

I'll be using Golang and Ebitengine. I'll also be using my own UI code. All other code will be written within on day, and hopefully you can do the same. Choose your own language, game engine, whatever, the idea of the code should be the same.

From the User's Perspective

First, we're in a different perspective, so we need to implement that. The world is built on a grid. There are enemies that you can shoot, and that will chase you down. There are civilians that you can save. The walls can have different colors, and the floor and ceiling must be shaded. Walls facing one way are darker that walls facing the other way. The player can move forwards and backwards, and turns with the keyboard as well. There will be three phases, game, win, and lose. Win will occur once the player saves all civilians. Lose will occur if an enemy destroys the player.
A minimap (useful for debugging).

Shortlist

The ceiling (or sky) is black
The floor is grey
The world is grid based
Lose screen
Win screen
Reset logic
Colored walls
Different shading depending on wall direction
Sprite drawing
Enemy logic
Shooting logic
Player movement
Civilians and civilian logic
Minimap
Collision

First Steps

First up of course, we get our blank window up, looks good.

To start creating our grid, we're going to define the types of tiles we can make. Here you can see that we have empty space that entities can walk through. We also have colored walls to create variation. The player's spawn is important to have, as well as spawns for civilians and enemies. These spawn tiles will be replaced with empty tiles once the entity has spawned.

type TileCode int

const (
    TC_EMPTY TileCode = iota
    TC_WHITE_WALL
    TC_RED_WALL
    TC_GREEN_WALL
    TC_BLUE_WALL
    TC_SPAWN
    TC_CIVIL
    TC_ENEMY
)

I've also created a grid using there tile codes. See if you can understand how the layout looks!

var rawGrid = [][]int{
    {1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {2, 5, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 6, 1},
    {2, 0, 2, 0, 6, 0, 0, 0, 0, 0, 0, 0, 1, 7, 0, 1},
    {2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 4, 1, 1, 4, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 0, 0, 5, 0, 0, 0, 0, 4, 0, 0, 4, 0, 1},
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 0, 0, 0, 6, 0, 0, 0, 0, 4, 1, 1, 4, 0, 1},
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 3, 3, 3, 3, 3, 3, 1, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 1, 6, 7, 0, 0, 0, 0, 0, 1, 1, 0, 1},
    {1, 1, 6, 7, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
}

Now let's make actual tiles. Since spawn tiles get converted to empty tiles, we don't have to worry about them when dealing with tile logic.

type Tile struct {
    color color.RGBA
    solid bool
}

Tiles are extremely simple, and don't even need to hold their own position. There are cases when it is useful to hold the position, but the indices of the tile in the grid should suffice.

Now we have to load our premade grid into real tiles, by converting integers into tiles and entities. We will skip entities for now, but will return to them soon.

func (g *Game) loadGrid(rawGrid [][]int) {
    g.grid = make([][]Tile, len(rawGrid))

    for r := range len(rawGrid) {
        g.grid[r] = make([]Tile, len(rawGrid[r]))

        for c := range len(rawGrid[r]) {
            switch TileCode(rawGrid[r][c]) {
            case TC_EMPTY:
                g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
            case TC_WHITE_WALL:
                g.grid[r][c] = Tile{color.RGBA{255, 255, 255, 255}, true}
            case TC_RED_WALL:
                g.grid[r][c] = Tile{color.RGBA{255, 0, 0, 255}, true}
            case TC_GREEN_WALL:
                g.grid[r][c] = Tile{color.RGBA{0, 255, 0, 255}, true}
            case TC_BLUE_WALL:
                g.grid[r][c] = Tile{color.RGBA{0, 0, 255, 255}, true}

            // Entities
            case TC_SPAWN:
                g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
            case TC_CIVIL:
                g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
            case TC_ENEMY:
                g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
            }
        }
    }
}

Now, we kind of want to be able to see if we're loading correctly. Because of this, I saw we should start working on the minimap now. Firstly, the minimap will be a seperate image that we later blit to the screen.

g.minimap = ebiten.NewImage(75, 75)

Now, all we need to do is loop over each tile and draw it to this new screen.

func (g *Game) drawMinimap(screen *ebiten.Image) {
    // Calculate how big we should make each minimap tile
    tileWidth := float32(g.minimap.Bounds().Dx()) / float32(len(g.grid[0]))
    tileHeight := float32(g.minimap.Bounds().Dy()) / float32(len(g.grid))

    // Draw each tile
    for r := range len(g.grid) {
        for c := range len(g.grid[r]) {
            vector.DrawFilledRect(g.minimap, float32(c)*tileWidth, float32(r)*tileHeight, tileWidth, tileHeight, g.grid[r][c].color, false)
        }
    }

    op := ebiten.DrawImageOptions{}
    op.GeoM.Translate(SCREEN_WIDTH-float64(g.minimap.Bounds().Dx()), SCREEN_HEIGHT-float64(g.minimap.Bounds().Dy()))
    screen.DrawImage(g.minimap, &op)
}

Looks pretty good!

Now we're going to get an easy one out of the way by drawing the floor and ceiling.

func (g *Game) drawBounds(screen *ebiten.Image) {
    vector.DrawFilledRect(screen, 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT/2, color.RGBA{0, 0, 0, 255}, false)
    vector.DrawFilledRect(screen, 0, SCREEN_HEIGHT/2, SCREEN_WIDTH, SCREEN_HEIGHT/2, color.RGBA{128, 128, 128, 255}, false)
}

For those thinking in 2D, this just looks like 2 rectangles, which is just silly. Obviously, it's an infinite grey plane.

Now, if we want to start being able to see the world, we need to place the player in it, so let's do that.

type Player struct {
    x, y float64
    w, h float64
    angle float64

    shotCooldown int
}

And we can spawn a new player using the grid.

case TC_SPAWN:
    g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
    g.player = &Player{
        x: float64(c)+0.5,
        y: float64(r)+0.5,
        w: 0.5,
        h: 0.5,
    }

And, to see that this works, let's draw the player on the minimap as a yellow square.

// Draw the player
vector.DrawFilledRect(
    g.minimap,
    float32(g.player.x-g.player.w/2)*tileWidth,
    float32(g.player.y-g.player.h/2)*tileHeight,
    float32(g.player.w)*tileWidth,
    float32(g.player.h)*tileHeight,
    color.RGBA{255, 255, 0, 255},
    false,
    )

Now we may as well place the enemies. But first, we must define what an enemy is.

type Enemy struct {
    x, y float64
    w, h float64
    img  *ebiten.Image
}

The game will store a list of these enemies, and we just need to populate it in the grid loading code.

case TC_ENEMY:
    g.grid[r][c] = Tile{color.RGBA{0, 0, 0, 255}, false}
    g.enemies = append(g.enemies, &Enemy{
        x: float64(c)+0.5,
        y: float64(r)+0.5,
        w: 0.5,
        h: 0.5,
    })

And simply enough, let's draw a magenta square where the enemies are on the minimap.

Now we just do the same for civillians.

Let's start the most interesting part of this project, the raycasting. Raycasting is a method to convert a 2D world into what seems to be 3D. The camera (which will be the player) casts rays out across their entire field of view. When a ray hits a wall, we can use the distance it traveled to draw a vertical line on screen. We can also use the color of the wall in our drawing. While going through our code, we're going to also show what we're doing on the minimap to make it easy to visualise. First, mathematics, how do we cast rays? Where do we cast rays? So on.

Here is a diagram of our player projecting, and where the screen is in 2D space. One thing we must use is the field of view and width of the screen to get the distance between the player and the screen center. This value will be useful later, but let's define it.

If you know you trigonometry, you'll notice that the tangent of half the field of view is equal to half the screen width over our magic value.
Therefore:

tan(FOV/2) = (SCREEN_WIDTH/2) / SCREEN_DIS

Rearranging gives us:

SCREEN_DIS * tan(FOV/2) = (SCREEN_WIDTH/2) // Multiply both sides by SCREEN_DIS
SCREEN_DIS = (SCREEN_WIDTH/2) / tan(FOV/2) // Divide both sides by tan(FOV/2)

Perfect! That's step one done.

Next, we need to figure out how to cast the rays evenly. You may expect that we'll cast rays at even degree increments, but this would be an incorrect implementation. The reason for this is because when these rays pass through the "screen", they don't evenly line up per pixel. More rays will hit in the center, so when we draw the screen, the center will be stretched out warping our visuals. This way, we need to cast rays in such a way that they land on the screen at even increments.

In this image, we know i, and SD (SCREEN_DIS). i will loop over all pixels on the screen, starting from the far left pixel column, to the far right. We just need to calculate a, and luckily for us, we've use similar trigonometry just before.

tan(a) = i / SCREEN_DIS

Rearranging gives us:


a = atan(i / SCREEN_DIS) // Apply inverse tangent to both sides

So now we know the angle of each ray we need to shoot. Of course, we must also add the player's angle. With each ray, we just get the distance and color of the wall we hit, and draw a line based on this information.

func (g *Game) drawWorld(screen *ebiten.Image) {
    const FOV = 90
    const HALF_FOV = float64(FOV>>1)
    const HALF_SCREEN_WIDTH = float64(SCREEN_WIDTH>>1)
    const HALF_SCREEN_HEIGHT = float64(SCREEN_HEIGHT>>1)

    screenDis := HALF_SCREEN_WIDTH / math.Tan(HALF_FOV)

    for i := -HALF_SCREEN_WIDTH; i < HALF_SCREEN_WIDTH; i++ {
        a := math.Atan(float64(i)/screenDis) + g.player.angle
        dis, clr := g.castRay(a)

        // Didn't hit anything
        if dis == -1 {
            continue
        }

        vector.DrawFilledRect(screen, float32(i+HALF_SCREEN_WIDTH), 10, 1, 100, clr, false)
    }
}

We're just drawing a line if we hit anything for now, as we'll do distance to height calculation later. And with that, we're ready to cast each ray!

The secret to raycasting is that there are actually 2 rays that get cast. One ray check horizontal grid lines, and the other check vertical. Splitting this logic may seem unnecessary, but the seperation of concerns makes ray travel a simply addition. Let's start with the horizontal line check. In this check we have to find the starting position of the ray, and the travel distance for each iteration. The starting position of the ray is the first horizontal grid line we would encounter. First, we're going to find the ratio for moving in the x and the y direction. This tells us that for every step in the y direction, how far we should move in the x.
This ratio makes it very easy to find the starting position of the ray, and the travel distance.

ratio := math.Cos(a) / math.Sin(a)

Now, we need to find the distance in the y coordinate from our player's position, and the next horizontal line.

iter := 0
if a == 0 || a == math.Pi { // Perfectly parallel
    // Don't even try
    iter = VIEW_DIS
} else if a > math.Pi { // Looking upwards
    ratio := math.Cos(a) / math.Sin(a)
    sy := float64(int(g.player.y))
    sx := g.player.x + (sy-g.player.y)*ratio
    dy := -1.0
    dx := dy * ratio
} else { // Looking downwards
    ratio := math.Cos(a) / math.Sin(a)
    sy := float64(int(g.player.y))+1
    sx := g.player.x + (sy-g.player.y)*ratio
    dy := 1.0
    dx := dy * ratio
}

Hopefully this code above makes sense, but if it doesn't let's walk through. iter will be our counter to see how many times we move the ray forward. If the angle of our ray makes is perfeclty parallel with the horizontal lines, it will never reach a collision point. Because of this, we don't want to iterate, so we act as if we've already exhausted our iterations. Now we have our look up and look down cases. We first calculate the ratio between moving vertically and horizontally. If we're looking up, we round the player's y coordinate down, and use the ratio we calculated to get the start x position. Then, we get delta x and y very simply. We will always move up by one tile at a time, so we use -1 for dy, and use ratio to calculate dx. The downward case does the exact same thing, but increases y so that we move downwards. Now we can start iterating.

We want to simply do 3 thing on each loop iteration.

Are we out of bounds?
Have we hit a wall?
Move on.

for iter < VIEW_DIS {
    // Out of bounds?
    if sx < 0 ||
        sy < 0 ||
        sy > float64(len(g.grid)) ||
        sx > float64(len(g.grid[0])) {
        break
    }

    // Check grid collisions
    hit, clr := g.getGridCollision(sx, sy)
    if hit {
        horColor = clr
        horHit = true
        disX := sx-g.player.x
        disY := sy-g.player.y
        horDis = math.Sqrt(disX*disX + disY*disY)
        break
    }

    // Move on
    sx += dx
    sy += dy
    iter++
}

Now, we must do the same check for vertical lines.

// Vertical line check
iter = 0
if a == math.Pi/2 || a == 3*math.Pi/2 { // Perfectly parallel
    // Don't even try
    iter = VIEW_DIS
} else if a > math.Pi/2 && a < 3*math.Pi/2 { // Looking left
    ratio := math.Sin(a) / math.Cos(a)
    sx = float64(int(g.player.x))
    sy = g.player.y + (sx-g.player.x)*ratio
    dx = -1.0
    dy = dx * ratio
} else { // Looking right
    ratio := math.Sin(a) / math.Cos(a)
    sx = float64(int(g.player.x))+1
    sy = g.player.y + (sx-g.player.x)*ratio
    dx = 1.0
    dy = dx * ratio
}

for iter < VIEW_DIS {
    // Out of bounds?
    if sx < 0 ||
        sy < 0 ||
        sy > float64(len(g.grid)) ||
        sx > float64(len(g.grid[0])) {
        break
    }

    // Check grid collisions
    hit, clr := g.getGridCollision(sx, sy)
    if hit {
        verColor = clr
        verHit = true
        disX := sx-g.player.x
        disY := sy-g.player.y
        verDis = math.Sqrt(disX*disX + disY*disY)
        break
    }

    // Move on
    sx += dx
    sy += dy
    iter++
}

Our last step in this function is to make sure we return the correct data. We want to return the nearest collision if we can.

// Get correct data
if !horHit && !verHit {
    return -1, color.RGBA{0, 0, 0, 0}
}

if !horHit || verDis < horDis {
    return verDis, verColor
}

return horDis, horColor

We've got our lines drawing, which means we're probably doing something right! You may have noticed we use a function called g.getGridCollision, which we haven't implemented. Let's say a ray hits a grid intersection, if that is the case, then there are 4 colors the ray could be. Because of this, we must be careful with how to register this collision. There are 2 main cases for a ray collision.

The collision is on an intersection between a horizontal and vertical line
The collision is on either a vertical or horizontal line

func (g *Game) getGridCollision(x, y float64) (bool, color.RGBA) {
    horHit := float64(int(y)) == y
    verHit := float64(int(x)) == x

    var t *Tile

    if horHit && verHit {
        t = g.getSolidTileAtPos(x-1, y-1)
        if t != nil {
            return true, t.color
        }

        t = g.getSolidTileAtPos(x-1, y)
        if t != nil {
            return true, t.color
        }

        t = g.getSolidTileAtPos(x, y-1)
        if t != nil {
            return true, t.color
        }

        t = g.getSolidTileAtPos(x, y)
        if t != nil {
            return true, t.color
        }
    } else if verHit {
        t = g.getSolidTileAtPos(x-1, y)
        if t != nil {
            return true, t.color
        }

        t = g.getSolidTileAtPos(x, y)
        if t != nil {
            return true, t.color
        }
    } else {
        t = g.getSolidTileAtPos(x, y-1)
        if t != nil {
            return true, t.color
        }

        t = g.getSolidTileAtPos(x, y)
        if t != nil {
            return true, t.color
        }
    }

    return false, color.RGBA{}
}

func (g *Game) getSolidTileAtPos(x, y float64) (*Tile) {
    t := g.getTileAtPos(x, y)
    if t == nil {
        return nil
    }

    if !t.solid {
        return nil
    }

    return t
}

func (g *Game) getTileAtPos(x, y float64) (*Tile) {
    if x < 0 ||
        y < 0 ||
        y > float64(len(g.grid)) ||
        x > float64(len(g.grid[0])) {
        return nil
    }

    return &g.grid[int(y)][int(x)]
}

Lot of if statements, but that's okay. What's good is that it seems to work (for now).

As you can see, we get the colour of the wall we're looking at (the player is facing east by default). Now we just have to use the distance to the wall to calculate the visual height.

height := float32(WALL_HEIGHT / dis * screenDis )
vector.DrawFilledRect(screen, float32(i+HALF_SCREEN_WIDTH), float32(HALF_SCREEN_HEIGHT)-height/2, 1, height, clr, false)

Very nice! The hardest part is done! I move the player to a more interesting position so that we could see more of what was happening. However, it would be cooler if we could move the player ourselves, so let's write that now.

func (p *Player) update(g *Game) {
    if ebiten.IsKeyPressed(ebiten.KeyA) {
        p.angle -= 0.04
    }

    if ebiten.IsKeyPressed(ebiten.KeyD) {
        p.angle += 0.04
    }

    if ebiten.IsKeyPressed(ebiten.KeyW) {
        dx := math.Cos(p.angle) * 0.1
        dy := math.Sin(p.angle) * 0.1
        p.x += dx
        p.y += dy
    }

    if ebiten.IsKeyPressed(ebiten.KeyS) {
        dx := math.Cos(p.angle) * 0.1
        dy := math.Sin(p.angle) * 0.1
        p.x -= dx
        p.y -= dy
    }
}

Nice and simple, and from this, I got us this view.

Looks warped? You may think we already fixed the warping beforehand, however, we only fixed one of the warpings. The other warping is due to the distance from the player to the wall. If you were to face a flat wall, you would assume to see a consistent height across the wall, but we don't. The reason for this is because the rays furthest from the center will have to travel further to hit this wall. Therefore, we need to help out these rays so that our visuals think they hit sooner.

a = g.player.angle - a
dis *= math.Cos(a)

This makes rays further from the center of the screen travel distance shorter.

Let's check how much we've done so far.

[x] The ceiling (or sky) is black
[x] The floor is grey
[x] The world is grid based
[ ] Lose screen
[ ] Win screen
[ ] Reset logic
[x] Coloured walls
[ ] Different shading depending on wall direction
[ ] Sprite drawing
[ ] Enemy logic
[ ] Shooting logic
[x] Player movement
[ ] Civillians and civillian logic
[x] Minimap
[ ] Collision

So looks like we've still got quite a bit to do. Don't fret however, most of what we have left is quite easy.

Shading the walls based on direction is quite simple. If we hit a wall using a vertical ray, make it slightly darker. Let's implement this.

Here's a function for darkening colors

func darken(clr color.RGBA, b float64) color.RGBA {
    return color.RGBA{
        byte(float64(clr.R)*b),
        byte(float64(clr.G)*b),
        byte(float64(clr.B)*b),
        clr.A,
    }
}

// The return statement from g.castRay
return verDis, darken(verColor, 0.8)

And this gives us quite a good result with very little effort!

Now for the civilians. Our civilians are going to be angry blobs, because that's just the art I had. Let's loop over all civilians, and draw a red vertical line where they are.

func (g *Game) drawEntities(screen *ebiten.Image) {
    const FOV = math.Pi/2
    const HALF_FOV = float64(FOV/2)
    const HALF_SCREEN_WIDTH = float64(SCREEN_WIDTH>>1)

    screenDis := HALF_SCREEN_WIDTH / math.Tan(HALF_FOV)

    for _, civil := range g.civils {
        dx := civil.x - g.player.x
        dy := civil.y - g.player.y
        dis := math.Sqrt(dx*dx + dy*dy)

        // Relative angle to civil
        a := math.Acos(dx/dis)
        if dy < 0 {
            a = -a
        }
        a -= g.player.angle
        if a > HALF_FOV && a < math.Pi*2-HALF_FOV {
            // Civil isn't in our view
            continue
        }

        // What pixel column the center of the enemy will be in
        i := math.Tan(a) * screenDis + HALF_SCREEN_WIDTH

        vector.StrokeLine(screen, float32(i), 0, float32(i), SCREEN_HEIGHT, 5, color.RGBA{255, 0, 0, 255}, false)
    }
}

All we're doing here is getting the angle to the civillian, checking their in our view, then drawing a line where they should end up visually.

I've walked around a bit and can confirm that the red lines are appearing as they should. Now let's draw an image where they should be. The image needs to be sized the same way we did with the walls. We also need the civilians to stand on the ground, which we can do be calculating where the ground will be.

dis *= math.Cos(a)
height := CIVIL_HEIGHT * screenDis / dis
maxHeight := WALL_HEIGHT * screenDis / dis
op := ebiten.DrawImageOptions{}
op.GeoM.Scale(height/float64(imgH), height/float64(imgH))
op.GeoM.Translate(i-float64(height/2), HALF_SCREEN_HEIGHT+maxHeight/2-height)
screen.DrawImage(img, &op)

As you can see, we use maxHeight to find the floor, then place the civillian on that floor.

Looks good!
Well, at least the one on the right does. The one on the left is in the wall! And so we have to fix the issue of occlusion. We can't fix occlusion if we can't remember how far away the walls are, so let's keep track of it.

// Z buffer definition
zBuffer := [SCREEN_WIDTH]float64{}

// On each ray case
zBuffer[int(i+HALF_SCREEN_WIDTH)] = dis

// Passing info between drawing functions
zBuffer := g.drawWorld(screen)
g.drawEntities(screen, zBuffer)

Now let's do a simple version of occlusion. If the center of the civil is occluded, we'll occlude the entire sprite.

// Occlusion
if zBuffer[int(i)] < dis && zBuffer[int(i)] != -1 {
    continue
}

This works quite well, and will work for our make in a day case. Now we must be able to save these civilians!

func (p *Player) saveCivils(g *Game) {
    for i := 0; i < len(g.civils); i++ {
        civil := g.civils[i]
        dx := civil.x - p.x
        dy := civil.y - p.y
        dis := math.Sqrt(dx*dx + dy*dy)
        if dis < 1 {
            // Save the civil!
            g.civils = slices.Delete(g.civils, i, i+1)
            i--
        }
    }
}

if len(g.civils) == 0 {
    g.phase = WIN
}

As soon as we get close enough to a civillian, we delete them (...save them). Then in the game's update we can simply check if there are any civillians left. And this works!

func (g *Game) reset() {
    g.phase = PLAY
    g.loadGrid(rawGrid)
}

And this takes us straight back into the game again, just like how it started.

Let's do another progress check

[x] The ceiling (or sky) is black
[x] The floor is grey
[x] The world is grid based
[ ] Lose screen
[x] Win screen
[x] Reset logic
[x] Coloured walls
[x] Different shading depending on wall direction
[x] Sprite drawing
[ ] Enemy logic
[ ] Shooting logic
[x] Player movement
[x] Civillians and civillian logic
[x] Minimap
[ ] Collision

4 left!
Let's draw those enemies! Side note, I generalized and placed the sprite drawing code in a separate function. This way we don't have to write all that code again for drawing enemies.

func (g *Game) drawEntities(screen *ebiten.Image, zBuffer [SCREEN_WIDTH]float64) {
    const CIVIL_HEIGHT = 0.4
    const ENEMY_HEIGHT = 0.8

    civilImg := g.vis.GetImage("civil")
    for _, civil := range g.civils {
        g.drawSprite(screen, civilImg, CIVIL_HEIGHT, civil.x, civil.y, zBuffer)
    }

    enemyImg := g.vis.GetImage("enemy")
    for _, enemy := range g.enemies {
        g.drawSprite(screen, enemyImg, ENEMY_HEIGHT, enemy.x, enemy.y, zBuffer)
    }
}

See? Made it extremely easy.

We can use similar code used for saving civillians to check if we've lost

func (p *Player) checkKilled(g *Game) {
    for i := 0; i < len(g.enemies); i++ {
        enemy := g.enemies[i]
        dx := enemy.x - p.x
        dy := enemy.y - p.y
        dis := math.Sqrt(dx*dx + dy*dy)
        if dis < 0.3 {
            // We die!
            g.phase = LOSE
        }
    }
}

Very simple, but we need a defense against this! Now it's time for shooting logic.

For shooting, we can simply use the ray casting we use for drawing! We just ignore the colour we recieve, but use the distance figure. Using the distance we shoot, and the angle we shoot at, we should easily be able to figure out what enemy we've hit.

if p.shotCooldown == 0 {
    if ebiten.IsKeyPressed(ebiten.KeySpace) {
        p.shotCooldown = FPS
        p.shoot(g)
    }
} else {
    p.shotCooldown--
}

func (p *Player) shoot(g *Game) {
    maxDis, _ := g.castRay(p.angle)
    if maxDis == -1 {
        maxDis = 99999.9
    }

    const FOV = math.Pi/2
    const HALF_FOV = float64(FOV/2)

    for i := 0; i < len(g.enemies); i++ {
        enemy := g.enemies[i]
        dx := enemy.x - g.player.x
        dy := enemy.y - g.player.y
        dis := math.Sqrt(dx*dx + dy*dy)

        if dis > maxDis {
            continue
        }

        // Relative angle to enemy
        a := math.Acos(dx/dis)
        if dy < 0 {
            a = -a
        }
        a -= g.player.angle
        a = boundAngle(a)
        if a > HALF_FOV && a < math.Pi*2-HALF_FOV {
            // Enemy isn't in our view
            continue
        }

        // Horizontal offset (0 means we hit the enemies center)
        offset := math.Abs(math.Tan(a) * dis)

        if offset > 0.3 {
            continue
        }

        // We hit the enemy!
        g.enemies = slices.Delete(g.enemies, i, i+1)
        i--
    }
}

This code looks like a mashing of different code we've already written. You may notice offset, which would be used to calculate the pixel column to draw the sprite at. For this, however, it's used to determine a hit. As you can image, you should hit what is in the center of the screen, therefore, anything close the center is hit.

The final problem on the checklist is enemy logic. I want the enemy to chase the player, and so we're going to need to use a searching algorithm. We'll be using dijkstras, as it is relatively simple, and gets us the shortest path. We'll call this algorithm every update frame on each enemy.

func (e *Enemy) update(g *Game) {
    // Try to move to next position
    if e.x != e.nextX {
        if math.Abs(e.nextX - e.x) < 0.01 {
            e.x = e.nextX
        } else if e.nextX > e.x {
            e.x += 0.01
        } else {
            e.x -= 0.01
        }
        return
    }

    if e.y != e.nextY {
        if math.Abs(e.nextY - e.y) < 0.01 {
            e.y = e.nextY
        } else if e.nextY > e.y {
            e.y += 0.01
        } else {
            e.y -= 0.01
        }
        return
    }

    startX := int(e.x)
    startY := int(e.y)
    endX := int(g.player.x)
    endY := int(g.player.y)

    type SpaceInfo struct {
        visited bool
        dis int
        parentX, parentY int
    }

    type Pos struct {
        x, y int
        parentX, parentY int
    }

    spaceInfo := make([][]SpaceInfo, len(g.grid))
    for r := range len(g.grid) {
        spaceInfo[r] = make([]SpaceInfo, len(g.grid[0]))
        for c := range len(g.grid) {
            spaceInfo[r][c].dis = 99999
        }
    }

    spaceInfo[startY][startX].dis = 0
    spaceInfo[startY][startX].parentX = startX
    spaceInfo[startY][startX].parentY = startY

    queue := []Pos{{startX, startY, startX, startY}}

    var pos Pos

    for len(queue) != 0 {
        pos = queue[0]
        queue = queue[1:]

        if pos.x < 0 || pos.y < 0 || pos.y >= len(g.grid) || pos.x >= len(g.grid[0]) {
            continue
        }

        if g.grid[pos.y][pos.x].solid {
            continue
        }

        if pos.x == endX && pos.y == endY {
            break
        }

        newDis := getMovementDistance(startX, startY, pos.x, pos.y)

        if spaceInfo[pos.y][pos.x].visited {
            if spaceInfo[pos.y][pos.x].dis <= newDis {
                continue
            }
        }

        spaceInfo[pos.y][pos.x].visited = true
        spaceInfo[pos.y][pos.x].dis = newDis
        spaceInfo[pos.y][pos.x].parentX = pos.parentX
        spaceInfo[pos.y][pos.x].parentY = pos.parentY

        queue = append(queue, Pos{pos.x-1, pos.y, pos.x, pos.y})
        queue = append(queue, Pos{pos.x+1, pos.y, pos.x, pos.y})
        queue = append(queue, Pos{pos.x, pos.y-1, pos.x, pos.y})
        queue = append(queue, Pos{pos.x, pos.y+1, pos.x, pos.y})
    }

    // Couldn't find path
    if pos.x != endX || pos.y != endY {
        return
    }

    curTile := spaceInfo[pos.parentY][pos.parentX]
    nextTile := spaceInfo[curTile.parentY][curTile.parentX]

    for curTile.parentX != startX || curTile.parentY != startY {
        pos.x = curTile.parentX
        pos.y = curTile.parentY
        curTile = nextTile
        nextTile = spaceInfo[curTile.parentY][curTile.parentX]
    }

    // Now we have the position of the next tile, set the enemy there
    e.nextX = float64(pos.x)+0.25
    e.nextY = float64(pos.y)+0.25
}

Just a bit of code... Either way, it works! Now we have a fairly playable game.

There's one more thing, collision. Collision should be quite easy, just check the position the player is trying to move to, and check for solid tiles.

// Player update
newX := p.x
newY := p.y

if ebiten.IsKeyPressed(ebiten.KeyW) {
    dx := math.Cos(p.angle) * 0.05
    dy := math.Sin(p.angle) * 0.05
    newX += dx
    newY += dy
}

if ebiten.IsKeyPressed(ebiten.KeyS) {
    dx := math.Cos(p.angle) * 0.05
    dy := math.Sin(p.angle) * 0.05
    newX -= dx
    newY -= dy
}

if !g.checkCollide(newX, newY, p.w, p.h) {
    p.x = newX
    p.y = newY
}

func (g *Game) checkCollide(x, y, w, h float64) bool {
    c := int(x)
    r := int(y)
    t := g.getTileAtPos(float64(c), float64(r))
    if t != nil {
        if t.solid {
            return true
        }
    }

    c = int(x+w)
    r = int(y)
    t = g.getTileAtPos(float64(c), float64(r))
    if t != nil {
        if t.solid {
            return true
        }
    }

    c = int(x)
    r = int(y+h)
    t = g.getTileAtPos(float64(c), float64(r))
    if t != nil {
        if t.solid {
            return true
        }
    }

    c = int(x+w)
    r = int(y+h)
    t = g.getTileAtPos(float64(c), float64(r))
    if t != nil {
        if t.solid {
            return true
        }
    }

    return false
}

And that's it, the last check on the checklist.

Done

Wow, I decided to come back with a tougher one here, and it was quite fun. Hopefully from this you understand the rendering we used, and would be able to tinker with the logic yourself. Which leads me to your challenges.

Your Next Steps

You've go the code here for you to look at and modify, so here are some ideas for you.

Walls can be any color
Add different enemy types
Walls with different heights
Textured walls
Jumping
Non-perpendicular walls

I haven't had the spare day to make one of these in a while, so hopefully I get another one soon, any suggestions would help!

Make In A Day: Game Of Life

Chig Beef — Tue, 10 Jun 2025 07:23:20 +0000

I don't think I've ever made Conway's Game of Life, so this will be a first for me. This game will be an interesting one for 2 reasons. The board is meant to be infinite. It's a 0-player game.

Either way, we have to make it in one day. I'll write out a full spec for us all to follow. If our application adheres to our concrete design list, we've made Conway's Game of Life!

Follow in your own programming language, but I'm using Golang.

From the User's Perspective

There's only one phase to this game. There should be a step over button, but also a play and pause. There is an infinite grid of on/off cells. A cell with less than 2 surrounding alive tiles dies. A cell with more than 3 surrounding alive tiles dies. A cell with 2 or 3 surrounding alive tiles stays alive. A cell with 3 neighbors that is dead becomes alive.

This is very short, let's make the list.

Shortlist

The game will have a run mode where it will auto-step at a consistent pace
This mode can be resumed and paused
The game can be manually stepped
The game is made up of an infinite grid of on/off cells
The user should be able to move around the grid
A cell with less than 2 surrounding alive tiles dies
A cell with more than 3 surrounding alive tiles dies
A cell with 2 or 3 surrounding alive tiles stays alive
A cell with 3 neighbors that is dead becomes alive
The cells for a new frame should update based on the last frame

This is a very short list, but there are a few parts that will make it difficult to get correct.

The Code

As per usual, we start off with our empty window.

We're probably going to need some UI elements, so let's put them in. We're going to need a pause and play button, a step button, and a reset button. The pause/play buttons will simply switch an auto-stepping bool.

Now we have the hard part, how do we make an infinite board? My idea is to have a list that only contains the currently "on" tiles. To create the next step, this list must first be fully copied. Then, it would be "bulked", which would go through each tile, and create dummy tiles. These dummy tiles are the tiles around activated tiles, which may come alive. Once all the rules are done, we can then strip out the off tiles, finishing the step. Sounds like a good plan, so let's start by making tiles.

type Tile struct {
    row, col int
    on bool
}

func (t *Tile) draw(g *Game) {
    clr := tileOnColor
    }

    g.vis.DrawRect(
        float64(t.col*TILE_SIZE-g.offsetX),
        float64(t.row*TILE_SIZE-g.offsetY),
        TILE_SIZE,
        TILE_SIZE,
        clr,
    )
}

You may remember my bulking idea, where we generate surrouning tiles.
Let's add this method to the tile.

func (t *Tile) getSurrounds() [8]Tile {
    return [8]Tile{
        {t.row-1, t.col-1, false},
        {t.row-1, t.col, false},
        {t.row-1, t.col+1, false},
        {t.row, t.col-1, false},
        {t.row, t.col+1, false},
        {t.row+1, t.col-1, false},
        {t.row+1, t.col, false},
        {t.row+1, t.col+1, false},
    }
}

We have a finished tile, so now we need a virtual grid that can deal with them. Let's start with just adding a tile to the grid. When adding a tile, we don't want it to override a tile in the same position.

func (g *Grid) add(t Tile) {
    for _, o := range g.tiles {
        if o.row == t.row && o.col == t.col {
            return
        }
    }

    g.tiles = append(g.tiles, t)
}

Pretty simple, now let's do stripping.

func (g *Grid) strip() {
    // Will give a little extra space,
    // but will be used later when bulking
    newTiles := make([]Tile, 0, len(g.tiles))

    for _, o := range g.tiles {
        if o.on {
            newTiles = append(newTiles, o)
        }
    }

    g.tiles = newTiles
}

Bulking should also be very simple, just generate surrounding tiles, and add them one by one.

func (g *Grid) bulk() {
    // Only use current length, don't create new slice
    curLength := len(g.tiles)

    for i := range curLength {

        // Paranoia, shouldn't be possible because of strip
        if g.tiles[i].on {
            surTiles := g.tiles[i].getSurrounds()
            for n := range 8 {
                g.add(surTiles[n])
            }
        }
    }
}

The way we've done it allows us to use the same slice to read and write to. This makes can avoid a reallocation of our slice. We're really pushing through this well and quick, now let's do the copy method.

func (g *Grid) clone() Grid {
    newGrid := Grid{}

    // Allocate the whole slice
    newGrid.tiles = make([]Tile, len(g.tiles))

    // Copy over each tile
    for i, t := range g.tiles {
        newGrid.tiles[i] = t
    }

    return newGrid
}

func (g *Grid) step() {
    lastFrame := g.clone()
    g.bulk()
    g.applyRules(lastFrame)
    g.strip()
}

The step method we defined above is exactly how our plan should be executed. We'll write the applyRules method later. There's no point in writing it if we can't, place and see it in action! So let's work on placing tiles and moving the camera.

func (g *Game) leftClick() {
    // Get actual position
    x := int(g.mousePos[0]) + g.offsetX
    y := int(g.mousePos[1]) + g.offsetY

    // Get row and col
    row := y / TILE_SIZE
    col := x / TILE_SIZE

    // Place the tile
    g.grid.add(Tile{row, col, true})
}

func (g *Game) cameraMove() {
    if ebiten.IsKeyPressed(ebiten.KeyW) {
        g.offsetY--
    }

    if ebiten.IsKeyPressed(ebiten.KeyS) {
        g.offsetY++
    }

    if ebiten.IsKeyPressed(ebiten.KeyA) {
        g.offsetX--
    }

    if ebiten.IsKeyPressed(ebiten.KeyD) {
        g.offsetX++
    }
}

Perfect, let's see how much we've done so far.

[x] The game will have a run mode where it will auto-step at a consistent pace
[x] This mode can be resumed and paused
[x] The game can be manually stepped
[x] The game is made up of an infinite grid of on/off cells
[x] The user should be able to move around the grid
[ ] A cell with less than 2 surrounding alive tiles dies
[ ] A cell with more than 3 surrounding alive tiles dies
[ ] A cell with 2 or 3 surrounding alive tiles stays alive
[ ] A cell with 3 neighbours that is dead becomes alive
[x] The cells for a new frame should update based on the last frame

We've done everything except the actual game logic! Let's implement that real quick. But first, we're going to need a few more methods. For example, it would useful to be able to count the number of alive surrounds a tile has.

func (g *Grid) isOn(row, col int) {
    for i, o := range g.tiles {
        if o.row == row && o.col == col {
            return o.on
        }
    }
    return false
}

func (t *Tile) countSurrounds(lastGrid Grid) int {
    var n int

    if lastGrid.isOn(t.row-1, t.col-1) {
        n++
    }

    if lastGrid.isOn(t.row-1, t.col) {
        n++
    }

    if lastGrid.isOn(t.row-1, t.col+1) {
        n++
    }

    if lastGrid.isOn(t.row, t.col-1) {
        n++
    }

    if lastGrid.isOn(t.row, t.col+1) {
        n++
    }

    if lastGrid.isOn(t.row+1, t.col-1) {
        n++
    }

    if lastGrid.isOn(t.row+1, t.col) {
        n++
    }

    if lastGrid.isOn(t.row+1, t.col+1) {
        n++
    }

    return n
}

Now let's write that logic.

func (t *Tile) step(lastGrid Grid) {
    n := t.countSurrounds(lastGrid)

    // Die (alone)
    if n < 2 {
        t.on = false
        return
    }

    // Die (popular)
    if n > 3 {
        t.on = false
        return
    }

    // Exist
    if n == 2 {
        return
    }

    // Born
    if n == 3 {
        t.on = true
        return
    }
}

How simple is that! And it works perfectly!

Done

Nicely done, that was a simple yet fun one. An infinite grid can be a daunting idea, but we managed to implement a working solution. You may want to look at other possible ways to describe an infinite grid, to see what works best for you. The code for this project as well as the others is here as always. The way we've implemented our code would make it relatively simple to alter the rules.

Your Next Steps

Now that you have Conway's Game of Life, here are some ways you could possibly extend it.

Make hexagonal tiles instead
Alter the game's rules
Allow the change of animation speed
Give cells health that can increase
Make a playable character that can kill cells
Create a live shared Game of Life instance between devices
Colour the cells and have blending mechanics

If you have any more ideas for games I should explain and make, put them in the comments.

Make In A Day: Sudoku

Chig Beef — Wed, 04 Jun 2025 00:38:35 +0000

I've always wanted to implement sudoku. Solving a sudoku is an issue on its on, but this is a step beyond. We want our own program to check whether the user has finished the sudoku. I'm going to be honest, the challenge this time started off very easy, but near the end increased in difficulty.

Now, of course, we have to make this in a single day. I'll give you the strict design, then we can get to work. If you want, you can stop reading after the design and make it yourself.

From the User's Perspective

We're only going to have one phase for this game, just like space invaders. If you haven't played sudoku before, the game is centered on a 9x9 grid. It needs to be obvious that the grid is chopped up into 9 3x3 grids. We're going to have a few set sudokus to solve. Clicking reset will clear the board and pick one of the set sudokus. There should be some sort of indication when we solve a sudoku. I think we should also try to add an auto-solver. Our auto-solver won't be a good algorithm, but it'll be good enough for a make in day!

Shortlist

There is a 9x9 grid made up of 9 3x3 grids
There will be multiple pre-made sudokus to play
There is a reset button
The user can add numbers to the grid, but only if valid
The user can remove numbers from the grid, but only those they placed
The game will show when the sudoku is solved
There will be an auto-solve button

Product of a Day

A 9x9 grid, for me, that's a 2D array, so let's put that in and get it drawing.
We need to draw the grid lines, then the text on top.

// Draw grid lines
g.vis.DrawLine(0, 0, 0, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE, 0, TILE_SIZE, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*2, 0, TILE_SIZE*2, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*3, 0, TILE_SIZE*3, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE*4, 0, TILE_SIZE*4, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*5, 0, TILE_SIZE*5, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*6, 0, TILE_SIZE*6, TILE_SIZE*9, 1, color.White)
g.vis.DrawLine(TILE_SIZE*7, 0, TILE_SIZE*7, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*8, 0, TILE_SIZE*8, TILE_SIZE*9, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(TILE_SIZE*9, 0, TILE_SIZE*9, TILE_SIZE*9, 1, color.White)

g.vis.DrawLine(0, 0, TILE_SIZE*9, 0, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE, TILE_SIZE*9, TILE_SIZE, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*2, TILE_SIZE*9, TILE_SIZE*2, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*3, TILE_SIZE*9, TILE_SIZE*3, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE*4, TILE_SIZE*9, TILE_SIZE*4, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*5, TILE_SIZE*9, TILE_SIZE*5, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*6, TILE_SIZE*9, TILE_SIZE*6, 1, color.White)
g.vis.DrawLine(0, TILE_SIZE*7, TILE_SIZE*9, TILE_SIZE*7, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*8, TILE_SIZE*9, TILE_SIZE*8, DFLT_LINE_WIDTH, color.White)
g.vis.DrawLine(0, TILE_SIZE*9, TILE_SIZE*9, TILE_SIZE*9, 1, color.White)

for r := range GRID_SIZE {
    for c := range GRID_SIZE {
        if g.grid[r][c] == 0 {
            continue
        }

        op := text.DrawOptions{}

        op.PrimaryAlign = text.AlignCenter
        op.SecondaryAlign = text.AlignCenter

        g.vis.DrawText(strconv.Itoa(g.grid[r][c]),TILE_SIZE, float64(c)*TILE_SIZE+TILE_SIZE/2, float64(r)*TILE_SIZE+TILE_SIZE/2, g.vis.GetFont("default"), &op)
    }
}

You can see we have no numbers drawn, because we don't draw zeroes. I did check that the numbers were drawn correctly. But we're not drawing the zeroes because we're going to have them denote an empty tile. And of course, the numbers in the grid can't be over 9. We've also drawn thicker lines to show the sub-grids. Now, I really don't want the player to be able to write any character. Because of this, I'm going to have 9 buttons, and the current selected number. In this case, choosing a button then pressing in the grid places that number.

And now we need to be able to place these numbers in the grid.

func (g *Game) leftClick() {
    x := int(g.mousePos[0] / TILE_SIZE)
    y := int(g.mousePos[1] / TILE_SIZE)

    if x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE {
        return
    }

    g.grid[y][x] = g.curNumber
}

Now that we have the placing of our own numbers, we want a sudoku to solve for ourselves. Let's just grab a few from online, and save them to use. We also want to randomly choose a grid whenever we open the game or reset.

var premadeGrids = [][GRID_SIZE][GRID_SIZE]int{
    {
        {5, 3, 0, 7, 0, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9},
    },
}

func (g *Game) reset() {
    i := rand.Intn(len(premadeGrids))
    g.grid = premadeGrids[i]
}

Looks like it's working to me. We do have an issue, however. Currently, we can override numbers that are pre-placed, which we don't want. We could do a check on the original grid, to check whether it's valid to place. However, what I think is more correct is to create a tile structure. This way, we can have a Boolean that locks it. This also means that later on we can extend the tile. For example, if we want to give the player the ability to type all the possible numbers a tile could be, we could store that in the tile.

type Tile struct {
    num int
    locked bool
}

func (g *Game) reset() {
    i := rand.Intn(len(premadeGrids))
    for r := range GRID_SIZE {
        for c := range GRID_SIZE {
            n := premadeGrids[i][r][c]
            g.grid[r][c] = Tile{num:n, locked:n != 0}
        }
    }
}

Looks pretty good so far, so let's check our list.

[x] There is a 9x9 grid made up of 9 3x3 grids
[x] There will be multiple pre-made sudokus to play
[x] There is a reset button
[x] The user can add numbers to the grid, but only if valid
[x] The user can remove numbers from the grid, but only those they placed
[ ] The game will show when the sudoku is solved
[ ] There will be an auto-solve button

Nice, only 2 problems left! Checking we've solved the sudoku, and auto-solving.

Solving is quite simple, the first check is to check for zeroes. If there are any of them, that means we haven't finished yet. We then check each column, row, and sub-grids for duplicates. If we find none, then we have to inform the user they won.

I've made a method getWinState, and if this returns true, then the sudoku lines will turn green. For placeholder, it will just return true.

Looks like it's working.

// 0 Check
for r := range GRID_SIZE {
    for c := range GRID_SIZE {
        if g.grid[r][c].num == 0 {
            return false
        }
    }
}

The zero check is quite simple, as soon as we find a zero, the problem can't be solved. Now before we start with the other checks, we need a way to make sure there's no duplicates. First, we could use a map.
If the size of the map is not 9, then we haven't solved the puzzle. We could compress this down to an array of Booleans with 9 spaces. We use the number in the tile to index the array to true. If there is a false in this array, the puzzle isn't solved. To compress this even more, we could use a 9-bit integer. Each bit will be a true or false for whether a given number is shown. If the number equals 0b111111111, which is 511, then we've got a valid section. We can't have 9 bits, so we have to take the next biggest integer size, 16 bits. Let's take this approach.

func (g *Game) checkWinState() bool {
    // 0 Check
    for r := range GRID_SIZE {
        for c := range GRID_SIZE {
            if g.grid[r][c].num == 0 {
                return false
            }
        }
    }

    // Row Check
    for r := range GRID_SIZE {
        var check uint16 = 0
        for c := range GRID_SIZE {
            check |= uint16(1 << (g.grid[r][c].num-1))
        }

        if check != 511 {
            return false
        }
    }

    // Col Check
    for c := range GRID_SIZE {
        var check uint16 = 0
        for r := range GRID_SIZE {
            check |= uint16(1 << (g.grid[r][c].num-1))
        }

        if check != 511 {
            return false
        }
    }

    // Sub-Grid Check
    for or := range SUB_GRID_SIZE {
        for oc := range SUB_GRID_SIZE {
            var check uint16 = 0
            for ir := range SUB_GRID_SIZE {
                for ic := range SUB_GRID_SIZE {
                    check |= uint16(1 << (g.grid[or*SUB_GRID_SIZE+ir][oc*SUB_GRID_SIZE+ic].num-1))
                }
            }

            if check != 511 {
                return false
            }
        }
    }

    return true
}

Using this code, the puzzle only goes green when I complete it correctly. Now we only have one more thing on our list, auto solve. We're going to be using a backtracking algorithm, which brute-forces its way through. It attempts to try every possibility until it finds the correct one. It would be smart to clear the board before we start, just in case the user messes stuff up.

func (g *Game) auto() {
    for r := range GRID_SIZE {
        for c := range GRID_SIZE {
            if g.grid[r][c].locked {
                continue
            }
            g.grid[r][c].num = 0
        }
    }

    g.solve(0, 0)
}

g.solve is a recursive method that we will use. It takes in a position on the grid. It will iterate over 1 through 9 on this tile. Each iteration, it will call itself on the next tile. If a valid iteration is achieved, it will return and end the process.

This isn't actually what I want to do, however. This will cause the game to hang, as the solver is checking all possibilities. I think it would be cooler if we could watch it try to find the answer in real time. The rules we've written don't forbid this, so let's see if we can do this. A note is that we don't want to allow the player to press tiles while this is happening.

We want to start the solver at 0, 0, and increment it at each step. Once it has hit 9, it will set it back to 0, and increment the next tile. Then it will go back to the first tile and go through the process again. Once it has hit the bottom right, if it is solved, it should stop. From this, we need to know the position of the tile we're working on. This approach also requires all number to be at least one, so let's do that.

func (g *Game) auto() {
    // Done!
    if g.checkWinState() {
        g.autoSolving = false
        return
    }

    // Invalid move
    if g.autoRow < 0 || g.autoRow >= GRID_SIZE {
        g.autoSolving = false
        return
    }

    if g.grid[g.autoRow][g.autoCol].locked {
        g.autoMove(g.autoRow, g.autoCol+1)
        return
    }

    // This tile is done
    if g.grid[g.autoRow][g.autoCol].num == 9 {
        g.grid[g.autoRow][g.autoCol].num = 1

        // Move to the next tile
        g.autoMove(g.autoRow, g.autoCol+1)
        return
    }

    g.grid[g.autoRow][g.autoCol].num++
    g.autoMove(0, 0)
    return
}

func (g *Game) autoMove(r, c int) {
    // Out of bounds
    if r < 0 || r >= GRID_SIZE {
        g.autoRow = 0
        g.autoCol = 0
        return
    }

    // Wrap
    if c < 0 {
        g.autoRow = r-1
        g.autoCol = GRID_SIZE-1
        return
    }

    if c >= GRID_SIZE {
        g.autoRow = r+1
        g.autoCol = 0
        return
    }

    // Correct (no change needed
    g.autoRow = r
    g.autoCol = c
}

This code goes through each and every possibility, so it is extremely slow. What we want is a way to speed this thing up a bit.

Optimization

First step is the fact that this method is only being called once per frame. We could get away with calling it multiple times per frame.
So let's do that first.

func (g *Game) auto() {
    t1 := time.Now()
    var diff time.Duration = 0

    for diff.Milliseconds() < MS_PER_FRAME {
        g.solve()

        t2 := time.Now()
        diff = t2.Sub(t1)
    }
}

This works very well. In each frame, we have so much dead time, and this takes advantage of that fact. Without the optimization, the first tile would change very rapidly. Now, the entire first row is constantly changing. I added a counter that would print how many times g.solve is called per frame. It is called around 100,000 times every frame, so 6,000,000 a second. This is an incredible time save, but we're still a long way off. To create a reasonable solver, we still need to cut down the solve time by multiple orders of magnitude.

Now, our spec does not specifically say how fast something like this should take. However, I don't think it's reasonable to say we solved it, and then it takes a full day to compute. This challenge is make in a day, not make in a day then run for two. So what is our next point to attack? Well we've tried calling the method more, now let's trying needing to call it less.

We're going to make it so that when incrementing, we don't pick a number that is in a further column. We can do the exact same thing for further rows. The code below helps us determine this.

func (g *Game) countRowMatches(r, c, n int) int {
    count := 0

    for c = c+1; c < GRID_SIZE; c++ {
        if g.grid[r][c].num == n {
            count++
        }
    }

    return count
}

"Human" Solving

This does well, but is still too slow. It takes quite a while to affect the 3rd row. Now, we admit defeat. Well, not exactly. Let's try a completely different approach. What if we go through each tile, and mark off all the numbers that tile can't be. If that tile can only be one number, we set it to that number. We then repeat this process until all tiles are done. If we get stuck, we're going to fall back on the brute force approach given above.

func (g *Game) humanSolve() bool {
    if !g.checkedAllPoss {
        if g.checkAllValidPoss() {
            g.checkedAllPoss = true
            g.autoRow = 0
            g.autoCol = 0
        }
        return true
    }

    // Now find singles and place them
    if g.placeEnsuredTile() {
        g.checkedAllPoss = false
        g.autoRow = 0
        g.autoCol = 0
        return true
    }

    return false
}

// Returns true if a wrap occurs
func (g *Game) nextTile() bool {
    // Move to next tile
    g.autoMove(g.autoRow, g.autoCol+1)

    // Wrapped?
    return g.autoRow == 0 && g.autoCol == 0 
}

func (g *Game) placeEnsuredTile() bool {
    // Number already given
    if g.grid[g.autoRow][g.autoCol].num != 0 {
        return g.nextTile()
    }

    if g.grid[g.autoRow][g.autoCol].locked {
        return g.nextTile()
    }

    numValids := 0
    lastIndex := 0
    for i := range 9 {
        if g.grid[g.autoRow][g.autoCol].canBe[i] {
            numValids++
            lastIndex = i
        }
    }

    if numValids == 1 {
        g.grid[g.autoRow][g.autoCol].num = lastIndex+1
    }


    return g.nextTile()
}

func (g *Game) checkAllValidPoss() bool {
    // Number already given
    if g.grid[g.autoRow][g.autoCol].num != 0 {
        return g.nextTile()
    }

    if g.grid[g.autoRow][g.autoCol].locked {
        return g.nextTile()
    }

    g.grid[g.autoRow][g.autoCol].canBe = [9]bool{true, true, true, true, true, true, true, true, true}

    for r := range GRID_SIZE {
        if r == g.autoRow {
            continue
        }

        if g.grid[r][g.autoCol].num == 0 {
            continue
        }

        g.grid[g.autoRow][g.autoCol].canBe[g.grid[r][g.autoCol].num-1] = false
    }

    for c := range GRID_SIZE {
        if c == g.autoCol {
            continue
        }

        if g.grid[g.autoRow][c].num == 0 {
            continue
        }

        g.grid[g.autoRow][g.autoCol].canBe[g.grid[g.autoRow][c].num-1] = false
    }

    startRow := g.autoRow-g.autoRow%3
    startCol := g.autoCol-g.autoCol%3

    for subRow := range 3 {
        for subCol := range 3 {
            r := startRow+subRow
            c := startCol+subCol

            if c == g.autoCol {
                continue
            }

            if r == g.autoRow {
                continue
            }

            if g.grid[r][c].num == 0 {
                continue
            }

            g.grid[g.autoRow][g.autoCol].canBe[g.grid[r][c].num-1] = false
        }
    }

    return g.nextTile()
}

From my testing, if it can figure out a solution, it's pretty much instant.

But that's a lot of code, so let's walk through. The algorithm first goes through each tile to calculate all the possible numbers that tile could be. Once it has finished that, it goes back to the start, and checks for tiles that can only be one thing. If it finds a tile that can only be one thing, it will set it to that thing. If this whole thing doesn't work, we fall back to brute force.

Done

I'm kind of sick of sudokus at this point. It was fun though, and we did some important optimization work. Honestly, I might work on this in my spare time to speed up the solver. Otherwise, the code is here as always. Maybe I'll use hidden twins to allow the solver to solve the sudoku quicker. Or, I could play around with other methods. Regardless, I'll keep this version on the GitHub, and create a second folder so that we can get a before and after sort of idea.

Your Next Steps

With this sudoku solver looks pretty good now, but you can add more, here are some ideas.

Use a faster sudoku solving algorithm
Automatically generate sudokus
Allow for sudokus of differing sizes

If you have any more ideas for this series, put it in the comments!

One last thing, my minesweeper post reach one of the top 7 of the week! I'm glad people are enjoying these, and I hope people are learning a lot from them (:

Make In A Day: Space Invaders

Chig Beef — Sat, 31 May 2025 07:43:01 +0000

The last game we made in a day was minesweeper, and we were very successful. This time we've got another simple game, space invaders. I would argue that space invaders is simpler than minesweeper. Well, we're going to find out either way.

From the User's Perspective

There are only 2 phases in minesweeper, game, and lose. Ultimately, you keep playing until you lose, showing your score. There is a player at the bottom of the screen, who shoots projectiles upward. The player only moves left and right, same as the aliens. The aliens, however, move down a row when they reach a side. Every time you kill an alien, you get an amount of points. You have 3 lives. The enemies can also shoot back, which can kill the player or damage the towers. The towers degrade as they get hit by any projectile. We're going to have 3 different types of aliens. If all towers are destroyed, or all lives are lost, or the aliens reach the bottom, the player loses. Once all aliens are cleared, the board is reset, but the player keeps their points. The aliens slowly speed up over time.

That looks like quite a bit less than we had for minesweeper!
Now let's make that shortlist.

Shortlist

There are 2 phases, play, lose
Always show the score
The player at the bottom can move left and right
The player shoots projectiles upward
The alien pack moves left, until they hit a wall, in which they switch direction, and move down a layer
There are 3 alien types, giving differing amounts of points for kills
The player has 3 lives
Aliens occasionally shoot projectiles
The player loses a life when hit by a projectile
There are 3 towers
The towers lose health when hit by a projectile
If all towers are destroyed, or all lives are lost, or the aliens reach the bottom, push to lose state
Once all aliens are cleared the board is reset
The aliens slowly speed up over time.

The Code

Now I've set up a blank window, so let's start the actual code. The 2 phases is pretty simple, we can just use an enum (or, the Golang equivalent).

type Phase byte

const (
    PLAY Phase = iota
    LOSE
)

We need to have the score on the screen at all times. We're going to have an integer that shows on screen constantly. Then we update it as needed.

func (g *Game) updateScore() {
    g.play.Text[0].Text = strconv.Itoa(g.score)
    g.lose.Text[0].Text = strconv.Itoa(g.score)
}

So now we need a player that can sit at the bottom of the screen shooting upwards.

type Player struct {
    x, y              float64
    weaponCooldown    int
    weaponCooldownMax int
    img               *ebiten.Image
}

Here's the data for the player, and look at it one screen!.

func (p *Player) update(g *Game) {
    if p.weaponCooldown > 0 {
        p.weaponCooldown--
    } else {
        if ebiten.IsKeyPressed(ebiten.KeySpace) {
            p.shoot(g)
        }
    }

    if ebiten.IsKeyPressed(ebiten.KeyA) {
        p.x--
    }

    if ebiten.IsKeyPressed(ebiten.KeyD) {
        p.x++
    }

    if p.x < 0 {
        p.x = 0
    }

    if p.x > 100-ENTITY_SIZE {
        p.x = 100 - ENTITY_SIZE
    }
}

Last thing for the player is shooting, but of course, we need to have something to shoot. So we're going to make some bullets.

type Bullet struct {
    x, y float64
    dy   float64
}

We can use this struct for enemies later as well, by just switching dy so that the bullet travels down instead.

func (p *Player) shoot(g *Game) {
    p.weaponCooldown = p.weaponCooldownMax
    g.bullets = append(g.bullets, Bullet{
        x:  p.x + ENTITY_SIZE/2 - BULLET_WIDTH/2,
        y:  p.y - BULLET_HEIGHT - 1,
        dy: -1,
    })
}

This method is then called when we have the space bar held down. Look, the new bullet's x and y look a bit strange, all that is to get it lined up right. I've also done a little trick here. The bullet's update method returns a boolean, which turns true when it steps out of bounds.

for i := len(g.bullets) - 1; i >= 0; i-- {
    if g.bullets[i].update(g) {
        g.bullets = slices.Delete(g.bullets, i, i+1)
    }
}

While updating the bullets, if we find a dead bullet, we remove it. You may also notice that I move through the list backwards. This is because removing from a list while interating over it leads to issues. You would go to the next element, however, since you remove the last element, the element you want to go to is in the previous position. Going through backwards fixes this issue.

Let's get the player's lives showing up in the top right. Simply adding the number of lives we have to the player, and drawing that many player images in the top left works.

Now we need to start work on a pack of aliens.

type Alien struct {
    x, y        float64
    img         *ebiten.Image
    shootChance float64
    points      int
    dead        bool
}

type AlienPack struct {
    pack [PACK_WIDTH][PACK_HEIGHT]Alien
    dx   float64
}

r := 0
for c := range PACK_WIDTH {
    ap.pack[c][r] = Alien{
        x:           float64((c + 1) * (ENTITY_SIZE + 1)),
        y:           float64((r + 1) * (ENTITY_SIZE + 1)),
        img:         g.vis.GetImage("alien3"),
        shootChance: 0.0015,
        points:      300,
    }
}

Aliens here are extremely similar to the player. They have the points they give when killed, and also a small chance to shoot back. We keep them in a pack so it's easier to move them around. Then at the end, we can create a pack by adding a bunch of aliens. And we get a cool result!

Right now this pack doesn't move, but that shouldn't be too hard to fix.

func (ap *AlienPack) update(g *Game) {
    flip := false

    // Move all the aliens
    for c := range len(ap.pack) {
        for r := range len(ap.pack[c]) {
            ap.pack[c][r].x += ap.dx
            if ap.pack[c][r].update(g) {
                flip = true
            }
        }
    }

    if flip {
        ap.flip()
    }
}

func (ap *AlienPack) flip() {
    // Opposite direction
    ap.dx *= -1

    // Move down a bit
    for c := range len(ap.pack) {
        for r := range len(ap.pack[c]) {
            ap.pack[c][r].y += ENTITY_SIZE / 2
        }
    }
}

This code here is pretty simple. Move all enemies in the same direction. Once the pack has hit a wall, flip the movement direction, and move everything down. And getting these enemies to shoot is even easier.

func (a *Alien) update(g *Game) bool {
    if a.dead {
        return false
    }

    a.shoot(g)

    // Possibly flip direction
    if a.x <= 1 {
        return true
    }

    if a.x >= 99-ENTITY_SIZE {
        return true
    }

    return false
}

func (a *Alien) shoot(g *Game) {
    if rand.Float64() >= a.shootChance {
        return
    }

    g.bullets = append(g.bullets, Bullet{
        x:  a.x + ENTITY_SIZE/2 - BULLET_WIDTH/2,
        y:  a.y + ENTITY_SIZE + 1,
        dy: 0.5,
    })
}

A key point here is that we know the source of a bullet based on its dy. If you wanted to have a more in-depth game, maybe with multiplayer, you would have a concrete way to decide the source of a bullet. For our problem, however, this is fine. The reason I'm bringing this up, is because an alien at the back would otherwise hit an alien at the front. For hitting the player, this doesn't matter, so we're going to do that first. The alien's update method returns true if it figured out it should initiate a flip. The alien pack uses this to execute the flip.

func (b *Bullet) hitTarget(g *Game) bool {
    // Player collision
    if g.player.hit(b) {
        return true
    }

    // Enemy collision
    for c := range len(g.pack.pack) {
        for r := range len(g.pack.pack[c]) {
            a := &g.pack.pack[c][r]
            if a.hit(b, g) {
                return true
            }
        }
    }

    return false
}

func (a *Alien) hit(b *Bullet, g *Game) bool {
    if !rectCollide(b.x, b.y, BULLET_WIDTH, BULLET_HEIGHT, a.x, a.y, ENTITY_SIZE, ENTITY_SIZE) {
        return false
    }

    if a.dead {
        return false
    }

    if b.dy != -1 {
        return false
    }

    a.dead = true
    g.score += a.points

    return true
}

func (p *Player) hit(b *Bullet) bool {
    if !rectCollide(b.x, b.y, BULLET_WIDTH, BULLET_HEIGHT, p.x, p.y, ENTITY_SIZE, ENTITY_SIZE) {
        return false
    }

    p.lives--
    return true
}

The bullet tries to hit whatever it can. If it finds anything, it only hits that and dies. For the player, it checks collision and loses a life. For the aliens, it has to check a bit more, but if it hits, it just kills it. Dead aliens don't visibly show, can't initiate a flip, and can't shoot.

Let's check how far we've gotten.

[x] There are 2 phases, play, lose
[x] Always show the score
[x] The player at the bottom can move left and right
[x] The player shoots projectiles upward
[x] The alien pack moves left, until they hit a wall, in which they switch direction, and move down a layer
[x] There are 3 alien types, giving differing amounts of points for kills
[x] The player has 3 lives
[x] Aliens occasionaly shoot projectiles
[x] The player loses a life when hit by a projectile
[ ] There are 3 towers
[ ] The towers lose health when hit by a projectile
[ ] If all towers are destroyed, or all lives are lost, or the aliens reach the bottom, push to lose state
[ ] Once all aliens are cleared the board is reset
[ ] The aliens slowly speed up over time.

Looks like we've done quite a bit so far, but we've got a bit to go for a playable game. Let's leave towers until last, and focus on the last alien things.

ap.dx *= 1.01

A single line at the start of an alien pack's flip method, or when we clear the pack. This adds to the diffulty overtime, and eventually makes it too hard to beat the pack.

func (g *Game) checkWinConditions() {
    if g.pack.empty() {
        g.pack.newPack(g)
    }
}

func (ap *AlienPack) empty() bool {
    for r := range PACK_HEIGHT {
        for c := range PACK_WIDTH {
            if !ap.pack[c][r].dead {
                return false
            }
        }
    }
    return true
}

Here, the code for starting a new pack once we've killed the last is very simple. So now we have to start working on those towers.

type Tower struct {
    x, y   float64
    health int
    img    *ebiten.Image
}

func (t *Tower) hit(b *Bullet, g *Game) bool {
    if t.health == 0 {
        return false
    }

    if !rectCollide(b.x, b.y, BULLET_WIDTH, BULLET_HEIGHT, t.x, t.y, ENTITY_SIZE, ENTITY_SIZE) {
        return false
    }

    t.health -= 1
    return true
}

func (t *Tower) draw(g *Game) {
    if t.health > 0 {
        g.vis.DrawImage(t.img, t.x, t.y, ENTITY_SIZE, ENTITY_SIZE, &ebiten.DrawImageOptions{})
    }
}

Very simple looking so far, let's place them whenever we start a game.

for i := range 3 {
    g.towers[i] = Tower{
        x:      float64(25 * (i + 1)),
        y:      50 - 2*(ENTITY_SIZE+1),
        health: 10,
        img:    g.vis.GetImage("tower"),
    }
}

So now we've got one more thing to do to, and this game is finished!
We have to get the lose conditions correct, those being.

All towers destroyed
All lives lost
Aliens have reached the towers

func (g *Game) checkLoseConditions() {
    // Player lives check
    if g.player.lives == 0 {
        g.phase = LOSE
        return
    }

    // Tower lives check
    allTowersDead := true
    for i := range g.towers {
        if g.towers[i].health > 0 {
            allTowersDead = false
            break
        }
    }
    if allTowersDead {
        g.phase = LOSE
        return
    }

    // Enemy breached check
    towerY := g.towers[0].y
    for r := range PACK_HEIGHT {
        for c := range PACK_WIDTH {
            e := &g.pack.pack[c][r]

            if e.dead {
                continue
            }

            if e.y+ENTITY_SIZE >= towerY {
                g.phase = LOSE
                return
            }
        }
    }
}

We don't care whether a alien directly collides with a tower, just as long as they're low enough to do so. So the last thing is that lose page, that we can reset from, and to show our final score.

Then this takes us straight back into a new game. And we're done!

Done

As usual the code will be in a GitHub repo along with the minesweeper game we made last time. Hopefully you followed along, or went your own way making your own. At the very least, you now have your own space invaders that you can fiddle and tinker with.

Your Next Steps

Now that you have space invaders, here are some ways you could possibly extend it.

Add other variations to the enemy types, such as how fast they shoot, and how much damage they do
Maybe the aliens don't move together as a pack
Of course, the classic leaderboard
Add multiplayer (whether on the same machine, or over a connection)
Add upgrades that can be bought using points
Add different types of players, such as one that's faster, or one with a rocket launcher that does splash damage
Allow the player to charge up their shot to make it more powerful

If you have any more ideas for games I should explain and make, put them in the comments.

Make In A Day: Minesweeper

Chig Beef — Fri, 30 May 2025 04:05:32 +0000

One of the most important things I was forced to create in school was minesweeper. This is because it brings up recursion, which every programmer seems to struggle with. Heck, in university, there are many students that still don't grasp it, halfway through the degree. So when people ask how they can learn recursion, my favorite task is minesweeper. And, of course, you get a cool game out of it!

So, here's the challenge, can we make it in one day? Don't start the timer yet, we must design first, list out what we have to do. That's the good part of games like these, they are well-defined, and can be described in a page. I'll describe the game in long form, from the perspective of interactions from the user. I'll then list out notes on these features. In concept, if our application adheres to this list, we've made minesweeper!

Before we begin, we have to write this code in something, obviously. For me, personally, I'll be using Golang as my language, and Ebitengine for graphics. I also have extra code I've written over the years to help me here. This code has nothing to do with minesweeper, but is code that deals with UI logic, and images. The sort of features you'd get from other application engines, but my own crude version.

From the User's Perspective

Minesweeper is a very simple game, either you hit a mine and lose, or you clear the board and win. In this way, there are really only 3 phases in the game, those being win, lose, and play. The game can be reset at any time, when you press the little face at the top. There is a timer, to tell you how long you've taken to clear the mines. Opposite this timer, is another number. This is the number of flags you have left to place. This allows the player to see how many mines are left to win. The board will be a 9x9 grid of tiles. There will be 10 mines in the grid. Never when you play minesweeper, is the first revealed tile a mine. You do not need to worry about the logic of changing the face. Using right click should use a flag on a tile. Flagged tiles shouldn't be revealable. Left clicking a tile should reveal it. If the tile is a mine, it should push the game into the win state. If the tile has no surrounding mines, it should reveal all surrounding tiles. If all tiles that aren't mines are revealed, the game moves to the win state. Revealed tiles should show how many surrounding tiles are mines, or nothing if 0. In win and lose state, the only pressable button should be the reset button. Since lose state happens when a mine is revealed, a revealed mine should show that it has blown. Lose state should also show the remaining mines.

Shortlist

There are 3 phases, play, win, lose
The reset button can be pressed at any time, and resets the timer, grid, and flags
There is a flag counter
There is a 9x9 grid of tiles
There will be 10 mines, which are placed to avoid the player's first click
Right clicking will flag a tile
Left clicking a non-flagged tile reveals it
Revealing a mine switches to lose state
Revealing all non-mine tiles switches to win state
Revealed tiles, if not 0, should show the number of surrounding mines
The exploded mine should be noticable
Lose state should show remaining mines
Revealing a tile with no surrounding mines should reveal all surrounding tiles

First Steps

Now we've got a well defined problem, let's follow along implementing them. For yourself, you may want to stop here and program by yourself, or follow my logic. I would encourage you to take the list above, and create minesweeper yourself, to see how easy solving a well-defined problem really is.

To start off with, I got a blank window with the title "Minesweeper".
Now we can easily tick off the first step, and create 3 phases.

type Phase byte

const (
    PLAY Phase = iota
    WIN
    LOSE
)

The next step is a reset button, so let's add that in.

stagui.Button{
    X:       92.5,
    Y:       0.5,
    W:       7,
    H:       7,
    Name:    "reset",
    BgColor: buttonColor,
    BgImg:   g.vis.GetImage("face"),
}

I've hooked this button up to a reset method, which is empty right now.
We'll fill it in when we have something to reset.

Now we need a flag counter from step 3.

Look at that great UI!
Now we need to start working on tiles.

Deep in the Code

There's a bunch of information we have about tiles, listed here.

They need to know how many surrounding tiles are mines
They need to know if they're a bomb
They have a revealed and hidden state
They have a flagged and unflagged state

To me this sounds pretty simple, 3 bools and an int.
Now, you could have all this in one int, to describe this.
Both options are equally valid, just a matter of opinion.
One may save more memory, the other may reduce chance for invalid state.

type Tile struct {
    surrounds               int
    mine, flagged, revealed bool
}

func (t *Tile) reveal(g *Game) {

}

func (t *Tile) draw(g *Game, x, y float64) {
    // TODO: Replace placeholder
    g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{128, 128, 128, 255})
}

That big blob on the left are our tiles.
Let's skip mines for later, and do flagging.
When we right click a tile, we should flag it.

func (g *Game) rightClick() {
    x := int(g.mousePos[0] / TILE_SIZE)
    y := int(g.mousePos[1] / TILE_SIZE)

    if x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE {
        return
    }

    // Can only flag hidden tiles
    if g.grid[y][x].revealed {
        return
    }

    // Taking back a flag
    if g.grid[y][x].flagged {
        g.grid[y][x].flagged = false
        g.flags++
        g.updateFlagCounter()
        return
    }

    // Trying to place a flag
    if !g.grid[y][x].flagged {
        // No more flags
        if g.flags == 0 {
            return
        }

        // Place a flag
        g.grid[y][x].flagged = true
        g.flags--
        g.updateFlagCounter()
        return
    }
}

Hopefully the code above makes sense, and we get the below result.
We only call the above method when we right click for the first frame.

Looks like it's working well, now for revealing.

func (t *Tile) reveal(g *Game) {
    // Can't double reveal
    if t.revealed {
        return
    }

    // Don't accidentally reveal mines
    if t.flagged {
        return
    }

    t.revealed = true

    if t.mine {
        g.phase = LOSE
        return
    }

    // TODO: Check win state

    // TODO: Reveal surrounding tiles
}

Looks like we're getting somewhere.
You'll notice the TODOs in this method, I put them there because it's extremely important we don't forget.
Imagine if we forget the win state!

func (g *Game) checkWin() {
    // Check for a non-mined tile without a mine
    for r := range GRID_SIZE {
        for c := range GRID_SIZE {
            if !g.grid[r][c].revealed && !g.grid[r][c].mine {
                return
            }
        }
    }

    // We won!
    g.phase = WIN
}

The win logic is quite easy, one every non-mine tile is revealed, we've won!

Now let's do mine placing logic, which is one of the harder parts of this game.
What we want, is a random position that will avoid the first clicking place.
The placement of a mine must also avoid previously placed mines.
Now, we could do the simple solution, which is randomly pick numbers until we find a valid one.
This solution, however, has a case where it stalls infinitely.
In this way, we must create a correct solution.
The first thing I want to do is simplify the problem.
Rather than getting a position, we can get a single random number.
We can then use mod and div to convert this to a position.
Every tile position can be described by a single number, that being.

i = GRID_SIZE*y+x

Now, we've simplified the problem to a single random number.
We just want that random number to not contact the other given random numbers.

// Add this new position to the list of tiles to avoid
avoids = append(avoids, mineY*GRID_SIZE+mineX)

So now we have an easy way to keep track of tiles to avoid.
At the first tile, there are GRID_SIZE*GRID_SIZE-1 valid positions.
The -1 is the first click position.
So now we know we need a random number from 0 to GRID_SIZE*GRID_SIZE-len(avoids).
And now we have the random number, we need to get the correct position.
So we go through the list of position to avoid, and if our position is greater or equal to that position, we increase our position by 1.
The last important point is that we must have a sorted list, otherwise our solution fails.

func (g *Game) placeMines(x, y int) {
    // List of tiles to avoid
    avoids := []int{y*GRID_SIZE + x}

    for range START_MINES {
        inlinePos := rand.Intn(GRID_SIZE*GRID_SIZE - len(avoids))

        // Avoid positions
        for _, avoidPos := range avoids {
            if inlinePos >= avoidPos {
                inlinePos++
            }
        }

        // Convert to a 2D position
        mineX := inlinePos % GRID_SIZE
        mineY := inlinePos / GRID_SIZE

        // Turn it into a mine
        g.grid[mineY][mineX].mine = true

        // Add this new position to the list of tiles to avoid (sorted)
        insertPos := 0
        for insertPos = 0; insertPos < len(avoids); insertPos++ {
            if avoids[insertPos] > inlinePos {
                break
            }
        }
        avoids = slices.Insert(avoids, insertPos, mineY*GRID_SIZE+mineX)
    }
}

This method is everything we just explained as code.
Try to read through it as well as you can if you didn't understand my explanation.
Is this the best way to get a random position?
Probably not, but it works, and is simple enought to reason with.
Let's take a second to see what we've ticked off the list.

[x] There are 3 phases, play, win, lose
[ ] The reset button can be pressed at any time, and resets the timer, grid, and flags
[x] There is a flag counter
[x] There is a 9x9 grid of tiles
[x] There will be 10 mines, which are placed to avoid the player's first click
[x] Right clicking will flag a tile
[x] Left clicking a non-flagged tile reveals it
[x] Revealing a mine switches to lose state
[x] Revealing all non-mine tiles switches to win state
[ ] Revealed tiles, if not 0, should show the number of surrounding mines
[ ] The exploded mine should be noticable
[ ] Lose state should show remaining mines
[ ] Revealing a tile with no surrounding mines should reveal all surrounding tiles

Looks like we've already done quite a bit here.
Let's tick of an easy one, numbering tiles.
First though, we have to count this number up first.
Then we can display this number relatively simply.

func (g *Game) countMines() {
    for r := range GRID_SIZE {
        for c := range GRID_SIZE {
            // Each tile

            for nr := r - 1; nr <= r+1; nr++ {
                for nc := c - 1; nc <= c+1; nc++ {
                    // Each surrounding position

                    // Don't check self
                    if nr == r && nc == c {
                        continue
                    }

                    // Out of bounds check
                    if nr < 0 || nc < 0 || nr >= GRID_SIZE || nc >= GRID_SIZE {
                        continue
                    }

                    if g.grid[nr][nc].mine {
                        g.grid[r][c].surrounds++
                    }
                }
            }
        }
    }
}

Looks good!
Now let's check that exploded mine when we lose.
Let's add an exploded property to tiles.

func (t *Tile) draw(g *Game, x, y float64) {
    if t.flagged {
        g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{128, 128, 128, 255})
        g.vis.DrawImage(g.vis.GetImage("flag"), x, y, TILE_SIZE, TILE_SIZE, &ebiten.DrawImageOptions{})
        return
    }

    if t.exploded {
        g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{255, 0, 0, 255})
        g.vis.DrawImage(g.vis.GetImage("mine"), x, y, TILE_SIZE, TILE_SIZE, &ebiten.DrawImageOptions{})
        return
    }

    if t.revealed {
        g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{64, 64, 64, 255})
        if t.surrounds != 0 {
            g.vis.DrawText(strconv.Itoa(t.surrounds), TILE_SIZE*0.8, x, y, g.vis.GetFont("default"), &text.DrawOptions{})
        }
        return
    }

    if t.mine && g.phase == LOSE {
        g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{64, 64, 64, 255})
        g.vis.DrawImage(g.vis.GetImage("mine"), x, y, TILE_SIZE, TILE_SIZE, &ebiten.DrawImageOptions{})
        return
    }

    g.vis.DrawRect(x, y, TILE_SIZE, TILE_SIZE, color.RGBA{128, 128, 128, 255})
}

Here is my drawing logic.
As you can see, we get to see all mines, and the exploded mine.

Now there's only 2 things left, the timer, and the recursive revealing.
Let's do the recursive revealing.
Now we've really set ourself up quite easily here, except one thing.
Tiles don't know what their neighbours are!
This is a simple fix though, all we need to do is tell each tile its position.
Then the tile can simply ask its neighbours to be revealed.

func (t *Tile) revealNeighbours(g *Game) {
    for nr := t.r - 1; nr <= t.r+1; nr++ {
        for nc := t.c - 1; nc <= t.c+1; nc++ {
            // Each surrounding position

            // Don't check self
            if nr == t.r && nc == t.c {
                continue
            }

            // Out of bounds check
            if nr < 0 || nc < 0 || nr >= GRID_SIZE || nc >= GRID_SIZE {
                continue
            }

            g.grid[nr][nc].reveal(g)
        }
    }
}

That's very simple, isn't it.
Now how is this code called?
At the end of the reveal method, I added this.

if t.surrounds == 0 {
    t.revealNeighbours(g)
}

And this works just fine!
The reveal method has safe-guards to make sure that you don't double-reveal a tile.
Then, it only reveals its neighbours if it has 0 surrounding mines.
There are no gaps in our logic, and it works well.

So now we've only got one task left for us, that being the timer.
All we need is the number to go up every second.
Now, my own simple brain wants to simple have a counter to increments every frame.
Then, dividing by the ticks per second, we get a timer.
However, if you were to slow down the game, you could effectively cheat.
Instead, I need a solution that only updates a counter when there has definitely been an increase in time.
For me, Golang gives me a reasonable solution.
I can save the time that I started this run.
Then, every frame, I can take the difference between the current real time, and that time.
I then write that time to the screen.
Real simple.

g.page.Text[1].Text = strconv.Itoa(int(time.Now().Sub(g.startTime).Seconds()))

I know that's an ugly line but it does exactly as I said.
Take the start time, and get the number of seconds we've take from then to now.
Then display it.

Done

Not too bad, was it! If you want my full code, I've put it all here.

Your Next Steps

Now that you have minesweeper, you probably have a few ideas for extending it. Maybe you want to make a massive board, in which case I would suggest adding an easy, medium, and hard difficulty. A cool idea that I had never thought of before would be to allow tiles to hold multiple mines. Maybe allow players to save their times, and make a leaderboard mechanic. You could make it so that mines can move between hidden tiles. If the player wins, why not let them keep going, and then the score is how many boards they can clear?

My Next Steps

Now, this is definitely a fun challenge, and if it's your first time, very educational. It would be great to have more applications like this to make, so if you can think of any, tell me in the comments.

Go Create Pac-Man in One Day!

Chig Beef — Wed, 13 Nov 2024 03:18:05 +0000

Got a day free this week? Why not see if you can make Pac-Man entirely within 24 hours? It sounds like a simple challenge, because it is, but it's the perfect challenge for testing your skills, new tools, new languages, working with sounds and images, or using Git.

Getting Started

The first thing you should do is decide what language and tools you're going to use. For me, I used C as my language, and raylib as my graphics library. A simple choice for a simple game, however, you may decide to use a full game engine, other languages, and so on. A good choice is a language that you are wanting to learn, and for me, I wanted to get better at using C.

Helpful Information

To create Pac-Man, there are some rules that you should follow.
I'm going to explain what I consider the fundamental algorithms of the game, but you can add more you find from here.

First you have the grid of the game, which can be the original, or any modified version you want. When you reach the end of the grid, however, the player should be able to warp to the other side. Then you have pellets, the player, and 4 ghosts.

The pellets should disappear when the play moves over them, you can choose to keep track of score.

The player just has to moves around the grid, and other than that, doesn't do much.

Each ghost is more interesting.

The Ghosts

Each ghost has a specific target for each movement. The different ghosts determines what this target is. Otherwise, there are still some rules that apply to every ghost. The can't move back on the themselves, and they take the greedy path to their target. So as long as they get closer to the target in the next movement, it doesn't matter if that path is twice as long.

The first ghost is Blinky, and Blinky's target is the player's current position.

Pinky's target is 4 tiles in front of the player, so if the player is moving left, it will be 4 tiles left of the player.

Clyde's target changes depending on how far away from the player Clyde is. If Clyde is more than 8 tiles away from the player, its target is the player's current position. Otherwise it's a scatter position, outside the bounds of the grid. Really the position doesn't matter, but if you want the exact position, it's on the website linked.

Inky's target is based on both Blinky's position and the player's position. Take a line from Blinky's position to the player's position, then double the length of that line so you have a straight line from the new position and Blinky, with the player in the middle. That position is the new position.

Ending

There's not much more to it, but the more you add the better. Mine is a very simple version, without images, sound, or a score. Put down your code in the comments! And have fun designing, implementing, and playing this game!

Reinvent The Wheel (Maybe)

Chig Beef — Sun, 01 Sep 2024 13:13:57 +0000

According to Wikipedia, the wheel was reinvented in 1888 with pneumatic tires. Taking action against a bad design to create something better, something more useful, and the guy who had the idea went on to found the company after his last name, Dunlop.

Well that's a very specific case of reinventing the wheel, but what makes a good case for doing so? Why should you? Generally these days there's a library for anything, why bother?

There are plenty of reasons why you should, but just as many why you shouldn't. Reinventing the wheel is a timely and costly endeavor, but under the right circumstances, pays off immensely.

For The Sake Of Learning

This is my favorite reason to reinvent the wheel, personally. Especially as a student early in my career, where I don't get too much chance to create profound, innovative technology. To some extent, you can't learn much without reinventing the wheel. Sure, I can understand how a raycaster works, but after making my own I truly understand it deeply, giving a few benefits.

I was able to explain what I had created, even teach others how to implement it.
I'm able to extend what I've created, leading to more learning, and experience.
I had something to show for my hard work, which can be impressive for a job application.

Let's go through each of those points a bit more, with my real (probably biased) experiences.

I made my own raycaster in February, if you don't know what that is, it's a fast way to create crude 3D graphics, used when computers weren't fast enough to render a full 3D world at real time. Recently, my friend saw what I had made, and is trying to go on this same path. He'll come to me every once in a while with an issue he has. "Why do I get this fish-eye effect?", "Why are there gaps in the walls?". Not only is it a great feeling being able to answer these questions, but being able to explain why thoroughly. This created a transition from learning, to teaching, and teaching is one of the greatest ways to learn.

That same raycaster isn't a dead project, I keep working on, upgrading it, and learning more. Soon, I'm going to implement a BSP (binary space partitioning) tree into my program. That's another wheel to reinvent, is that a bad thing? Not at all, in fact there's a high chance I'll have the same conversation with my friend but this time with BSP trees.

And lastly, how has reinventing the wheel given me any help with jobs? I study at a university, and it would be a pretty safe guess to say 50% of students don't code at all outside of assignments and other tasks. That's a safe estimate, my honest guess would be closer to 80%. It doesn't take much to get a leg up, and practicing, reinventing the wheel, has given me a personality around my friends, he likes to learn, and more importantly, he can make programs. Because of this, I got referred by another friend for a small job maintaining a website. I don't work on websites, I know barely anything about the front end, or even PHP. Of course I got the job anyway, because people know I can program whatever I focus on. I would never be looked at that way without reinventing a few wheels.

For The Sake Of A Better Product

Ever been on a website, or an app, and there was some bug? Maybe text wasn't displayed properly, or it was too slow, whatever it was, it annoyed you, and you thought, "yeah, I could fix that". Then that thought quickly flies away as you go back to using the stupid app.

But why? Why let it go? You had an issue with it, so it's a user issue. A good business fixes user issues, so wouldn't this be perfect work experience?

I was working checkout at a grocer, scanning items through. My next item was butternut, the button for butternut doesn't work. Annoyed, I pressed the search button, I knew what I was in for. First 5 letters went in fine, but after that it took an entire second to type every letter. It then took another 1 or 2 seconds to load the results. Then I finally was able to weigh the butternut and pack it. Horribly inefficient.

I went home after my shift to work on my own search function. I made a fake app for a grocer, made a million random items, and created a button to run the search code. I made the most basic search function, added caching, and suddenly, in 90% of use cases, it was instant. It also helped to not automatically trigger searching on every key press, but that's just my opinion.

Now, since the program used at the grocer possibly isn't under their control, I don't think I have a shot at replacing that terrible code with my own, however, there is a good chance you could in your situation.

Now you've not only made the product better for yourself, but literally everyone. Once again, wouldn't that look impressive? Possibly to an employer?

For The Sake Of Performance And Streamlining

The example I just gave works here too. Sometimes the way it has been done isn't quite fast enough. Databases are all at a high level, why would you even reinvent them? For performance of course! That's exactly (for the most part) what TigerBeetle did. They reinvented the wheel, how dare they?! That's exactly what they're told not to do, but despite that, it was the correct choice. Don't let this one example speak for them all, sometimes writing it yourself will produce no reasonable gain in performance, so it's always a good idea to do plenty of research before partaking in such an endeavor.

Identify portions of your programs where performance matters, and don't waste your time optimizing the rest.
Michael Abrash

You really have to know exactly what you're optimizing, and more importantly, whether it makes a reasonable difference.

For The Sake Of Ego

I generally don't use a game engine. All I need is a language, and the ability to draw pixels to a window. Sure, that's cool to say, but I gain nothing from that. Here's another example, I can write basic programs in assembly. You see what I mean? Sounds a bit shallow right? In this case, only write your own bespoke version if you need to.

I generally don't use a game engine, they don't allow me to blank. I can write simple programs in assembly, I used it to make blank. If you can't back up your reinvention with valid reasoning, there's a good chance you're wasting your time in folly of ego. Sometimes you can see this reasoning before your endeavor, but it's not always the case. Just know that until you can give a good reason, you're just going to sound pretentious, and therefore shouldn't reinvent the wheel.

For The Sake Of Distrust

I don't trust that the standard library has a good websockets implementation, so I'm going to rewrite it by myself. Bad idea. Don't be allergic to reading code (if it's open source).

If you don't trust someone else's code, try reading it. Maybe their code is exactly what you would've written, if not better, but instead you've wasted your time because "you're the only one who knows how to code right." Now that isn't to say you should outsource all of your code, that's how we get leftpad incidents, but be more open to using someone else's code, you'll get a lot further.

For The Sake Of Performance And Streamlining (Again)

High-performance code should ideally run so fast that any further improvement in the code would be pointless.
Michael Abrash

Diminishing returns hurt, but it's a law of optimization that you can't change. Sometimes, you have to cut your losses, and suck up a little bit of extra execution time, saving you hours of pointless research (unless it's for learning's sake, then go for it!).

Imagine, going back to my checkout example, that the program already ran with a 50ms delay. I go home, spending a few days working on my own, getting the delay down to 25ms. 2x improvement, that's incredible! But going back to work the next day, I find no visible difference. I wasted all my time, when honestly, it was just fast enough already. The company doesn't think it's a big enough change to implement. Future employers don't find the innovation that impressive. I don't reap much reward from it either.

Conclusion

Don't reinvent the wheel. But maybe, every once in a while, the old wheel just isn't good enough. Without reinventing the wheel, we're stuck without imagination, reimagination. That's extremely important for computing, with such a powerful tool at our disposal.

PCs can do just about anything you can imagine.
Michael Abrash

Converting my Wolfeinstein3D Engine to a DOOM Engine

Chig Beef — Sat, 17 Aug 2024 12:16:07 +0000

Back in February, I started working on a raycaster. It was really fun, and I put it on GutHub. Well I've actually been working on this engine behind the scenes. It's hard to show in the little thumbnail, but I added jumping. I know that sounds like a stupid thing to add to a raycaster, but trust me, it's more helpful than you probably realize.

Fixing What I Had

Before I could add more features to my raycaster, I had to fix it. You see, there was a bit of fish-eye, but not the normal kind. In a raycaster there are 2 types of fish-eye, one is related to cosine, and one to tangent.

If you know how raycasting works, you would expect that if this blue circle (the camera) is at this position shooting the red rays, then the white wall should be projected perfectly flat. However, this wouldn't be the case, because the rays in the middle are shorter than the rays on the sides. This creates a warping effect, a fish-eye. This is the cosine fish-eye, but there's a second one. Now imagine each ray is shot out at regular intervals, say 1 ray per degree. This is how the tangent fish-eye is created. If we shoot rays out like this onto a flat wall, and then take a look at the distribution we get, we will see we get a lot more collisions in the center of vision, and a lot fewer around the edges. This creates a subtle, but noticeable effect. To fix it, you just have to make sure the rays are cast out and regular intervals screen-wise, not degree-wise.

Floors and Ceilings

An obvious step between Wolfenstein3D and DOOM is the fact that the floors and ceilings have textures. This has been a pain point for me for the whole process. Figuring out how to get it to work was a difficult, but making sure it was performant was extremely difficult.

There's a really cool optimization you can do in this context, and it's because the ceiling and floor are at the same height (relative to the camera, just opposite). For every pixel on screen, you can cast a ray out to the ceiling and floor and get the angle and distance of that ray. This can all be precalculated, saving a lot of time every frame. After this, we get the x and y position that the ray hits, and use that as an offset into a texture to draw that pixel. There's a few more optimizations I've figured out over my time working on the project. Firstly, you might think that you should give less pixels to things further away, but that looks terrible. The truth is, especially at higher resolutions, things that are close have too many pixels, especially with my low resolution textures. Because of this, I can draw less accurately (e.g. bigger pixels) for the floor and ceiling that is closer to the camera. The other optimization is not drawing floors and ceiling behind walls, because you can't see them anyway. To do this in a really efficient way you can draw the floor in columns, bottom up. Once the floor hits the drawn wall, then you move onto the next column.

Tangent Warping on Sprites

For some reason it took me a while to figure out how to draw sprites correctly. It took me a long time to realize I was having the tangent warping issue again. Not really much to say here, other than draw your sprites in the right position and at the right size.

Sprites Behind Walls

One thing that can be a point of a headache is what to do when a sprite is slightly behind a wall. I had to split the drawing of sprites into columns and use a depth buffer to check which columns I should draw. One thing to keep in mind is that issue can occur when a sprite is in a wall, so you know, don't let that happen.

It adds a good effect when enemies aren't, you know, just appearing into existence.

Diagonal Walls

One of the most prominent differences between Wolfenstein3D and DOOM is that lines can be at any angle. This allows for really complex level design, a step above the restricted Wolfenstein levels.

To add this into the engine, it was a massive rework. You can't use raycasting in the original sense anymore. What I do is take a line from the camera, all the way to the maximum view distance. This line is overlaid with every line in the level. It then checks them for a collision, and uses the closest collision point. Sounds slow? Well that foreshadowing for later, but not yet (if only we could partition space in a binary fashion). I used diagonal lines rarely (mostly because I was nervous of whether they'd work well). This was also a good time to add another DOOM special, wall sliding! My implementation isn't too great, but it's a lot better than being stopped dead in your tracks.

Wall Heights

This added a lot of interesting features to my levels. Looks pretty cool, right?

It's not too hard to add different heights for walls... at first. There's a few gotchas that can, well, get you. The first one is what to do when a wall is too short? You can stretch the image, but that looks weird. What you really should do is crop the image to maintain pixel size. Well what if the wall is too tall? You have to draw another image to make up for that little bit extra, because once again, you can't just stretch the image. Now you've got a lot done, but you've also added jumping, and after peaking over a wall you see nothing. Nothing? That's not right, you should see another wall, but we only draw the first wall a ray hits. To fix this, we just have to draw every wall a ray hits, from back to front. You can also add an optimization to eliminate overdraw.

The Next Steps

I'm currently cooking the next feature in the oven, which is different ceiling heights. Different wall heights was cool, but it looks weird if they're not capped by a ceiling. The next step after this is stairs, which may sound hard, but since I've already implemented jumping, it's going to be fairly easy.

Why Even Make a DOOM Engine

In the path towards a fully 3D engine (e.g., a Quake engine), it may seem like a useless detour to work on the 2.5D DOOM engine. But if you can't solve it in 2D, you can't solve it in 3D. Can you implement a BSP tree in 2D? If the answer is no, why do you think you can implement a 3D BSP tree? Things in 3D get complicated real fast, and honestly, DOOM engines are cool. Once I've got a solid engine working, I'll probably make a game with it, but definitely open source it at some point because the technology really should be accessible.

John Carmack's First Game

Chig Beef — Tue, 06 Aug 2024 09:12:20 +0000

Who's your programming hero? There are many names that could come up, but for some reason one name seems to bleed throughout all programming industries. We all know what games make John Carmack's programming so iconic, DOOM especially comes to mind, but that obviously wasn't his first game.

Why Look Back?

I was working away at some of my own game projects, and sometimes it felt like I wasn't getting anywhere because I hadn't released any of it. That's when it hit me, most game developers don't get popular off their first game, at least, not DOOM popular. So while I was having fun working on a game I would love to play, it inevitably bloats up into oblivion. So everybody has to start somewhere, but what's a good point to start at? Luckily, we have an example in John Carmack.

Shadowforge (1989)

Published by Nite Owl Productions, Shadowforge is an RPG for the Apple II. It had turn-based combat, xp, movement, a tile-based world, sound effects, and different attack types. If you're wondering what gameplay looks like, here's a video.
Also, here's an image of gameplay (in case you don't want to watch the video).

So What's Going On Here?

It's already cool seeing a game like this from one of best programmers ever, but I want you to go through this list and check off what you think you could develop.

Player name
XP/Level system
Currency
Weapons
Inventory
Movement (grid based)
Multiple attack types
A tile based world
Low-res sprites
Enemies
Commands
Sound effects

Obviously there's more to the game than that, but a very large percentage of programmers could pick up any language with any engine/graphics library, and create these features within a month, heck, maybe a week.
It all depends on your skill level and familiarity with your tools, but regardless you could do it, you could make John Carmack's first game.

Foreshadowing

Or so you thought, but as John Carmack is, he is able to one-up even the simplest of concepts. If you ended up watching the gameplay video, you may have noticed that tiles appear and disappear. This is actually simulating visibility. How would John Carmack have done this? Well, the simplest solution I could imagine would be to cast rays from the player in all direction, and only draw the tiles that get hit by these rays.
Sound familiar?

Hovertank One

Let's fast-forward to April, 1991. id was being published by Softdisk, and, would release games at a consistent rate. One of these games was 3D, or, kind of. Computers back then could display 3D graphics, but not at real-time, it was just too much computation. John Carmack implemented a technique to create the illusion of 3D graphics, while only requiring minimal hardware.

So how did this technology work? Well, you would cast rays out from the player at regular intervals of space until they hit a wall. When it hit a wall, you would draw a line, and how tall that line is depends on how far the line travelled. Rays? Casting? That sounds exactly the same as casting rays in Shadowforge to check for visible tiles. This doesn't seem that interesting, until you realize that creating 3D graphics this way was in Catacomb 3-D, Wolfenstein3D, and DOOM.

Whether John Carmack actually used some sort of ray-casting in Shadowforge is unknown, but, it would hold a nice testament. Every game John Carmack made was useful to him. These games all built off one another, becoming better and better each time. They all came from a humble starting point.

The technology that allows you to see the most iconic maps wasn't made in a day, or even just DOOM's development time, it's from pre-existing experience.

Your Own Games

How should this change how you create your games?
Firstly, if you're just starting out, limit the scope of your game, and I don't mean just make it a bit smaller, I mean this game should take no longer than a month to make. Sure, you can get experience programming by making large games, but you'll never get experience releasing them. John Carmack was able to get a lot of experience releasing games while working for publishers like Softdisk.

Secondly, use technology from your previous games. The ray-casting in Shadowforge and Hovertank serve extremely different purposes, but it was an extremely useful thing to have learned. Concepts like these aren't bound by language or tools, you can create a ray-caster with anything. Personally, I released a game called *NULL, and although it's small and very simple, I added the ability to save runs by recording game inputs. You can also replay this runs so you can show off your fastest times. This is something I can bring into future games. I'm intentionally implementing useful concepts to build from in future.

John Carmack didn't just spawn in implementing BSP trees, but neither did you, so spend a bit of time creating a simple game, you'll never know how useful it will be in the future.