Pathing Headaches; Bug Hunting

Sometimes on this Blag I like to just talk about programming, and some of the challenges I've come across throughout this project. This is one such post.

The 'crowning achievement' of a few months ago, within World, was updates to the pathfinding system. The fixes and speedups here literally made the game work, compared to the terrible game breaking behaviors beforehand. A result of this update was a particularly rare exception thrown on the server. This exception resulted in an invalid path, but when recomputed raw (without the path cache) the answer was correct. I've run for months with the bug in play, but just ignored. The game runs fine without it being fixed; at least, as far as is obvious to see. Nonetheless an outstanding bug (a crash bug) in this glorious system could not be sustained.

First an explanation of the pathing and mapping system. Part of me wants to say "it's not very complicated", but I'll leave that analysis to others. The map, as far as the server cares, is a connected directed graph. Each vertex is a possible location for an entity to exist. Edges are walkable/movable paths, the length of which determines the time to walk the edge. The graph is built up as a hexagonal grid, but in actuality the hexagonal limitation is not implied by the graph, it's merely a consequence of the graph's construction. As far as the mapping system cares, it's a generic graph with no basis on the game geometry, terrain, or environment.

Finding paths, then, is a fairly straightforward application of well known computer science algorithms. Any game programmer worth their sodium knows the A* pathfinding algorithm. It's a natural fit in this case, and so it is used.

The game, by its nature, requests a ridiculous number of paths per second. Due to constant formation and range adjustments, as well as navigating around other entities, paths are needed very frequently. Compute time is important in this case. I opted to build a caching system for common types of paths. Turns out the cache hit rate is about 99%, so it's well worth it.

The bug in question is a caching bug, so a bit more detail there is relevant. Each map-vertex stores a set of known target cells, and which neighbor to move to to get to it. That is, a cell 'A' may remember paths to 'B', 'C', and 'D', which lead through its neighbor 'B', 'C', and 'C' respectively. The paths are incremental. Rebuilding a path from cache is a simple linear sequence of hashtable lookups to determine the next step.

When a path is not available from the cache, A* is executed to build a path. However, at each A* vertex inspection, if there's a path directly to the end target, we can shortcut the remainder of the A* traversal and simply append the remaining known path to the newly calculated derived path. At this point the derived path's entries' caches are updated with both the tail of the derived path and the known path. Thereby the cache is augmented in the case of a found partial path.

That's it. Where's the bug?

The bug is that somehow, through some sequence of queries, a new path is requested that is broken. The cache implies a sequence to reach the target, but one of the vertices along the way has no cache entry to the target. What's missing?

Throughout the last months when the exception would pop up I'd inspect the cache data. However, inspecting 10000 vertices in a small map isn't exactly tractable. Confirming the cache coherency after all changes would make the game unplayably slow, and so never exhibit the bug. Then, some perfectly reasonable person suggested I just brute force the damn thing and find the problematic sequence.

So I rigged up a unit test to build a 10x10 map cell grid and exhaustively checked all possible sequences of 3 queried paths, and then test the cache coherency. 2 hours later I realized that I'd just executed an O(n^6) algorithm with n=100, broke into the debugger, and realized that I'd be waiting a few years for results, and slapped myself in the face.

So I rigged up a unit test to build a 10x1 map cell grid and bla bla bla. It ran, and it.. didn't crash. Figures.

So I rigged up a unit test to build a 4x4 map cell grid instead. 35 minutes later an exception came up. I checked the pattern of queries. It was not what I expected to see. I was expecting a bug in the partial-path re-caching behavior. It's the most complicated thing in the system and therefore the most likely to fail. What I saw took another 30 minutes to just understand. I made pictures.

Those are the relevant nodes. Actually the node above b is relevant too but I forgot when I made the image. The first queried path was from a to h:

The second path was from b to i:

 

When I first saw this path I was briefly confused. It seemed curious that the path through e to h would differ between the two. However, given A* on this graph it is reasonable because of the differing endpoint. g is closer in cartesian distance to its target than f, so the path is subtly different. It seemed weird but possibly a problem. I didn't know how yet though.

The third path was from c to h:

This path has a partial-cache hit at d. That path is d, e, g, h, the purple path. However, you'll note that the path obtained (in orange) is d, e, f, h! Well, it turns out the cache is a single store, and so only the first path from e to h is stored. d knows that it can get to h through e (and historically this path went through g). However, when the path resolution steps into e, e says the next step is f, because that was the first path from e to h stored.

This bit of inconsistency result in some confusion when the breaking query fires, from c to f:

The queried path should be entirely in cache, since it lies along the orange, previously queried and cached, path. However, when the path cache steps into d, d has no known paths to f. d has only ever pathed through g, and so the cache read has failed.

Why did this fail? It's because of a combination of three assumptions that are not always correct:

• Given a point A and B, there will only ever be one path determined from A to B. This is true if B is the final destination, but not if a vertex beyond B is the target.
• A partial cache hit, already being written to the cache, does not need to be written to the cache. This is true if the earlier (incorrect) assumption is, but since the known path can differ internally, the newly found path needs to be written to the cache as well. When this is written the c to f path is correctly written when the c to g path is finalized.

Bug fixed. :)

Next time, the new terrain engine. Here's a preview.

TOASTcapture!

So; Motion Capture!

A few weeks ago I got the bright idea that we could use a Kinect to record animation data to use for the game. That sounded like fun so I bought one and started working on building a recording program. It sorta started working, so we decided that, while a friend was in town, we'd invite a pile of friends over, stick them in front of the camera, and have them record some silliness.

Now, it took a few weeks of difficult math that's still being worked on, but the translation to our skeletal system is good enough to get a decent preview of now, hence this post. First, some numbers, a video link, then some discussion on challenges.

30 mocap sessions recorded. Each of these is about 2.5MB of raw floating point data; 21 points in 3d space per frame, a timestamp per frame, somewhere around 30 frames per second. Each session consisted of a sequence of typical animations we use for the game. Most of the glorious participants recorded a set for a specific class or enemy type, so we have a wide variety of styles here.

6.5 hours to run the skeletal solver for all the recorded mocap data. I'll be the first to admit this could be improved, but it sounds somewhat impressive or something.

60 MB of additional animation data required to be downloaded by the client (for now). Given that the entire rest of the content is about a quarter of that, it's a noticable hit. This data is horribly horribly de-compressed so it can be fixed, and the keyframe data should be smoothed anyway, but again; DATA GRAR.

27:38 of recorded animation data. Each person recorded just under a minute of live-time; even though each session took about 10 minutes to perform. The script was set up to give some time to think of what to do, as well as some lead-in and lead-out time per animation.

The Video is here. It's... WAY WAY longer than I was expecting honestly. I don't expect people to watch 30 minutes of random animating; but it could be fun to skip through and see how much we did :) OR, if you were HERE, find your own set to see what it looked like!

There are a pile of problems with the data. The most obvious is that some of the recordings just flat out come out wrong. Anything that isn't mostly standing up, moves to fast, rotates a lot, hides arms behind (my scout pose), hides legs behind the body (kneeling), etc, all totally fail to be recorded correctly. This is completely expectable given the nature of the camera, but it does mean we need to adjust what we can do with it. In some cases we could rotate the actor (and invert it when processing).

Others are problems with the translation; if you look at the data even briefly you'll see the magical swimming torso problem... MATH IS HARD. The hands and feet aren't tuned yet, the rest poses weren't all recorded correctly, etc.

But its fun! And it was educational. Once the keyframe compression is managed (either manually or automatedly) I'll be able to realistically reference the animations in the game. There's also a matter of time syncing; most of the actions recorded don't conform to the timing standards of the rest of the game, so they'd appear really late or never actually appear to swing.

Always more to do :)

Math is Delicious!

Alright, I totally was gonna spend tonight making an awesome movie showing some new fun stuff, like the scenario with 200 dudes, and then knocking them all off cliffs, and stuff like that.

But instead I spent 5 hours wrangling the Jacobian transpose iteration method for syncing our skeletal data to that provided by the Kinect SDK. And massaging the data into proper form, and getting every last damn transform right. It's complicated! But its almost almost there now. I had a serious breakthrough in solving the main problems today. The method is working very well now, except for the hip and torso joints which still corner out for some reason. Once that's figured out there's some keyframe compression required, but then I'll have some nice motion captured imagery to share with the blag.

I never really talked mocap here, did I? Oh well. I'll talk about it when it works :)

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.

Meta-Work

Long time no see!

Why no videos, updates, etc? There's a good reason for it. It turns out that a lot of the work involved in building a complete system is... really really boring!

At least, it is to the player. I've always been kind of secretly entertained by the 'meta-work' needed to build the complete system, so the last few months of productivity have been somewhat enjoyable for me. They don't, however, make for exciting videos or complicated subject matter.

So what's actually been done since the last updates?

Game stuff:
  - Motion pretty well works now. The last post was all about movement. It plans therein didn't 100% work, but they got things moving in the right direction. In conjunction with fixing a few low level bugs, units seem to move fairly predictably and controllably now. There're a few things that could improve still; for example, if you command a move with a new formation orientation, should the group rotate or move first? Turns out to not be a simple implementation detail. It makes sense to say 'if retreating, move first' and 'if attacking, rotate first', but it's not entirely that simple.
  - Some scenario stuff. Been working on a more heavily scripted scenario, so things like triggers, unit details,  player triggers, custom units, etc, have been improved noticably in the scenario editor. As noted above, though, showing the scenario editor is not exactly rivetting entertainment. When the scenario is complete I'll video-up a playthrough. Maybe with multiple people.

And Meta stuff:
  - Wrote new Universe server, with lots of sub-servers:
    - Scenario server; maintains a list of available scenarios and can launch them; they're each launched into a new instance of the zone server, each of which can have updated EXE/DLLs and game databases. This means code updates can apply to a live server.
    - Accounts server; this replaces the old one, as a part of the universe. Account/player/commander/primary data is now stored more simply as well; just as local (server) files. This removes the pain of the unnecessary link to SQL, and simplifies deployment. (See? Deployment is a boring word, but it is important!)
    - Assets server; this is an entirely new and complciated system:
      - The game client no longer ships with ANY content; it only downloads and installs the DLLs and EXEs and maybe a config file. Upon load, a set of required assets are pulled down from the universe server's asset system. Later, when game assets are needed, they are loaded on the fly, with a temporary asset put in place while loads run in parallel.
      - The server and client both SHA1 hash their asset data, so when the client starts it can do a simple comparison to know if its content is up to date. No unnecessary transfers.
      - So in the end, the server can update the game database, animations, textures, terrains, models, etc etc, withOUT requiring a new install or patch of the client. The client only has to push an update for code changes.
      - Obviously this is a big and complicated (and awesome) piece of architecture, which I'm quite happy with. This doesn't make it interesting to show people though. :) "Oh boy, my units are boxes! Oh wait, now they're people again" isn't terribly exciting, but it IS useful to me :)
   - Lastly, cloud deployment of the universe and content. 'redtoast.net' now points to an Amazon EC2 micro instance, which runs the universe (as well as other services like apache). I've built scripts to run on this instance to auto update from source control and rerun the universe, re-deploy the client, etc. It's neat! It's boring, but it's neat!
   - Because of the cloud deployment, everything now works without my home machine running the custom servers. Maybe this means I can have a more publicly accessible pre-pre-alpha....

Some new game data will come soon, with the new scenario (soon), and then some new universe related neatness!

Party on.

Movement revisited

I'm going to use this space today to think out loud. Er, think externally. You know what I mean. Sometimes putting things into words forces it to organize and coalesce into a concrete idea and plan, and the complication of formation movement could use some consolidation.

So forgive the stream of consciousness, and read on if you wish. Any ideas, counter or otherwise, are welcome.


It's an easy assumption to make, that movement and unit control is important. It's arguably the most important thing to get right in any game. I know it is one of Miyamoto's 3 more important things for game development (Character, Camera, Control, IIRC), so it deserves some attention. In our game, the control is somewhat more complicated, since it is neither direct nor constrained. Almost all movement is given as an intent; rather than moving the units directly, the units are told they need to move, however they can manage that given their other constraints. This is important because managing those constraints are critical to gameplay.

Anyway, what are the constraints that make this complicated?

1. Stay as close to in-formation as you can, maximally deviating by a class-specified variable distance.
2. Move towards the user's selected goal location (including pathfinding)
3. Get to a class-specified distance from your current hostile target.

The current approach, so far, has been to compute an 'ideal' location for each of the criteria, then use that to weight each currently-adjacent cell, thereby determining which direction to move (or not, if at the ideal). Even computing the ideals for each is complicated, let's ponder that first.

1. Compute the current estimated formation location of the squad as a whole, and from that compute our ideal offset. 
2. The user's goal location is set for the formation as a whole; finding a relative position to this is not compicated. When obstacles are included and pathfinding is required it becomes a mess, since individual units may opt to take a different path to the ideal location.
3. The attack-distance ideal can be defined as the closest location to the current location that is the specified distance. This one is pretty easy at least.

So given three target locations, how do we decide which to use? So far the subtleties in this decision have all resulting in problems. If 1 is too important, then the units cannot move to the target location. If 2 is too important, the units deviate from each other and the formation mechanics break down terribly once combat is engaged. (Oh, if we're not in combat then most of this is easier, so we're ignoring that condition for now). If 3 is too important, it is impossible to retreat, since units will stay at combat range. Anyone who has played the game at various points has probably seen all three of these faults.

While we're making things sound dire, a few more complications: Pathfinding that accounts for formation offsets is complicated. That is to say, if you want the formation to move around a corner while staying in formation, the individual paths are substantially more complicated than a simple A* will find. Each step would need to determine the 'radius' it accomodates, but this would have to have some directionality to it. Units on the right edge of a formation would need no extra space around right turns, but lots of space on left turns. Can this be computed efficiently? Each cell could retain 6 'wedge distances', perhaps, which represent the distance within each hex wedge that is walkable. Currently we retain a single 'free radius', but there is no directionality to it. (This radius is used to limit occupancy by large units, and was used in some formation movement tests already).

A second option for formation pathfinding is to compute the path at the squad level rather than the individual unit level. This could solve the problems with diverging paths as well. The question is how and when to compute the next step. It could be recomputed every time the estimated current formation location changes, and set to a few cells forward on the path, perhaps. If computed this way, the singular occupancy radius could be used to generate a smooth formation path, which should keep the units together.

See? That was an idea. I hadn't thought of that before. This is useful. I like this experiment.

So I suppose now we have a coherent answer for the ideal locations. Back to resolving the decision making once the ideals are known.

It feels like, rather than a weighting function, a sequential deciding criteria may work. Consider:

1. If the unit is not within tolerance of the current formation ideal, move to that, otherwise:
2. If the unit is not within tolerance of the target formation ideal, move to that, otherwise:
3. Move to the target-distance ideal.

Could something this simple just work? The current approach uses weighting functions rather than a decided single purpose for each move. Maybe it is worth a try. 

It's worthy to note that when I started writing this last paragraph I started by assuming this approach wouldn't work, and I began writing reasons. I failed, but isn't it interesting to note where one assumes incorrectly, without even noticing that one is confused?

Recapping the movement process:

• Component 1: Formation estimation
• The formation leader maintains an estimate of the current formation location. Whenever this location changes cells, a new path will be calculated to the user's target location, using formation-width weighting to round corners. The new target formation location will be set a few cells down this path. (Setting it to merely 1 cell away will should result is some nasty stutterstepping and un-smoothness, but given earlier mistakes, I will TEST this when implemented).
• Component 2: Per-unit movement step
• Compute the current-formation ideal location and leeway. If the current location is outside of this leeway, move towards the ideal and finalize decision.
• Compute the target-formation ideal location and leeway. If the current location is outside of this leeway, move towards the target-ideal and finalize. NEW IDEA: If the location towards the target-ideal violates the current-ideal leeway, STOP motion and wait one tick to re-evaluate. We don't want to cause cyclical stepping between target and current in the case that the current is 'stuck' away from the target.
• Scan neighbor locations for the cell closest to the target-distance ideal. If a better cell exists and this cell neither violates the current-ideal nor target-ideal, move to this cell and finalize.

For now I'll use A* for the pathing, and I'll ignore efficiency entirely. (Early optimization is the root of all evil, after all)

I can do this. Let's see what happens.

-------------

Here's an image of the scenario editor showing a variable-width path. I rigged up the editor to show me the pathing calculations; easier than expected, even though it requires bringing in server code to the editor. Apparently the mapping subsystem isn't coupled too tightly to the rest.

-------------

Aftermath 1: They dance around a bit, but in they at least get around, eventually. The twitchiness will need to be addressed, but I believe it is in better shape than beforehand, at least.

Aftermath 2: After adding in the post-constraints (moving to target will no longer move outside the current), it works smoother. There were some code bugs associated with the time to decide motion that got resolved as part of this.

Aftermath 3: There's a problem still remaining if the target and currents have no overlap; in this case each unit will stop proceeding. In theory this just means that the unit is awaiting the formation to reform correctly, but there are stable cases where this happens; for example, a formation directly turning around. Each unit is stuck waiting on each other; kind of like deadlock. Adjusting the formation location analyzer helped this a bit, since the prior was quantized in angle and really angle-twitchy, but the lock is still possible. Smoothly changing the rotation from start to finish may be necessary as a pathing-like step.

Post-Lan

So, this last Saturday (the 19th) was one of the bigger playtests of World in recent memory. I took the excuse of a Diablo 3 LAN and made some peeps play the game.

For this purpose, I decided to make a new type of scenario to hopefully make the game a bit more dynamic. Actually I wrote a whole bunch of new stuff, so it was perhaps good for inspiration to work if nothing else. I think this post will be a combination mini-postmortem and World Update.

New stuff written for LAN:
  Territory Control scenario type:
     Team score / Team score boosting actions / Team score winning conditions
     Auto-join smallest team.
     Mid-scenario respawn for dead commander groups / players.
  Database functions:
     Can make interactions from GDocs.
     Interactions can channel.
     Added 'SoloGrant' effects, which grant an ability to the target, but when granting to subsequent targets will remove the grant from the first (so that only 1 has the grant at a time).
     Units can join the commander now via interaction (territory control points use this).
     Built two new types of enemies with some new tech needed: Earth and air elementals, they use a different rig and have some different abilities (which were too strong)
     Added per-enemy grant state that stacks for every hostile player in the game. This scales up enemies for multiple players.
  Mapping:
     Updated logic that connects gridcells together; it can now span empty area for knockback/projectile paths, so non-infinite slopes can still have knockbacks/projectile fired over them.
     Did a lot of cleanup work to allow building a fairly large scenario map.

Stuff written that I probably haven't mentioned:
   Primary units can now res unconscious commanders by using a long channeled action. The commanders' action bar is replaced by a button that grabs any available primary to do the res. This channel is 'weak', and is interruptable by any damage, in addition to normal interrupts.
   Maneuvers update; no longer transition between formations.
   Out-of-combat idle animation switch.

How'd it go:
   AAAAAAAGGGGGHHH.
  The scenario was too big and the client chokes. The ray intersections needed to run locomotion for all the entities, even just the ones in close proximity, brought it to a painfully low frame rate. I think I'll get rid of loco. For the LAN I just had to remove a pile of units, making it boring-er. On top of that, the scenario map was probably a good 3 times too big; it's really easy to mis-estimate size when building maps. Traversing the map would've probably taken a good 2 minutes at normal walk pace, withOUT enemies killing you en route.
   The navigation and pathing code for formations broke pretty bad too; that system may need a fundamental readdressing, rather than tweaks. Occasionally groups just stopped behaving reasonably.
   And, the scaling was WAY WAY off. Each single enemy was massively massively overpowered with the per-player buff in place. As in, a single kobold being nigh-unkillable, rather than dead on arrival. The elementals in particular were extremely unforgiving. A higher level group (10ish) with some game knowledge, can fight them and its hard. Level 1 groups (since the kobolds were too hard and I removed most of them, noone levelled), with introductory players? They died. A lot. At least they have respawn :p
   BUT. Aside from one server bug that I patched up really realy quick, the server managed running the scenario with 4 players without too much trouble. The combats worked, even if they were unbalanced. The new mechanics written for the scenario worked, even if they weren't terribly relevant.

And hopefully people had at least a little fun.
The final score was 200 to 198. Of the 6 control points, 3 of them were actually reached by players. There were '0' PvP combats in a PvP scenario, but there was plenty of death caused by the random assortment of PvE mobs on the map.

air elementals are fun :)

 

AAgggh Movement is complicated

(I think I wrote this a night or two before the LAN at 4:30 and forgot to publish. Given how the LAN combat went, it may be amusing)

Moving in formation is complicated!

Turns out we have 4 conflicting criteria we need to reconcile in order to determine where a unit is moving. The user's specified target location, the current formation estimate location, the class-specific ideal distance (from their target, for attacking), and the class-and-mode-specific leeway, which gives units a range to roam in around their formation centerpoint.

The latest bug was that leeway was never usable, because the importance of following the user target location was guaranteed to be greater in all cases. There's more, but now I sleep.............

Maneuvers

It's been awhile since I wrote a design thoughts essay post. I've been intending on writing this one since before it implemented and sequentially changed. So, without further boilerplate:

Maneuvers: 


A maneuver, in the context of a World skirmish of course, is an action invoked by the commander, used to change between formations and locations in a specified manner. The intent was that a maneuver would be used to quickly change between formations in combat situations. The end result and implementation were a bit more complicated.

Let us define the exact details of the maneuver in the Skirmish context. A maneuver consists of 4 stages, a windup (channeling, which can be broken, and an associated buff state), initiation (which triggers class specific actions), advancement (moving to the target location, which can also trigger class specific actions), and finalization (reaching the target location, also triggers class actions). Notice an awful amount of detail hooks there. Each class specifies how it behaves for each maneuver. A shieldman may conclude a maneuver with a shield slam. An archer may lead a maneuver with a volley of covering fire. The commander may provide a group buff while advancing. Furthermore, the commander will have multiple maneuvers, so each differing kind can have different per-class hooks.

Except, that's rather massively complicated. The first maneuver we made is a simple 'Charge' maneuver; run at the enemy and engage rapidly. If we make a second maneuver that is similar, should it have entirely different class actions? Nah, let's categorize maneuvers. Now, all 'Charge' maneuvers share the same actions. This lets the commander upgrade the maneuver without forcing us to re-implement all the maneuver-actions. We could make a 'Charge 2' (for lack of a better name atm) that winds up faster and provides a speed increase while running, but now it otherwise acts exactly like 'Charge 1'.

So now we can run at things and have new class differentiation points. Yay! What about other kinds of maneuvers? A coordinated retreat is kind of like a Charge, except away instead of toward, so the implementation there is easy. We make a new maneuver category to change class actions and it works without problem. A slow pressure advancement works similarly. After that we created a 'Hold' or 'Stand your ground' maneuver command. This one was different, in that there's no movement phase, and the ending triggers are different, but it still works. The same logic can be used to make a maneuver that just tries to get the formation back in order quickly.

So 5 maneuver types; Charge, Advance, Retreat, Hold, Reform. They almost perfectly correspond to the 5 formation movement modes (Charge, Advance, Defend, Retreat, Hold), which is cause for thought. Should maneuvers replace formation movement entirely? We concluded that no; maneuvers are a specific command with costs and benefits associated with. It would be silly to run with a charging sprint as your default move command. Sometimes you just move.

Implementation took a bit of effort but there was nothing terribly interesting to report about it. We've had the maneuvers in place and working for a few weeks now, so they've been used enough to know that Charging is Fun, Advancing is useful, Hold has potential but the current scenarios do not require it, retreat is occasionally necessary and the only reasonable way to extricate a group from combat, and reform is... well, a little less interesting, but it COULD be with more maneuver-actions by class.

A success? Well, sort of. Remember that part above where I said that a maneuver is a method of transiting between formations? Turns out we never did that, but we always have to specify the target formation anyway. So, why is this part ignored?

My opinion now is that the original concept was flawed, because it was based on a different pace of combat than the game actually exhibits. If you imagine a combat where units stay rigidly in formation, there is very little motion, and slight positioning different matter tremendously, then special methods to adjust inside a formation are relevant. This was in part the original concept. What we have now, however, is a massively more fluid, dynamic, and mostly chaotic combat engine. Is this good? The chaos is kind of enjoyable when you're the cause of it (which may be why Charge-ing is Fun :) ). With retreat/reform you can manage the chaos inside your group enough to not be bogged down. Advancing does a reasonable job of slowly pushing forward with a more organized wall. I think it works! Let's keep it. But what do we do about the maneuver definition?

Meh. Delete it.

We'll see how it plays without formation swapping; I bet it'll work fine.

Next essay I'll talk about Consciousness, or more specifically, lack thereof, as a game mechanic.

Video Update! :p

Lots of complicated stuff in this last month, but most of it is under the hood things like installers and nav. Also work is super busy, so Fridays have mostly been spent unconscious (mentally, if not physically).

Maneuvers and Streams are the big new visible things. They both deserve a design post of their own, so I'll leave it for later.

http://youtu.be/Nq6o-fEdI8k

Forward Progress

No new video again this week. Why? Because I'm not ready to show functioning Maneuvers yet.

Mostly I'm happy to report a fairly functional installer. I've fixed the major problems with it, up to and including fixing the missing terrain, and it's even playable! Heck, even Shalis installed it with no problems and was up and playing (albeit without terrain at the time :) )

Bug fixery bug fixery bug fixery. Maneuvers are neat!

Install?!

So, there's no video today, because I spent the night trying to find out how to build an installer for the client using ClickOnce.

And lo and behold, I have one. It works and even autoupdates. It's not as elegant as I wished on the build side, but really when is build management elegant? I'd link it here (since it's on the web, technically), but I'd like to test it with someone on the line first :)

Word! Hopefully it'll work well enough to at least make testing easier! It was always kind of an amazing pain trying to get the app on even local machines to test.

Friday movie

http://youtu.be/Zk7GfSFoCmY

This week I decided to mess around and play piano over the video, and add captions to show the emphasis and new things, rather than voice.

As for the actual code update; the UI is mostly functional at this point. Aside from side elements (like being able to change class/pick skills) the new UI is noticably more functional than the old one, which pleases me. The scenario got a small update, as did the enemies contained in it. It's still just a test scenario of course :)

I think the next plan is to get back to server implementation for a bit; It's time to write maneuvers! Kol and I have some design work to do and confirm before writing them, but I think I'll try and get myself to write up what Maneuvers will be here, concretely, before implementing. Then ideally when they work and show in the vids it'll be interesting :)

Next time!

Friday Update and Video!

Yeah yeah, a week late. I got a lot done so it's worth it.

Formation editing, formation mode commands, units icons, unit vitals, unit actions, among others.

But mostly I changed up the recording so it's much longer, and I went for it and recorded some voiceover. It might be terrible. :)

http://youtu.be/62Cj_MTade8

Hey hey! 3 in a row.

Maybe I'll be able to keep this friday thing up, eh.

While the client's getting revamped it's a pretty consistent kind of update. More stuff is working again. :)

Minimap improved, input system architected, formation editing panel works.

No audio yet, I didn't feel like hearing my voice. :p

The link is the post title, or....

Friday Update #2

Alright! Got some more protocol in there:

Commander selection and connected states are menu-ed up. Game knows how to watch the scenario's state and flip between inactive and active modes. Ready/NotReady works. Player list is shown with ready state. First version of minimap is in there, fixed the healthbars.

Not much, but the old client's guts are making their way across.

Video up at http://youtu.be/RSd6-xmJ28U

It's good practice making them. :) Maybe next week I'll be daring and include... SOUND....

Er, not that there's sound in the game yet; someday.

Friday Updates!

Hey. Since I often do a bit of World-work on fridays, I'm gonna make it the designated mediapostagenessday. Or something. So what's new?

• New client work in progress still: Main control structures and game initialization protocols are done now. You can log in (or not), select a character (or not), connect to a server (or localhost), then receive data, then make yourself ready (or... not?) to start the scenario.
• There's a small scoreboard to show other players and their ready-status that'll expand in the future. The game-starting mode is also somewhat setup to show a YOU LOST or YOU WON kind of screen for now. In the long run it's more of a 'scenario complete' mode

So yes, generic new client progress. Once the actual world visualization is in there shall be another video.

Holidays Complete. Back to work :)

So let's see, what's new:

• Many scenario editing fixes and updates. Implementation of trigger system is about half done. Regions can be used to invoke triggers, but the only thing that can respond is an enemy spawner. Regions can modify units now too; that is, provide a buff or debuff. That buff can do anything any other state can, include granting abilities or causing damage, so there's some versatility there.
• New formation movement mechanics. We're working on a major rev to formations in general. We started overhauling the basic movement methods, since they're actually amazingly complicated for our game. We were finding that formations felt clunky more than anything, and alot of that is the lack of coherence of the group, so I took a more error-estimation based approach to maintaining formation. We also nuked the formation concept of leeway (the allowed error any unit is allowed from perfect form), and made it a per-class concept instead.
• Once formations worked a little smoother I was starting on maneuvers (group actions), but got derailed by...
• Rewriting the entire top level of the client program. :) The UI toolkit was severely inhibiting my style, so... it had to go. Mostly I felt like I was hacking around it instead of owning it, so I decided to take a more games-inspired approach to input/window/ui/display management. Sometimes you just have to take a plunge and do something hard in order to be happy with it.

More than that, really, but stopping there makes for a nice segue.

BACK in the day, when I started Twilight 1, I started with the main menu. Seems kind of obvious place to start, but I recall being excited to just play with the concept and do something arbitrary, visually at least. Later menus I made were more functional and fun, which is fine but boring. The existing skirmish client menus fell into that category.

So naturally I decided to be artistic again, even if it feels like wasted time. I came up with a concept and threw it together pretty quickly. It's nice to have a short term goal, especially when I'd just decided to throw away the existing toplevel module and start clean.

And since it turned out looking kinda neat, I thought I'd try and record it. Of course, that meant rewriting some graphics guts to get Fraps able to record it (in WPF, we don't display to the default swapchain in directx, and fraps only records the default swapchain), but it didn't take too long in any case.

Oh right, a link. I've never done the recording/encoding/uploading/youtube thang, so it's got some flaws, but you can't get better without tryin'. :) Enjoy.

Now to go get the client able to play again...