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