Collision detection in online games with 1000s of players

I would think that collision detection of each player is done on the client's computer ( the player's computer )....and then their position and oritentation is sent back to the server.

The only pathfinding that is going on is for monsters in the world, not for players. So the serve only has to compute paths for each monster, then move the monster and send that position to each player ( if that player is within the viscinity of the monster )

Also, there are numerous optimizations for pathfinding, so basically having 5000 players wouldn't really affect collision and pathfinding, UNLESS every single one of those players decided to congregate in the same area. Then the server might crash :-p

But surely the player can have pathfinding too, what if you click the other side of a fence, i have seen online games walk the player around the fence to the clicked position, that requires some path finding.

Doing the collision detection the the clients machine would make sense if it wasnt for the cheating aspect. What, for example, is stopping someone from just sending the position change packet to the server from a custom app, and making the character appear to walk through the wall on everone elses client?

Quote:

Original post by quant But surely the player can have pathfinding too, what if you click the other side of a fence, i have seen online games walk the player around the fence to the clicked position, that requires some path finding.

Well if the player has pathfinding, that can be computed on his machine as well. There's no need to have the server do it.

Quote:

Doing the collision detection the the clients machine would make sense if it wasnt for the cheating aspect. What, for example, is stopping someone from just sending the position change packet to the server from a custom app, and making the character appear to walk through the wall on everone elses client?

Well the custom app would have to be sending a false position, since again, all the collision detection for the player is done on the client's computer. Although, some games with a minimum amount of players ( Halo, Counter strike ), will do collision on the server AND the client to make sure everything is synchornized.

Quote:

I would think that collision detection of each player is done on the client's computer

I can imagine people running through walls and things like that :P

I think making collision detection client side would be very cheating prone, instead, server could use some type of space subdivision to reduce collision tests to an acceptable level, couldn it?

As for the path finding for the players, I can't imagine any way of cheating it and taking any advantage, so it could be done client-side...

Unless there is a REALLY good anti-cheating system in the game, I think most important things must be done server-side

[edit] Damn, I'm so slow writing replies :P [edit]

Well I don't think it would be plausible to do ALL collision detection on the server. Things would slow down to a halt. Perhaps the server could 'check' the position of each player after a certain period of time, lets say every 30-60 seconds. Then if the position is invalid, move the player.

Well in runescape it seems to be serverside, as when your network lags and some packets travel slower, you get forward-back-forward running

I think runescape uses some tile based system (or at least used to before it went 3d), so collision detection is probably as simple as checking to see if there is something in the grid space that the player is trying to move in to, that is cheap as chips.

Quote:

Original post by quant ...yet it would also be prone to cheats if it were done on the client side

I can say that at least in Everquest 2 quite a bit is done client side that you wouldn't expect (friends with runtime disassemblers, Everquest accounts, and no care whether or not they get banned can show you some really amusing things). I don't know if this is the case for most online games, or if Sony just doesn't know what they're doing or just doesn't care. The only anti-cheating mechanism that I know if is that whenever a player changes zones, the offsets for most everything changes. Of course... if you know what you're doing, it's not hard to find the offsets again and build a database relating the offsets... well... you get the idea ;~)

Path finding can be done on client computers. You'll still want to do collision detection on the server, though. If they try to move inside of something you can stop them, and the client can either try to generate a new path or wait for the user to try to moving somewhere else. The client also doesn't need to send the entire path, just the first few nodes and send the rest as they're needed.

Depending on the client for the game's collision detection is definitely a bad idea. I can think of two good uses for client-side collision detection:

1. Pathfinding for the player.
2. Motion prediction to prevent lag.

The server will still need to be the authority for collision detection, which means it still needs to perform its own... which brings us back to the original problem.

Partioning definitely helps. There's no need to test a player for a collision with 999 other players if he's not in the same zone with them. Here are some other techniques I use in my server, most of which are probably common sense:

1. Don't perform collision detection on an object unless it's moving (or being moved).
2. Use two tests. The first is an inexpensive calculation that compares the two objects' maximum bounding radii. If the radii's circles don't intersect, no collision is possible. If they do, perform the second, more accurate, and more expensive test.
3. Don't iterate through the collision detection loop more than necessary. In my game, for example, a collision always cancels an object's movement, so there's no need to keep checking for more collisions after the first is found.

Ken Lander's article about collision detection is very useful. I use most of the techniques he described in my advanced collision tests.

[edit]Wow, lots of posts while I was writing this.[/edit]

Thanks for the info DaToof, but surely even with partitioning it is still going to lag like hell.

Imagine you have 1000 players, and you split the world into 100 zones. On average you will have 10 people in each zone, each player will need to be tested againt the other 9, so that is going to be 45 tests per zone. Multiply that by 100 and you have 4500 tests in total. Surely that will bring the game to a grinding halt with even the simplest of collision test. And that excludes geometry.

What? You don't need to test everything against everything else, that's horribly inefficient. Divide the world into cells, each cell contains all the objects there. Test all the objects in that cell with the other objects in that cell and it's neighbors, not every item in the whole entire freeking world. If cells end up with lots of objects in them, you can also subdivide them.

Quote:

Original post by smart_idiot What? You don't need to test everything against everything else, that's horribly inefficient. Divide the world into cells, each cell contains all the items there. Test all the items in that cell with the other objects in that cell and it's neighbors, not every item in the whole entire freeking world.

You got the idiot bit right..

Isn't that what i did? I tested for collisions against everything in the partition, not for things in other partitions.

It takes 45 tests to test for collisions between objects in the same "cell". If there are 100 "cells" then that is 4500 collision detections.

I assume by zones you mean entirely different areas. . .

Quote:

Original post by quant Thanks for the info DaToof, but surely even with partitioning it is still going to lag like hell. Imagine you have 1000 players, and you split the world into 100 zones. On average you will have 10 people in each zone, each player will need to be tested againt the other 9, so that is going to be 45 tests per zone. Multiply that by 100 and you have 4500 tests in total. Surely that will bring the game to a grinding halt with even the simplest of collision test. And that excludes geometry.

In a worst-case scenario where every object that can move is moving, yes, they will all need to be tested in one game tick. In a best-case scenario, however, you won't have to perform any collision tests at all. Most of the time, the scenario will fall somewhere in the middle.

The method I described runs as close to linear time as I could get. The formula looks something like this:

(total collision tests per tick) = (moving objects) * (objects in same zone)

My game hasn't had many serious problems with lag. Granted, I've never tested it with 1000 players, but I've had it up to 100 mobile objects (both players and NPCs) without a hitch, and the server machine was a P100 with 32MB RAM, so I'm fairly confident in its scalability.

Quote:

Original post by smart_idiot I assume by zones you mean entirely different areas. . .

Yes. In my game, a zone is just an object that contains child objects. When the children move, collision tests are performed against the other children.

a fairly common trick is to not compute collisions for every entity at every time slice. Depending on how tricky you want the implementation to be, this can be as easy as just doing collision for a few of your zones, either a fixed number, or you can give the server a time budget:

time_out = clock() + 50;counter = 0;while ((clock () < time_out) && (counter < num_Zones)){  ZoneID = (ZoneID + 1) % num_Zones;  counter++;  Detect_Collisions (ZoneID);}

On the more complex side, you could store a "Last time I checked a collision timestamp" variable per entity. Then, also per entity, you would calculate a "collision test priority", something involving the entity's speed, and the distance to the nearest neighbor. Then check collisions for every character whose priority means they should be checked.

Priority_dt = Nearest_Neighbor / (0.2 + Velocity);if (Priority_dt > 50) Priority_dt = 50;if (clock () > Last_check + Priority_dt){  Do_Collision_Check (i);  Nearest_Neighbor = ???;  Velocity = ???;  Last_check = clock ();}

note that the 0.2 is just to avoid /0.0

Collision detection / clipping of the players against the world (typically a tilemap, or a tilemap with some irregularly shaped objects), should be O(N), not O(N^2)

This is because you don't need to check every player against every other thing.

Also splitting it up into zones, regions, blocks etc will make it better, so that typically it's close to O(N) for collision detection.

Add that to the fact that the server only needs to clip or test collisions against things which move - I don't know how much of the time in MMORPGs, players spend moving, but certainly, while they're in dialogue, shops etc, they won't be moving.

I don't think it's a big deal.

Pathfinding should also be pretty cheap, because the paths will always be fairly short - something like A* etc, would have a maximum path length constraint to stop it blowing up and searching the entire world - specifically, you might rule that a path can't cross zone boundaries.

You could do pathfinding on the client and server, and use the results on both of them. Or it could be done on just one of them, because it's not a security risk (clipping obviously IS a security risk so should be done on the server)

Mark

Another thing to remember is that you don't typically have 1000's of players per physical server. The zones are split between different boxes (or at least different cpus) and each one keeps track of track 100's at most. Even "continuous worlds" like UO and AC1/2 still have a concept of zones - they're just hidden from the player.