Jump to content


Community Members
  • Content Count

  • Joined

  • Last visited

Community Reputation

3 Neutral

About MattFox

  • Rank
  1. 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
  2. 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
  3. 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
  4. 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 dec
  5. 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 bo
  • Create New...