Bulletin board for Dead Light District, an upcoming Roblox horror game.

Will be updated as the game is developed.

Layout Algorithm

Today is a very special day because it marks the first time that I’ll be posting on here. I decided that a Discord server with zero people probably wasn’t the best option for a development log.

Let me showcase something I’ve been working on since last December!

It’s an algorithm that cuts shapes in half.

You input the vertices in clockwise order, then you define a line and the algorithm spits out the shapes created from the cut. The vertices for those shapes are then defined in clockwise order, so you can repeat the algorithm as many times as you want.

These are a few quick demonstrations. The first video shows very clearly where the shape is being cut (green line) and the second video shows what it looks like to slice a shape into four different pieces. Technically, the cuts aren’t moving, but it looks that way because I’m clearing the workspace and rendering a new cut each frame.

It is pretty intense on the graphics.

Anyways, the reason why I wanted to work on this algorithm is that my game will most likely use it.

Imagine a new layout every round, each layout built procedurally from the ground up.

This is what I dreamed of as a game developer.

Alright, in terms of implementation-

Implementation Notes

You might think this was simple to code, but ever so often, computers can run into rounding errors when making long computations. This is because a program can only store so many decimal places before it runs out of memory.

For example, the calculation for Point A might end up being 0.0000001 studs away from Point B, but the program wouldn’t be able to tell that the two vertices are practically on top of each other.

`if not IsBetween(P, B, O) then return O, N end`

This was the problem child.

What it means is that if P sits even slightly outside of B or O due to rounding errors, then the vertex that intersects with the cut line won’t be seen by the program.

That’s bad because if one vertex goes missing, part of the shape goes missing with it.

I tried to fix the problem by rounding any slightly-off values to the nearest 0.01 studs. It did decrease the frequency of the errors, but occasionally one or two vertices would slip and the entire cut wold fail. Nah. I wasn’t taking occasionally for an answer.

Here were the two ways that I went thinking about it:

`If the distance A to B + the distance B to C = the distance of A to C, then B is in between A and C.`

`If the angle from A to B to C is 180 degrees, then B is in between A and C.`

Originally, I used the distance implementation, so when I came back to the algorithm in January, I started working with angles and the rounding errors became less frequent.

I re-coded the rest of the algorithm to accommodate for angle measurements. Voilà! The rounding errors disappeared completely. I was filled with pure joy and happiness when I saw this happen.

The only errors now will only occur every once in a hundred thousand attempts or so.

Showcase Video

Here’s what I have created so far!

The structures are randomly generated. If you look closely, you might be able to spot some weird edges that came from rounding errors at the time that I filmed it.

Long story short, now that I’m done, I can use this algorithm to generate building layouts with lots of variation. The investment was definitely worth the payoff and it holds so much potential.

I’ll consider open-sourcing if people show interest the algorithm and I manage to perfect it even further.

For now, I can’t wait to see what I can do with it!