Friday, September 28, 2012

Cleaning up the World

Last time on the World Update was meta-systems programming, so what's this time?

The last two months have brought primarily 3 things: A new scenario, massive performance improvements, and some new unit action design in progress. It's been a surprisingly meaningful set of improvements, worth pondering how it came to be. So let the prose commence: :)

1. The Watchtower Scenario

I wanted to make a defensive scenario; one where the players hold an area for a known amount of time under considerable attack, and succeed if their target lives long enough, and otherwise fail. Turns out there was a lot of new tech required to really pull it off well enough to play.

First, Map triggers.

To be clean, I implemented a somewhat generic triggering system for the scenario editor, and tied the win condition of this scenario type to a trigger. In this case, it's just a timer. I also wanted to be able to control the start conditions and start time of the attack, so there's another trigger required, and one that the user has to be able to execute. I then needed to be able to control waves of enemies spawning, so, more triggers. 

It turns out trigger/response systems are pretty nice; they're the obvious alternative to some kind of embedded scripting language. Lots of games go this route and for good reason; it's simple, powerful, and not error prone. I set up trigger possibilities for timers (triggered from other triggers), for the scenario starting, for entering a region/map cell, and for entities that are triggerable. Oh, I also implemented entity grouping, so that I can trigger off an entire group being killed.

The next problem when building the scenario is that there are lots and lots of enemies. The first version had 495 spawns on the map. Managing that number was so impossible that I just deleted them all and started over when I wanted a change. In fact, instead of rebuilding the scenario's enemies to adjust difficulty, I just changed the spawn mechanism to allow spawning multiple units. Yay! Now it's just a number.

So now spawns can make many units; turns out that complicates a lot of logic that watches spawn counts and spawners. Figures.

So while I was at that, I decided to make it harder and make the spawn count variable. No sense making it easy on myself. Variable in what way? Well, how bout adding a spawn count for each allied player, and for every enemy player? That gives us a way to scale difficulty with player count. It also lets us make allies contingent on player count, which is neat (base line 4 spawns, -2 per player, =2 spawns when alone, none if 2 or more players). On top of that, let's add a difficulty parameter to the scenario, let the user control the difficulty when triggering the attack, then multiply the spawn count using that. Fun! 

Well, briefly fun. I hit the hardest mode I set up and the first wave spawned 164 easy kobolds, and 30 allies for my team. Turns out the game can't handle that kind of load, and it.. well, it doesn't work. In fact, nothing moves at all since its so slow. On the plus side, my base was still alive after 10 minutes, so I won. :)

In any case, this brings us to:

2. Performance

Alright, actually I'm lying. The very very first time I made the scenario, with 15 kobolds, it completely died. Yeah, it didn't take 140 to bring it to its knees. 15 lousy kobolds was enough. Why now? Because the kobolds are attacking, rather than waiting for you to get near, so the path calculations are very long, and very slow, and actually just completely broken as it turns out.

I spent a good month just working on performance, and probably all but a week on one singular task. The first profiling yielded some useful information; 99% of the time was being spent on map traversal code. This includes evaluating area of effect, moving to range, estimating action range, and most importantly, path finding. (Somewhat surprisingly, the AoE calculation was 35% of the time, because every unit pulses a 20 hex radius aoe effect every 2 seconds, as part of the code game mechanics. More later).

So path finding. Lots of literature on speeding it up. A* is the common algorithm, but we were already using it, so...

Actually it turns out we were only 'technically' using it. We were actually using 'it badly'. Okay, that didn't work. Whatever. The algorithm was broken on many levels. If I could count the ways I would but I don't want to because I'd feel stupid.

I made some unit tests to help iron out the kinks. That wasn't enough, I updated teh scenario editor to show detailed debugging information on the paths. I wrote heuristics and double checked. I allocated 40 or 50 megs of ram to caching pathing information (oh, and wrote the caching). I bla bla bla bla fixed it.

Before, my test path took 60ms to compute. (Hopefully you're thinking 'Wow that's terrible!', and not 'Wow Nick is a terrible programmer!'). After, it takes .1 ms. Also, the cache hits about 98% of the time over the new scenario playthrough, and the cache lookup is faster than that even. Needless to say it's better now.

So it's faster. Turns out it's WAY more than that. There were some interesting side effects. 

First, the old algorithm would scan the entire map if a path couldn't be found. This sounds uncommon, but note that any time any unit is on their destination spot, there is no valid path! In this case the units would take the directest route possible. In addition to making it super super slow, this meant that units would not path around their allies, leading to single file lines of extremely stupid enemies that get stuck a lot. This worked against the player's units in interestingly broken ways too.

Secondly, because of this fix some aspects of the autoattack algorithm became obvious. When things can path around each other successfully the AI's decision making because more obvious. It turns out the AA would only ever try to attack the highest threat, even if it was inaccessible. This made the game feel incredibly slow, as everything shifted around (unsuccessfully) to try and act, and inevitably didn't. The game would even get into 100% stalemate situations with 20 units all in a jumble trying to move around each other. LAME. 

So I rewrote auto attack. While I was at it, rewrote the movement control AI for players and enemies, and the special attack code (same as auto, really...) Also rewrote the trigger for the AA. Previously it was timed (instead of using attack speed), and now it actually acts when the Attacks come off cooldown.

Honestly its amazing these things went so long without even being noticed. The game is COMPLETELY DIFFERENT after these fixes. It just... behaves! It's.. .like it actually works! It's 100% amazing to me how much better the game plays now. I'm really struggling to convey JUST HOW satisfying it is when the behaviors start working like they should, and JUST HOW stupid you feel when you realize how long there've been seriously broken issues that just weren't quite explainable. The game always.. felt right before? But it really wasn't.

Now it is.

One last note...

The defense scenario, the first time I ran it, was extremely easy. After all these fixes, the attacks are faster, the enemies close better, the ranged attacks work correctly, and your units are more dependent than ever on positioning. The game got a lot lot harder, but harder in lots of really good ways. 

I did more than just these main things, and we've got more stuff we're trying (I did mentioned a third thing up there, didn't I...), but that 'Now it is' line was just too good not to (try to) end on.

Peace. More soon :) It really needs a movie to show the unit motion and count... Tomorrow night maybe.