Jump to content

  • Log In with Google      Sign In   
  • Create Account

sheep19

Member Since 20 Jul 2007
Offline Last Active Jun 13 2016 01:40 PM

#5260511 Using a physics engine on the server

Posted by sheep19 on 04 November 2015 - 09:50 AM

If you are behind (sending commands too late) you need to immediately catch up, which means stepping the simulation several times without rendering. This will glitch a little bit, but hopefully only happens at most once. If you are ahead (sending commands too early, causing unnecessary latency) you can smoothly drop the step delta. Say, if you're ahead by X steps, you subtract (X / 10) steps from the local offset (which means you step simulation slower / less frequently for a little bit.) (Also, you have to keep the time -> server ticks offset variable as a double or fraction)

Finally, you want some "desired" set of jitter buffering. It may be OK to be between 0-4 steps ahead of the server, for example, because transmission times will jump around a little bit. You may even want to count how many times you have to adjust the clock (either direction) and slowly increasae the acceptable jitter size if you have to adjust it often, to compensate.

 

Hello. I'd like to thank for your help. I have implemented what has been discussed in this thread, and the results are much better than before!

The player now is almost exactly where he should by the time the update packet is received! (It's not exactly 100% correct, but it's barely noticeable).

 

One thing remains to do. Currently the client completely ignores the tick diff reported by the server and just adds +2 to each input's tick (+2 is because that's what I noticed was the best with the server running on localhost).

By setting an artificial delay to my network, the results change, because the tick diff changes. With 50 milliseconds delay, the client gets this: http://pastebin.com/kNu9RL1U

 

As you can see, it changes just a bit when it does.

Here is my idea: Use an average of the last X tick differences (updated each frame) and round to the nearest integer. But what would be a good value for X? Probably it should be a small number - I was thinking of maybe 5.




#5258859 Using a physics engine on the server

Posted by sheep19 on 24 October 2015 - 01:59 PM

"current tick" in each packet is common. "current tick rate" is not very useful, because the idea is that the tick rate is exactly the same on client and server -- 60 times per second (or whatever you choose.)

Often it's useful to have the server send to the client "this is how off you are in your ticks" -- i e, the client sends "this command is for tick X" and the server sends back "your command arrived Y ticks early/late." The client can then adjust its compensation any way it sees fit. Maybe adjust by a third downwards if it's early (to reduce latency) and adjust by the full amount, limited to a value of 10 ticks per adjustment, if it's late.
If you use this to also tell the client what the current tick is when the client late-joins, that one-time adjustment of course needs to potentially be big.

 

 

Alright, so I'm in the process of doing what has been discussed here.

  • Clients include the target tick in their (input) packets.
  • Server includes tick difference for each state update sent to clients.

 

The clients will use that difference to appropriately set the target tick:

targetTick = currentTick + tickDifference (I haven't implemented this part yet).

Where targetTick will be sent to the server (like you said, send for the future).

 

For now, clients send their currentTick.

 

On the client, when a new state from the server is received, I print the tick difference. Here are the results: http://pastebin.com/dh7GFFcq

In the first few frames, the tick difference is 1 and increases up to 20~ until the first input from the client is received by the server.

 

So my question is, how does the client use tick difference information? Should it just calculate the targetTick using the last value of tickDifference? The value won't be correct until the server processes the 1st input from the client, but this will be corrected really soon.

 

====

Also, another question regarding this. With this approach, the client sends input "for the future" to the server. The inputs should arrive exactly at that tick and be processed by the server.

Let's say that the client sends a input with targetTick = 5. But due to a lag spike, the server receives it at server tick = 7. But now, at server tick = 7, the server has 3 inputs from that clients (because inputs are received in order by my own protocol).

So, in that update loop at tick = 7, the server should process all 3 inputs at once, correct?




#5258731 Using a physics engine on the server

Posted by sheep19 on 23 October 2015 - 02:41 PM

"current tick" in each packet is common. "current tick rate" is not very useful, because the idea is that the tick rate is exactly the same on client and server -- 60 times per second (or whatever you choose.)

Often it's useful to have the server send to the client "this is how off you are in your ticks" -- i e, the client sends "this command is for tick X" and the server sends back "your command arrived Y ticks early/late." The client can then adjust its compensation any way it sees fit. Maybe adjust by a third downwards if it's early (to reduce latency) and adjust by the full amount, limited to a value of 10 ticks per adjustment, if it's late.
If you use this to also tell the client what the current tick is when the client late-joins, that one-time adjustment of course needs to potentially be big.

 

Yes, that's what I meant. I don't know how I wrote "tick rate" instead :P

 

So yes, it also seems easier to implement if the server tells the client the difference to each client instead of the client having to do it manually!

 

Thanks for your advice!




#5258711 Using a physics engine on the server

Posted by sheep19 on 23 October 2015 - 12:42 PM

 

But, due to latency, the server will always be ahead of the clients, right? So when the server receives an input with tick count 15 (from client A), it might actually be at _simulationTickCount 30. What does it do in that case? Furthermore, another client, B, which has more lag than client A sends his tick count 15 at 30 server tick rate... What should the server do?[/size]

 
That's why I say clients send commands for the future. If the client knows it's 6 steps away from the server, and it's currently client tick 22, the client will send a command for tick 28.

 

So the client needs to learn how many steps he is away from the server.

Would adding a current tick rate variable to client inputs and server world states suffice? The client can make the subtraction and find the answer.




#5256276 Using a physics engine on the server

Posted by sheep19 on 08 October 2015 - 02:36 PM

 

let's say the whole update() function took more than 16 ms.


Then your game is broken on that server.
An occasional timestep that takes longer might be OK, but if this happens with any frequency, then your hardware spec and software meeds mis-match.
You should at that point detect the problem, show a clear error message to the user, and end the game.

 

 

Alright. So, yes, I can assume that update() takes less than 16. If not, I'll need new hardware :)

 

So I've added this after the accumulator loop:

 

std::this_thread::sleep_for(std::chrono::microseconds(static_cast<int>((TIME_STEP - accumulator) * 1'000'0000.0f)));




#5256227 Using a physics engine on the server

Posted by sheep19 on 08 October 2015 - 10:07 AM

maybe i have missed something, but do you run physics/collision-detection only on the server, and not on the clients as well?

 

You are correct. The physics / collision-detection is only on the server. Clients buffer 2 states from the server and interpolate between them.

But this temporary, I will implement it on the client as well, after I'm done with this.

 

After reading (and hopefully understanding the article), I've modified my code to look like:

 

// === THIS CODE IS RUN ON THE SERVER ===

const float TIME_STEP = 0.016f;
                    
auto t0 = std::chrono::steady_clock::now();
auto t1 = t0;

float accumulator = 0.0f;

while (game->isRunning())
{
    auto t1 = std::chrono::steady_clock::now();
    auto frameTime = ((float)std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count()) / 1'000'000.0f; // in seconds
    t0 = t1;
    
    accumulator += frameTime;
    
    while (accumulator >= TIME_STEP)
    {
        game->update(TIME_STEP); // read client inputs and update physics accordingly
        accumulator -= TIME_STEP;
    }
}

 

 

This is Game::update(float):

 

1) read inputs for each client
2) if the player is moving set his velocity towards his looking direction, else set it to 0
3) update the (physics) world
4) sleep(TIME_STEP)

 

Is it correct this time?

 

Thanks to everyone for the help.




#5256154 Using a physics engine on the server

Posted by sheep19 on 08 October 2015 - 12:36 AM

 

At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?


Not really, for two reasons:

1) Simulation takes some time, so you really want to be using a monotonic clock to calculate "sleep until" time, rather than assume 16 ms per step.
2) This does not synchronize the clients with the servers in any way. The clients need to run the simulation at the same rate (although graphics may be faster or slower.)

Separately:

About the inputs, I don't this I can do this easily. This is because if packets are lost, the client resends them.


What does the server do, then? Wait for the input? That means any player can pause the server by simply delaying packets a bit.

In general, you don't want to stop, block, or delay anything in a smooth networked simulation. If you're worried about single packet losses, you can include the commands for the last N steps in each packet -- so, if you send packets at 30 Hz, and simulate at 60 Hz, you may include input for the last 8 steps in the packet. This will use some additional upstream bandwidth, but that's generally not noticeable, and it generally RLE compresses really well.

Being able to use the same step numbers on client and server to know "what time" you're talking about is crucial. Until you get to the same logical step rate on client and server, you'll keep having problems with physics sync.

Gaffer's article is almost exactly like the canonical game loop article; using either is fine.

 

 

1) I understand. I can subtract the time of the update() function like braindigitalis suggested.

But let's say the whole update() function took more than 16 ms. The result would be negative, so the thread wouldn't sleep at all.

Is this ok? (I don't think this will happen, as now it takes ~0.4 ms. But things might change in the future, so...)

 

Can I assume that the server's update function won't take more than 16ms?

If it takes longer, is it okay that the thread won't sleep at all?

 

 

2) Yes, this does not synchronize the clients. I will have to implement this on the client side as well.

 

No, the server's game loop does not wait for inputs. There is a separate thread that listens for inputs and when they are received they are passed to it.

 

By the way, the clients gather inputs every frame and send them every 33ms.




#5256095 Using a physics engine on the server

Posted by sheep19 on 07 October 2015 - 03:42 PM

 


At the end of update() on the server, I do
std::this_thread::sleep_for(16ms);
And then update the physics engine using the delta time from the previous frame.
Doesn't this guarantee a 60Hz simulation step rate?

 

This will only be a 60hz step rate if you subtract the time taken to run update() from the 16ms. Also if your update takes more than 16ms then, you can end up in a "spiral of death".

 

The links provided about how to fix your time step are the correct approach for these reasons and more smile.png

 

 

I didn't understand much from that article... But I found this one: http://gafferongames.com/game-physics/fix-your-timestep/

I'll work on it tomorrow.




#5256085 Using a physics engine on the server

Posted by sheep19 on 07 October 2015 - 03:02 PM

@sheep19: It sounds like you're not using a fixed simulation step rate. I believe you will, in the end, have real trouble with this. I suggest you decide on a fixed number of simulation steps per second (30? 60? 182? whatever.) Then, run the input-and-simulation at that rate on all clients and on the server. However, rendering will be run at whatever rate the client computer can keep up with. You should also send the user inputs in a given group size -- say, 60 Hz simulation, two inputs per packet, means 30 packets per second. This way, there is no difference in "how many inputs are there in a second" or "how does a player move for a particular network packet."

For more on this, check out this article: http://www.mindcontrol.org/~hplus/graphics/game_loop.html

 

At the end of update() on the server, I do

std::this_thread::sleep_for(16ms);

And then update the physics engine using the delta time from the previous frame.

Doesn't this guarantee a 60Hz simulation step rate?

 

About the inputs, I don't this I can do this easily. This is because if packets are lost, the client resends them. This would complicate things a lot. I believe what I did above is sufficient (setting the velocity based on the inputs received for that single frame).




#5255948 Using a physics engine on the server

Posted by sheep19 on 07 October 2015 - 12:12 AM

Hello again. I have come up with a solution:

// update the world
    WorldState worldState;
    for(std::size_t i = 0; i < _entities.size(); ++i)
    {
        auto& entity = _entities[i];
        auto client = _clients[i];

        entity.rigidBody->applyCentralForce(-GRAVITY);
       
        float dirX = 0.0f;
        float dirZ = 0.0f;
        bool movingForward = false;
       
        for(auto& inputState : newInputs[client->id()])
        {
            for(auto& input : inputState.inputs)
            {
                if (input.movingForward)
                {
                    movingForward = true;
                   
                    dirX += input.dir.x;
                    dirZ += input.dir.y;
                }
               
                entity.dir = input.dir;
            }
           
            _lastInputIds[client->id()] = inputState.id; // this can be optimized
        }
       
        if (movingForward)
            entity.rigidBody->setLinearVelocity(btVector3(dirX * cfg.playerSpeed(), entity.rigidBody->getLinearVelocity().y(), dirZ * cfg.playerSpeed()));
        else
            entity.rigidBody->setLinearVelocity(btVector3(0.0f, entity.rigidBody->getLinearVelocity().y(), 0.0f));
       
        worldState.addEntityData(client->id(), entity);
    }
   
    _world->stepSimulation(dt);

Essentially what I am doing is to calculate the sum of the direction vectors for all input packets and set the velocity (for that frame) based on those.

 

Example:

Let's say the player's speed is 20.

Two inputs arrive with vectors (1, 0) and (0, 1).

 

So:

dirX = 1 (1 + 0)

dirZ = 1 (0 + 1)

Speed will be set to Vector3(1, 0, 1).

 

In other words, instead of moving the player gradually, I am setting a larger velocity which has the same effect.

 

The other solution is to manually translate the player. But I don't like this because if many input packets are sent together, collisions may be skipped...




#5189186 [SDLNet] Server does not receive incoming connection from client

Posted by sheep19 on 26 October 2014 - 02:21 AM

I found the problem. On Server I should have initialized the IPaddress structure using this function:

SDLNet_ResolveHost(&ip, nullptr, 12000)

 

instead of setting the fields manually.




#5093537 Wander behaviour in 3D

Posted by sheep19 on 12 September 2013 - 07:14 AM

Hi,

 

I am implementing a Wander behaviour. In the book I am studying (AI for games), the author uses a 2.5D world.

So what he does is:

Set a circle around the player and put a target that moves on edge of the circle. Then use Seek behaviour to get to it.

 

The problem is that I am in full 3D, so I need something more than a circle. I (naturally) tried a sphere, but I want to be able to define different rotation angles (i.e I want the character to rotate more left/right thatn up/down).

 

As a sphere is defined by two angles (theta and phi), I tried to use a larger value for one of the two to see what happens. But the position of the target depends on both the two angles, so it didn't turn up like I wanted to.

 

This is what I am currently doing:

public SteeringOutput GetSteering()
	{
		SteeringOutput steering = new SteeringOutput();
		
		// set linear velocity at the direction we are moving
		steering.linearVel = character.Transform().forward;
		
		// the velocity is along this direction, at full speed
		steering.linearVel.Normalize();
		steering.linearVel *= maxAcceleration;
		
		theta += Util.RandomBinomial() * maxAngle;
		phi += Util.RandomBinomial() * maxAngle ;
		
		var pos = character.Transform().position;
		pos.x += circleRadius * Mathf.Cos(theta * Mathf.Deg2Rad) * Mathf.Sin(phi * Mathf.Deg2Rad);
		pos.y += circleRadius * Mathf.Sin(theta * Mathf.Deg2Rad) * Mathf.Sin(phi * Mathf.Deg2Rad);
		pos.z += circleRadius * Mathf.Cos(phi * Mathf.Deg2Rad);
		
		target.Transform().position = pos;
		
		steering = seek.GetSteering();
		
		return steering;
	}

What can I do to get the effect I want?

 




#5052107 Will this 3D game (in addition to some 2D) be anough for me to get a job?

Posted by sheep19 on 11 April 2013 - 08:07 AM

Unfortunately, it's not that easy for me.

 

It's not easy for anybody, and it wasn't easy for anybody, including the people who have responded to your questions.

I know, sorry if the way I written it gave a wrong impression.




#5028170 [raytracing] Surface normal on triangle sometimes has the wrong direction

Posted by sheep19 on 02 February 2013 - 03:51 PM

Out of curiosity, are you sure the winding for the vertices in each triangle of the torus is consistent (that is, verts in each triangle should all be ordered clockwise or counter-clockwise; triangles with different windings will have flipped normals)? Also, what are the values for the vertices (is there potential precision error)? There isn't anything obviously wrong from your normal calculation, which is why I'm asking these questions. This is the code for triangles I used in my own raytracer (in case it provides any inspiration):
 

// When loading triangles, I set the normal as:
// Vector3f u = t.b - t.a; (note: t is the Triangle)
// Vector3f v = t.c - t.a;
// t.normal = u.cross(v);
// t.normal.normalize();

class Triangle : public Shape
{
public:
	Vector3f a, b, c;
	Vector3f normal; // normalized

	Triangle() : Shape(Shape::E_TRIANGLE)
	{
	}

	virtual bool intersects(const Ray& ray, float& t, Vector3f& n) const
	{
		// from http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm (and Plane.intersect())
		n = normal;
		
		float num = normal.dot(a - ray.start);
		float den = normal.dot(ray.direction);
		
		if (num != 0 && den == 0)
		{
			return false;
		}
		else if (num == 0 && den == 0)
		{
			t = 0; // parallel in same plane
			return true;
		}
		else
		{
			t = num / den;
		}

		Vector3f u = b - a;
		Vector3f v = c - a;
		Vector3f w = ray.start + ray.direction * t - a;

		float uv = u.dot(v);
		float wv = w.dot(v);
		float vv = v.dot(v);
		float wu = w.dot(u);
		float uu = u.dot(u);

		float s1 = (uv * wv - vv * wu) / (uv * uv - uu * vv);
		float t1 = (uv * wu - uu * wv) / (uv * uv - uu * vv);

		return s1 >= 0 && t1 >= 0 && (s1 + t1) <= 1;
	}
};

Actually I changed the floats to doubles for everything that has to do with geometry and those black pixels disappeared! So yes, they were precision errors.




#5017868 Ray-AABB collision detection

Posted by sheep19 on 05 January 2013 - 02:46 PM

Hi. To improve the performance of my raytracer, I decided to use  Uniform Space Partitioning. Basically, I divide the world into 3D boxes, and put objects (Surfaces) inside them. When tracing a ray, I check first with the boxes and if there is a hit, I check with the Surfaces it contains.

 

The problem is, from 11 seconds I dropped to only 8 seconds. Another thing I noticed is that when the world is divided into more boxes, it takes more time to render. So this means there is a problem with my AABB-Ray collision function.

 

bool intersects(const ref Ray r) const
	{
		Vector3 n = void,						// normal
				v = void, u = void;				// vectors
		
		float t = void;
		
		// plane 0 (front)
		v = Vector3(max.x, min.y, min.z) - min;
		u = Vector3(min.x, max.y, min.z) - min;
		n = cross(v, u);
		n.normalize();
		t = dot(r.d, n);
		
		/++writeln("t0 = ", t);
		if( t > 0 )
			writeln("plane 0 intersected");
		else
			writeln("plane 0 not intersected");++/
		
		Vector3 temp = min - r.e;
		Vector3 p = r.e + r.d * dot(temp, n) / t;
		//writeln("p0 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 0\n");
			return true;
		}
		/++else
			writeln("NO 0\n");++/
		
		
		// plane 1 (right)
		v = Vector3(max.x, max.y, min.z) - Vector3(max.x, min.y, min.z);
		u = Vector3(max.x, min.y, max.z) - Vector3(max.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t1 = ", t);
		
		if( t > 0 )
			writeln("plane 1 intersected");
		else
			writeln("plane 1 not intersected");++/
		
		temp = Vector3(max.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p1 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 1\n");
			return true;
		}
		/++else
			writeln("NO 1\n");++/
		
		// plane 2 (left)
		v = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, max.y, min.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t2 = ", t);
		
		if( t > 0 )
			writeln("plane 2 intersected");
		else
			writeln("plane 2 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p2 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 2\n");
			return true;
		}
		/++else
			writeln("NO 2\n");++/
		
		// plane 3 (back)
		v = Vector3(max.x, min.y, max.z) - Vector3(min.x, min.y, max.z);
		u = Vector3(min.x, max.y, max.z) - Vector3(min.x, min.y, max.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t3 = ", t);
		
		if( t > 0 )
			writeln("plane 3 intersected");
		else
			writeln("plane 3 not intersected");++/
		
		temp = Vector3(min.x, min.y, max.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p3 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 3\n");
			return true;
		}
		/++else
			writeln("NO 3\n");++/
		
		// plane 4 (top)
		v = Vector3(min.x, max.y, max.z) - Vector3(min.x, max.y, min.z);
		u = Vector3(max.x, max.y, min.z) - Vector3(min.x, max.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t4 = ", t);
		
		if( t > 0 )
			writeln("plane 4 intersected");
		else
			writeln("plane 4 not intersected");++/
		
		temp = Vector3(min.x, max.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p4 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 4\n");
			return true;
		}
		else
			/++writeln("NO 4\n");++/
		
		// plane 5 (bottom)
		v = Vector3(max.x, min.y, min.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t5 = ", t);
		
		if( t > 0 )
			writeln("plane 5 intersected");
		else
			writeln("plane 5 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p5 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 5\n");
			return true;
		}
		/++else
			writeln("NO 5\n");++/
		
		return false;
	}

What I do is check all six planes and then if the hit point is inside the boundaries. I know this is the worst method. What's a better way to do this?

 

Please, if you suggest something, provide an explanation why it works, as that's the important thing here - I want to learn this stuff.

Thank you :)






PARTNERS