Sabbatical Log: November 12th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

A new day, time to burn it all down:

Yesterday I decided to basically start over on the debug overlay. I’ll keep some of the infrastructure (calls, types, line drawing code, and so on), but everything else needs to go.

Bounding boxes! These boxes are based on screen positions and sprites, not hit maps. It’s a good exercise to know that I can translate those simple things into the debug overlay.

Now I’m going to make a smaller test collision object that’s simpler than the tree, and see if I can’t get it working.

I’ve now got a layer that renders the bounding boxes of the hitmaps, as well as the simple object (which is a “tie”) I mentioned earlier. As we can see, things are kind of jacked. In particular the y-axis appears to be messed up on hitmap loading; if you look closely, even the triangles are weird. Given that only the squares are working, I strongly suspect the issue is when there’s a gap between the hitmap and the edges of the sprite that uses it.

Time for more digging!

I found a couple bugs: one in the loading of hitmaps that accounted for the distortion (just dividing by the wrong value to get y coordinates), and one in positioning hitmaps (somewhat more complicated, but my translation from screen locations to cartesian points was incorrect).

So now hit maps are positioned correctly (they sometimes lag the triangles because the hit maps are from before any pushing happens on a frame), and you can even see the triangles are imposing the correct boundaries. Not quite done with the debug overlay yet, still need to actually render the hitmap not just it’s bounding box.

I’ve got hit maps rendering appropriately, I think but…

the tree is still messed up.

Switching to just a convex polygon for the tree “works,” which suggests something with the polygon decomposition.

Which I thought I had eliminated as a source of errors, but here we are. Yet more digging!

While I haven’t quite explained what’s going on entirely, I have found an odd result in the decomposition – some polygons are overlapping, which shouldn’t be possible. I’ve verified that the naive splits work fine, so it’s got to be something in the exhaustive search. I’m working through all the little details to try and find what I got wrong, my gut is telling me it’s either the “can see”-test or the partitioning. I think all developers can relate to the “wait, I already know this works… oh wait, it’s busted”-feeling I’ve got right now.

Back to the bug mines.

I found an issue with the decomposition algorithm treating some exterior lines as if they were valid diagonals, which would have definitely broken things a bit. Having painstakingly re-entered the points that come out of the algorithm for the tree, I’m again feeling pretty confident in it. #famouslastwords

Of course, things are still broken in the actual overlay so I’m not out of the mines yet.

I’ve confirmed that the collision system “sees” those errant polygons where they’re visible, so again I’m thinking it’s a bug with how I’m positioning multiple hitmaps for a component with more than one.

Continue onto November 13th

Sabbatical Log: November 11th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Another weekend, so another day I may not spend all that much time coding. We’ll see.

At the end of yesterday, I had my naive polygon partitioning half working. The approach I’ve decided on is as follows:

  • If a polygon has fewer than 10 vertices, do the expensive algorithm
  • Otherwise, try and split the polygon in half along either a vertical or horizontal line
    • Try up to 8 different lines per axis, evenly spaced
    • Take the the split that produces polygons of the closest “size”, in terms of number of vertices
    • Then try and partition the two new polygons, recursively

This did require a little more incidental algorithmic work, as I needed to determine whether a splitting line is valid (that is, does it produce exactly two new polygons) and then actually split a polygon along a line.

Determining validity was easy enough, just check whether the line intersects exactly two edges. Splitting was a little more complicated, and at the moment I’ve only implemented vertical splitting.

Time to wrap this up, and see if it I can finally load up a tree.

It’s working! I think.

I’ve verified my test cases by hand, but that’s pretty error prone – for example, the tree polygon has 18 vertices and is decomposed into 12 polygons. I don’t have a ton of confidence that I got the tests correct for that one, though the smaller tests I feel better about.

It’s also been a bit since I’ve done anything visual, which isn’t great. So I’m going to spend the rest of the day working on a debug overlay. I want to visualize bounding boxes, hit polygons, and move the “last collision”-point rendering code into something less hacky.

After a bit of work, I ended up here

Soooo, still some bugs to work out. My gut is that it’s actually a rendering issue, perhaps a placement issue. Unfortunately, it could just a well still be an algorithm error. I continue to dig.

After extensive digging, I’m pretty sure the algorithm is correct – so it’s some other error.

I added rendering of bounding boxes (even though those don’t really exist, conceptually), and discovered some bugs in the placement of polygons post decomposition. I’ve also added a number of alternative colors to the hit maps, to show the different polygons more clearly.

You can see that some things fall outside the bounds, and the whole thing is taller than it should be. Time to dig into the hitmap loading code.

While I’ve made a bit of progress, as the day winds down I’m inclined to toss most of this debug code. The divide (the frame buffer doing all the unit conversions) I went with has pushed a lot of logic into weird places, and I suspect there are some more fundamental errors in hitmap layout.

To illustrate, replacing all the complicated geometry of the actual tree base with something simpler…

…reveals quite a lot of distortion.

So tomorrow I think I’ll step back from this particular problem, focus on getting the debug overlay correctly showing bounds and anchors points – and come back to this multi-polygon problem when I’m better equipped to tackle it.

Continue onto November 12th

Sabbatical Log: November 10th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

It’s the weekend again, so this will be a light work day. My main goal is to get the collision code “multi-polygon aware”, so I can flip on collision detection for trees and see what breaks.

While I’ve got most of the code updated, an interesting speed bump has occurred. My polygon partitioning code isn’t very fast, and with a very complex (and concave) polygon like the tree’s hit map it takes minutes to come to solution. I suspect the main problem is that the algorithm looks for an ideal solution, which isn’t really what I need.

I started down the path of optimizing the algorithm (adding caches, removing allocations, avoiding intermediate objects, etc.), but I’ve decided to abandon that for now and try something “dumber” but more elegant. I’m going to try very simple partitions along the axises for polygons with greater-than-some-number-of-vertices, and see if I can just get the problem reduced into something tractable. Ultimately we don’t want ideal decompositions, we want correct and comprehensible ones.

Continue onto November 11th

Sabbatical Log: November 9th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Before I move onto more complicated objects, I need to introduce a notion of “levels”. Right now every sprite is rendered on the same plane, which makes it basically impossible for things to occlude each other.

While I could introduce some explicit groupings of entities, I’m going to keep things simple and just add a level component and split things like the player and walls into multiple entities.

I’ve just finished decomposing the player into three separate parts, one for each “level”. I’m going with floor, mid, and top levels because that “makes sense” to me: attacks will occupy the mid or floor, and jumping will go through the top. It also map nicely to the moving parts of most things: feet, bodies, and heads.

I also had to introduce a PlayerControlSystem, now that the player isn’t represented by a single entity. I’m expecting this pattern to be very common, the smarts of enemies have to go somewhere after all. For the player all it’s doing is making sure the various body parts stay connected, and the player doesn’t leave the bounds of the room (other systems make sure the individual entities don’t, but that’s not quite correct for the whole player).

Collision detection has also become level aware, since two objects on different levels should not collide. It occurred to me that different levels can be checked in parallel, but I haven’t pursued that yet.

Visually not a lot has changed, but you can see the that the player’s body and head (but not their feet) are rendered above the rest of the objects now.

I’ve made some progress on implementing the next object, a tree. I chose a tree because it uses a lot of the new code, without being all that interactive.

To be precise, a tree:

  • Occupies multiple levels
  • Has collision
  • Is composed of multiple entities

To support a tree, I changed up my room object -> entity mapping code to support creating more than one entity. I also added a quick check to the collision system to check bounding boxes before doing the heavy math, a no-brainer optimization that I’d put off doing til I had to. Somewhat unexpectedly what forced my hand was not the time spent calculating collisions (CPU usage for the whole program is less than 2% right now), but rather that I put my test tree far away from every other collision aware entity and the large distances caused overflow errors in my fixed point implementation.

A new level was also needed (which I’m calling Ceiling) for objects that tower over the player, otherwise things like trees would be conceptually as tall as the player.


You might notice that collision detection isn’t actually on yet, and that’s because the collision map for a tree looks like this:

Which, as you can see, isn’t a convex polygon. Before I can flip on collisions for the tree, I need to implement a system for decomposing concave polygons into multiple convex ones. I’ll also need update code so that individual entities can have multiple hitmaps.

It looks like I haven’t mentioned the format of hit maps I’m using before, so let me quickly outline. You can juuuust barely see in the above that I’ve got points at each vertex. Those points are single pixels, and are each a different shade of gray. The hitmap is constructed by connecting each pixel to the next lighter one. I added the pink and green coloring to make it easier to see, the actual data just has the points – the rest of the canvas is transparent

As the day wraps up, I’ve got a working algorithm (and tests) for decomposing an arbitrary polygon into convex polygons. I still need to make the changes to the rest of the engine to deal with sets of polygons, but that’s a task for tomorrow.

In other news, these new tests have brought us up to 100 total. I’m honestly not all that pleased with the coverage of the systems, but the coverage of the actual math is pretty good (and has caught several regressions).

Continue onto November 10th

Sabbatical Log: November 8th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Time to get to work on some flowers! These should be a basic entity with nothing fancy, just a position (existing component) and a frame counter (new component). The lion’s share of the work is going to be making room instances instead of just using room “templates”.

I’ve got animated, collision-less, objects loading into rooms now. Doesn’t look that impressive, but it’s laid the groundwork for much more complicated things.

(It’s the flower)

Rooms now exist (and have state), there’s a new AnimationSystem that handles advancing frames for anything animating, and GameState now manages room instances rather than only tracking the name of the room your in. RoomTemplates also grew a notion of objects with properties, so things can be placed in rooms with Tiled.

There’s really nothing fancy enough to be worth showing in the code. I still need to make animations configurable (right now they’re hard coded), and convert the collision demo and player to use animations instead of being “known” by the renderer.

I’ve changed animations to actually be backed by files on disk. Like everything else, I went through the trouble of getting hot loading working so changes to the definition files are reflected immediately.

The format is just a frequency followed by frames, nothing fancy.

Continue onto November 9th

Sabbatical Log: November 7th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

I found one last issue with the collision system, which is around the very rare exact-vertex collision. For this case I’m just going to draw a line between the vertices and then act like the collision was with the normal to that line.

I’m not all that interested in writing a map editor, since that would take a lot of time away from actually working on the game parts of this project. Looking around, it looks like Tiled is the best free option available – so I’m going to start there and see how well it works for me.

(ed note: at time of writing I was still evaluating Tiled, as of time of publishing I know I’m going to stick with it and have kicked the suggested $14 their way)

After wrestling with map creation and XML parsing – I’ve got a solid parser for Tiled’s format, a test map, and have integrated map loading and rendering into the codebase (including updating all the tests that relied on the old “an image is the bounds”-behavior). I’ve also got the same hot-reloading logic that I have for assets working, so while I’m actually recreating Kakariko I can watch it load up without a restart.

Now I’m going to spend some time finish up the proper background of Kakariko, and then move on to adding some real objects. Probably going to start with simple animating objects (like flowers) and static obstacles (like walls and cliffs).


All the actual background bits have been implemented (and no issues found). I’ll be in a good spot to start implementing some actual things to interact with tomorrow.

Right now, the room system is pretty simple. The game state only cares about the name of the room (since no objects exist yet), and “room template” (which is backed by Tiled’s XML files) is pretty simple (though has some hints of things to come):

TileMap is just a name and an array of AssetNames (the same enum used to render sprites), and Tiles are just a (X, Y, TileIndex)-tuple.

As with Assets, Rooms have a corresponding RoomManager that is used to hide the “MonoGame-y” bits from the actual game logic.

I’m pretty happy with today’s progress, all said and done.

Continue onto November 8th

Sabbatical Log: November 6th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Voting day!

Also “get collision actually working”-day. At the moment all the collision-y bits appear to working fine, I just don’t have a great story for what happens when things do collide. Simply reversing the colliding objects velocity works, but looks janky.

I’m going to look into assigning the collision to a sector of the unit circle and reflecting accordingly.

Status update, bouncing sort of works! But it doesn’t resolve edge cases correctly, namely what happens when two vertices collide and what happens when an object gets “pushed” into another one. You’d think vertex-on-vertex collisions were kind of rare, but I’m intentionally snapping things onto grid (each “pixel” is actually a 16×16 grid, but things are only rendered on pixel boundries) and that makes it pretty common.

It is kind of fun to watch fall apart though.

(it immediately crashes after this)


After some more digging, I discovered an error in my translation from cartesian coordinates to screen coordinates (and vice versa) which was causing some extreme weirdness. After fixing that, things are mostly working – collision detection appears reliable, and the only weirdness is around “what do do you do afterwards”-logic which isn’t meant to be universal anyway (I’m just trying to “bounce” to demonstrate things are working).

In the following picture I’ve added a dot centered on where ever the last collision happened, so it’s easier to see.

I’ve introduced a “push things out of collision”-pass, and I suspect it will stay around. There’s still some wonkiness (you’ll see some below), but given this “small area, large hit boxes, pointy shapes, smooth bounces”-logic is kind of worst case (I expect most uses in the actual game to be at 45 degree angles and not continuous) I think I can put a pin in collision for now.

Next up will be proper maps.

Continue onto November 7th

Sabbatical Log: November 5th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Starting off today I’ve got a lot of code that almost works, finding collisions on single axes quite reliably. Now I need to get it actually detecting collisions properly.

I’ve now got collision working. My general fix was to use the single axis code to find candidate times for each polygon pair, and then iterate through them finding the earliest time where all axes were colliding (if any).

I did have to introduce a notion of “tolerance” in overlap detection because of error accumulation. I’ve settled on 1/10,000,000 for now, we’ll see how that plays out in practice.

Next up, some performance work on this system. I focused on getting it correct, now I’d like to get it allocation free.

Side note: hand verifying collision test cases is rather painful. However, I’ve now got 45 separate test cases to detect regressions, and that’s going to be very helpful going forward.

After a couple hours work, I’ve removed all allocations and System.Collections(.Generic) reference from the collision detection subsystem. I did this with my pretty standard tricks of custom enumerables, and pre-allocated buffers. I also got some performance improvements by not recalculating things that will never change (like normals) and by treated polygons as translations of a basic “polygon pattern.”

Now I need to actually integrate the collision detection into a proper ASystem, and get some stuff on the screen. I think I’ll start by building a “pen” with some different shapes in it, and see whether all of this work is actually useful.

While working on the collision system, I found I needed to remove a number of hacks. Things like: actually tracking velocity, rendering more than one entity, having a notion of a hitmap, and so on. End result, collision system still isn’t done but now there’s a slooooowly sliding triangle on the screen.


Continue onto November 6th

Sabbatical Log: November 4th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Fun Saturday nights lead to somewhat less fun Sunday mornings. Still going to try and make some progress on the collision detection problem, but definitely not firing on all cylinders.

I’ve managed to get most of a collision detection algorithm implemented, at least to the point of determining which polygons will collide and at what times.

The gist is:

  • Only work over convex polygons (I’ll handle this shortcoming later)
  • For each pair of polygons…
    • Treat the first polygon as stationary and increase or decrease the velocity of the second polygon so the same “relative motion” is happening
    • For each line segment in their polygon, determine it’s normal
      • For a line running along the vector (x,y) the normal is (-y, x)
    • Keep any normal that isn’t parallel to a normal I’ve already found
      • Two lines are parallel if their cross product is 0
    • Project each polygon in the pair onto each normal, producing two line segments per normal
      • This is just taking the dot product between the normal and the start and end point of each line segment, and keeping the min and max over the whole polygon.
    • Take those line segments, and determine if the one corresponding to the second polygon (the only one moving) is moving towards the other line segment
      • If not, they will never collide on that axis
      • If so, the distance divided by its velocity (projected onto the same axis) is the time to collision
    • The minimum time of collision on all axises, if any, is the time these two polygons will collide

I’ve now got both the time and the point of collision working. I’ve decided what I’m going to consider the point of collision is point halfway between the closest vertices and/or line segments of the involved polygons.

This boils down to:

  • I’m given two polygons that are “colliding”
  • For both polygons
    • Enumerate one of their vertices and the others line segments
    • Determine the the closest point on the line segment to the vertex (I based my math on this article)
    • If there is no closest point, move on
    • Measure the distance between the found point and the vertex
    • Take all the vertices (and their paired points) with the smallest distance
      • There may be multiple!
  • If you have no vertices/points, then repeat the above but instead of measuring between vertices and line segments, compare only vertices
  • Average each set of points you found (one set is from the first polygon, one from the other) to create new points
    • Most of the time you’ll only have one, but if you’re in the case where two line segments are parallel and going to collide you’ll have more
  • The point of collision is the point halfway between these two average points

I’ve got some tests for these two separate algorithms covering collisions between different sized square, triangles, octagons, and pentagons. I have yet to stick the two system together into a generic “detect and resolve collisions”-pass, but I’m getting close.

Whelp, sticking them together revealed a real logic error. The algorithm I’ve implemented is reasoning about single axises, so I’m getting phantom collisions whenever two shapes overlap on a normal.

I’ve got some ideas on a fix, which I’ll get to exploring tomorrow.

Continue onto November 5th

Sabbatical Log: November 3rd

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

It’s the weekend, so I’m doing mostly social stuff and not coding. However, I have gotten started on a rough implementation of the Separating-Axis-Theorem with some tweaks to handle polygons in motion. I’m thinking I’ll avoid, at least in the final implementation, floating point and instead do a poor man’s fixed point by scaling everything by a large constant multiple.

I went down something of a rabbit hole on the fixed point representation, as I realized that a lot of the code I’d written for collision detection was using integers… that rapidly rounding to 0, causing explosions.

The most interesting bit on the fixed point representation (which is just a struct wrapped around a long, where the “raw value” is multiplied by 2^20 before storage) has been working out how to implement all the operations:

  • Addition (c = a + b) is straight forward
    • c * 2^20 = a * 2^20 + b * 2^20
  • Ditto for subtraction (c = a – b)
    • c * 2^20 = a * 2^20 – b * 2^20
  • Multiplication (c = a * b) is trickier because
    • a * 2^20 * b * 2^20 = (a * b) * (2^20)^2
    • So I divided by 2^20 at the end to correctly calculate c
  • Division (c = a / b) is likewise tricky, as
    • (a * 2^20) / (b * 2^20) = a / b
    • Even worse, this loses precision
    • So I multiply by 2^20 before dividing, correctly calculating c
    • This can still lose precision at the high end, but I’m expecting most numbers to be much less than int.MaxValue. Perhaps I’ll throw on that case in the future.
  • Square root (c = a^(1/2)) is also rather tricky
    • First, I’ve got to actually implement a square root algorithm without using built-in floating point
    • I stole the iterative algorithm from Wikipedia
    • Using it, I calculate ((2^20) * a)^(1/2) = 2^10 * (a^(1/2))
    • I then multiply by 2^10 to get the desired result.

My implementation seems good to about 3 decimal places, and while I’m sure I’ll have to do some performance work (probably using lookup tables for common square roots) I’m pretty happy with it – I’ve got a small test verifying the above operations.

Continue onto November 4th