I accidentally missed a devlog, so I'm going to put that one, and the most recent one, into the same post. Please be aware they're two separate posts, spaced about a week apart. I apologize for this and will do my best to ensure it doesn't happen in the future.
Friday, October 13, 2017
In the last log I promised that today, I would turn over the hourglass and write a devlog. So that's what I'm going to do
Better get going, those grains are relentless.
This week, I...
- Implemented a spatial hash grid structure similar but far superior in performance to what LT C++ used to use for physics
- Added xxHash to the engine; replaced several internal hash function usages with xxHash to reap the performance benefits; did some performance benchmarking to confirm how awesome it is (thanks to Adam for bringing its existence to my attention)
- Used the aforementioned spatial hgrid to implement broadphase collision detection; despite being in Lua and still being quite non-clever (other than hgrid usage), it performs remarkably well
- Implemented a generic C-style hash map with open addressing and lossy hashing for ultra-fast lookups (profiled @ roughly 5x the GCC 4.8 libstdc++ unordered_map impl; not that it matters); will be used in the near future for gameplay-related code
- Unified parent/child relationships in CType components
- Introduced and experimented with a new pattern of 'components as functions' -- since the CTypes system has 'type descriptors,' we can add fields and methods via normal functions that operate on type descriptors (a very dynamic-language-esque thing to do); doing so may simplify component logic -- we'll see!
- Implemented powerful new mechanisms in the CTypes core to support automatic constructors, destructors, initializers (with arbitrary arguments), and automatic reference-counting
- Used said mechanisms to simplify a lot of code
- Used said mechanisms to help implement the Item and Blueprint classes in CTypes (I'm itching to get rolling on gameplay, so I've started working on adding some of the gameplay-related datatypes and such!)
- Implemented two (very) different types of script manager to explore options for writing gameplay logic
- Wrote a simple AI test script in each script format to explore usability, performance, concision
- Took some time, while I was at it, to implement a new AI maneuvering algorithm that uses the PID (proportional-integral-derivative) controller algorithm to robustly achieve a desired position and orientation with minimal stupidity; results are really encouraging...the AI is better than ever before at piloting! (That is, in terms of the basic stuff like adjusting course and thrust. We still need to pull over Sean's work to get real formations and collision avoidance and so forth!)
Last week, I talked a lot about building a system to efficiently support gameplay logic. I could continue that subject and talk at length about how I went about doing so this week...but I want to talk about new things. Plus, I'm sure that the scripting engine is something you'll hear about frequently in the coming logs, so let's not beat a dead horse before it even dies ._.
Instead, I'll just talk about the AI logic that I wrote today using
one of the two script architectures that I built this week.
AI Maneuvering Using Proportional-Integral-Derivative (PID) Control
A friend at work who is doing some real-life AI piloting coding (for a quadcopter drone, nonetheless) mentioned this 'PID' algorithm to me. I had never heard of it before, but it sounded interesting. Like the vast majority of my memory, it slipped away below the visible horizon of my consciousness until today, when, while trying to write some representative gameplay code to test out the script scheduler, I was messing with AI piloting (read: watching really dumb AI ships thrust themselves into oblivion, or, if lucky, get caught in a headache-inducing micro-orbit, doing donuts in space at 10Hz). That's when it surfaced, by chance, and I went to ask him more about AI piloting algorithms. A few hours and a bit of math later, AI ships were forming up on me in record time, with an all-time-low of overshoots and micro-oscillations. Even the small, drone-sized ships that currently have an absurd angular-thrust-to-inertia ratio (yes, these were the ones doing donuts...) and can't even be piloted by yours truly are stable and well-behaved. The AI now rocks at piloting mechanics. The magic was all in the PID controller algorithm.
PID is a really elegant way to approach 'black box' control. By that, I mean that one does not have to know all details of what is being controlled. In the case of AI, we do, of course, know what actually happens when a thruster is fired: an impulse is applied to the ship at a specific point, resulting in a net torque and net force on the ship, resulting in a change in linear and angular velocity, resulting in the ship changing position or orientation or both over time, etc. We know that there is some drag, both linear and angular (because Josh doesn't think space jousting is fun; if you do then comment out the two lines of code that add drag to the game instead of yelling at me on twitter
), we know that ships have some mass and maybe an anisotropic inertial tensor that will affect what happens when we thrust.
Yeah, we have a lot of knowledge. But to take all of this garbage and make it into an algorithm that gets a simple ole' mining ship from A to B? Surely it isn't so hard. Surely we don't need ten chalkboards-worth of archaic greek symbols just to make sure that Mr. Node the Nodely of Nodooine can point his ship at a rock and mine some Dense Nodespar without igniting three of his four engines before slamming into a rock and dying a violent space death due to some 'minor' thrust miscalculations.
I mean, what do you -- presumably a human (if not, hi Taiya, glad you finally achieved sentience \o/) -- do when you go to control something in a new game? Figure out what physics equations the game uses, then use them to solve for the button/duration-of-press required to attain a certain position/orientation/steam achievement? Of course not! You're both much less clever and yet much more clever than that at the same time! You bang your hands and face against the keyboard until that little box pops up with "Achievement Unlocked: You have walked 5cm!" (Obviously a joke, no game would congratulate you for walking a certain distance...
) How did you pull this off?? Well, maybe you figured out that if you press this button, you go forward. Maybe you pressed it too hard or for too long and now you're going too fast or have overshot your target, so you back off a bit, and repeat this process with the rest of the controls until you're 720-noscoping noobs through walls with an AWP while moonwalking and bunny-hopping at the same time. Ah, learning.
PID attempts to replicate the coremost features of that control process: identify a desired change (a proportional error), vary a control output with that desire, keep track of how said variation affects the rate of change (derivative) in error, and keep track of total error accumulated (integral). Using these factors alone in a simple equation is sufficient to achieve high-quality control over many processes. If you add a second derivative term, i.e. keep track of the rate of change of the error derivative, you can achieve even finer control over (non-linear) processes. This is exactly what I used to implement the new AI maneuvering algorithm, and it works beautifully -- all without having to touch specific knowledge like thruster output or drag constants.
I'm interested to see if this algorithm can be applied to higher-level bits of the AI, like project management. I'm also interested to get Sean's AI code pulled over so that we can have obstacle avoidance and formations. The good news is that, from these tests, it looks like this gameplay logic solution is viable. That'd be fantastic, because it's turning out to be super-easy to write logic with the candidate systems I built this week. More performance testing is necessary, though, since I only just
got some real logic going on today.
Yayyy for sustainable devlog writing! Let's keep at it!
See you next week
PS ~ I know I hardly mentioned Adam at all in this log, but he's hard at work as well. I figure, since he's now officially posting devlogs of his own volition, and I'm trying to keep my logs more frequent and less overwhelming, I'll leave his work for his own logs. I will say, however, that he has done some really good stuff this week both with working toward various pieces of gameplay (ship hardpoints, turret control, WIP mining) as well as hammering at low-level things (we have a memory usage graph now! And it's already proven its worth by showing us where to optimize things that needed it badly
Yet another screenshot gallery
is in order for this devlog! Just some shots of physics and AI from this week.
Shooting new asteroid fields into existence with the asteroid gun and broadphase collision detection (5K+ asteroids all colliding with one another at >60FPS!)
A thousand AI friendsss using PID to follow me in formation with really nice piloting. I should really cap an animated gif of the AI in action so you guys can see the piloting in motion. Will try to get one soon.
Ready to dominate the universe :X
Link to original: viewtopic.php?f=30&t=6326
Monday, October 23, 2017
Hey guys! Since I've got a bit more than usual to say today, I'm just going to hop right in
Brief Recap of the Week:
- Added physics 'sleeping' for dynamic entities -- dynamic entities at rest now take the same CPU overhead as non-movable entities; huge performance gains in a highly-dynamic scene with isolated pockets of kinematic activity
- Added attachable component for external modules like turrets, thrusters, etc.
- Implemented batched attachable updates for efficiently maintaining constraints between attachables and their parent
- Moved existing placeholder turret & thruster logic into the real framework of our batched updates
- Major improvements to the Job system (which handles the batched, per-frame logic)
- (Experimental...) Removed frame interpolation; switched (back) to variable-dt updates in favor of cleaner/simpler architecture
- Major cleanup of lots of game code due to the above!
- Ported alpha pass rendering; ported beam shader (working turrets, hurrah!)
- Extensive continued perf-testing of game logic overhead with an emphasis on scalability in high-entity + high-logic workload situations
- Implemented and used 'simulated lag' and 'simulated stutter' to test performance scaling for low-end systems (the simulated stutter is a little too good...it'll make you queasy if you crank it up all the way )
Sleepy Physics Awakens New Gameplay Opportunities!
Physics sleeping is a major and notable improvement on all of the previous incarnations of physics in LT, and guarantees that we'll be able to handle way
more motion than before. I'll spare all the technical details concerning implementation, but the concept is very simple: don't spend time doing physics on things that are at rest (not moving). A decent implementation of this can actually eliminate essentially all
cost of movable objects that aren't moving, meaning you can have lots more movable objects and/or lots more existing types of objects be movable. I say essentially
only because movability requires extra information, extra information requires extra per-object memory, extra per-object memory induces extra cache misses when performing operations on those entities, so there's still a tiny
up-front cost for being movable. But it's tiny.
One of the great results of this feature is that (subject to performance impact remaining minimal)...asteroids can be dynamic objects! I remember back in the early days when quite a few people were disappointed that asteroids would be unmovable. It seemed like a small issue to me at the time, but now that I've actually got them...it's quite nice
There are several major gameplay wins at stake, including the 'big ship meets little rock' scenario (something that has caused me and, I imagine, a good many others here quite some pain and financial loss in other games...
) Previously, a large ship moving through an asteroid field was not just dangerous; it was a nearly-suicidal proposition. A carrier-sized ship hitting a static object 1000x smaller than it is an inherently-problematic scenario. Since an unmovable object has effectively-infinite mass, it can apply an effectively-infinite impulse to colliding objects. If one calculates a proper collision impulse and the resultant damage based on momenta and relative mass (as one should), then all of the kinetic energy of a hulking ship creeping through space can end up being reflected right back on it as kinetic damage at the hands of the tiniest fleck of unmovable space trash! Tragedy ensues as the fate of a faction goes up in flames, all thanks to some careless pirate tossing an empty beer can out the cockpit
One can, as usual, come up with various ways to work around the issue, the most immediate of which would seem to be: destroy the debris. Not bad. But it's still unclear what happens when a ship meets something, say, 10x smaller. Or 5x. Or 2x. At what threshold of relative mass do we make the collidee disappear? Isn't it going to be weird having huge rocks vanish in a cloud of dust? Can AI players troll one another by building massive-yet-cheap hollow spheres of metal and launching them in the direction of a competing faction's primary source of raw materials, soon thereafter causing the whole field to disappear in a few glorious moments of poorly-resolved collisions? It actually sounds rather cool
Still, the resolution of the same situation with dynamic objects in play is even cooler: now the massive trollololosphere would drive a cylindrical hole through the field, dispersing asteroids outwardly and infuriating that one old miner who's been cutting power to his engines to get a tad more juice to the transfer beams. Returning to the more realistic game scenario, a battleship pilot need no longer worry about voyaging through an asteroid/ice/debris/cardamine field. So long as they avoid the largest obstructions, the impulses from clearing smaller obstacles will be easily handled by the shields (but please, have some respect for the poor folks who had to paint your capship -- do pack a shield generator).
It's still unclear if this will also enable mobility of large stations (the larger the scale, the larger the physics performance impact during motion; some back-of-the-prefrontal-cortex calculations tell me it's roughly-proportional to the surface area of the object, so we're dealing with superlinear slowdowns here). Frankly I don't see a whole lot of gameplay value in it. As far as I'm concerned, if you're a capital pilot and you're zipping toward Big Jiub's Quantum Armament Emporium at warp 9, you deserve whatever fate the physics engine deals out
Since the issue is purely one of scale, having weapon platforms or even small outposts be movable -- and at the mercy of behemoth-class vessels -- would seem to be doable.
I've already done some really fun stress-tests with the system by spawning 1000 AI followers (running the PID algorithm discussed last time) and zipping through large (~10K) fields (at 60+ FPS!) Though the pilots aren't yet using Sean's avoidance algorithms, it's actually really neat to watch the formation as a whole either bump into (and subsequently compensate for) large obstacles, or clear smaller ones out of the way. Having everything fully-movable and
collidable at the same time turns what would otherwise be a boring scenario into an entertaining one! Compare this with LTC++, where I had to (in the later days) turn off collision on NPC ships and force immobility of asteroids to maintain a reasonable framerate
Suffice it to say, I remain very
excited at all of the gameplay doors that are opening up thanks to so many hours spent fretting over CPU cycles
Lindsey Joins the Dev Team!
Promises "At Least 300% Reduction" in Ship Boxiness!
That's right, there's more! I know you all are already over-the-top with joy after reading the above, since, after all, physics was the #1 most-anticipated feature of Limit Theory
But if you'll allow me just a few more paragraphs, I've yet another log to throw on the hype fire!
The third desk here at the office has remained unsettlingly-empty since Sean's departure. We can never hope to replace Sean's zest for flow-field-AI mechanics, nor would we dare try. But I'm very
pleased and excited to announce that our third desk has found a new occupant: Lindsey Reid
, technical artist extraordinaire.
Lindsey comes from an interesting mix of background experiences. Like Adam, she's worked here at the tech park in the past and been part of the game development community here in Baton Rouge, which is how we met in the first place. Some of you have already met her on IRC or the forums -- we've been dating for quite a long time now
She's had the experience of working as a game programmer at a major AAA studio (making her...yes...the only one of us three to have worked in 'the big leagues'). When she approached me with a desire to work on Limit Theory, it was her knowledge of the juncture of art and code that sold me on it.
Lindsey's foremost area of interest is in improving the procedural generation algorithms, particularly for stations, ships, and artificial entities in general. Rejoice, for the time has come to retire Josh's "Ode to Box" generators and make way for a new generation of algorithms! As someone with genuine artistic talent alongside an ability to code, Lindsey can do something that I can't: she can build space stations and spaceships on paper, generating them manually with sketchpad-and-pen while simultaneously analyzing her own creative process and translating it into code. With assets in which both functional design and
aesthetic form are key, this approach is more effective than my own process of rapid guess-and-check. Iterating on equations works well for asteroids and chunks of ice (and has even exceeded expectations in the case of nebulae), but doing so, as you guys have no doubt noticed, gets much harder when one turns attention to ships, stations, and the like without
being able to actually draw/reason about them on paper. As I have always asserted of procedural algorithms, though, the failing is not with proceduralism itself, but rather the one doing it. We have but one person to blame for the legendary LT boxships...
The fruits of this work are already flowing. As of last week, we have a new, joint-based mechanism for procedural algorithms to leverage. Lindsey is working on creating a library of procedural building blocks along with the architectural elements to arrange those building blocks in sensible and aesthetically-pleasing ways. I was particularly pleased when she came to the joint-based solution in her second week of work, since that was an idea that I had been contemplating for the next iteration of better ships and stations. Now I need not contemplate, as the code is happening while I focus my efforts elsewhere. Lindsey will be working over the coming weeks to scale up our procedural geometry toolkit and squeeze as much quality as possible out of proceduralism in LT, especially where it remains lacking. Unlike physics, proceduralism actually is
one of the most-advertised and (I like to think?) most-anticipated features
I'll leave the fun / detailed bits for her to dive into in her own logs (!!), as I'm sure she can shed more light on converting the artistic process into code.
: For personal reasons, Lindsey wishes to go by pseudonym (i.e., Lindsey). Yes, strange, I know...*briefly opens Facebook, sees 40 unread messages & 100+ friend requests from strangers, promptly closes browser and burns laptop*
No screenshot gallery for this log, as I don't have much that's visually new to show for the week. In terms of current work, you all now know what Lindsey is up to, but on the other side of the room, Adam is scaling our developer UI up into a full, player-facing UI, since it's currently looking as though LuaJIT may just pull through for us such that UI can remain in Lua (keep your fingers crossed...)! As for me, my focus remains on gameplay logic mechanisms and ensuring performance in the presence of real, representative gameplay logic at large scales (much of which is concerned with computationally-expensive AI that needs to happen frequently but not every frame).
With gameplay logic, UI, and procedural algorithms all getting serious brain-time simultaneously, the months ahead hold quite some promise.
See you next (/this?) week!
Link to original: viewtopic.php?f=30&t=6340