3
\$\begingroup\$

Take WoW or Runescape for an example. You have an incredibly large map, filled with cities and forests, each filled with people and monsters.

Monsters roam around an area at random that is 25x25 tiles big (ambiguous). This is done server-side, so every player than comes across this area sees the same location of the same monster, and when a player attacks/kills that monster; other players see it too.

How is this calculated without being a massively intensive task? If you have 500 different types of monsters, all of which have 5 maximum spawned, you'll be calculating 2500 different paths continuously.

\$\endgroup\$
8
\$\begingroup\$

I think the "MMO" aspect of the question here is mostly irrelevant (although it does provide trade one major optimization for another, discussed later); the core issue is the same as would be faced by any game with large worlds and many gameplay entities that need pathing.

There's a handful of things you can do to help with this. The tl;dr is to make sure you only path when you really need to, to do things hierarchically if possible (divide-and-conquer) and to choose the cheapest algorithms you can. Presented in no particular order, I'd consider some combination of these options:

  • One solution is to do the path computation hierarchically. If the world is divided into a hierarchical spatial structure (as it probably should be, as doing so is important for lots of other computational optimizations), you can build connectivity information for each level of that hierarchy and path via that coarser graph instead. Most pathfinding algorithms scale in cost with the size of the domain, and by doing initial pathing at a coarser subdivision of the world you can drastically reduce the domain. This is sufficient to set the character moving in basically the right direction, and when they get close enough you can switch to something more detailed.

  • Another solution is to do the pathing in buckets. If you have 500 entities, tick pathing for 250 in one frame, and the other 250 the next frame (et cetera). You can achieve a decent boost this way, although you have to be careful not to use too many buckets because then the lag in an entity beginning to walk its path will be apparent if that entity is, say, in the last of ten buckets.

  • You can also use less "accurate" methods than A*, which are also less computationally expensive. A* is the "go-to pathing algorithm" because it can find optimal paths, which sounds great from a technical perspective, but from a gameplay design perspective it's not always so great: perfect isn't real, and entities that act too perfect (especially if they can compute the most optimal path over distances longer than they could see) stick out like a sore thumb often. "Cheating" AI isn't so fun, so reducing the accuracy (and expense) of a pathing solution can get you benefits in both domains. Edge-following algorithms, pathing between major landmarks instead of a per-tile or per-graph-node basis, or starting to walk a path before it is complete (allowing you to spread path computation over N frames) are various ways to achieve this.

  • In a single player game you could use distance to the player's focus point to weight pathing, and process the paths of distance objects far less frequently. This is rarely worth doing in an MMO since usually somebody will be near enough... but on the other hand, if you have a server cluster you can instead try to farm the path calculations out among N different machines.

  • You also, you know, not calculate paths for all of those entities. Have entities move in pre-calculated wander or patrol paths most of the time; these are simple point-to-point movements that are extremely cheap to process. You only need to engage pathing for the entities when a player disrupts them and they need to path to the player to attack and follow, until they hit a tethering distance from their spawn point and give up and return to it.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd add that, at least at coarser levels, precomputation is an option too. And this could be done with the Floyd-Warshall algorithm. \$\endgroup\$ – rcpinto Aug 8 '16 at 15:52
  • \$\begingroup\$ Actually the fact that this is a MMOG is not that irrelevant. In a single player game you can update only what the player sees. In a MMOG, there is not only one player, so this optimisation is not really valid any more I guess (or not as much as for a single player game) \$\endgroup\$ – Zouch Aug 9 '16 at 18:35
  • \$\begingroup\$ Yes, that is the big exception I tried to touch on. There is also the fact that "most" MMOs don't really do pathing on this scale, but I didn't really talk about that because maybe the OP still wants to for some reason \$\endgroup\$ – Josh Aug 9 '16 at 18:43
1
\$\begingroup\$

Mob movement in most MMORPGs is usually extremely simple. You rarely see mobs actually do complex paths. Most run around aimlessly near their spawn area, sometimes you have them follow a predetermined route of waypoints. Neither requires any complex route finding at all, especially because players and mobs do not block each other in most MMORPGs.

You only see actual pathfinding when they engage a player. And even then they usually have a very short range in which they follow the player, so the path-length is considerably small. The smaller the range, the less there is to compute.

Also, most MMORPGs only have a very short sightrange. Players only receive updates about mob movement in a very small range around their character, so they usually still scale quite linear.

All of that combined results in a game which isn't actually as CPU and network-intense as one would think.

\$\endgroup\$
  • \$\begingroup\$ Am I missing something in my understanding of why MMO's even do pathfinding for the mob chasing the player? If a mob is chasing a player, wouldn't it be infinitely better on performance to do absolutely no pathfinding at all, but rather simply feed the NPC the exact path the player object traveled? Including when they jumped. The path is ALREADY determined in the future. It even gives ample opportunity to easily do skill-based checks or chance to innovate in gameplay, such as rolling for trips over obstacles (ex. rogue easily outrunning an npc, due to higher trip avoidance or fun skills) \$\endgroup\$ – Carter81 Aug 10 '16 at 5:26
  • \$\begingroup\$ And problems are pretty easily solved, that I can think of. Unless I'm missing something obvious? Example, if required (ex. jumping to one's death), have checks ahead of time if an NPC would follow suit. This can be determined long before the NPC reaches that path, if player is ahead. Then either cancel following, or do some kind of cheat based on a efficiently & quickly predetermined time estimate to "catch up", where the NPC vanishes & after such time, appears again behind the player. (If infinite chasing were a thing.) Lots of interesting ways to handle this stuff. \$\endgroup\$ – Carter81 Aug 10 '16 at 5:27
  • \$\begingroup\$ I was thinking long distance pathfinding, btw. For short distances from the player, it's pretty simple. For long distances, I know zig-zags would be an immediate problem in this, as the NPC wouldn't take the closest path to the player, but would zig-zag with them (And thus be perpetually behind the player), but a combination of pathfinding & path feeding, as well as calculating distance from player, would make more sense than even simple calculations, let alone complex ones. I'm a bit surprised games, which can do all kinds of subtle cheating, do things so simply or cheat so obviously. \$\endgroup\$ – Carter81 Aug 10 '16 at 5:29
  • \$\begingroup\$ Nevermind, it's probably not a new idea at all. I assume that many already do this method, by baking paths around obstacles so the NPC doesn't need to figure out how to get around them. Duh. Unless the obstacles are dynamic, it can all be loaded already on predetermined rails. Especially in MMO's with static worlds. I just know it's very simplified, such as in WoW, where pathfinding will break if you jump off a small cliff. So the ideas are already there, many just don't use them even so for various reasons. That makes more sense. \$\endgroup\$ – Carter81 Aug 10 '16 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.