Sabbatical Log: November 15th

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’ve wrapped up my performance work for now, making the following changes:

  • Looking up stateful components of entities is now O(1) instead of O(number of stateful components)
  • Special cased some FixedPoint multiply and divide operations to avoid extra work
  • Added a coarse first pass to collision detection that excludes whole sets of polygons that could not possibly be colliding with anything before going into polygon-by-polygon checks
    • I already had a quick bounds check for individual polygons, but adding a coarser first pass reduces the number of polygons considered by 50-90%

Debug build performance is quite snappy again, so I can get back to what I’d been wanting to do yesterday – responding to collisions.

Real life intervened today and I didn’t get nearly as much coding time in as I’d hoped, but I did manage to get animation switching for the player working. To illustrate, I did standing and walking animations for the cardinal directions.

They’re kind of janky, but they’ll do for now. Making any sort of animation is time consuming, if only because there’s a lot of little fiddling to make things line up. Again, hot reloading of assets and animations really increasing the iteration speed but these 24 animations (up/down/left/right x standing/walking x head/body/feet) still took ~2 hours to get to “good enough”.

Continue onto November 16th

Sabbatical Log: November 14th

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.

Having lots of trees has revealed an issue

Collision detection is taking up tooooons of time…

But only in DEBUG builds.

Given that I only have 3 #if DEBUG’s in the code, I’m expecting to find something interesting as the root cause. Time to break out a proper profiler.

Turns out, it’s a combination of not optimizing away a property access and an on demand creation of a 0-value FixedPoint.

RELEASE builds are smart enough to remove it, DEBUG builds pay the price. So I’m burning ~70% of CPU on comparing a number to zero, which is a professional first for me.

Removing the property access, and pre-calculating zero values gets me into the 30-50 FPS range in DEBUG builds – better but not good enough. Putting an IsZero field on FixedPoint (calculated at construction time) gets me the extra 10 frames back.

From one point of view this is somewhat wasted, RELEASE builds are the “true” builds and they never exhibited this problem. However, I feel the DEBUG experience is very important as I’m using this as a learning tool – so RELEASE builds are rare. It’s the same reason I’ve added hot reloading everywhere, not important for the final product but incredibly important for the development experience.

I’m going to spend a little more time doing some performance cleanup, and then move onto the proper task for today: actions upon collision.

I’ve refactored collision detection so now an event is triggered, rather than there being a hard coded bounce effect. I’ve only got two events at the moment: bounce, and do nothing.

I originally attempted to trigger systems instead of events (so there’d be a TriangleSystem, a SquareSystem, etc.) but that quickly got messy as everywhere else assumes ASystems run once an update. Furthermore, I think I’m going to impose considerable limits on what can be done in a collision trigger – forbidding things like changing hitmaps while collisions are still resolving. Having Systems with and without those limitations feels wrong, so a new concept is necessary.

I’m going to spend some more time with a profiler on collisions, since I’m refactoring anyway. I think it’s probably time to clean up some pointless enumeration that’s happen as well, since I’m looking at performance.

It seems likely I’ll have to push the first graphic parts of “respond to a collision” to tomorrow – we’ll see.

Continue onto November 15th

Sabbatical Log: November 13th

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 today, tree hitmap polygons appear correct.

They also work for collision purposes. The (hopefully) final bug was an error in converting between Cartesian coordinates (used for collision) and screen coordinates (the “source of truth”, used for everything else, including position tracking) – I wasn’t tracking the original height of the decomposed polygon correctly, which resulted in a random-ish vertical translation.

There’s a lot to clean up from this work, allocations are everywhere as a sacrifice to debugging expedience. So I’m going to spend a lot of time today cleaning up.

A couple hours later, I’m back to no use of System.Collections(.Generic) except for IComparer (since some methods on Array use it). As before, my general approach has been to pre-allocate arrays of a sufficient size and just reuse them.

I suspect I’m going to want to make a pass formalizing that pattern (I do already have a Buffer type floating around, but not everything uses it) and maybe switch to an explicit object pool. My goal isn’t to minimize allocated memory, it’s to avoid dynamic allocations in order to keep garbage collections rare and fast.

I’m going to switch back to improving the debug overlay, I still need to add some statistics and make it possible to switch overlays without recompiling.

I’ve got overlay toggling working, as you can see below:

I settled on a shortcut of “hold a number, and tap D” to switch them on and off.

I had to take a slight detour into text rendering to get the labels in to the top left working. MonoGame has support for some images-as-fonts stuff, but I’ve been avoiding most of the built in stuff (this is a learning exercise, after all) so I rolled my own. It’s just a single texture with characters at an even spacing, so offsetting and rendering are pretty simple. For the moment all that logic is specific to the debug overlays, but I expect I’ll reuse it when I get to dialog boxes.

And I’ve now wrapped up a debug overlay that illustrates the time spent in various systems.

You can see a graph in the bottom left (4 + D, is the shortcut to bring it up), the black vertical space represents 1/60th of a second and the horizontal is the last 60 updates (which should be about a second). Each system gets a different color to indicate how much of a frame it takes, and a system is only shown if it will be visible in the graph. Currently I don’t capture time spent rendering – I’m still not quite sure how I want to do that since it’s not formally part of the game state like the other systems are.

This whole endeavor has endeared me to the Entity-Component-System pattern even more. By structuring all the logic in Systems, it was trivial to get profiling in for this last overlay. The generic-ness of Entities made all the bounding overlays simple as well.

Final debug overlay for now, an FPS and render time indicator. This turned out to be pretty tricky, if only because high accuracy timers are non-trivial in .NET and the debug overlay is part of the render loop which complicates the bookkeeping.

It doesn’t look like much

It updates once a second, and as you can see the current state of things is quite fast! Not all that surprising, given it’s a half-done reproduction of a 27 year old game.

Up next, I’m going to go add a bunch more trees to the Kakariko map and see if anything breaks. If everything’s good, I’ll then move onto responding to collisions – right now the bounce code is part of collision detection, it needs to get moved into a separate system and other reactions need to be added.

Continue onto November 14th

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