   MMORPG Server
  Hi,I'm making an MMORPG server, and right now, I'm thinking about how I should keep track of each character's position.  By that, I don't mean how to store their data.  I actually mean the following:Let's say if one character is in position (50,50).  Now, the client side (that player) clicks on (45,45) on the map.  The client side will, of course, do the pathfinding, and will go by the following track (assuming no objects blocking the way)50,50 start49,4948,4847,4746,4645,45 arrivedbut now, one thing I want to question is.  Does the server first receive the message 49,49 from the client, and then will Check if 49,49 is beside 50,50 (since character is going from 50,50 to 49,49), and then allow him?  Then 48,48, then 47,47, and so on?  Will this be a lot of workload for the server if it has to check every single coordinate?Or should the client do the pathfinding first, send the whole path to the server, and the server check if the path is ok?  If it is okay, and the client starts moving step by step, and let's say now the client is in 48,48, but some guy logged in at 47,47 suddenly... then how should the server respond?  because the path needs to be changed...what's the profession to do this, may i ask?   
  i would recomend only sending the target position to the server, let the server do the pathfinding and only let the client do its own pathfinding to predict the servers result (to reduce the visible effect of lag).basically this means that both the server and the client should do the pathfinding, if the client has correct information about the world the results should be identical , if the client has outdated or incorrect information its easy for the server to send a correction.the way i would do it is this:clients sends : i want to go to 45,45client and server does the pathfinding and starts moving the player.server sends position updates to all clients regulary (including the moving client) or you could possibly let the server send the target position to all clients and thus send position updates alot less frequently (could be a bad idea if predicting the movement of other entities can give you an in-game advantage though),as for unexpected obstacles (such as a new player logging in) there are plenty of possible solutions, the easiest is simply to ignore it and let the server correct the clients movement, as soon as the client is notified of the new player it should be able to figure out what path the server is using (since both should use the same pathfinding algoritm), in a good enviroment the client should know about the new entity in less than 500ms.another option is to let the client know that a new entity will appear before it actually appears. (the client should then be able to adjust its path properly without any extra information) (basically you can delay insertion of new players by ~1 second);  hi Anonymous Poster, thx for ur reply, but according to your strategy, it wastes both PC and Server CPU... pathfinding is an algorithm that takes i think NlogN or logN... it is not something fast to do...if 100 players are on my server repeatingly clicking everywhere... or just 1 person... that means server has to repeatedly do pathfinding... it will lag the server and shut it down in less than 30 seconds...wouldnt it make more sense if One side does the calculation and send the results to the other side for confirmation?there are many ways to do this, but i really want the most "professional" and "efficient" way to do this...  i would like to hear more suggestions... anyone knows can give me a hint?cuz i want the game to be a pretty "tight" real-time MMORPG...   ;  the server has to be authoritative or you leave yourself wide open to client-side manipulation of data.  The server must be completely authoritative and tell every client where it must be at any given time.  Performing pathfinding isn't even necessary, you can simply compute a vector from the player to the point, run to that point and perform collision checks with the ground and/or any dynamic/static geometry in the world.  Terrain following is the most computationally expensive operation here.   ;Quote:Original post by eraser_iresahi Anonymous Poster, thx for ur reply, but according to your strategy, it wastes both PC and Server CPU... pathfinding is an algorithm that takes i think NlogN or logN... it is not something fast to do...if 100 players are on my server repeatingly clicking everywhere... or just 1 person... that means server has to repeatedly do pathfinding... it will lag the server and shut it down in less than 30 seconds...wouldnt it make more sense if One side does the calculation and send the results to the other side for confirmation?there are many ways to do this, but i really want the most "professional" and "efficient" way to do this...  i would like to hear more suggestions... anyone knows can give me a hint?cuz i want the game to be a pretty "tight" real-time MMORPG...well the server has to do the pathfinding anyway (if you want pathfinding) since the server has to be authorative as morph said,doing pathfinding on the client is not really a big task, (your average RTS does pathfinding for tons of units), Since the server has to be authorative (to ensure consistency and prevent cheating) the clients would want to be able to predict the data its about the recieve from the server (in order to minimize the visible effects of latency),simply verifying the path is an alternative but sending a complete path requires alot more bandwidth than simply sending the desired location, and bandwidth is far more precious than cpu cycles, pathfinding in an mmo doesn't need to be perfect, you don't need to find the shortest path, simply moving the general direction + simple obstacle avoidance is definitly enough.another option would be to use a system similar to the one used by Ultima Online, Where the client does the pathfinding and uses it to move normally (tile based movement so the client always moves one tile at the time no matter what).exactly what kind of system you want depends alot on the game, for pure tilebased movement its feasible to simple send go up / down / left / right etc.thus you can pretty much fit a movement command in 2 bits (4 directions) or 3 bits (8 directions). preferably packed with other data aswell. perhaps use a 13 or 14bit client ID (13bits should allow for ~8000 clients on one server, 14bits allow ~16000) thus squeezing both the ID and the direction in 2 bytes.packing data that way requires some extra cpu cycles though but its definitly worth it, (hardware is cheap, bandwidth costs tons of money every day).as for users spamming the server with expensive requests your best option is to simply ignore them. (the client should prevent the player from sending them repeatedly in the first place, if a faulty or modified client does it you should disconnect it)the key thing though is to ensure that you don't send more data than you absolutely have to, and that the server is responsible for anything critical to the game state.CPU usage on the server is a secondary problem, your server should take advantage of SMP and preferably be capable of splitting the game world over multiple physical servers, thus adding more cpu power is cheap and easy if it becomes necessary. bandwidth , security and consistency are the main concerns, if you use 64kbps / player you can have 16 players on a 1Mbps connection and 1600 players on a 100Mbps connection (not quite true though since more players would mean that you'd need more bandwidth for each player due to a larger amount of information that needs to be sent to them)since you call it an MMO you should probably make your estimates for ~1000-10000 players / world, and 20-50 players close enough to eachother to need frequent updates about eachother. each player shouldn't need more than 20-30kbps bandwidth during normal play (otherwise it won't be playable on dial-up),for a tight realtime MMO you don't want pathfinding, and you probably want to use frequent numbered position updates (use udp for that) and simply verify movement on the server to prevent teleporting or speedhacking.the bandwidth preservation rule becomes even more critical in that scenario though since latency becomes a much worse enemy......................................................as it is though the best solution is directly dependant on the game mechanics, overall design and number of players.;  Here's an alternative:  Have the client send a movement list.  If you're using a grid based layout (which it sounds like you are), this can be done without using too much bandwidth, keeping pathfinding on the client side while avoiding client authority.  Basically, you have 8 directions (sides and diagonals) you can travel, which can be stored in 3 bits, then the client does the path finding and sends the server something along the lines of (to get from 50,50 to 45,45):Move(5): SW SW SW SW SW //straight exampleMove(6): SW SW S W SW SW //minor obstacle exampleMove(10): S S S S S W W W W W //big obstacle exampleYou can then have the server halt the player if they hit an obstacle on that path (and inform the client to redo the path from there), or do server side calculations only for badly predicted client paths (or allow dynamic objects to intersect, or do an approximate fudge in the right direction while waiting for the client to repeat the path finding, etc)   ;  >doing pathfinding on the client is not really a big task, (your average RTS >does pathfinding for tons of units)That might be true if you run one server, but imagine case where 50-80 gameservers are running ony one physical server..You definately do NOT want them to take more then 1-2% cpu time.Let the client do the pathfinding (or any expensive operation forthat matter) and send it to the server, the server knows the current position and can determine if the movement (or whatever operation itis) is valid and update all other clients.;Quote:Original post by MaulingMonkeyHere's an alternative:  Have the client send a movement list.  If you're using a grid based layout (which it sounds like you are), this can be done without using too much bandwidth, keeping pathfinding on the client side while avoiding client authority.  Basically, you have 8 directions (sides and diagonals) you can travel, which can be stored in 3 bits, then the client does the path finding and sends the server something along the lines of (to get from 50,50 to 45,45):Move(5): SW SW SW SW SW //straight exampleMove(6): SW SW S W SW SW //minor obstacle exampleMove(10): S S S S S W W W W W //big obstacle exampleYou can then have the server halt the player if they hit an obstacle on that path (and inform the client to redo the path from there), or do server side calculations only for badly predicted client paths (or allow dynamic objects to intersect, or do an approximate fudge in the right direction while waiting for the client to repeat the path finding, etc)sending the full path is still only useful if the path is unlikely to change (that is, if its rare for the client to change his mind half-way)ultipleQuote:Original post by Kitt3n>doing pathfinding on the client is not really a big task, (your average RTS >does pathfinding for tons of units)That might be true if you run one server, but imagine case where 50-80 gameservers are running ony one physical server..uhm, what have you been smoking ? how can running more servers make clientside calculations harder, and why the .... would you run multiple game servers on a single physical server for an MMO ?   ;Quote:That might be true if you run one server, but imagine case where 50-80 gameservers are running ony one physical server..Just to give you a bit of a reality check, you generally run 1 game server on multiple physical servers...   ;Quote:Original post by MENTALQuote:That might be true if you run one server, but imagine case where 50-80 gameservers are running ony one physical server..Just to give you a bit of a reality check, you generally run 1 game server on multiple physical servers...This is true, however there might be on reason to run one game server on 2 multiple servers even though there might be like 50 zones with its own process.  So instead of having 50 servers you only need 2 but when it expands you just need to move the process over.  I know someone who has done this for a very small MMO that is growing slowly.