Dinosawer wrote: ↑
Sat Oct 14, 2017 1:20 am
This is not about ai logic BFett, but about getting the ai to move its ship from point a to point b. Not about determining what a and b should be in the first place, which is what you think of.
Kinda surprised Josh hadn't heard about PID before though
^ Dino is correct here. This is the lowest-of-the-low level AI we're talking about, where the AI has already figured out what position and orientation it wants to achieve, and now has to figure out how to set thrust power accordingly (the equivalent of the player pressing WASD and mousing around to control direction / using a gamepad / joystick).
And yeah, I'm really surprised I hadn't heard of it too!! It's such a great nugget of knowledge. It seems like the usage/knowledge of it is weirdly domain-specific atm (even the article talks about it heavily in terms of real-life control processes + the math analysis is noticeably light). Can't believe this hasn't come up in my studies of math or programming as a more general concept (e.g. control of dynamical systems). Wot else am I missing out on???
Damocles wrote: ↑
Sat Oct 14, 2017 6:14 am
Since the output is a single value (1 dimension), I guess the error is the lateral devition from the target point, and the controlled value is the steering angle to apply.
Then there is probably another PID for the forward/backward trust. (error is distance to target-point)
And one for up/down. (another angle error)
Those 3 PIDs control then forward, yaw and tilt trusters.
Wich makes it 9 Parameters to tune.
Yes, basically. I have six controllers running on each AI ship, corresponding to 6-DOF flight controls (right, up, forward, yaw, pitch, roll). Target thrust values are just computed from some simple vector math involving the current position/orientation and the target position/orientation. Currently I use the same constants for all params but scale linear thrust differently than angular. So effectively one set of params for linear and another for angular (makes sense IMO).
Kekasi wrote: ↑
Sat Oct 14, 2017 8:11 am
My main concern is the amount of complexity that would be needed to make this work for all ships and situations. Especially battle situations where some thruster would be destroyed.
My vote is to push all that complexity into the PID controller, and then make it as efficient as possible.
Although, currently I don't know the differences in performance and if there's a large enough drop just from PID controllers, then I agree that there needs to be a middle ground between using them and having faster custom controllers.
I can't say for sure yet because I haven't tested it, but part of my thinking was that this would be a boon for those situations as well, since PID will adjust accordingly if a thruster is destroyed. So I believe we are
pushing the complexity into the PID; it just handles complexity quite nicely without a lot of code (kind of the point).
I can say that escorts currently adjust nicely when I shoot them with big asteroids, pushing them out of formation, or make them run into large obstacles (since they're not avoiding them yet) and have to re-form. Their maneuvering looks basically ideal to me -- very responsive but still smooth, and taking all factors into account automatically. For example, if I'm going very fast and knock a forward escort out of formation in my forward direction, he'll do the smart thing, re-orienting himself in my forward direction and slowly accelerating until he naturally falls back into formation due to me catching up, by which time he's matched my velocity. This is the fastest way he could possibly get back into formation in that situation. Compare to simple algorithm that would try to come back to the current formation position (hence orienting opposite my forward direction), only to overshoot and fall behind due to having to stop and rotate back to match my forward.
We'll see how it keeps up with more and more complex situations. I'm definitely all for pushing the complexity into the PID controller. I also really like the thought that we can tune constants differently based on AI personality/skill (less skilled pilots might have a low Kd / Kp ratio, for example, causing them to oscillate sometimes instead of nailing the damping just right.)
charles wrote: ↑
Sat Oct 14, 2017 9:09 am
Do read at least the first few paragraphs of the PID article that Josh linked too. My guess is that the goal point can be a vector of a 3 dimensional location and a 3 dimensional velocity (I’m struggling to remember the precise term). With sufficient good undergrad level maths, this vector may be treated as a single value. And therefore, the PID algorithm can work on that vector as a single value. From my brief reading of the article, the PID is a very general and fairly optimal approach to control.
Righto; it's general enough that I think you could pretty easily do the vector-valued version of it, where the deriv would just be the Jacobian of the error function. I haven't done this yet, but would be interested to try it. I believe it would further increase stability especially
for angular terms, which don't have the same degree of linear independence that the thrust vectors do (in fact, thinking about it, I don't think treating the linear thrust term as a vector error would make any difference due to linear thrust being LI). YPR, OTOH, are sometimes difficult for the current PID to get right due to their nonlinearity & interdependence. I suspect converting to vector form would see nice improvements.
Hyperion wrote: ↑
Sat Oct 14, 2017 6:19 am
So what performance benefits from the xxHash are we talking about here? it's faster, but what does that ultimately mean for the game experience? Does it mean higher AI counts? Quicker load times when travelling through a wormhole while the game generates the assets in the next system? Higher framerates with lots of objects on screen? Does it mean we can now have "real" debris fields as ship modules can blow up dynamically and now you have to worry about flying chunks of dead ships slamming into your own? (Especially with the new physics and ECS able to handle oodles of objects)
Hard to say since it's such a low-level primitive. It should basically have 'relatively small' yet far-reaching implications. I was already using Murmur3 in most places, so I had a decent hash function already. But, as a concrete example, I use hash lookups as part of glyph caching to accelerate font rendering. While the cost of the hash is quite small, I still noticed several hundred microseconds in frametime reduction when I converted that to xxHash. There's currently not a lot of text being drawn compared to what you could imagine in certain game situations. So in that particular place, xxHash might save a millisecond or two when the player has lots of UI on-screen. Might sound small, but 'a millisecond or two' is massive when you consider how small of a change that is + the fact that we are on a 16ms budget.
It's used in broadphase collision (the hashgrid -- go figure!) I implemented broadphase after I already had xx available, so I don't know what the speedup is like there. But I imagine that, in this place, xxHash might buy us the ability to have, say, 20-25% more collision-enabled objects in the scene. That's just a really rough estimate based on my knowledge that the hgrid is pretty hash-intensive. Could be way off.
If we use hgrids to implement frustum culling (which is 'very likely' to happen, I would say), that may again translate to more objects that can be put on-screen, although in this case I would put the gain at less than 10% since the object rendering will outweigh the hashing by far (and the cull grid would be coarser than the broadphase phys grid). Then again, hgrids are not a normal choice for frustum culling, so we may use something more conventional like octree. We'll just have to see.
Probably no change in load times?
Real debris fields are probably already quite viable due to, as you point out, fast ECS & fast physics?
As you can tell this is a tough question for me to answer
But we should see 'nontrivial' perf gains in lots of different areas. Hard to quantify that all the way down to game experience impact.
Hyperion wrote: ↑
Sat Oct 14, 2017 6:19 am
Also, for formations, ...
Most of what I see there looks totally viable.
If you want to know if you can convert a shape to a formation, ask yourself these questions:
Viable Formation Shape Questions:
If you can answer 'yes' to any of them, then your shape can be made into a formation.
- Can you write an algorithm that, given access to a random number generator, produces a random point on the boundary of this shape?
- Can you write a parametric function f : Z -> R3 (integers to 3D space) that maps integers to points on the boundary of this shape?
- Given a point in 3D space, can you tell me, at least roughly, how close I am to the boundary of this shape?
- Can you write a function that deforms some other simple shape (like a sphere, cube, torus, etc.) into this shape? In math terms: can you give me a homeomorphism between this shape and a simpler primitive shape?
There are probably other mechanisms, those are just a few that I thought of off the top of my head and would be pretty easy to implement.
Note that I was really talking about 'surface' formations above (2-dimensional manifolds). Line/curve formations are a bit more restrictive; the easiest way to make them is to write the parametric function directly. OTOH, volume formations (e.g. a thick shell) are more-or-less trivial since if you can write a function that tells me if a point is inside the volume, then I can use rejection-sampling to build formation points.
TL;DR: fancy formations are pretty easy.