0
\$\begingroup\$

Main


What are the differences between those path-finding algorithms.

  • Is Navigation Mesh faster in finding the path?
  • Is it more correct than Quad/Oc Tree?
  • Does Navigation Mesh use Quad/Oc tree under the hood?

My problem is that while creating RTS game I have to make a decision between the 2. The main reason I haven't yet is that Quad Tree is a very good solution because the space is partitioned into bigger nodes that makes path finding quite faster. But if NavMesh in unity uses the same techniques under the hood then there is no reason to bother with Quad Tree.

I have noticed that by the way how the NavMesh is built in Unity it creates quite large chunks of NavMesh, so I can assume that this helps to reduce the calculations if the path lies through that big chunk.


Less Important


Also, I am wondering if NavMesh uses HPA* under the hood?

[With combination of Oct Tree that allows to partition path-finding to bigger chunks and calculate the path in them separately and then combine.] --- --- --- --- --- --- (This last part doesn't seem like it would be an optimization at all, as it just basically calculates the path the same way as without it, so the previous path would be recalculated anyway on fail, but if some custom design solutions could be added to it, like corridors to another part of nav mesh (thinking about it now - it could be implemented with current NavMesh as custom soltuion))

If any clarifications about the split into bigger chunks would be required I can try to draw and provide some images.

\$\endgroup\$
1
\$\begingroup\$

There are some tech specs & blog posts on Unity Navigation floating around, if you're curious. But if you're looking for the best approach for your particular game, you'd need to consider a host of factors:

  • Entity load - how many entities will be actively pathfinding at once
  • Path complexity - static/fixed vs dynamic/variable terrain, will there be other moving and/or pathfinding entities
  • Performance on your target platforms, including your other systems, what do you consider to be acceptable frame rates
  • Ease of integration & support - your time is valuable, could it be better spent on a different area of production
  • Timelines/targets - pathfinding is a key system, that other aspects of development rely on, so working on a custom PF implementation will delay your overall project, if that's important

Really these are general considerations for any game subsystem/component, but hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. Right now I am interested more in which pathfinding is the most performant if you consider that there may be any number of units searching for the path at the same time. Full 3D grid plane with height differences like in NavMesh would be a a good bonus. But the question specifically targets 2 pathfinding approaches that I would like to differentiate. And find out which one is more performance light. \$\endgroup\$ – Candid Moon _Max_ Jan 21 at 14:45
  • 1
    \$\begingroup\$ Performance considerations require parameters/constraints. A given approach may be efficient for large N units moving predictably, but less efficient for small N units moving erratically. You have to define your scope & assumptions in order to get a meaningful answer. \$\endgroup\$ – MandisaW Jan 23 at 16:04
  • \$\begingroup\$ from my experience, I have coded multithreaded pathfinding, used a lot of different approaches and I must say that for my case any constraints don't matter. I am looking at a general case of use of these approaches to pathfinding. If anything people should be able to answer which algorithm is better for one type of actions and is less efficient to other actions compared to another algorithm. I don't have any specific requirements. Even game design can change. So it's just get from point A to point B most accurately and as fast as possible and efficient if there can be any obstacle. \$\endgroup\$ – Candid Moon _Max_ Jan 23 at 16:33
  • 2
    \$\begingroup\$ The reason multiple pathfinding approaches even exist is because their usefulness is case-dependent. If you want an answer for your specific case (RTS game, using Unity, on platform X), then make a test mockup and check out Profiler. If you want an abstract discussion of PF algorithms in a hypothetical unconstrained generic context, that sounds like a better fit for Comp Sci SE (cs.stackexchange.com) \$\endgroup\$ – MandisaW Jan 23 at 17:34
  • \$\begingroup\$ Question is related to Unity NavMesh system, so posting it here makes sense for me. Every algorithm has a complexity. For an RTS I would use flow field wich is a great option except its memory usage. But I am interested in those 2 for various reasons that I am not obliged to disclose as far as I remember that rules of this website state. Question is A* quad/oc vs Nav Mesh with tag unity. I am looking for answer to this specific question. \$\endgroup\$ – Candid Moon _Max_ Jan 23 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.