# MattFox

Community Members

5

3 Neutral

• Rank
Tiro
1. ## Pathfinding yet again: NavMeshes

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' ??)
2. ## Pathfinding yet again: NavMeshes

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.
3. ## Pathfinding yet again: NavMeshes

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. 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.