Physics

FriendlyFire

So I’ve been discussing with w0d on the topic of physics. We both agreed that perhaps we should stop reinventing the wheel and use an existing physics library instead of making our own stuff.

This has led me to look into a proper physics library. My first stop was Bullet, a popular physics library written in C/C++. Turns out it also has a C# wrapper:
http://code.google.com/p/bulletsharp/
which can be integrated with SlimMath:
http://code.google.com/p/slimmath/
which could replace our hacked together Vector/Matrix/Quaternion stuff.

If we were to adopt both of those, we’d get solid and fast collision detection and physically accurate simulation of objects like ships, which would also solve the issues we’ve been having with simulating NPC movement.

I know it’s a big thing to integrate but coding all of this on our own is perhaps even worse… so what do you guys think?

Schmackbolzen

I am not sure where you are heading with this. Is it meant to be for NPCs only? I guess it could be usefully for accurate hit detection, but since there is always a discrepancy between client and server simulation, I am not sure whether it will be playable.

For now I just would let NPCs evade targets (or fly through) as it is with the original server.

FriendlyFire

Alright, and how do you make NPCs evade targets? Do you have code for making the NPCs move around in a 3D space with accurate torque, inertia and damping simulation?

Schmackbolzen

I need the same stuff for my own engine, where I have a real physics engine (Newton), so at some point I will

Checking whether to evade would be a sphere check (E.g. simple check whether both radii are too close). The other stuff is not that easy, but I will need to solve it, too. Even asked a physics student about it who also does simulations and he said he didn’t have a solution himself.

The problem is, you probably will have to solve this even if you use a real physics engine.

Edit: Thinking about it, I had written a very simple physics simulation based on v=at and s=vt (without collision) and that should do the job. You can fly curves and lines with (e.g. just set some points around it). At least that would work and at some point we still can switch to a real physics engine. I don’t think the NPCs now have real mass etc, but that could also be integrated.

FriendlyFire

The NPCs in vanilla FL use the exact same data as players: they have inertia, torque and damping, all in three axes with limits on each axis. You can’t simplify this to v=a*t and expect things to work, and doing this in 3D is a lot more complicated than you seem to think.

Bullet, meanwhile, has all of this functionality already, and in a much more stable and much faster form than you’d be able to code in a few weeks/months.

Schmackbolzen

Actually I was under the impression they don’t use that. Like a rather simple simulation. As soon as you include these factors it gets way more complicated and even if you use a physics engine you still will have to calculate the forces needed to move the mass. So it actually gets harder rather than easier. If you have a solution to that problem I would be very interested to hear it.

Schmackbolzen

I have asked one of our “Simulation Students” how they solve their stuff and got a method that should work. Will have to test it, though. Basically instead of finding the force to fly a path they project the path and calculate the forces for every timestep to minimize the error. This is way easier than the other way around.

w0dk4

I dont think that’s really the right direction to “solve” this. Here is a scenario:

An NPC wants to fly to a waypoint. It will need to have a few basic functionalities to complete the task:

turn the ship into the right direction
when still more away than xx m from waypoint, full throttle
when closer than xx m from waypoint, reduce throttle appropriately

Note, FL is based on fluid dynamics (with drag), space in FL is not really space but rather underwater or something similar. If you would remove drag via the INI files (aka “real” space physics), I’m very certain that the FL AI would fuck up big time, because it expects drag. In real physics, ships would have to turn before reaching the waypoint to get their velocity to zero again, but I dont think FL is that sophisticated in it’s AI, so it will simply reduce throttle. We can use the same shortcuts here.

/edit:

Also Im very certain that the FL AI does not compute paths for the npcs. I think it uses the same mechanic as the “GoTo” client mechanic, it will simply fly around objects it encounters on the way. In combat, it appears to use simple maneuvers, like “fleeing” (fly in a direction away from enemy), engaging (face enemy and fire), evading (fly in a semi-random fashion and turn every XX m).
Of course we could come up with a completely new AI with more complicated path calculations and what not, but for now I dont see the use of that. We need state machines for the npcs that decide the ships control parameters frame by frame (or every n frames, depending on the control type).

/edit2:

I’m aware that the FL AI actually computes “high level” paths, but this is very likely done with the shortest path calculation that is also used on the client. And this in turn is again the simple “fly to waypoint” scenario.

FriendlyFire

The complicated bit isn’t the high level control, it’s the low level. I invite you to just make an NPC move in a believable manner with proper throttle control, proper turning, all with force, torque, inertia and drag simulation. We have to simulate this otherwise NPCs won’t move right (not the proper manoeuvrability).

w0dk4

Ya, I was responding to “Basically instead of finding the force to fly a path they project the path and calculate the forces for every timestep to minimize the error. This is way easier than the other way around.” if that wasnt clear btw

Schmackbolzen

Well, since they also use this for robotics control (all with n axes etc) this works under real conditions. That’s all I can say. I will try to implement it in my engine as soon as I find the time. He also said the advantage is that it reacts good to disturbances.

w0dk4

Well, if you get something workable in your engine (C++?), then that would be great, but for the time being I dont think any of us has the time to reinvent the wheel on physics.

Also, a proper physics engine gets us loads of features for free (collisions, etc…)

Schmackbolzen

I actually am talking about using a physics engine. As soon as you want to include torque, inertia etc a simple simulation gets quite complex. I think you should try to work with a physics engine to see what I mean. It doesn’t magically solve everything for you. Quite the opposite. Now you can solve all the equations, but since they all work on the force level, you have to calculate every needed force. And that’s what I was getting at all the time.

Btw. my engine is of course written in Freepascal

FriendlyFire

I’d just like to bump this. The primary reason I and w0d are working on this is so we can use a good, modern and fast server for Freeworlds instead of the hacked together mess that is FLServer with all our stuff piled on top.

We cannot afford to wait around for years so that you get your engine working, Schmack. We need something reliable and we need it soon. This is why we’d considered using an existing, proven engine instead.

I’d just like to know whether you guys are even considering the fact that if we don’t release something within the next few months, all this work will largely be rendered void by newer, better games coming out very soon? If we want to make this work and make this be worth something, we need to kick into gear. There are many things to do yet, but we all know that the two core things are collisions and NPCs. If we have both, we have something we can show to the wider world.

So, what do we do now?

Schmackbolzen

I think you misunderstood. I only mentioned my engine, because I already have a working physics engine included (actually I have used two with it, now it is Newton, before that it was ODE). I don’t expect it to ever finish, at least not with the very sporadic time investment I am able to do.

I rather tried to explain the problems I see, which is why I suggested to use a rather simple solution. If you want server side physics and an accurate simulation, a physics engine is most probably the easiest solution, although you still have to calculate the factors of the equations. Which is all what physics engines do. You give the values, the solver gives you the solution.

Meaning if you want to let the AI fly a curve, you will have to calculate the forces for each timestep. I guess you could trick and just change rotation etc, but then you would remove the other forces out of the equation, losing the advantage of the physics engine.

I hope that cleared most of the things up.

FriendlyFire

If you take a look at the Bullet API, you’ll find things like

applyTorque
applyImpulse
applyForce
setCenterOfMassTransform

Those are the elements we need. We already know what force an engine can provide, and we can interpolate it using throttle. We can also linearly interpolate torque in the same way.

By using this we gain accurate simulation of all the physics we need for free in an efficient manner. We don’t have the code to take inertia, dampening, and torque and compute movement in 3D space; do you? We can’t ignore those, so we have to have something. Libraries hide all of that nasty 3D physics work.

Likewise, we also gain collision detection in the bargain. Do you have collision detection code?

The problem here is that you’re just saying “no” without giving alternatives. Coding it ourselves is going to result in a lot of hair pulling and not much results.

Schmackbolzen

I think we are talking at cross-purposes.

I am not saying no. I first suggested to use a rather simple approach without collision, torque, inertia etc., but you did not want that. I then agreed that if you want an accurate simulation, using a physics engine is probably the easiest way, although you still have to provide the forces for each time step. I then asked one of our students how to calculate them and tried explaining that to you, which you also did not like. Since I need that for my engine, which uses a physics engine, I then said, that I will try this approach and that I think it will work.

If you think you can teach the AI flying around using a physics engine without the controller model (this is the one I described), go ahead, I would be very interested to see how that works.

FriendlyFire

You’ve not explained your method properly then because it did not appear to support inertia, torque and dampening calculations. We need a system that basically works like players fly: pick a direction to move to and point there, the ship does the rest in a way that’s accurate depending on its flight characteristics.

If you can do that with your method, then fantastic.

Schmackbolzen

That’s what I want to test. The challenge is to get the system stable. There are many algorithms in control theory and most of it is solved. As long as you don’t do to extreme corrections per time step it should work. But I don’t want it to get much complicated.

So I would try a rather simple approach like linearly increased forces and if that is to weak I go exponential (relative to the error). That should keep the ship on the calculated path, which you dynamically adapt (that would be the AI then). So the feedback control keeps it on path an the AI reacts to obstacles, new goals etc and changes it accordingly. Having the ship e.g always vertical to the path would also be the job of the controller.

Dampening would be some sort of max speed, which you also could include, meaning after a certain velocity in direction of the path no speed increase is done, only course corrections.

Schmackbolzen

Just to give an update: I am currently learning for my exams and thus couldn’t do much. I have finished the theory (amongst other things cubic bezier curves for path and I got a simple way to calculate the length of the curve, which you need) and am still confident, that it will work. I will post a video of it as soon as I got it working. But feel free to test it yourselves, if you got the time for it.