I concluded the last log with a paragraph about how I planned to continue integrating my GPU Bullet System into ShipBasher by establishing round-trip communication between CPU-based physics code and a compute shader running on my GPU for bulk processing of bullets. As of now I've finally achieved this as well as uncovered and fixed some shocking bugs. The path here was quite a saga, so I shall recount it in parts.
Several years ago I started playing EVE Online and have gone back and forth between active play and long breaks ever since. I love many facets of the game and it's probably little surprise that it's one of the inspirations guiding my development of ShipBasher, both aesthetically and mechanically.
Because EVE Online runs on a single massive server cluster that has to handle tens of thousands of concurrent active players at times, there's no budget for careful, precise physics calculations when big swarms of ships start yeeting clouds of bullets at each other. As far as my research has led me to understand, the server instead abstracts away all the bullet motion and simply treats every ship as a sphere - a shape that can be fully defined with only four numbers, those being its position in each of three dimensions and its radius. With this knowledge, the server can get a fairly decent approximation of the ability of one ship in one place to damage a ship of a given size in some other place. Whenever a weapon fires, it crunches these numbers and a few others and determines what happens - all further detail is just visual effects.
All those little red, orange, and blue squares are indicators of player's ships. One can see the need for performance optimization.
I don't intend to approximate this roughly in ShipBasher, but I saw great potential in the idea of treating each ship as a simple sphere for coarse collision detection. I realized I could have every ship compute how big a sphere would fully enclose it, tell the GPU Bullet System what that value is, and thereby enable that system to easily differentiate between bullets near enough to a ship to be likely to touch it and bullets adrift in space unlikely to be touching anything. Presumably, most of the time the bullets about to hit things will be a minority of all the bullets that exist (since there's a lot more space not inside a ship than there is inside a ship in most circumstances), so if I can narrow those down and only do physics calculations for those, I can support much larger quantities of bullets without a much larger performance impact. The first step to doing this, of course, is to get those bounding spheres, which, like many things in programming, proved more complicated than it sounds.
Modules consist, in the game engine, of combinations of physical objects and visual objects, which don't necessarily (and usually don't) exactly match in shape or size. Most visual objects are "meshes," collections of 3D vertices connected with triangles, and most physical objects are "colliders," which are sets of equations that define geometric shapes and are invisible, but important for running simulations of solid objects. Calculating the exact radius of a collider is usually fairly simple, but requires a different strategy for every given type of collider that might exist in the finished game, and calculating the radius of a mesh is conceptually simple but very tedious. Fortunately, one thing that colliders and meshes have in common is that the engine uses axis-aligned bounding boxes as representations of their rough sizes. I could have used these instead of spheres, but it would have added slightly more work for the compute shader, and every bit of optimization counts in a system that might have to handle hundreds of thousands of bullets at once.
I investigated a few strategies for converting bounding boxes into approximate spheres and eventually settled on iterating through every collider and renderer (a visual object that has a bounding box - usually a mesh) attached to a given ship and, based on its relative position and the radius of its bounding box, incrementally calculating an approximate radius for the whole ship. This technique should be mathematically guaranteed to never give a result smaller than the "true" radius of the ship, but typically does overestimate slightly. Fortunately for my purposes, the smaller each individual module is relative to the ship, the more precise the overall calculation ends up being.
I didn't actually need to include renderers at this point, but later on I expect to reuse the radius value in a few other parts of the game, and I want players to see a radius that is consistent with how big the ship actually appears to be.
With that part out of the way for now, I changed tack and started getting the GPU Bullet System ready to deal with spheres. I reprogrammed the compute shader to use a new buffer of spheres in addition to its existing buffer of bullets, and as a temporary debugging feature I rigged the bullet management script to generate some random spheres to feed into this new buffer alongside some random bullets (since the existing turrets are only able to target things like ships and modules, not imaginary spheres):
Not to be an overachiever, I didn't bother building a fancy visualization for the spheres, since they were temporary after all. I just had the engine draw some random debug lines based on the centers and radii of the spheres to give a vague sense of where their boundaries were. Also visible here are the debug lines and bullets from the old turrets, which I didn't bother disabling, but more importantly there are the white bullets spewing out in random directions. Note how most are radiating out from the origin, but a few are traveling other directions - these have struck a sphere and "bounced" (I put it in quotes because I didn't bother with actual reflection vector math and just made a crude approximation) off. Collision detection, hooray!
Next all I had to do was feed the compute shader with the real bounding spheres from the ships' actual positions and radii:
I had the wherewithal to turn off the starfield background at this point so the important things could be seen clearly. At left is the GPU Bullet System as it was before, flinging yellow dots into space to look pretty but do nothing else. At right is the new version. The target ship in the distance (as well as the testing ship in the foreground) has calculated its bounding sphere and added it to the sphere buffer as a 4D vector, in which the first three values are the position and the last value is the radius. Due to the way GPUs are built to deal with matrices and four-component colors (red, green, blue, and an "alpha" value typically used for opacity), this format is easy to implement and process.
The compute shader at this point had two tasks for each bullet: move it forward a bit based on its velocity if it is active, and go through all the bounding spheres to see if the bullet is inside one of them. This does mean that every compute thread is going to run through the full collection of all bounding spheres, as I haven't implemented any optimizations such as spatial partitioning, but considering that I don't expect there to be a huge number of ships active at once, I decided that a little inefficiency at this particular stage was a lesser evil than the extra complexity of some algorithm for picking and choosing which spheres to check. In fact, unless there actually are a huge number of ships, I suspect that my choice was in fact the optimal one here.
Once the compute shader had run, all of the active bullets had advanced forward and any bullets that touched a ship's bounding sphere had been detected. For the moment I simply had the GPU change their velocities to point directly away from the bounding sphere (that "bounce" I described above) so I could see that it was working, but all of the bullets were still confined to the realm of the GPU. They made it onto the screen, but no information about what happened to them made it back into the rest of my codebase, meaning that ships didn't know they'd been hit (nor did anything else, even the bullet manager script) and thus couldn't be damaged or otherwise affected. My next task (and the subject of the next entry to come) was thus to establish a line of communication from the compute shader back to the CPU and the scripts it was running.
No comments:
Post a Comment