Pathfinding yet again: NavMeshes

[MattFox]

Hi there. I'm MattFox and I am an eager young programmer willing to dive into the 0AD project. (Ok, not that young anymore, don't remind me of that )

I pretty much want to add myself to the growing list of people who tried to improve / rewrite the pathfinding - and failed. Before I accept defeat though, I want to use this thread to document my progress (and thus give me an incentive to keep working because you will certainly all love what I want to do ).

------

Navigation Meshes are a way to represent the information needed for pathfinding. They can be as detailed as one wishes and are not bound to right angles or parallel alignments, so that it is possible to create obstructions of any orientation and complexity. In complex surroundings (eg in a settlement) they adaptively refine while only minimal amount of information is stored (and explored by the A* algorithm) for large monotone areas (eg open fields or lakes). Basically NavMeshes are the way to go for pathfinding. If you have never heard of them checkout http://udn.epicgames...hReference.html and if you really want to know how all that stuff works read this master thesis http://skatgame.net/...demyen_2006.pdf .

------

For another project of mine I have already written some basic navigation using NavMeshes with rectangular Navigation Cells that adaptively grow / subdivide as the world changes. I am willing to put that code under the GPL and will thus try to integrate it into the 0ad project. It will give me an estimate of how much better (and faster) it is than the current pathfinding. Unfortunately it will be necessary to switch to arbitrary polygons (or triangles) to allow buildings and other obstructions to be placed in arbitrary angles relative to the coordinate axes. The pathfinding works almost identically, but I will need to redesign the joining / intersection of Cells. The algorithm needs some tweaks to allow units with non-zero radius to avoid corners and not bump into them (yes, it is simply done live during the algorithm. no changes of any datastructures needed). Things like checking whether it is possible to place a building at a specific position will fall of trivially once the NavMesh is implemented.

1. Initial tests Use my already existing code to replace the current pathfinding on a grid. It will only create rectangular NavCells (of arbitrary size, depending on the enviroment) but is thus the simplest replacement at the moment and will give me some outlook of how much faster it is compared to other already existing implementations.
   
2. Minor tweaks Things that can be included very easily are e.g.: keeping track of the connected components in the navigation graph to instantly return from an impossible navigation attempt (trying to find a path to a point that can never be reached is the worst case of A*); check whether it is possible to place a building at a given position (don't know where and how it is done at the moment)... (etc?)
   
3. Allowing units of non-zero radius This step will need some tweaking of the algorithm but should then be able to correctly navigate units with circular bounding zones around any obstacle.
   
4. Change to arbitrary polygons To befit the arbitrary orientation of buildings in 0ad it will be necessary to allow arbitrary (or only triangular) convex polygons as basis to span the entire map with as little polygons as possible. This step will remove any inaccuracy due to discretisations as they can be seen in the current pathfinding (buildings will have their exact form blocked, and not some covering of them in some grid). This will also get rid of any "recalculations of the grid" as they seem to be necessary at the moment. (Modifying the NavMesh is almost trivial and can be done live. Only checking for connected components can be a bit more tricky and should probably be delegated to a seperate thread.)
   

The fourth step will probably take the most time. Let's see how far I will get =) At some point I also want to dive into the close-range navigation as the NavMeshes can (and should) be used there as well and I have some additional ideas regarding formations etc..

------

That is it for the moment. I am still stuck at step 0: understanding the current codebase. Hopefully I will soon be able to present to you the first results of step 1

Edited September 25, 2013 by MattFox

[sanderd17]

The project currently uses two pathfinders, the long and short range one. The long range now has a very rough grid that's used to calculate the approximate path. The short range works grid-less, but is very naive and has a big complexity. Mismatches between the two are the main reason for problems. When a grid cell is unobstructed according to the long range pathfinder, it's possible that a unit is too wide to fit through, so the short pathfinder kicks in and calculates a route that's far too long, which is very expensive. The other case is also possible, where a unit would be able to pass through a gap between buildings, but the long range pathfinder doesn't see the gap. You need to manually approach your units to there, so the short pathfinder kicks in immediately to calculate the path through the gap.

There is being worked on a new pathfinder (http://trac.wildfiregames.com/ticket/1756 - reading the patch might give you an idea on where to look). The new way to do it is using a much denser grid, and share that grid between the short and long range pathfinder, so there are no mismatches. Because A* is very bad with all equivalent paths, the algorithm has been transformed to A* + JPS, which is great on uniform grids. When this change is complete, the short range one must also be re-written to work grid-wise (for consistency, as I explained).

For your algorithm, it looks like you'll have to redesign both pathfinders to guarantee consistency. If you can pull it off, I'll be interested in the results, but I fear that a non-grid-based pathfinder will be too expensive for long paths (from one side of the map to the other) with 1000s of obstructions in between.

[scroogie]

Just to add to the good explanations of sanderd, if you look at the short range pathfinder, it is basically a points-of-visibility algorithm with high precision obstruction edges connecting corners. I think there was also an article in a GPG issue that explained PoV pathfinding. Maybe it helps to understand the idea behind it. Apart from the mismatches of the two systems, the problem seems to be that it is simply too expensive.

I don't know how good a NavMesh approach will fare, especially because of the modifications of the obstructions, online replanning, and unit clearance (i.e. point 3), but its definitely worth a try. I assume you'd need some additional subdivision to floodfill (or however you build the navmesh) only parts of the map.

[RedFox]

Hi MattFox, nice to see another coder throwing himself into the fray on this one.

I think the best place you can start from is creating a list of features that the 0AD pathfinder needs. For example, because the game design foresees variable-cost terrain movement (slower movement in mud and bog than on grass), the amount of possible options is drastically reduced.

Another big issue is unit sizes - we need a pathfinder that works from small wardogs to large elephants. When we fail to find a path, we need to provide a new path that moves as close to the target as possible.

I think the main issue however, is not the pathfinder itself - it's the entire system of ObstructionManager. Basically, every individual unit has an obstruction square (the kind of obstruction you pathfind around). I think this is the biggest flaw of the system, because if you have 200 or more units in close order, the pathfinding becomes incredibly complex.

A better solution would be to introduce a new CollisionManager module that manages individual unit-to-unit collisions only. You can see games like StarCraft 2 that do this:

And it works great - units that collide simply push each-other apart and out of the way.

There is actually a grid-based pathfinding method that uses a hierarchical passability mesh/grid. Incidentally, it also solves unit-sizes due to its clearance-oriented structure. This method is a combination of Clearance-based pathfinding grid with HPA* (Hierarchical Annotated A*): http://aigamedev.com...ed-pathfinding/

It's the only solution that really solves all the pathfinding problems we're facing (besides unit collison that is).

Traditional A* grid approach would use floodfilled planes to detect unreachable areas (something like this - notice how unreachable planes are colored different). This can be used with any grid-based method, you just check if (source.planeID == destination.planeID). After that check fails (there is no path available), we just pick the closest tile that has the source.planeID and pathfind to that.

Alright, enough ranting from me. I'm really glad someone decided to just jump into the fray - but there are a lot of issues that must be confronted. One thing is clear though - simply implementing a new pathfinder won't fix anything if we have 200 tightly packed obstructions that ruin the algorithm.

[FeXoR]

I agree.

One tiny comment though to:

When we fail to find a path, we need to provide a new path that moves as close to the target as possible.

In case the attack range of the ordered unit is smaller than the minimum distance reachable it might me better to minimize finalDistance / pathLength.

The player might not want a unit to walk around a big obstruction (like mountains or forests) for nothing.

On the other hand this could be seen as a case where "babysitting" units might be acceptable.

Edited September 24, 2013 by FeXoR

[Ykkrosh]

Unfortunately it will be necessary to switch to arbitrary polygons (or triangles) to allow buildings and other obstructions to be placed in arbitrary angles relative to the coordinate axes.

The not-quite-completed new pathfinder design (around #1756) takes completely the opposite approach: it converts all the buildings into square grid cells, and uses that grid for all pathfinding. (And it uses 4x4 cells per terrain tile, to ensure there's enough precision for units to fit through tight gaps without noticeable quantisation issues). I liked that approach since it means there's no difference between terrain and buildings, the lack of angles simplifies a lot of code, and it's (relatively) easy to be really fast at pathfinding over a grid. With navmeshes I assume you have to try hard to minimise the number of cells, e.g. I guess you may need to smooth the terrain-tile passability grid to avoid creating hundreds of cells around the edges of 45-degree rivers etc. It'd be interesting to find out whether it's a feasible approach in practice for the kinds of map layouts we have

Things that can be included very easily are e.g.: keeping track of the connected components in the navigation graph to instantly return from an impossible navigation attempt (trying to find a path to a point that can never be reached is the worst case of A*)

Yeah, I think that's the biggest reason for slowness in our current pathfinder. The new pathfinder patch fixes that by constructing a reachability graph from the grid representation - if a unit tries to move to an unreachable goal then it'll use the graph to pick the nearest reachable location and pathfind to there instead. (The goal can be a point or a circle or a square, which makes things a little trickier - e.g. it's fine for an archer to attack a ship in deep water, as long as it can find a tile on the shore that's within attack range.)

check whether it is possible to place a building at a given position (don't know where and how it is done at the moment)...

(CCmpObstruction::CheckFoundation.)

[MattFox]

Thanks everybody for the open welcome =)

For your algorithm, it looks like you'll have to redesign both pathfinders to guarantee consistency. If you can pull it off, I'll be interested in the results, but I fear that a non-grid-based pathfinder will be too expensive for long paths (from one side of the map to the other) with 1000s of obstructions in between.

The pathfinding should actually be much more efficient. Yes, there will probably be thousands of polygons to cover the map - but there are now tens of thousands of cells to do the same. Traversing one polygon is not much more complex than expanding the neighbors of a cell in a grid, so joining several gridcells (or joining larger areas in other convex polygons) can only speed up the pathfinding.

I have never compared my NavMesh implementation with A*+JPS, but that is what the first step is for =) (As the number of expanded nodes in the A* algorithm decreases significantly I still expect a speedup compared to any grid based variant)

Just to add to the good explanations of sanderd, if you look at the short range pathfinder, it is basically a points-of-visibility algorithm with high precision obstruction edges connecting corners. I think there was also an article in a GPG issue that explained PoV pathfinding. Maybe it helps to understand the idea behind it. Apart from the mismatches of the two systems, the problem seems to be that it is simply too expensive.

The PoV algorithm gives good results (corner hugging), but the graph that needs to be traversed by the algorithm is much too broad. Especially on open fields there are way too many connected edges and thus neighbors in the graph that need to be expanded and added to the priority queue. The underlying representation of the world adds another problem (a broad graph would not be too bad if there are few possible nodes to begin with): looking at the pictures http://www.wildfireg...ic=15270&st=120 one can see, that the tilted buildings create jagged lines due to the discretisation. There are thus a lot of 'corners' that are actually in the middle of an obstruction and will never be part of a shortest path.

[...]

A better solution would be to introduce a new CollisionManager module that manages individual unit-to-unit collisions only. You can see games like StarCraft 2 that do this: [...]

And it works great - units that collide simply push each-other apart and out of the way.

Hmm this looks very nice, but only as long as there are only units owned by the same player. You want your units to be able to move through your own army - but want your army to be able to stop an enemy unit. So you would still have to navigate around enemies if you want to pass them even if you are able to push units aside.

Traditional A* grid approach would use floodfilled planes to detect unreachable areas (something like this - notice how unreachable planes are colored different). This can be used with any grid-based method, you just check if (source.planeID == destination.planeID). After that check fails (there is no path available), we just pick the closest tile that has the source.planeID and pathfind to that.

That is basically what I meant with connected components in the navigation graph. There is another floodfill necessary whenever a building is placed (as it could block a chokepoint and thus disconnect two parts of the map) and I am not quite sure about the impact on the performance of that operation.

One thing is clear though - simply implementing a new pathfinder won't fix anything if we have 200 tightly packed obstructions that ruin the algorithm.

True, but a more efficient large-scale pathfinding is nice on its own and the new datatypes might solve some problems with the short-range navigation as well... We'll see...

In case the attack range of the ordered unit is smaller than the minimum distance reachable it might me better to minimize finalDistance / pathLength.

The player might not want a unit to walk around a big obstruction (like mountains or forests) for nothing.

On the other hand this could be seen as a case where "babysitting" units might be acceptable.

I guess babysitting should be fine for a start. At least it is not as simple as minimizing the function you suggested. Minimize(finalDistance / pathLength) actually maximizes the pathLength (a longer path with the same finalDistance is prefered). Changing it to minimize(finalDistance * pathLength) would not work at all because pathLength=0 is a local minimum... For the moment I am already out of ideas how to solve this

The not-quite-completed new pathfinder design (around #1756) takes completely the opposite approach: it converts all the buildings into square grid cells, and uses that grid for all pathfinding. (And it uses 4x4 cells per terrain tile, to ensure there's enough precision for units to fit through tight gaps without noticeable quantisation issues). I liked that approach since it means there's no difference between terrain and buildings, the lack of angles simplifies a lot of code, and it's (relatively) easy to be really fast at pathfinding over a grid. With navmeshes I assume you have to try hard to minimise the number of cells, e.g. I guess you may need to smooth the terrain-tile passability grid to avoid creating hundreds of cells around the edges of 45-degree rivers etc. It'd be interesting to find out whether it's a feasible approach in practice for the kinds of map layouts we have

I have looked at your progress reports in the aforementioned thread (http://www.wildfireg...ic=15270&st=120). It is true that the finer grid solves some problems, but I think I disagree with you on the "it's (relatively) easy to be really fast at pathfinding over a grid" part. The speed of the algorithm is directily correlated to the number of nodes that we need to look at. And a polygon based representation will never have as many nodes as a full grid. True, JPS reduces the number of expanded nodes tremendously - that is why I'm excited to compare the stats - but I am confident that my algorithm will at least be on par with A*+JPS. I know for sure that Blizzard uses NavMeshes in Starcraft II. If it is feasable for them it should be feasable for 0ad as well.

[FeXoR]

Hmm this looks very nice, but only as long as there are only units owned by the same player. You want your units to be able to move through your own army - but want your army to be able to stop an enemy unit. So you would still have to navigate around enemies if you want to pass them even if you are able to push units aside.

I don't think it would be terrible to let enemy units be shifted. In the end the passing units would much likely die while passing through.

Still this might need some thoughts.

I guess babysitting should be fine for a start. At least it is not as simple as minimizing the function you suggested. Minimize(finalDistance / pathLength) actually maximizes the pathLength (a longer path with the same finalDistance is prefered). Changing it to minimize(finalDistance * pathLength) would not work at all because pathLength=0 is a local minimum... For the moment I am already out of ideas how to solve this

Oh, true! minimize(finalDistance * (pathLength + finalDistance)) might do? As it is minimize(finalDistance * pathLength + finalDistance^2) the minimum of finalDistance^2 is "stronger" than the minimum of finalDistance * pathLength (as long as finalDistance > 1). Not sure...

Or maybe minimize(pathLength * (pathLength + finalDistance)) ?

I'll think of it... (still babysitting would be OK ATM)

[RedFox]

We won't need any special treatment of enemies in the pathfinder. The hypothetical new "CollisionManager" would detect collisions and decides whether to start fighting (collide with enemy), pushing (collide with friendly), or try to find a path around the friend/foe (disengage from fights).

[FeXoR]

We won't need any special treatment of enemies in the pathfinder. The hypothetical new "CollisionManager" would detect collisions and decides whether to start fighting (collide with enemy), pushing (collide with friendly), or try to find a path around the friend/foe (disengage from fights).

The first case: Should only happen if an attack-move order was given (so ATM never since attack-move is not implemented (AFAIK)).<- [i didn't know, Awesome!]

The last case: I though "try to find a path around the friend/foe" is exactly the case to avoid(?) (Should not happen if an attack-move order is given).

So, no, the range manage does not have the priority to decide what's to do. It should depend on the order given.

Edited September 26, 2013 by FeXoR

[Don]

Wait, attack-move works?? How do I use it?

[Ykkrosh]

Traversing one polygon is not much more complex than expanding the neighbors of a cell in a grid

Hmm, I'm not sure the constant overheads are entirely negligible. E.g. if you're doing a Starcraft 2 style triangular navmesh, each triangular cell has 3 neighbours, and you might store those as 3 pointers, which is 24 bytes per cell (on x86_64), whereas square grids require 0 bytes to represent neighbours (you just compute them with pointer arithmetic), so it'll use up some more cache space. Or e.g. you probably want to store the unexplored/open/closed status for each cell, and you need to reset them all to 'unexplored' before starting a new path computation - if you've got a square grid then you can have a separate array of those status flags and initialise it to 0 easily, whereas I think it's trickier to do it efficiently if you've got an arbitrary graph of cells. (That initialisation can be a non-trivial cost if you're doing a lot of very short paths). So I think there's some extra cost per cell and the question is how well the reduction in cell count outweighs that.

...I'm not really convincing myself that those are insurmountable problems, though

[FeXoR]

Wait, attack-move works?? How do I use it?

Seems so. Should be strg+rightKlick.

[MattFox]

Oh, true! minimize(finalDistance * (pathLength + finalDistance)) might do? As it is minimize(finalDistance * pathLength + finalDistance^2) the minimum of finalDistance^2 is "stronger" than the minimum of finalDistance * pathLength (as long as finalDistance > 1). Not sure...

Or maybe minimize(pathLength * (pathLength + finalDistance)) ?

I'll think of it... (still babysitting would be OK ATM)

If the unit is on its way and we repeat the same order we want it to move to the same spot, so using "pathlength" is a bit risky. At least I am not convinced that any of those functions would guarantee that the unit does not decide to move somewhere else when repeating the order.

Hmm, I'm not sure the constant overheads are entirely negligible. E.g. if you're doing a Starcraft 2 style triangular navmesh, each triangular cell has 3 neighbours, and you might store those as 3 pointers, which is 24 bytes per cell (on x86_64), whereas square grids require 0 bytes to represent neighbours (you just compute them with pointer arithmetic), so it'll use up some more cache space. Or e.g. you probably want to store the unexplored/open/closed status for each cell, and you need to reset them all to 'unexplored' before starting a new path computation - if you've got a square grid then you can have a separate array of those status flags and initialise it to 0 easily, whereas I think it's trickier to do it efficiently if you've got an arbitrary graph of cells. (That initialisation can be a non-trivial cost if you're doing a lot of very short paths). So I think there's some extra cost per cell and the question is how well the reduction in cell count outweighs that.

...I'm not really convincing myself that those are insurmountable problems, though

On the other hand you store at least one byte per gridcell. Imagine a field of 10 times 10 cells (with 4x4 cells per tile thats less than 3x3 tiles!). The grid needs at least 100 bytes to represent this field, while the NavMesh still only needs 24 bytes + boundaries.

And it's not strictly necessary to initialise any status flags to 0. As long as we are not parallel we can simply increase a counter for each call to ComputePath. Any cell with stored status < this counter is treated as having the value 0. (if we need several states like 'unseen', 'seen', 'closed' we can simply increase the counter by 2 every time) Only when we overflow we need to reset all states. (ok, thats a bit hackish. nicer is the following approach)

As soon as we are parallel we need to create an independent structure anyway. E.g. a map<cell_id_t, u8> will do and does not require any initialization.

Edited September 27, 2013 by MattFox

[RedFox]

When it comes to optimization, I would rather focus on a well thought out algorithmic approach at first. Micro-optimizations as some call them shouldn't be the focus, though they shouldn't be disregarded either - a good cache locality optimization can make many algorithms several times faster.

I guess the main benefit of a grid-based system is its relative sequential nature, which is better for CPU cache than other pointer based methods. Notoriously, linked lists are ridiculously slow on modern hardware, even though they are algorithmically faster for insert/remove, any simple array/vector based system will beat it hands down because sequential memory is naturally attuned for CPU cache.

When you are working on your new solution, I hope you will keep this in mind. Although, if we the algorithm significantly reduces overall complexity, it will definitely be worth it.

I'll be looking forward to what you can conjure in the upcoming few weeks.

[MattFox]

Ok, so i have some understanding of the code by now. I have inserted my code to create a NavMesh from a given grid - but have not increased the density to 4x4 cells per tile yet. Don't want to change too much code without really understanding everything. I have struggled a bit with the all-too-easily-overflowing fixed datatype but still converted all of my code to use them. I also had to remove all of the C++11 code :-( My beloved range-based for loops :-(

Visualizing the walkability of the map (in m_Grid)

you can imagine how those tiles can be joined to form larger cells (suboptimal coloring based on the cell-id):

Conserving all flags this reduced the number of cells on this map from 65536 to some 7000. Ignoring the construction_obstruction flag (which is irrelevant for pathfinding) only 5854 cells are necessary to cover the map

This suggests a speedup of between 3 (median size of a NavCell) and 11 (average size of a NavCell). The really interesting comparison would use 4x4 cells per tile to begin with though. The size of the areas without change would not decrease so the NavCells can stay just as large as they are right now (we only have to add some smaller ones near the borders), so I expect the difference to be more noticeable then.

Pathfinding does not work yet, so there is no direct comparison of speeds at this time :-( To allow future camparisons I have already visualized a small benchmark of the old pathfinding though. Thought I'd share it with you in case you are interested:

The plot shows the time it took to calculate a path (in ms) in dependence of its final length (in game units). You can clearly see the constant 10ms efford for any path to an unreachable goal due to the algorithm basically searching all of the walkable space. There is another line near 1ms probably due to starting positions that are either unreachable or on an island (test map was peloponnesian wars).

------

I have to admit that I am a bit less optimistic seeing these numbers. From the delay of ingame orders I imagined the pathfinding to be worse than it actually is and I had hoped for a higher median cell size. Still I am looking forward to the timings of my algorithm - especially when adding the denser grid as I know that the grid based A* scales really bad with increasing grid density.

Edited September 29, 2013 by MattFox

[RedFox]

Looking good. To avoid the worst case of A*, you'll have to do some simple heuristics like described before. An iterative flood-fill method should be pretty fast and do the trick.

Running some tests with my own A* setup on reasonably complex map layouts, a 48x48 (2304 tiles) can take around ~1500 iterations to cover the map, while a 512x512 (262144) can have over 88700 iterations per A* search query.

If you can reduce the number of cells tenfold from a 256x256 map (~65k -> ~6k), you'd already cut down the number iterations by a huge amount, to somewhere around ~5000 for the whole map.

Looks like a huge algorithmic victory to be gained regardless

[scroogie]

Great to see that you are actually investigating this. Perhaps, as other people have repeatedly tried to look into this, you could preserve somewhere how you investigated / tested solutions. Are you replacing both the short-range and long-range pathfinder, or one of them?

[MattFox]

Great to see that you are actually investigating this. Perhaps, as other people have repeatedly tried to look into this, you could preserve somewhere how you investigated / tested solutions. Are you replacing both the short-range and long-range pathfinder, or one of them?

Right now I am trying to implement a long-range navigation based on the NavMeshes. I have written an algorithm for that some time ago - but realized that it finds suboptimal solutions in some cases so I basically rewrote the algorithm with what I learned between back then and now. It works - but is actually slower than the old grid based A* ^^ I have some ideas how to speed it up tremendously though, so I will not post any numbers before trying to optimize the algorithm some more.

The ultimate goal is to replace both the long- and short-ranged pathfinding.

If everything fails (and it turns out to be slower even in the case of the denser grid - which is rather unlikely) I have still gained some knowledge:

first of course I now know my way around the codebase at least enough to work on the code. That alone is worth a lot.

secondly the math section of the codebase _seriously_ needs some work:

- The old pathfinding spends 35% of its time in the isqrt function. That function itself can be made more efficient with some lookup tables and the goldschmidt algorithm but the best solution is to replace the CFixedVector2D::Length() function by an approximation. The one I use for my algorithm basically uses 2-3 multiplications and one division for an approximation that has an maximal relative error of 0.3%. It is worth considering to change to this approximation for all calculations.

- fixed::Pi(), fixed::Zero(), fixed::Epsilon() create new objects and perform two deep copies per call. My algorithm actually spends 4% of its time inside fixed::Pi() (That is more time than I need for all of my euclidian distance approximations ). All three functions should be replaced by constants. (Is there a reason the return value of those functions is not 'const CFixed &' but rather 'CFixed' ??)

[Thanduel]

Speaking of the maths functions, I recently spent some time writing faster algorithms for the fixed point trig functions. The performance improvement is about double for both atan2 and the sincos function with improved accuracy in the case of the atan2 function. Hopefully that is helpful in some way for what you are doing. Here is the ticket:

http://trac.wildfiregames.com/ticket/2109

Also I agree with you that it doesn't make sense that methods like Zero and Pi create new objects instead of providing a reference to a predefined const object. Personally I got around that by making the paramaterised constructor public so that I could define static const objects -- for example so that I could define a static const lookup table that is evalulated at compile time.

Edited October 3, 2013 by Thanduel

[Ykkrosh]

- The old pathfinding spends 35% of its time in the isqrt function. That function itself can be made more efficient with some lookup tables and the goldschmidt algorithm but the best solution is to replace the CFixedVector2D::Length() function by an approximation. The one I use for my algorithm basically uses 2-3 multiplications and one division for an approximation that has an maximal relative error of 0.3%. It is worth considering to change to this approximation for all calculations.

I think the best solution is to avoid calling CompareLength at all. Euclidean distance is actually a pretty bad heuristic for grid-based A*, because the paths consist of only diagonal/horizontal/vertical movements and are significantly longer than the Euclidean distance, so A* expands more nodes than it should. My newer JPS A* thing computes the heuristic as octile distance (i.e. sqrt(2)*numDiagSteps + numHorizVertSteps) which is more accurate and cheaper.

- fixed::Pi(), fixed::Zero(), fixed::Epsilon() create new objects and perform two deep copies per call. My algorithm actually spends 4% of its time inside fixed::Pi() (That is more time than I need for all of my euclidian distance approximations ). All three functions should be replaced by constants. (Is there a reason the return value of those functions is not 'const CFixed &' but rather 'CFixed' ??)

As far as the compiler is concerned, fixed is just an int - there should be no more cost to constructing the object or copying it than with any other int (assuming optimisations are turned on). If you're calling Pi() a lot, you might just want to define it inline in the .h file, so the compiler can recognise it's a constant int and remove the function call cost.

[RedFox]

Is there any further progress on this test? What kind of issues are you facing currently? Updating the navmesh? Performance issues?

For grid distances you could just use the standard "manhattan distance" method. It's a simple and fast method and also gives decent results.

[Wijitmaker]

I tried this morning to find the name of the former ES employee that offered to be a sounding board for AI related ideas/issues that 0 A.D. was coming into but I can't seem to find him. It might have been Pottinger or Pritchard, but I can't remember... But, I did come across this while doing old searches on the forums. Probably isn't anything you guys don't already know about though...

http://wildfiregames.com/users/code/resources/divisions/Graphics/Resources/terrainanalysis.zip

[historic_bruno]

I tried this morning to find the name of the former ES employee that offered to be a sounding board for AI related ideas/issues that 0 A.D. was coming into but I can't seem to find him. It might have been Pottinger or Pritchard, but I can't remember... But, I did come across this while doing old searches on the forums. Probably isn't anything you guys don't already know about though...

http://wildfiregames.com/users/code/resources/divisions/Graphics/Resources/terrainanalysis.zip

Great find, thanks! I had not seen that document before, but indeed it seems to confirm our suspicions and the general direction the pathfinder, AI and RMS are moving in.

[Radagast.]

I think the best solution is to avoid calling CompareLength at all. Euclidean distance is actually a pretty bad heuristic for grid-based A*, because the paths consist of only diagonal/horizontal/vertical movements and are significantly longer than the Euclidean distance, so A* expands more nodes than it should. My newer JPS A* thing computes the heuristic as octile distance (i.e. sqrt(2)*numDiagSteps + numHorizVertSteps) which is more accurate and cheaper.

As far as the compiler is concerned, fixed is just an int - there should be no more cost to constructing the object or copying it than with any other int (assuming optimisations are turned on). If you're calling Pi() a lot, you might just want to define it inline in the .h file, so the compiler can recognise it's a constant int and remove the function call cost.

The new pathfinder just works around this function. The non-uniform grid may be missed some time for roads .. but we will find a way round it. E.g. mounted units and vehicles. Btw. Can we still have slope-integration into the unit-speed? I think that's an essential part of the battle system.

Right now I am trying to implement a long-range navigation based on the NavMeshes. I have written an algorithm for that some time ago - but realized that it finds suboptimal solutions in some cases so I basically rewrote the algorithm with what I learned between back then and now. It works - but is actually slower than the old grid based A* ^^ I have some ideas how to speed it up tremendously though, so I will not post any numbers before trying to optimize the algorithm some more.

The ultimate goal is to replace both the long- and short-ranged pathfinding.

If everything fails (and it turns out to be slower even in the case of the denser grid - which is rather unlikely) I have still gained some knowledge:

first of course I now know my way around the codebase at least enough to work on the code. That alone is worth a lot.

secondly the math section of the codebase _seriously_ needs some work:

- The old pathfinding spends 35% of its time in the isqrt function. That function itself can be made more efficient with some lookup tables and the goldschmidt algorithm but the best solution is to replace the CFixedVector2D::Length() function by an approximation. The one I use for my algorithm basically uses 2-3 multiplications and one division for an approximation that has an maximal relative error of 0.3%. It is worth considering to change to this approximation for all calculations.

- fixed::Pi(), fixed::Zero(), fixed::Epsilon() create new objects and perform two deep copies per call. My algorithm actually spends 4% of its time inside fixed::Pi() (That is more time than I need for all of my euclidian distance approximations ). All three functions should be replaced by constants. (Is there a reason the return value of those functions is not 'const CFixed &' but rather 'CFixed' ??)

Interesting. As we have been talking about a 1x1 resolution pathfinder, this would probably support your algorithm.

Speaking of the maths functions, I recently spent some time writing faster algorithms for the fixed point trig functions. The performance improvement is about double for both atan2 and the sincos function with improved accuracy in the case of the atan2 function. Hopefully that is helpful in some way for what you are doing. Here is the ticket:

http://trac.wildfiregames.com/ticket/2109

Also I agree with you that it doesn't make sense that methods like Zero and Pi create new objects instead of providing a reference to a predefined const object. Personally I got around that by making the paramaterised constructor public so that I could define static const objects -- for example so that I could define a static const lookup table that is evalulated at compile time.

I think the ticket still has not been resolved. Thanduel we need your input once again for the JavaScript RMS side.