How to handle entity path-finding and movement in a large networked world?

Question

Considering the image above with tiles split into 32x32 boxes, I have an entity which is marked to 'aggro' nearby players that come close to it. I'd like this monster to ideally chase the player (and continue to chase the player for a while). Currently, my only movement is done my a simple interpolator for remote entities and this works because the gaps between movement updates are rather small.

I can't successfully just tell the client that the monster wants to move to the position he/she is at, as that will cause the entity move much faster than it should (this can probably be solved with using some math for the interpolation co-efficent) but more importantly it does not look realistic and may clip walls! I don't want to simulate the entire movement on the server if it can be avoided... although I guess I could but that still wouldn't solve the clipping issue. I suspect the solution involves some path-finding and sending the client periodic node updates and letting them simulate the movement but I'm unsure.

Thanks!

Answer 1

For a simple start you can implement steering behaviors. Specifically seek behaviors.

In addition to seeking the characters should use avoidance to steer away from obstacles.

Once you have those aspects working, you can implement some more intelligent following. That would include path finding. Now instead of steering towards their foes, enemies will steer towards each node on the path that leads them to their target.

Once the enemy gets "close enough" you can switch over to entirely steering behaviors. Since they're less expensive than path finding, and you'll get results that are good at close range.

Steering will also allow you to define maximum turn speeds and maximum speeds for enemies.

Steering can be managed on the client with periodic updates from the server to ensure they're still on track.

Answer 2

I can't successfully just tell the client that the monster wants to move to the position he/she is at, as that will cause the entity move much faster than it should (this can probably be solved with using some math for the interpolation co-efficent)

Actually this is simple to do. The direction of movement will be the target position minus the current position. All you need to do is scale that vector down to the movement speed you actually want. Repeat every frame.

but more importantly it does not look realistic and may clip walls! I don't want to simulate the entire movement on the server if it can be avoided...

You need to simulate the movement on the server. How else will you know that all players are seeing the same behaviour?

You will need some basic pathfinding. A* is the standard. You can calculate a path to the target and then following that path is simply a case of setting movement vectors as above. (Or you can use steering behaviours as in Byte56's answer, which is essentially the same thing with some added extras.)