Sabbatical Log: November 19th

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.

With some refinement to the existing sword and collision systems, I’ve got “push back” working when the sword collides with something.

It can be kinda hard to see in the gif, but the direction of push back depends upon the angle at which the sword hits the obstacle. I also implemented some new walls, the only thing notable about them is that they have two collision layers: one in the “floor”-level the player’s feet are in, and one in the “middle”-level that the sword is in.

It’s a little easier to see with the FPS of recording cranked up, and the collision debug layer turned on.

Next up, I’m going to make some bushes that can be cut – these will be the first destructible obstacles. It feels good to be getting dangerously close to “a game,” even if its almost 20 days in.

An aside, while I’m still working towards bushes. The flexibility of Entity-Component-System again comes through: I can easily model an entity with a hitmap that “extends” through multiple levels by just adding multiple level components.

So, this chunk of code

gets a bush that mostly “works,” despite it being a new thing. How I’d model this in classic object oriented style doesn’t immediately come to me, and it seems like when I did puzzle it out it’d be more complicated.

Here’s how it behaves, right now.

(collision on the player, and the sword)

Bushes now explode into leaves when hit with a sword.

As with the sword, there is now a BushSystem that receives events and handles the life-cycle of a bush. You’ll notice that cutting a bush still pushes the player back and ends their sword swing – which would be rather frustrating. While it’s tempting to just put “if sword” and “if bush” checks into the appropriate places, instead I’m going to add TakesDamage and DealsDamage components and check for those instead. In theory, this will make other damage sources interact better with bushes and make other “enemies” interact better with swords.

At the end of the day, I’ve got the sword and bush interactions working perfectly.

Tomorrow I’m going to spend a lot of time paying down some debt in entity management, and probably some other general performance improvements.

Continue onto November 20th

Sabbatical Log: November 18th

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 seem to have wrenched the hell out of my neck somehow, so I don’t know if I’ll get to any coding at all today. We’ll see.

Here’s where I left off yesterday

The swing logic works, though the animations themselves need some fixing. I also need to do the swing animations when facing up and down.

Can’t say my neck feels great, but I managed to fix up the animations for swinging. I also found a fun bug

That’s a consequence of some “keep the player in bounds”-checks being applied to all collision-having entities. Easy enough to fix, but a fun find.

I’ve now got all 4 swing directions working. I also fixed an interesting bug where newly created swords would get 1-frame of incorrect positioning: this was caused by the enumerable passed to the SwordSystem not containing the new sword, since it was bounded by the number of entities that existed at ASystem.Update() calltime.

I’m not going to be getting any sprite animator job offers, but it’ll do. I’m going to define hitmaps for the sword swipes, and then probably call it a day – maybe make another hot water bottle for my neck.

Tomorrow I intend to start having the sword hit things, walls and bushes to start with.

Continue onto November 19th

Sabbatical Log: November 17th

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.

This morning I got squirreled on more FixedPoint performance improvements. It occurred to me that the common Dot, Magnitude, and Normalize calculations could be optimized.

Precisely:

• Dot(P1, P2) = P1.X * P2.X + P1.Y * P2.Y
  • Both X(1|2) & Y(1|2) are scaled, so they’re really (x(1|2) * SCALE) & (y(1|2) * SCALE)
  • So our desired final product is [(x1 * x2) + (y1 * y2)] * SCALE
  • Which we can get by calculating
    • [(X1 * X2) + (Y1 * Y2)] / SCALE
  • This saves a division per multiply and introduces one new division, for a net savings of one division
• Magnitude(V) = (V.X^2 + V.Y^2)]^(1/2)
  • X and Y are scaled as above
  • Desired product is [(x * x + y * y)^(1/2)] * SCALE
  • We can get this by calculating
    • [(X * X) + (Y * Y)] ^ (1/2)
  • This saves a division per multiply and a multiply for the square root, for a net savings of two divisions and one multiply
• Normalize(V, (X|Y)) = V.(X|Y) / [(V.X^2 + V.Y^2)] ^ (1/2)
  • X and Y are scaled as above
  • Desired product is (x|y) / [(x * x + y * y)^(1/2)] * SCALE
  • We get this with
    • [(X|Y) * SCALE] / [(X * X + Y * Y) ^ (1/2)]
  • Saving a division per multiply, a multiply per division, a multiply per square root, and introduces a new multiply, for a net savings of 2 divisions
  • Additionally, I only calculate the denominator once and use it twice which saves another multiply

I also discovered a place where I was going over all possible entities, rather than just those in use, and fixed it – taking it from a 1,000 iteration loop to a few dozen iterations. So that’s nice.

I’ve decided on my next task will be to implement the sword (and it’s swings). This should get me to a good place for implementing an “enemy” (probably a bush, actually).

Again, lots of time spent extracting, formatting, and positioning assets – but I’ve got left and right sword swings triggering.

I’m repeatedly hammering the “swing” button

Clearly, some stuff still to be done. There’s no handling of a swing ending, or a player interrupting it, or anything like that – but it’s a start.

I’m choosing to model sword swings as spawning a new entity, because nothing has really done that to date – everything’s been spawned as part of either game start, or room creation. This will force me to go back and cleanup some entity management stuff later.

Continue onto November 18th

Sabbatical Log: November 16th

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.

Today will be attempt number 3 at properly responding to collisions. It’s vaguely comforting to be reminded that estimates are just as hard for personal projects as they are for real work…

And now I’ve got the very first collision reaction working, pushing on “walls”.

There was a bit of trickiness in keeping track of the “pushing”-state past the first frame, because the collision handling code will push objects out of collision with each other. There’s still some goofiness around the head animations, but that should be easy enough to fix.

The actual player state is pretty simple

… but the code updating that state is not

In the long term I’d like to get this logic modeled as a state machine – but for now I’m happy with it as is. I’m going to get the other directions working and then do some general clean up, after which I’ll decide on the next task to tackle.

I’ve got all the different pushing directions working now.

I’m going to do some cleanup on the player handling bits of code, I’ve got an entire separate system responsible for “gluing” the player pieces together and that feels like it should be part of the general player state handling system. I’ve also got very large lists of the different assets and animations in code, beginning to wonder if I shouldn’t automate their generation.

So far I’ve collapsed things down to a single player controlling system, and done away with the notion of a “dimension” component (instead I’m always measuring an asset explicitly). Digging through the code, I also removed some custom enumerables and enumerations because I don’t think they’re worth the extra lines of code – even if they are conceptually nice.

Continue onto November 17th

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