How to Design an Algorithm

Recently, in the Program Video Games Metroidvania module we added multiple levels/rooms to the game.

To make sure that we didn’t tax the CPU during physics calculations, we did a very simple optimisation that drastically reduced the number of checks we need to do for collisions.

When we load our level in, the data includes an array of numbers that tells us whether a tile is solid or air.

Let’s visualise this as a 2D array - and to keep it simple we can pretend a level is 5x5 tiles.

So, this is what we have, and if we use the data as-is to draw our colliders, we get something like this:

Now, when we want to test for any collisions we are running 18 collision checks.

We could add something called a “broad-phase-sweep” or “prune” that tries to reduce the number of colliders to test based on a heuristic.

Before adding complexity, let’s consider whether we can take things away.

It’s plain to see that we don’t need all the tiles in the middle - perhaps we can combine them all.

Something like this:

So, we scour Google. We read a bunch of Reddit posts about how to combine tiles in Unity, Godot, GameMaker… But, we can’t find exactly what we are looking for.

What we do find is something called “convex hull” which produces an output like this:

Okay, great! That’s less colliders.

But, hang on a second… Our collision detection is set up using all rectangles.

Now we have to update our collision detection and response to use lines.

Some questions we now need to ask ourselves:

• If an entity hits an edge, how do we know if it’s inside or outside the polygon?
• Do we need to store normal vectors for each line?
• Are there edge cases we need to consider?

This is getting much more complex.

Can we just… Not do that work? Can we go back to simple rectangles?

Let’s find out whether we can write a simple algorithm.

We have the two key ingredients required:

1. The input data
2. The desired outcome

Now, all we need to do is figure out the transformation.

First, let’s consider the data we have.

A 2D array of 1s and 0s.

Since it’s a 2D array where each sub-array is a row, that tells us the sorting order is row-major.

The simplest step we can try is to merge tiles that are next to each other on the same row.

Since the data is already sorted that way, the algorithm is simple.

wide_rectangles: [dynamic]Rect

for row, y in tiles {
	width := 0 // Width of current rectangle
	offset := 0 // X coordinate of start of rectangle
	for cell, x in row {
		// Extend rectangle
		if cell == 1 {
			// Start of rectangle
			if width == 0 {
				offset = x
			}
			width += 1
		}

		// End of rectangle
		if width > 0 && (cell == 0 || x == len(row) - 1) {
			rect := Rect {
				f32(offset) * TILE_SIZE,
				f32(y) * TILE_SIZE,
				f32(width) * TILE_SIZE,
				TILE_SIZE,
			}
			offset += width
			append(&wide_rectangles, rect)
			width = 0
		}
	}
}

Here is the result after the horizontal merge.

That’s already about a 56% saving. But, we can do better.

Our input data has changed. We aren’t inputting the array of 0s and 1s, but an array of rectangles.

What do we know about this data? Well… The sorting has carried over:

If we iterate through the array now, we can merge 1 and 2. But, 4 and 6 have 5 in between… So, we need to keep track of different sizes and positions.

Well, what if we sorted them by y position instead? Let’s try it.

slice.sort_by(wide_rectangles[:], proc(a, b: Rect) -> bool {
	if a.x != b.x do return a.x < b.x
	return a.y < b.y
})

This sorting proc first checks if they are aligned on the x position. If they aren’t, then they can’t be merged vertically anyway, so we sort by x:

Great, now we can iterate through in order and do basically the same thing - except this time with Rect rather than an integer.

merged: [dynamic]Rect
big_rect := wide_rectangles[0]

for rect in wide_rectangles[1:] {
	is_same_x := rect.x == big_rect.x
	is_same_width := rect.width == big_rect.width
	is_abutting := rect.y == big_rect.y + big_rect.height

	if is_same_x && is_same_width && is_abutting {
		big_rect.height += rect.height
	} else {
		append(&merged, big_rect)
		big_rect = rect
	}
}

append(&merged, big_rect)

The code is, once again, straightforward. We have three conditions that must be met in order to merge a rectangle.

1. They must start at the same x position
2. They must have the same width
3. They must be abutting - touching edges on the Y axis, in this case

The only sneaky part is remembering to append the final big_rect.

Here is the result:

We’ve reduced our collision checks from 18 to 4. That’s almost an 80% decrease in computation!

With just a handful of lines of code and some thinking about the data, we can create simple algorithms that exactly fit our use-case.

Don’t get me wrong, I’m not saying you should always create your own algorithms from scratch.

However, if you can’t find the algorithm you need and you start adapting your program to existing ones, you may end up in a situation in which nobody is happy.

You aren’t happy that you changed your design. Your users aren’t happy that things “feel weird” now.

You tailored a problem to an existing solution rather than the other way around.

In contrast, by looking at the data we had available and what we wanted to happen, we were able to figure out a straightforward transformation.

I haven’t tested this yet, but this seems like an embarrassingly parallel problem.

I’m quite sure we could apply both SIMD and Threads to this for a massive speed increase on larger data sets.

If you enjoyed this post, consider joining the mailing list for more like it. Thank you for reading!