pynavmesh 1.0.2

Python implementation of path finding algorithm in navigation meshes

What is it?

This is an implementation of algorithm for path finding in navigation mesh. The algorithm is based on Three Pathfinding library. In fact, all main ideas are the same, differs only small details. All done in Python and AssemblyScript. Path finding algorithm use three main concepts:

• structure all polygons navigation mesh to a bvh (bounding volume hierarchy)
• find closest path between centers of polygons by using A* algorithm in dual graph (vertices of this graph are centers of polygons, and two vertices are incident to one edge, iff corresponding polygons have a common edge)
• combine two previous concepts to find the path between input points

It's important to understand that the algorithm does not guaranteer the optimality of the generated path. In most cases the path is plausible.

This library does not contains methods for generating (or baking) navigation meshes. It assumes that navigation mesh is already generated. There are many tools for this:

• Recast Navigation This is the most famous navigation mesh solution. It allows generate mesh and find path in it
• PyRecastDetour This is Python bindings for some functions in Recast Navigation. Allows to output generated navigation mesh triangulation and it polygonal description
• Blender, Unity and so on

How to use

To install:

pip install pynavmesh

To create navigation mesh object:

import navmesh as nm
navmesh = nm.Navmesh(vertices, polygons)

• vertices is an array of the form [(x1, y1, z1), (x2, y2, z2), ...] and contains vertex coordinates
• polygons is an array of the form [[p11, p12, ..., p1n1], [p21, p22, p23, ..., p2n2], ...], where each array is a sequence of vertices, which form the polygon. Each pij is an integer - the index of the vertex in the vertices array

To find the path in the navigation mesh simply call

path = navmesh.serach_path(start, finish)

start and finish are tuples with coordinates. It return the array path, which contains the sequence of corners of it linear segments.

More details and examples on GitHub page.