Pathfinding yet again: NavMeshes

[kanetaka]

I read an interesting article about pathfinding in Japanese. Let me show you their ideas. They also published about it in English, Precomputed Pathfinding for Large and Detailed Worlds on MMO Servers (Fabien Gravot, Takanori Yokoyama, Youichiro Miyake), so you can read the details from that book.

They are developers of FINAL FANTASY XIV, a famous Japanese multiplayer online RPG. There are about 1,000 NPCs in a single map so they couldn't use real time pathfinding. Instead they use tables to store precomputed pathfindings. To reduce memory footprint for tables, they devide the map into grids and make hierarchal tables. The result is drastic. If a map has 20,000 locations for destination, the single table costs 1.1GB. Then dividing to 100 locations for each grid, the cost reduce to 11MB.

I hope this could help.

[iNcog]

OK so this topic of pathfinding really interests me.

The way I understand it, the way things currently are, pathfinding is bad in this game, but it also takes up huge chunks of CPU resources. So if you fix pathfinding you can fix two issues at once, right?

If I understand correctly, there are several things that make pathfinding bad and resource-hungry in the game:

- The long-range pathfinder and the short-range one have some compatibility issues, in that sometimes the long-range pathfinder says "ok do this" and the short-range one says "ok do that" and the unit just doesn't know which one it should listen to. So the proposed fix to this (very simplified), is to have both long and short ranged pathfinders use the same cell to work with, correct?

- The short-range pathfinder calculates too much when trying to find a new path, which means lag when lots of units move at the same time. What is the proposed work around for this? Would it be possible to implement something like "if a moving obstacle is found, then go left, up and continue, then after a certain distance, go down and right and continue on original path" ?

What stuff should I read if I were to have look at the pathfinding code myself? Where and how can I access to this code?

I feel pathfinding is one of the most important things to look at as of right now.

[Radagast.]

True, it's important currently to limit hardware tech and stagnating core speeds.

Though I wonder how to best make long and short pathfinder interact. (and I liked the different velocity areas of the old/current non-uniform-grid pathfinder though that is not really used yet .. and we could probably get same results using texture variant detection or using road objects which give units which walk ontop a speed bonus (or vehicles as is planned). )

The new pathfinder has a grid of 1x1 I think and I have hope that unit dimensions will be taken into account. This way, the short range pathfinder could fully rely on the long one. Hence it could follow something like that (though the AoK is probably much more complete, perhaps we can combine it):

- start moving towards target location.- look a bit ahead ( not too much to reduce lag, though this means it will use strange routes, e.g. following walls).- if collision with static object can be foreseen:    - go round like outlined in the empire heaven post linked by Ykkrosh.- if colliding with mobile unit + mobile unit is moving:    - wait one or two turns    - if still colliding: (e.g. too many units one after another in a row passing by in front of the moving+pathfinding object)        - go round in the opposite direction of the moving mobile entity_s direction of movement or introduce priority system to determine which side should let the other pass (preferably the side with less units should pass first if overhead is low). - continue moving forward until target  is reached (walk round a lake if the target is on an island in the middle and can_t be reached. choose nearest possible location or make unit demand a ship 'Unit requests a ship to reach target location.').

Edited May 26, 2014 by Hephaestion

[iNcog]

Aren't you describing the short-range pathfinder in that quote?

- look a bit ahead ( not too much to reduce lag, though this means it will use strange routes, e.g. following walls).

Would it make more sense to have the short range pathfinder simply guide the unit so that it sticks to the long range path? Normally the long range path would take big obstacles like walls into account, no? So if you make it so that the short range pathfinder works to follow the path laid by the long range pathfinder, the short range pathfinder would only work in the presence of obstacles, I guess.

Also, doesn't giving the long-range pathfinder higher resolution cells cause lag when lots of units are asked to move over long distances? There must surely be some drawback to having resolution cells?

Would this work out? Imagine this:

In blue you have the path set out by the long range unit. In red, you have a unit which isn't taken into account by the long range pathfinder. It's a unit on our unit's long range path. What the short range pathfinder does, very simply, is simply issue a series of preset commands when it detects the red unit which is blocking our unit's path.

Command 1: go left just a bit

Command 2: continue going parallel to the blue path over a small distance

Command 3: go right just a bit to continue following the blue path

the commands are preset so no calculation is required. the unit just moves when the short range pathfinder sees the obstacle.

You could change the geometry of the red unit's "collision shape" (or however it's called). Basically, when I say "collision shape" I mean what the short-range pathfinder detects when it detects a unit. You could something like this:

So it's simple. The triangle is in the direction of the units movement. If our unit's SRP (short range pathfinder) detects the brown line, it will use the yellow adjustment instead of the green one. i.e. :

Command a: go right just a bit

Command b: continue going parallel to the blue path over a small distance

Command c: go left just a bit to continue following the blue path

The idea is that the SRP tells the unit to turn into a direction based on whether the brown line is detected (in which case our unit moves to the right) or whether the purple line is detected (in which case our unit moves to the left).

Faster units (cavalry) would have a taller triangle. Slower but bigger units, like siege engines, would have big fat triangle. A unit that isn't moving would have no triangle at all, its "collision shape" would be a circle instead. All triangles would be preset. So when the unit is moving, the collision shape changes from one preset to another.

With this set-up, all the triangles are presets. All the green and yellow paths are also presets. The short-range pathfinder doesn't have to calculate anything at all. It just has to tell the unit to move to one side, continue, then get back on track. Everything being preset means that the only thing going on is commands being issued. Only the long range pathfinder does any actual calculations.

I'm not sure how unit movement would end up though. I'm just throwing this out there, as food for thought and in the hope that when it gets debunked I'll know a little more about pathfinding. I'm guessing such a set up might be efficient but also ugly? or something?

Edited May 26, 2014 by iNcog

[sanderd17]

What if the gap is just wide enough to fit one unit, so you can't do that parallel path thing.

Or what if a row of units is blocking it.

Also, all moveable entities have axis-aligned obstruction squares. That means the obstructions don't rotate with the unit. This is done for performance, as a simple position + offset is a lot easier to calculate than a rotated offset. Rotation requires you to calculate a sine and a cosine, causing it to be a lot slower than a simple addition.

[iNcog]

I see, it's much easier to use only squares than it is to use a triangle which rotates. OK, so this set up of mine would in fact garner terrible performance.

The way I would cope with a row of units blocking my unit is to repeat the "move to the side" command until my unit finally goes around the row of units. However that might mean that you get stuck vs a static obstruction first. So I don't think that using preset commands is the way to go, after all.

How does the current short-range pathfinder currently work? I take it the short range pathfinder doesn't take the long range (blue path) into account as of right now?

I think that the best compromise would be to have the short-range pathfinder work so that the unit remains on the blue path. So it would have to calculate the shortest possible path that brings it back to the blue path.

Edit: OK so I took some time to think about it. Basically two big improvements are in store:

1. Long range and short range pathfinding become more compatible thanks to smaller nav-cells (so short range pathfinder can base its work on long range path).

2. Short range pathfinding calculations can be simplified thanks to point 1. This results in performance improvement.

How does that sound?

lol i keep re-reading that pdf, understanding just a little more each time

Edited May 26, 2014 by iNcog

[sanderd17]

You can open the pathfinder, unitmotion and obstruction overlay (via the developer overlay: ALT+D). That shows you the various aspects of the pathfinding.

It marks tiles invalid for the long range pathfinder (the red tiles), you see unit obstructions (as squares that don't rotate), and building obstructions (as more precise rectangles). You also see the long and short paths when moving units. You see when a unit reaches a new waypoint (given by the long range pathfinder), and calculates a new short route to the next waypoint.

It's quite interesting to see how it works now. You can experiment with gaps that are small, with units in the way.

[iNcog]

I just did so

very interesting indeed

it's definitely the short range pathfinder which atm isn't working efficiently. hmm it seems to calculate another path every time the unit hits an obstacle (ie unit). so ideally you'd want the unit to calculate ONE path only and then follow that to the end. however given the random nature of things, the obstacles will move around as well.

formations do poorly it seems, when it comes to the short range pathfinder, since a unit in the formation will hit an static obstacle

food for thought. not sure what to think

[scroogie]

You can read more about issues and possible solutions in countless papers. I'd suggest these as a starter:

HPA* Near-optimal Hierarchical Pathfinding: http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf

It explains the idea and implementation of long-range / short-range pathfinding.

Jump-Point Search: https://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3761/4007

The algorithm that was chosen for the (incomplete) rewrite.

Apparently improvements will soon be published: http://www.nicta.com.au/pub?id=7771

As mentioned in the paper, it could potentially be combined with swamps as well: http://leibniz.cs.huji.ac.il/tr/1188.pdf

Another approach that seems to be getting a lot of attention is SUB: http://idm-lab.org/bib/abstracts/papers/icaps13.pdf

[Radagast.]

Symmetry reducing methods (Harabor and Grastien 2010) identify and eliminate path symmetries on grids. Forexample, Jump Point Search (JPS) (Harabor and Grastien 2011) performs symmetry reduction during runtime (with-out any preprocessing) to find shortest paths faster than Hierarchical Pathfinding A* (Botea, M̈uller, and Schaeffer 2004).

_{is a hybrid between hierarchical abstractionsand symmetry reducing methods: It is hierarchical because we first find a high-level path and then refine it to a low-levelpath. It is symmetry reducing because an edge of the sub-goal graph can correspond to many shortest paths betweenthe subgoals that it connects (which cannot happen on vis-ibility graphs because the straight line between vertices isthe only shortest path between them). Our method does notabstract groups of cells, but rather all shortest paths betweencells, which is similar to what JPS does. The jump points ofJPS are similar to our subgoals, except that the agent alwaysmoves on a straight line from one jump point to the next oneand thus moves in only one direction whereas the agent canmove from one subgoal to the next one in a combination oftwo directions.}

_{SUB involves preprocessing, though the data amount to store was around 2 MB for starcraft maps including the map data. It shall find optimal shortest paths 85 quicker than A* algorithm (which we currently use).}

_{I think JPS is a good choice as it doesn't involve storing preprocessed data and can reduce symmetry in realtime. (though it might not be that a huge improvement but still significant I guess).}

_{Thanks for the links.}

Edited May 27, 2014 by Hephaestion

[Norvegia]

If any of you plan on developing a new pathfinder, I hope you use choose an algorithm that can take advantage of thread level parallelism(TLP). Because the current push to lighter, thinner and more energy efficient devices many consumer CPUs have taken a step back in instruction level parallelism (ILP) (tablet cpus, intel atom, amd jaguar and beema). The possibility of TLP in the algorithm is therefore crucial imo.

[Stan`]

The thing is multithreading includes new bugs, thats why it's not used right now. It's easier to debug on a single thread than two.

[iNcog]

I wish I could help you guys... I genuinely feel kind of bad posting here knowing that I don't have the slightest knowledge in coding that would allow me to be of any help.

[Norvegia]

The thing is multithreading includes new bugs, thats why it's not used right now. It's easier to debug on a single thread than two.

I know this, but the algorithm needs to be parallel if you want to make the pathfinder exploit TLP some point in the future.

[sanderd17]

I know this, but the algorithm needs to be parallel if you want to make the pathfinder exploit TLP some point in the future.

No, it doesn't. We usually have a lot of pathfinding requests per turn. Because of the number, every pathfinding request could be calculated without parallelism, but the different requests could be executed in parallel. So the algorithm doesn't have to be prepared to split in multiple instances, but the interface to call the algorithm must be thread-prepared (i.e. start calculating a bunch of paths together). That interface is already prepared for multithreading.

[Norvegia]

No, it doesn't. We usually have a lot of pathfinding requests per turn. Because of the number, every pathfinding request could be calculated without parallelism, but the different requests could be executed in parallel. So the algorithm doesn't have to be prepared to split in multiple instances, but the interface to call the algorithm must be thread-prepared (i.e. start calculating a bunch of paths together). That interface is already prepared for multithreading.

So individual pathfinding request aren't dependent on each other? In that case the pathfinder is highly parallel. I thought this wasn't given, because of collision detection (ordered to enter the same spot at the same time). Edited May 28, 2014 by Norvegia

[iNcog]

So individual pathfinding request aren't dependent on each other? In that case the pathfinder is highly parallel. I thought this wasn't given, because of collision detection (ordered to enter the same spot at the same time).

Oh that means the game is set up to be well threaded. That's actually great