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.


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.

Behold!

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).


Hooray!

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.

Woooooooo

Continue onto November 6th