Back on Track! Another lesson in the importance of debugging tools... aka:
How to Debug Your Code Part 2.I'll have to chalk the "direct draw" / "pixel map" idea up as one of the "good ideas in theory, but bad in practice" category. The problem is memory. It uses way too much. Using it just for actors isn't much better than for walls, and 1GB of memory for just a handful of maps is ridiculous.
The more I thought about it, though, the more it bugged me that the original "Occupiable Volumes" approach wasn't working. Before I implemented it, I did a lot of math to make sure the theory was solid. I already knew the RAM needs would be minimal. It
should work... and even though I often felt it was a clunky solution, much of that was because I kept running into little problems and applying quick fixes.
I took a step back and combed through all my functions. This took a while, mainly because I had to study what I did to remember how it all worked.
The first problem was one of the "dumb bugs" kind... the sort you facepalm after you realize what you did. To create the topological sort, I check very wall against every other wall, testing for which one is in front. But that wasn't what I was doing. I was, instead, checking every wall against every other wall that came after it in the list. So, for example, I would check if Wall 1 was in front of Wall 2, but not if Wall 2 was in front of Wall 1.
Oddly enough, even with that bug it mostly worked. None of the Temple of Idosra maps failed to render correctly with that bug. I think my luck had mostly to do with the order that walls were built in. I loop through the maps from the lowest levels to the highest levels, so floors were usually on the bottom of the list anyway.
So I fixed the code and got this...
The "SR01" error is one I've mentioned before in this thread,
back in November. I even wrote "Either way, I implemented a new algorithm which works better," not knowing there was a bug that would rear its ugly head nine months later.
The "Escher Error" occurs when the map builder tries to build the "impossible room", as in an M.C. Escher drawing. For instance, if Wall A is in front of Wall B, which is in front of Wall C, which is, in turn, in front of Wall A. In this sort of the scenario the wall rendering order cannot be resolved.
The solution is to look at the very first conflict that rises, since it tends to "poison" the rest of the wall order graph and generate even more "Escher Errors".
Wall rendering order is checked by computing the area of the overlapping polygon created when I overlap the quadrilateral for Wall A with the quadrilateral for Wall B. This turned out to be the problem:
If I have two walls that are next to each other, such as the two floor segments illustrated above, it turns out a very thin overlapping polygon is computed. It's another instance of round-off error. Now it makes sense why I was getting more of these kinds of errors in the Game Boy version--the pixel units were smaller.
I already anticipated this and had a check that ignored any overlaps if the area of the overlap was less than some threshold. It turns out that area is not the best way to check for this case. The area of the overlap above was 14px
2, which is not a trivial overlap in most cases. Because the overlap was so long and thin, it built up a good size area.
I replaced the area check with an angles check. If any of the polygons have a very thin interior angle, I reject the overlap. This resolved the "Escher Error" and everything seems to be running smooth. I even took out a lot of the "quick fixes" I had applied over the months and so far all maps are rendering correctly, and all actors are rendering in the correct order.
I'm going to go ahead and move the "Occupiable Volumes"/"Topological Sort" back into the "good" category of solutions. So far it's solid, and I'm able to resume work in my Game Boy version of my game.
But... I don't think I'm going to just yet. While I was tinkering with the renderer I set up a couple of new features, so I'm going to go ahead and finish implementing them to see how they do. One thing I definitely want to address is casting some kind of shadow under the actors, so it's easier to tell where they are in relation to the map. In the Game Boy game especially, the actors are had to see so that additional visual aid will be very helpful.
Edit. Actor (dynamic) shadows now work!
CPU usage jumps between 5% and 8%, up to ~13% (the max for one core), so it's not quite acceptable. CPU usage is a function of the number of lights and the number of walls. So the number of pixels doesn't matter, since shadow casting against walls is more intensive than rendering the walls.
The feature needs a lot of work to be really useful. It's more of a proof of concept at this stage. If I can get a proof of concept to work, I'm usually successful at raising efficiency by one order of magnitude if I'm patient enough. So I think it is doable. For now, though, I'm going to revert to a simpler shadow casting routine that simply draws a dark blob under the actor.
Render11, the "dithering renderer" that works with the 8-color
Idosra game and 4-color GBJam game doesn't produce good looking shadows. They're blocky and jitter because of the low resolution. I have another renderer--Render17, which is the full-color one some of my earlier screenshots from Summer 2017 were taken from. When I get back to that one, I'll revisit dynamic shadow-casting.
I have one more proof of concept I might want to try with Render17... but I'm not sure if any maps that can use it will boot up anymore.