Merrak's Isometric Adventures -- Artificial Intelligence!

merrak

  • *
  • Posts: 2240
...That is clever. So the render loop and the 'light-loop' can run at different intervals. The renderer probably loops faster than the need of shadow recalculation...

I thought so at first, too. But then I booted up my fresh new renderer and was greeted with this: (Face added for dramatic effect)


Whoops! I have a feeling I may be putting the cart before the horse here. I asked myself what is the problem I'm trying to solve, then quickly realized there isn't one. Or maybe there is... but probably not because the renderer, as-is, is a lot faster than I give it credit for.

I disabled the shadow map code. It's still in the source in case I realize I need to use it again... in which case I'll work on optimizing it. But even if I never use it it's not a total waste. Most of the time I spent working on it was really spent cleaning up the source code, and that needed to be done anyway.

I also streamlined the shadow casting code, which has always been a separate process than the renderer. If at some point I want to look into using hardware wall rendering (shaders), I made an important step in getting that to work. It's also now easier to create new lights and remove lights outside of the boot-up process. Rather, I should say, it's now possible.

For the time being, I made a simpler repair to the wall renderer and I'm happy to say it is working now. I just need to turn my attention back to the actors renderer and I'll be back on my feet.

« Last Edit: August 27, 2018, 09:30:16 pm by merrak »

merrak

  • *
  • Posts: 2240
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 14px2, 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.

« Last Edit: August 31, 2018, 10:58:36 pm by merrak »

merrak

  • *
  • Posts: 2240
On Second Thought... I decided to go for it. Since the shadow casting functions were back in my immediate memory, I dug into the code and worked on optimizing it. I managed to speed it up by about 20x, which is okay, but I would've preferred two orders of magnitude, not one.

For rendering done entirely in software, it's not bad at all. I now have dynamic shadows and dynamic lights on a 720p display without pushing anything over to hardware rendering.


Here's the report card, highlighting the room in the figure above. There are two routines to note: "Sector.castActorShadows" (live shadow-casting), and "Wall.drawWall", which is the function that calls render11 to draw the pictures.


The hxScout report isn't the latest. I made one more adjustment that got it up to 17FPS. Still, that room is ridiculous in a number of ways. Each of the window panels counts as a separate light source. Plus, each doorway is a light source (average of the lights in neighboring sectors), so 22 total. The renderer CPU usage is a function of number of pixels and number of lights... so if I have 22 lights I might as well consider drawing the image 22 times. The most intensive part of the renderer is checking which points are inside a shadow.

A more reasonable room easily obtains 60FPS, so I think I'm just going to have to watch the light count. Fortunately, one easy optimization would also greatly improve the aesthetic: replacing the window light sources with a single "sun" light source that is further away. As it is, the light source is almost inside the window, and so the light fans out much more widely than it would from a real window.

Shadow casting is now extremely lean. I sped it up 10x just by replacing constructions of new classes with primitive type variables. There is no garbage to collect at all now. Between that and doubling the renderer speed I get my 20x improvement.

Unfortunately I think I've squeezed just about every bit of speed out of the renderer.* There is one more thing I can do to the shadow casting code, but there's not much to gain because it's already pretty quick, even with a lot of actors moving around. I really need to investigate whether or not I can push some of the renderer code into a shader.

* I might be able to figure out how to re-render only the pixels inside or near the new shadow by defining an AABB box the shadow lives in and looping through only those pixels.

merrak

  • *
  • Posts: 2240
GBJam 6 Update. My "entry" for GBJam 6 is now back on track, and only 14 days late so far! I think I made the right decision. The renderer upgrades have been well worth the trouble. I've made several more complex rooms and haven't found any rendering errors so far.

I'm surprised how well the live/dynamic shadows run. Granted, the Game Boy resolution is only 160x144--but shadow casting time is a function of the number of walls and actors in the room, not the resolution of the screen.

Here are some screenshots.


Marika's shadows are clearer in the top and bottom image. When a room has a single dominant light source then the shadows are solid. Rooms with multiple light sources cast almost no shadows, so I think I'll still need to place a little dark spot under the actors like I originally planned. One other thing I definitely plan to do is make Marika, and the other actors, brighter and a bit bigger. They're too hard to see in their current state.

The middle image is a goof--the light source has the wrong coordinates set and placed the light inside the pit. I like how it makes the pit look more dramatic, but it also messes with the perceived geometry of the room. One of the practical purposes of the lights is to make the room's geometry clear to the player.

Some thoughts for the future. When I get back to Temple of Idosra, I'm wondering if I should revert back to the original full-color version. The primary reason I dropped my plans back to the 8-color version is that I didn't think the renderer would be up to the task. The software renderer has proven to be quite capable to handling my original vision. The full-color renderer is much better at producing the kind of atmosphere I wanted for that game. These are older renders from last year:



I can also make a couple of upgrades. Since the game knows where the different rooms are ("occupiable volumes"), I should be able to generate atmospheric effects like light rays shining in from the windows. I really haven't explored the idea much. I don't think it would look good in rooms that had a lot of windows, so it might not be worth it.

The biggest upgrade would be to take advantage of shaders--pass the shadow vectors into a shader and let it handle rendering. The software renderer is still the dominant consumer of CPU power... and unlike shadow casting, its demand is a function of screen resolution.

All of this can wait for now. I'm working on maps for GBJam 6 game, dubbed "Towers of Vallas". The current plan is 10 full size maps and 5 mini maps for bosses. I'm shooting for a game that can be completed in 1 - 3 hours... or maybe a bit more if the player wants to look for all the secret areas. I already added one.  :D

mdotedot

  • *
  • Posts: 1500
Looking very, very nice.

Can you show us a GIF from the gameplay. I want to see the lighting in action please!?!?!

Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 2240
GIF Update!

Looking very, very nice.

Can you show us a GIF from the gameplay. I want to see the lighting in action please!?!?!

Here's one I recorded. It's a largish file, so I'm just going to leave a link to it rather than embed it in the post.

http://anorthogonaluniverse.com/misc/vallas/2018-09-09-01.gif

There are still a few rough edges to smooth out. The shadow is cast by a simple box. I do have a mechanism to cast a shadow of the figure itself (explored in "Goat Problem"), but because of the low resolution I think just a little bit of fuzz around the edges of the shadow will suffice.

Also, sometimes the shadows disappear entirely. This occurs if Marika or one of the other actors walks into the light source itself... in this case, the little lights on the walls are actually in the center of the tile they open up into. The map editor lets me set the row,column,level of a light. I just need to fine tune the position of the light so it is against the wall, but not in it.

mdotedot

  • *
  • Posts: 1500
AWESOME stuff Mate!!!

I'm sure you can tweak it a bit, but you have come far !
Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 2240
Thanks!

I think I'll need to make a couple more tweaks aside from what I mentioned... not much coding, just trying different things and seeing what looks best. In rooms that are already very bright there are no shadows. Each sector has a base lighting level ("sector ambient") and each light adds to this value. It's meant to simulate light that comes from all directions, like reflections off of walls, but the affect is too strong.




merrak

  • *
  • Posts: 2240
Hope you will be save"

I've done absolutely nothing on the game this week :P Everything at the university shut down so I would actually have some more free time, but I've been storm proofing the house as best I can. The usual problem is water: the highways around town pass through low areas so the town almost becomes an island if enough rain falls.

Just sit and wait, now. One thing I can do to be productive and also pass the time is balance the game. I've just been making guesses as to how to set things like NPC hitpoints, weapon damage, that sort of thing. I never really sat down and worked out just how all the numbers will work together.

I'm keeping the same mechanism for experience and leveling that I outlined once before. The key differences from the usual RPG fare:

-- The player does not have a level. The player can find books, and experience points are spent to acquire knowledge from the books. Since Towers of Vallas is a shorter game, there aren't that many books and there is no hierarchy. Idosra has a more complex setup. For example, most of the books in that game are written in other languages, which would need to be learned first.

-- Experience points are awarded for completing objectives. NPCs can be ground (grinded?) for some points, but most are rewarded for accomplishing certain tasks. The objective in Towers of Vallas is simple: loot gold. Some points are awarded for gaining access to certain areas, and then some points for finding gold... a lot of which is hidden in secret areas.

-- Character selection: You can play any character you want from the following list: Marika.

Actually, the engine is set up to allow for multiple players. I've entertained the idea of using SocketMUD and PHudBase to set up a real-time multiplayer game. How well that works would depend on how much I am able to optimize data transfer. I really don't see an MMORPG on the scale of hundreds or thousands of players working, but if the SocketMUD idea worked then I could see people setting up small-scale multiplayer sessions.

Critical position-based functions in the game use the row, column, level (RCL) coordinate system, not grid coordinates. It wouldn't be necessary for all players to know the exact positions and states of the others, so long as the sector position and RCL position are in sync.

Anyway--I'm rambling at this point and the wind's picking up so I think it's time to cut this update off and post while there's still power.

merrak

  • *
  • Posts: 2240
Return to Routine. A lot of us in the Carolinas are looking forward to getting a normal routine back. Fortunately, my town fared okay all things considered. Hurricane Matthew tore down most of the weaker trees, so this time around clean-up was quicker and power restored faster.

RPG Issues. I spent some time thinking about how to configure NPC enemies and maps. Up until now my main focus was on the engine, so I threw out some stats that worked and went with it. Now that I'm shifting to map and NPC design, I need to think carefully about how to balance the game.

I passed some time watching The Game Making Journey. Around video 8 or 9 he mentions using a spreadsheet to play out different scenarios in an RPG. That seemed like a good idea to me, so I threw this together in an afternoon:

Full Size: Link!

My spreadsheet lets me plug in some statistics relevant to player and NPC attack/defense and get a rough idea of the likelihood of negative outcomes. Obviously I can't model every variable--but this is a vast improvement over nothing.

The spreadsheet computes four difficulty ratings on a 0-10 scale. "Attack Count" is difficulty due to the number of rounds in a battle. "Health Risk" is difficulty roughly based on the probability of the player dying. "1x Exhaustion" is based on the chances the player will run out of movement points in battle, and "Group Exhaustion" is similar, but takes into account multiple NPCs in a room.

It's worth noting that "Attack Count" is not redundant, even though exhaustion is also based on the number of rounds of battle. The longer a battle lasts, the greater the odds that the player will make a mistake. The "patience" stat is a rough idea of how long the player can go before making an "oops".

This will help a lot when I get back to map design. I now will have a better idea of where to place enemies and what effect they'll have when the player is at a certain stage in the game.

Design Goals. One of my goals is to make combat "flatter". In a traditional RPG, the character level structure divides the game into distinct stages. For example, a level 50 character will have no use for a level 1 area, nor will a level 3 character stand a chance against a level 90 character. This would force me to create a linear game world.

"Towers of Vallas" shares a trait of the Megaman games--there are four "bosses" that can be defeated in any order. The player starts in a central area and finds their way to one of four towers. Each tower contains a couple of maps, capped with an end boss. Each boss also has a special weapon, skill, etc. that the player can obtain, which will make the next easier.

This is a tricky design to balance because I don't know what order the player will choose to complete the towers in. Like in Megaman, each boss has a weakness to the bonus awarded by defeating another boss. So in that sense there is an intended order. That's left for the player to discover.

« Last Edit: September 19, 2018, 08:10:30 pm by merrak »

Bombini

  • *
  • Posts: 1131
Happy to hear that nothing bad happened during the storm!

First, i really love that you are drawing inspirations from this concept and planning to implement it.
I think it offers the player a great opprotunity of choice and control.
It strenghtens as well the feeling for the player that she/he earned the new power.
This is great.

"Towers of Vallas" shares a trait of the Megaman games--there are four "bosses" that can be defeated in any order. The player starts in a central area and finds their way to one of four towers. Each tower contains a couple of maps, capped with an end boss. Each boss also has a special weapon, skill, etc. that the player can obtain, which will make the next easier.

This is a tricky design to balance because I don't know what order the player will choose to complete the towers in. Like in Megaman, each boss has a weakness to the bonus awarded by defeating another boss. So in that sense there is an intended order. That's left for the player to discover.

The spreadsheet can be a very powerful tool and i am happy to see your approach.
Maybe for inspiration/food for thought: A design friend of mine works on a game with a complex economy. He created 4 different player profiles (for example "heavy grinder", "casual player", "completionist") and wrote bots which simulate playing those profiles (not in the game which is not existing yet. Purely based on spreadsheets and data. He lets those bots play for days to adjust and finetune the balancing.

merrak

  • *
  • Posts: 2240
...A design friend of mine works on a game with a complex economy. He created 4 different player profiles (for example "heavy grinder", "casual player", "completionist") and wrote bots which simulate playing those profiles (not in the game which is not existing yet. Purely based on spreadsheets and data. He lets those bots play for days to adjust and finetune the balancing.

That sounds like a really good idea. I have given different play styles some thought, but simulating how they would work and getting some concrete numbers sounds like a good next step.

I like to have secret areas. I've already started to populate the maps with little hints that there's more than appears at first glance. Here's one such case...

How do you get to that balcony???

There's a finite number of NPCs in the game. Extra areas can not only provide some bonus treasure for the player, but also extra opportunities to level up... or extra challenges beyond what is in the base game. So for the "completionist", there's that route.

The second approach is to try to beat the game as quickly as possible. That's a matter of achieving a high enough "level" to complete the final area. I don't think it'd be possible to complete it from the start, but with my spreadsheet model I can work out what the minimum experience might be.