Pico 8 Conveyor Belt Project

I’ve been working on a game for Pico-8. It’s a sort of demake of Factorio, combined with, apparently, Zelda elements. (These things seems to evolve themselves with my own interest/motivation/limitations.)

In the spring of 2021, I started the project just wanting to learn more about Pico-8, and it evolved into a reasonably-sized project. I’ve recently revisited it, and am making enhancements to publish it on itch.io.

One of the issues I ran into when I first worked on it was the number of operations needed to check for collisions with movable objects and the belts. There are probably much better ways to accomplish belt movement, but the method I’ve been using is to move the movable object in the direction the belt was facing. This was a passable solution at the time.

However, as the game progressed, the problem with this approach became clear: it is a O(n*m) calculation. This means each object in the first list has to be checked against each object in the opposite list to determine whether to move the movable objects. That is, for every entry in the conveyer belts list (m), every entry in the movable objects list (n) is checked to see if their respective rectangles overlap. For 1000 belts and 1000 movable objects, this would be 1,000,000 checks every cycle. Not only is this not going to be a fun time for anybody due to all the frame delays, it has no upper bound. The greater the number of objects created, the worse the performance.

Originally I limited the impact of this by restricting the view to a single 128x128 field, which meant a max of 16x16 (256) conveyor belts, minus a few unplaceable sections, and limited the number of movable objects that could exist to some arbitrary number, like 50. This capped calculations to around 10k per frame; this is still an obnoxious amount, but doesn’t cause any noticeable degradation.

Original rectangle comparison script (lua):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function tile_occupied(x, y, collection, actor)
    offset = 7

    -- x and y here are absolute position; already adjusted for room position
    -- checks every object in the target collection
    for i, v in pairs(collection) do
        if not (
            -- v left past target's right, or
            -- v right past target's left
            v.x          > x + offset or
            v.x + offset < x          or
            -- v top past target's bottom, or
            -- v bottom past target's top
            v.y          > y + offset or
            v.y + offset < y
        ) and v != actor then
            printh('returning actor ' .. v.name .. ' from tile_occupied')
            return v
        end
    end
    return nil
end

The basic structure of the logic is: check whether x and y are both outside the bounds of the target collection entry, then invert the result. If the inverted result is true, the rectangles overlap, and a collision exists. Then a check is performed to make sure the actor isn’t colliding with itself (if they happen to be in the same collection), and if not, the found object is returned.

Coordinate Key Lookups

Since I wanted to expand the game world, I decided to see if I could reduce the amount of calculations needed. I looked into using table lookups, since I wanted to preserve those extra cycles for things that are important for enjoyment of the game, like drawing sprites. My theory was that I could reduce O(#movables * #belts) to O(#movables * 4). That is: find the belts that matter, then check only those.

At first, the key lookup approach seemed like it would work. I was already using a grid system, so rather than having to track 128x128 values (16,384, one for every coordinate on the screen), I only needed to track a maximum of 16x16 (256) because the grid size is 8 pixels square (the smallest pico-8 sprite size). Since I was already preventing double-placement, only one belt sprite could exist in a given cell. I converted the tracking tables from the default format of {[1]=sprite,[2]=sprite,...} to {['x,y']=sprite,['x,y']=sprite,...} where the key is now the topleft position of the cell location on the game grid. Then, to determine whether a cell is occupied, I just had to pass the target topleft cell grid coordinates and check the value for nil (which would mean the cell is unoccupied).

The topleft point of each cell is stored in the cell tracking map:

This worked great for stationary objects! The double-placement check was able to determine that a space was already occupied, and prevent placing a second object. This worked for the building structures too. I was off to a good start.

Calculating Rectangle Overlap

I hit a snag with the movable objects. The problem was that they moved. They didn’t snap to the grid, so only 1 of 64 possible pixels for a given 8x8 cell would trigger a match. The cheap solution is to devolve the animation, and force each sprite to be snapped to the vertices of the grid, but I felt this would make the game much less interesting.

Key lookup collision testing tool demo

Sample code

Note how only the top-left of each stationary sprite matches when the calculation doesn’t account for ‘snapping’ the player object to the grid vertices.

Now I had two additional problems to solve. The first problem was matching the movable object with a grid-snapped belt. The second problem was figuring out which of the four possible positions a sprite could be touching should be used to determine how to move the object.

The first problem was solved easily enough. Dividing the movable object’s coordinates by the grid cell size, then taking the floor, then multiplying by the cell size again would result in a ‘snapped’ coordinate point.

This wasn’t good enough, because the collision would always be skewed to the topleft, and behavior of certain structures, like belts, wouldn’t be conveyed properly to the movable objects. I determined that I needed more math.

More math

Determining overlap seemed like something that would have a mathematical formula, so rather than reinventing geometry, I did a little googling and found something that would work.

The basic function is as follows (I used python instead of pico-8 for my experiments for several reasons: python dictionaries are easier to print, loop, and read than lua tables; python prints and debugging are more flexible; string building and handling is more robust; and method signatures are checked so it’s more difficult to get undefined variables; all-in-all, python’s just easier for throwing together a quick idea and does a better job staying out of my way than lua does; I want to think about the logic, not the syntax):

1
2
3
4
5
6
7
8

def calculate_rect_overlap(actor: pygame.Rect, target: pygame.Rect):
    """
    - `actor`: the player; a `pygame.Rect` that has `x`, `y`, `width`, and `height` properties
    - `target`: the stationary target; a `pygame.Rect` that has `x`, `y`, `width`, and `height` properties
    """
    x_overlap = max(0, min(target.x + target.width , actor.x + actor.width ) - max(actor.x, target.x))
    y_overlap = max(0, min(target.y + target.height, actor.y + actor.height) - max(actor.y, target.y))
    return x_overlap, y_overlap

Operation sequence and explanation of x_overlap:

1. Get the x position of whichever rect’s right side is nearest to 0 (the rightmost of the actor or the rightmost of the target)
2. Get the x position of whichever rect’s left side is furthest from 0 (the leftmost of the actor or the leftmost of the target)
3. Subtract the second value from the first
4. Compare the result with 0, choosing the greater of the two

The result is the amount, on the x-axis, that the actor (player) overlaps the target.

The equivalent calculation is performed for the vertical parameters to get the y-overlap.

The product of these values is important to determine by how much the player rectangle overlaps the target rectangle, since the player can be on 4 rectangles simultaneously, and we want to assign properties to the player based on which target they are the most on top of. Otherwise the belt effect is really awkward, with some belts having priority when only a sliver of the player sprite is overlapping them.

The result is that for each collision check, no more than 4 (and possibly fewer) target sprites need to be checked.

Overlap calculation testing tool demo

Sample code

Final demo code (calculate_rect_overlap is slightly different because I didn’t take the time to make the target into a full pygame.Rect object, but it is functionally the same):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def check_overlap(actor):
    x = actor.x
    y = actor.y

    # get snapped coordinates
    offset_x = actor.width
    offset_y = actor.height
    check_points = {
            'quad1': {'x': snap(x), 'y': snap(y)},
            'quad2': {'x': snap(x) + offset_x, 'y': snap(y)},
            'quad3': {'x': snap(x) + offset_x, 'y': snap(y) + offset_y},
            'quad4': {'x': snap(x), 'y': snap(y) + offset_y},
    }

    # do rectangle math to find most overlapped
    most_overlapped = 'none'
    most_overlapped_area = 0
    for key, value in check_points.items():
        # `rect_topleft_points` is a test dictionary defined elsewhere in the script file with values like `{"32,32": "quad1,blue"}`
        overlapped_with = rect_topleft_points.get(f'{value.get("x")},{value.get("y")}')
        overlap = calculate_rect_overlap(actor, value) if overlapped_with else (0, 0)
        overlap_area = overlap[0] * overlap[1]
        if overlap_area > most_overlapped_area:
            most_overlapped_area = overlap_area
            most_overlapped = overlapped_with
    return most_overlapped

def calculate_rect_overlap(actor, target):
    # `rect_side` is the grid cell size, defined elsewhere in the script file
    x_overlap = max(0, min(target.get('x') + rect_side, actor.x + actor.width ) - max(actor.x, target.get('x')))
    y_overlap = max(0, min(target.get('y') + rect_side, actor.y + actor.height) - max(actor.y, target.get('y')))
    return x_overlap, y_overlap

Converting to lua and incorporating into the game

I’m going to look at storing this collision logic in a separate lua file to make porting it to other Pico-8 projects in the future simpler.

Lua equivalent code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

function in_quad(actor, collection, x, y)
    -- check for coordinates occupied by objects in target collection relative to current sprite
    if x == nil then
        x = actor.x
    end
    if y == nil then
        y = actor.y
    end
    offset = 8
    quads = {
        ['quad1'] = collection[snap_expand(x)          .. ',' .. snap_expand(y)         ],
        ['quad2'] = collection[snap_expand(x) + offset .. ',' .. snap_expand(y)         ],
        ['quad3'] = collection[snap_expand(x) + offset .. ',' .. snap_expand(y) + offset],
        ['quad4'] = collection[snap_expand(x)          .. ',' .. snap_expand(y) + offset],
    }

    most_overlapped = nil
    most_overlapped_area = 0
    for i, target in pairs(quads) do
        if target != nil then
            overlap_x, overlap_y = calculate_rect_overlap(actor, target)
            overlap_area = overlap_x * overlap_y
            if overlap_area > most_overlapped_area then
                most_overlapped_area = overlap_area
                most_overlapped = target
            end
        end
    end
    return most_overlapped
end

function calculate_rect_overlap(actor, target)
    cell_size = 8
    x_overlap = max(0, min(target.x + cell_size, actor.x + cell_size) - max(actor.x, target.x))
    y_overlap = max(0, min(target.y + cell_size, actor.y + cell_size) - max(actor.y, target.y))
    return x_overlap, y_overlap
end