search

Tugcga / Path-Finder

Python and AssemblyScript implementations of path finding and collision avoidance algorithms in navigation meshes
25 stars 6 forks source link

what is? #9

Open mimooh opened 1 year ago

mimooh commented 1 year ago

Hi, so what is this project? Is this a total rewrite of recast detour from C to Python? Is it? This would be extremely handy to have a native python implementation. As I understand, this sofware can be used to build a recast-compatible navmesh and find paths from A to B, right? How about the performance of pathfinding comparing to C?

Tugcga commented 1 year ago

No, you are not right. The main goal of this project - create module for using navigation mesh in browser. So, the priority target is wasm module. The main task - find closest path between two points in the given navigation mesh.

Python version used as first step to understand algorithms and test module architecture. From original RecastNavigation library I use only navigation mesh baking algorithm. In fact this algorithm is ported one-to-one from c++ to Python and then to AssemblyScript. All other algorithms are different. For example, path finding algorithm on a navigation mesh use different approach and works faster but less accurate (of course, relatively faster, because Python version can not works faster than c++).

Also in this module there are no any specific format for store navigation mesh. It stores as simple three arrays with polygon datas. So, it incompatible with RecastNavigation format.

mimooh commented 1 year ago

Thank you for this and the other answer! Let me reformulate: we have a python application that needs to build navmesh and find shortest paths only. Do you suggest Tugcga/Path-Finder (pure python as I get it) or rather to compile Tugcga/PyRecastDetour for linux? I think we prioritize simplicity of maintaining our project over speed of path finding (speeds are not that much different as I understand it). And let me thank you for all this software which looks very promising!

Tugcga commented 1 year ago

You can use Python version. It can be installed from pip and does not requires any dependencies. At allows to bake navmesh, search shortest path between two points and even has implementation of the RVO2 - agent collision avoidance algorithm. Python page of the module contains some examples how to use it.