Strategies for real-time networked player movement

[Jackolantern]

So in my new project idea I need real-time player movement but not with absolute time accuracy. Instead, movement is going to be tile-based (to those not familiar, it means your character is always lined-up to a tile, much like old school NES RPGs), with no twitch-based gameplay. So obviously right there that relaxes the requirements a bit, but it still needs to be accurate of course or the server and clients will keep getting out of sync and players will be doing the "EQ jitters" all over the place as the server keeps overriding the client and moving them around.

Anyway, I am trying to decide whether to go with movement keys or click-to-move. This is a classic resource trade-off. Movement keys is more bandwidth intensive, but less intensive on server CPU resources. Click-to-move is much easier on bandwidth, but harder on server CPU resources. Since the server CPU is quite a deep well compared to bandwidth, I am leaning heavily towards click-to-move. I also think it fits the general idea a bit better. Here are the two general algorithms:

For live movement:
1. A player presses movement key.
2. Client immediately lets them move.
3. Client sends message to server that player is moving in that direction.
4. Server sets direction flag on that player's data store.
5. On update loop, room info is processed, sending all players in that area notification that that player is moving in that direction.
6. Client makes other players see that player as moving.
7. On key up, client makes player stop moving.
8. Client sends message to server that player has stopped moving in that direction.
9. Server removes direction flag on that player.
10. On update loop, room info is processes, sending all players in that area notification that that player is no longer moving.
11. Client makes other players see that player has stopped moving.
12. Server validates with client that player is in the right cell.
13. If there is a problem, client updates to server location.
14. Server sends out validation location to all other players in area, who correct that player to that cell if needed.

For click-to-move:
1. A player clicks an open cell to move.
2. The client detects if the cell is an acceptable cell to try to move to (if not, notify user can't move there and abandon).
3. Perform A* or variant on client, and make sure the cell can be reached (if not, notify the user can't move there and abandon).
4. If the user can move there, perform the movement animations and send the clicked cell to the server.
5. On the server, make sure if the cell is an acceptable cell to try to move to (if not, send a rejection notice to the client and return them to initial cell).
6. Perform A* or variant on server, and make sure the cell can be reached (if not, send a rejection notice to the client and return them to initial cell).
7. Store the movement map list from A* on moving player's data store.
8. Send results to any player that was in the same area to see movement.
9. Perform the animations to move player on observing players' clients.

Does anyone see any problems with either of these methods? And yes, in the click-to-move, there will be a slight delay with observers seeing the other player's moving, but that is fine. The "more CPU intensive" part of click-to-move comes in at using A* on the server. Nothing in the movement keys strategy would be nearly as CPU intensive. But I think node can handle it just fine. It may not even be that much more intensive, since I am unsure what the actual overhead for each Socket.io event is under the covers in node, of which there would be many more with movement keys and could possibly add some serious weight to the movement key strategy.

[hallsofvallhalla]

i have ran over and over on this same stuff several times. One thing to be real careful with is the key press. I ran into several issues with JS and node where when I pressed two buttons it would get confused and the hold down would not send proper message or send it multiple times.
Click to move work well other than needing an occasional check to be sure all was still lined up. using tiles instead of pixels like I was will help a lot.

[Cayle]

Click to move would likely be less development effort. Most WSAD style navigation techniques must implement dead reckoning on both the client and server side

What you could do with the A* on click to move is to process the A* on the client and then it proposes a traverse path to the server. Naturally, the server gets the last word. If your main loop is sophisticated enough, you could even break this up when it reached to the server into a series of smaller commands and enqueue accordingly. BTW- if you want to keep a fog of war, you'll have to send navigation nodes as they are revealed.

[Jackolantern]

i have ran over and over on this same stuff several times. One thing to be real careful with is the key press. I ran into several issues with JS and node where when I pressed two buttons it would get confused and the hold down would not send proper message or send it multiple times.
Click to move work well other than needing an occasional check to be sure all was still lined up. using tiles instead of pixels like I was will help a lot.

I am really leaning towards click-to-move as well. It just feels like the movement keys would have so much back-and-forth, and so many ways to mess up.

Also, one thing I have been thinking about is how can you have decent flood control with movement keys? Since people may need to press a movement key quite often, it would be quite a balancing act between letting people move fast and preventing DOS attacks. But with click-to-move, input should come much less often, which would mean you could put up some solid flood control.

And I am definitely going with tile-based movement to keep players lined up on tiles rather than pixel-perfect movement. The game is going to be in the style of old school RPGs anyway, so that works fine for the project. Plus, the game is going to be fairly casual, and I think click-to-move fits better with that style than more of a traditional WASD setup.

Click to move would likely be less development effort. Most WSAD style navigation techniques must implement dead reckoning on both the client and server side

What you could do with the A* on click to move is to process the A* on the client and then it proposes a traverse path to the server. Naturally, the server gets the last word. If your main loop is sophisticated enough, you could even break this up when it reached to the server into a series of smaller commands and enqueue accordingly. BTW- if you want to keep a fog of war, you'll have to send navigation nodes as they are revealed.

No fog of war needed for this project. Each "area", as mentioned in the algorithm outlines above, are single screens. So a player is either a direct observer of another player's actions (they are in the same area) or they need no updating at all on another player's actions (they are not in the same area). That simplifies things a bit

As for when to process A*, are you suggesting to send the client's results to the server so the server can perform A* and immediately compare results? That could be interesting. I definitely do think there is no way around the server also processing A*, for security reasons. And I may take your advice and try to break it up if it creates too long of an action, so that much more simple and fast operations, such as a chat message, could be processed during the A* action. But I am thinking even a long sequence of mathematical and logical operations on all in-memory objects should not take too long. But I will likely need to make a demo to make sure.

Thanks both!

[Cayle]

You can break up the "proposals" from the clients and validate portions, on the fly. This is the same approach that I take with Angela's action Engine. A player an send X commands as separate commands, OR as a single "choreography", containing those X commands in sequence. So lets take motion across a tic-tac-toe board as an example. We never use A* and its attendant CPU usage on the server and validate each step as an independent action.

Example Rules: We have a 3 x 3 grid with 0,0 being the upper right. The player may move horizontally or vertically one step per turn, but never diagonally in our example.

The valid player sends [[0,0 -> 1,0], [1,0 -> 1,1], [1,1 -> 2,1], [1,1 -> 2,1]].

• In the cycle 1, he moves to the upper middle
• In the cycle 2, he moves to the middle
• In the cycle 3, he moves to the middle right
• In the cycle 4, he moves to the lower right

Cheater 1 sends [[0,0 -> 2,2]].

• Yeah right. Command ignored

Cheater 2 sends [[2,1 -> 2,2]].

• Player is in 0,0 and not 2,1 to start. Command ignored

Cheater 3 sends [[0,0 -> 1,0], [1,0 -> 1,1], [1,1 -> 2,2]].

• In the cycle 1, he moves to the upper middle
• In the cycle 2, he moves to the middle
• In the cycle 3, he... wait! You can't move diagonally! Command ignored
• In the cycle 4, he is still hanging out in 1,1 and awaiting further commands

[Jackolantern]

Interesting! I will look into that. Thanks

[Callan S.]

I don't understand the difference between keys and mouse if you are using a grid.

For example, you press A - the server knows you are moving forward and the animation to move forward will last X seconds.

During that time it can just ignore user input anyway, until the character is lined up with a grid again.

Same would go for a mouse click, really.

Also even if you weren't using a grid, do you really need to record perfectly each key press? As long as your server has a way of figuring if the players last know position to the next position is valid, you can have the client tell you where the player is. In such a case only a hacked client or a bad net connection will cause any contradiction (and in such a case, to rubber bandville you go - which wont be a problem for regular clients). I'd imagine that's how wow does it.

[Jackolantern]

The difference between movement keys and clicking is that, with movement keys, it is more like velocities where you press a button and immediately begin moving in a cardinal direction. With clicking, the only input is the final cell to move to and the game figures out the path to move. It doesn't sound all that different at the outset, but as you can see in the two high-level algorithms posted above, they are actually quite different

[hallsofvallhalla]

Browsers treat key downs and presses differently too. That is where I ran into issues. It the player would hold the button down it would send key downs over and over. Plus some other oddities.

[Jackolantern]

A combination of jQuery and directional Boolean flags can easily fix that