It seems to be the fate of blogs to be less written over time. Alas, when faced with the decision "Write more code or write more prose?", I've been picking code. It's been long enough that a small update would really not suffice. However, in the interests of getting going again, here's the recent World news:
New terrain engine integrated into actual game.
New terrain integrated into scenario editor (somewhat breaking old terrain too), editable in detail.
Large quantities of time spent tuning movement and lots of improvements to core game behavior; time well spent. Honestly this is probably the most important thing here but hardest to explain.
Enemy commander groups + updated AI directives system.
Several new classes for experimentation.
Expansion of particle effects systems, updates to Kinect motion capture and processing (Wiimote not really working :( )
New icons source, mostly rid of WoW Iconnery.
Zones can now change the map graph on the fly (the map, as it were). Still some lingering problems here (say, when someone blows up the spawning area, etc), but it's fun to make craters.
Multi-zone server; Daemon which runs multiple zones simultaneously. Having this running speeds up scenario launching, but since the cloud server is so slow (micro instance), it still isn't really used.
That's back to mid January. It's been good :)
Thursday, April 18, 2013
Saturday, March 9, 2013
More Music
As an experiment in learning streaming technology, and having some fun with hanging the Kinect from the ceilng, I live-recorded some music on twitch. Despite the uncomfortableness I have about being on camera, here you are: http://twitch.tv/ventare
It's worth getting used to, in any case. Who knows, maybe someone'll like it :p
It's worth getting used to, in any case. Who knows, maybe someone'll like it :p
Wednesday, February 13, 2013
Works in Progresses
Rather than deliberate and continue waiting to post anything, I'll post a small update without giving it much thought:
I'm planning on making a gameplay video of the watchtower scenario; it's old now but it does show some scenario tech that I never made a video for. It also has the pathing speedups and large unit count that we didn't have before the last video (which was 8 months ago or something crazy).
We've been tweaking game parameters and class mechanics pretty wildly. A few 'features' are totally cut out at the moment, to see how the game plays without them (pressure/engagement speed). We're playing with unit count, overall speed, number of abilities, comboing maneuvers and actions, etc.
We have a system for making things easily, so I guess it's time to play with it :p
But mostly I'm working on the new terrain engine. It's complicated. I'll do a post on it soon as its integrated into the actual game.
Video soon, I hope :)
I'm planning on making a gameplay video of the watchtower scenario; it's old now but it does show some scenario tech that I never made a video for. It also has the pathing speedups and large unit count that we didn't have before the last video (which was 8 months ago or something crazy).
We've been tweaking game parameters and class mechanics pretty wildly. A few 'features' are totally cut out at the moment, to see how the game plays without them (pressure/engagement speed). We're playing with unit count, overall speed, number of abilities, comboing maneuvers and actions, etc.
We have a system for making things easily, so I guess it's time to play with it :p
But mostly I'm working on the new terrain engine. It's complicated. I'll do a post on it soon as its integrated into the actual game.
Video soon, I hope :)
Sunday, January 6, 2013
Thursday, November 15, 2012
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:
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:
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.
The second path was from b to i:
The third path was from c to h:
This bit of inconsistency result in some confusion when the breaking query fires, from c to f:
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.
Friday, October 12, 2012
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 :)
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 :)
Saturday, October 6, 2012
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 :)
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 :)
Subscribe to:
Posts (Atom)