MattFox

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' ??)

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.

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.

Thanks everybody for the open welcome =) 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) 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. 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. 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. 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... 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 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.

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