Sabbatical Log: November 22nd and 23rd

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.

The 22nd was the Thanksgiving in the US – I didn’t get much done.

Back at it on the 23rd, post-holiday. Probably still a light day, but I’m going to work on smoothing out room transitions in the cardinal directions. With any luck, I’ll get to the stair-style transitions.

I’ve got the cardinal directions working now.

If you watch the transitions, you’ll notice the interactions of collision detection and exit systems. An exit placing the player inside a tree (for example) will result in them getting pushed back into an exit zone. I like that the interaction here “makes sense” and is an emergent property of the two systems interacting, not an explicitly handled edge case.

That said, I don’t love the ExitSystem code. It explicitly calculates the desired end position of the player and camera, and takes over camera positioning during an exit transition. I’m going to spend some time making it less ugly before moving onto other sorts of exits.

I’ve now cleaned up the ExitSystem code, and written a few tests. I mostly added comments, collapsed primitive fields into structured types, and moved the camera-y bits over to the CameraSystem. The CameraSystem now has a notion of being “explicitly pointed” somewhere, rather than deferring to another system it still keeps track of the camera but allows other systems to make camera requests. I also moved most of the logic that fills out the FrameState during a transition into the ExitSystem, since it was mostly duplicated anyway.

The ExitSystem remains kind of big and complex, but it’s much more manageable now. I may need another refactoring pass after adding other sorts of transitions, but I’m fine with it for now.

Here’s an outline of the current code:

Next up are the other transitions, for now I’m going to confine myself to four: going through doors, going up stairs, going down stairs, and falling down holes. It makes the most sense to me to model these as colliding with particular objects, as opposed to the edge triggered-ness of the cardinal direction transitions.

Continue onto November 24th

Sabbatical Log: November 21st

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 done a little more cleanup work this morning. I’ve removed entities from the BushSystem (so it no longer needs special compacting), and I’ve moved the compact calls into a new CleanupSystem. I like having cleanup in a system of its own, since then I get the same profiling as all other systems.

I’ve also decided that, at least for now, I’m going to trigger entity compacting every 100 GameState advances, when the ratio of dead entities to live one is >= 2, or when the EntityManager reaches the end of it’s backing buffer. Triggering any of these conditions resets the iteration count, so logically this means we’ll compact at least once every 100 iterations but may compact more frequently.

Reliably compacting entity storage also let me change the NewEntity() method into a simple bump allocator, so that’s nice.

I’ve decided today that I’m going to work on room transitions.

A random aside, I threw a memory profiler on a DEBUG build out of curiosity. It’s nice to see that there’s basically no churn once things settled down after app start.

At the moment, the only actual allocations are creating new Components. At some point I’ll move those to an object pool, and then we should get to actually zero allocations during normal operation.

I’ve now got the very basics of edge-triggered screen transitions working. There’s still a lot to do, for one the camera isn’t really aware of transitions which results in it lurching forward at the start.

The approach I went with was:

1. Mark everything in the current room as needing to be culled
   1. This uses a FlagComponent, so it’s cheap
2. Load up the new room
3. Go over all the old entities and update their positions so they are in the same logical position, but now relative to the new room’s coordinates
4. Disable loads of systems that shouldn’t be running during the transition
5. Apply a velocity to the player in the appropriate direction, to keep them moving into the new room
6. Let the game state advance until the camera lies entirely within the new room
7. Go remove all the entities marked in step 1
8. Re-enable all the systems disabled in step 4

This approach is pretty generic in terms of keeping things where they “belong” during a transition, and involves a minimum of new code. The only tricky part was getting the math down for transitioning between the rooms – I’m not convinced it’s completely correct.

I’ve been fighting a headache for an hour or so, so I’m going to call it for today. Tomorrow I’ll focus on fixing up the camera’s behavior, making sure transitions work between rooms of different sizes, and getting some test cases in.

Here’s the current behavior.

If you pay attention to the trees you can see the old entities getting culled at the end of the transition. The camera jump is apparent as well – it’s a consequence of the camera always wanting the player to be in the center of the screen, unless at a room’s edge, and the logical removal of aforementioned room’s edge.

Continue onto November 22nd and 23rd

Sabbatical Log: November 20th

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 my goal is to get entity management cleaned up, in particular I want to: get traversal proportional to number of entities with some property, compact entity lists, and speed up retrieving components for an entity.

Time to get to work.

I’ve got traversal down, and have removed lots of casts and other nastiness.

I’ve basically added component-type-specific containers to the EntityManager class, so lookups are cheap, and switched enumerations over to intrusive linked lists.

Previously I stored all stateful components in a 2-dimensional array and kept each component type in a specific column – this required some multiplications (and not power-of-two ones) and down casting, plus the ergonomics of multi-dimensional arrays in C# aren’t great. Now every component type gets its own array and accessor methods so there’s no down casting, access is cheaper, and the code is nicer.

Most systems want to iterate over all the entities with a specific component. Prior to this change I was looping over a column in that 2-dimensional array, stopping when I got to the next allocated Entity. This meant a lot of time was spent iterating over empty values, since most components are relatively sparse. Switching to a linked list makes iteration proportional to the number of active components.

I have one small twist on intrusive collections, which is rather that storing pointers I store indexes. Since Entity ids are already used to quickly access components for specific Entities, this has a nice symmetry and (at least in theory) means the GC has less to do. The interface for my linked lists is below:

As with most everything else, the size of the linked list is fixed at app start.

I also took some time to apply the same quick-check optimization I have in the collision detection system to the update position system (which is responsible for making sure entities don’t overlap at the end of a “frame”).

Next up, I need to implement compaction in the entity manager. Time to get back to it.

I’ve got compaction working by all appearances, and I have bunch of tests for it too. The basic idea is that, upon request, the entity manager will scan it’s internal table and renumber entities such that they’re all contiguous. It then takes that remapping, and informs each other thing that cares about entities – letting them update themselves.

Most of the work was punching the appropriate interface into the right places, the actually algorithms are not complicated.

Any instance that holds onto an Entity for longer than one update needs to implement IHoldsEntity (and be passed to Compact). I’m pretty sure I could remove all “extra-EntityManager” entity storage from, and may do so in the future. Right now there are only two classes that do so, the BushSystem (for tracking what is “pending being cut”) and the actual GameState class which has convenience accessors for the parts of a player and the camera entity.

Right now, since I’m debugging, I force a compaction between each system being invoked during an update. In the future I’ll want compaction to happen at more particular points, like screen transitions, and in response to extreme fragmentation.

All said I’m pretty happy with today’s results, I’ll probably do some more cleanup tomorrow and then move onto room transitions.

Continue onto November 21st

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