"Reinventing" navmeshes

Hey hey people,

The standard navmesh physics type has proven to be quite unstable in the build I’m using, so I thought I would try coding some similar behavior from scratch. Got it done by building a BVH tree from a mesh and sorting out faces like so,

nns = bvh.find_nearest_range(target, 24.0)
points = np.asarray([ 0 for p in range(len(nns)) ], dtype=object)
i = 0

for n in nns:
    co, normal, index, dist = n
    centroid = Vector([0,0,0])
    if dist > 0.01:
        poly = nav.meshes[0].getPolygon(index)
        isNeighbor = 0
        polyVerts = [vi for vi in range(3)]

        for v in range(3):
            vertex_co = (nav.meshes[0].getVertex(0,
            poly.getVertexIndex(v)).getXYZ()
            )

            if vertex_co in currPolyVerts:
                isNeighbor += 1
    
            polyVerts[v] = vertex_co
            centroid += vertex_co

        co = (centroid/3)+nav.worldPosition
        if isNeighbor > 1 and index not in path:
            points[i] = [co, polyVerts, index]
            i += 1

adjacent_points = points[points != 0]

This way I get neighboring faces to the one I’m pathfinding to, the rest is measuring distance and cost. Simple enough.

Now, what I’m wondering is if there’s a better way around. I got this approach working okay without much hassle and it’s optimal enough, but perhaps someone else has already figured out something more fancy?

i have made a similar thing for some of the same reasons, i don’t know if it is better or not.
it uses a dict to store the vertex positions by turning the position into a string and using that for the key and all the neighboring vertexes into a list like this

node[key] = [list of neighbors ]

import bge

cont = bge.logic.getCurrentController()

own = cont.owner
scene = own.scene
node = {}



def genkeyfromposition(v):
    out = "{:>.05f}:{:>.05f}:{:>.05f}".format(v[0],v[1],v[2])
    return out
 
for obj in scene.objects:
    if "navmesh" in obj:
        for mesh in obj.meshes:
            
            for p in range(mesh.numPolygons):
                poly = mesh.getPolygon(p)
                nv = poly.getNumVertex()
                i = []
                
                for v in range(nv):
                    v_index = poly.getVertexIndex(v)
                    vert = mesh.getVertex(0, v_index)
                    pos = obj.worldTransform * vert.XYZ
                    i.append(genkeyfromposition(pos))
                    key = genkeyfromposition(pos)
                    
                    if key not in node:
                        node[key] = []
                    
                for key in i:
                    node[key] +=i
       
for key in node:     
    if key in node[key]:
       a = list(set(node[key]))
       node[key]=a
       i = node[key].index(key)
       del node[key][i]
    
for key in node:
    print(key,node[key])
    
print(len(node))

I used this and made a ‘graph zipper’ so the actor only navigates a small chunk of map usually,
and if they need a very distant graph point, they can ‘await’ / think for a minute without slowing the game down.

it’s a bit complex to jump into - so I recommend building your own from scratch using the tutorials on the redblob site - python code is all there for basic a*

2 Likes

if you are sure ur npc can navigate through checkpoints only (like in a building with doors), you don’t have to bother with a navmesh( which is generated very dirty)

https://www.redblobgames.com/pathfinding/grids/graphs.html

a navmesh provides you with a way to mark ‘nodes’ or gridpoints as traversable

one can then use a obstacle simulation to avoid dynamic obstacles, but it’s kind of hacky.

my solution I ended up with, is re-rolling small A* graphs as needed locally(micrograph) to try and reach adjacent points further away (macro path)

so it combines obstacle simulation and long distance pathfinding into 1 system.

I must confess though when I wrote it I hacked it together.

Chunk = a collection of tiles - a chunk knows what chunks border it that it that are accessible from that chunk.

Tile = a tile knows what tiles border it

micrograph = the nodes a tile owns.

so if both objects are on the same chunk -> pathfind just parts of that chunk

like say chunks are labled using alphabet
A -> B -> C

where as tiles are using a index

1 -2 - 150 etc.

tiles nodes are stored like
Chunks[key][index][index]

we can path chunks -> get what tiles we will need -> path tiles -> get the path -> begin pathfinding the tiles locally and adjacent tiles to obstacle sim. (this allows navigation in vast open worlds in python)
[dumb* enemies can just path the local micrographs]

in C it would be screaming fast.

edit: to clarify*
in my game a ‘chunk’ was a object - a ‘tile’ was a quad face on the object - and the micrograph was the quads of a subdivided plane I skinned the quads with*

Oh yeah, I looked at your code before writting mine. It wasn’t exactly what I needed, but gave me a nice starting point c:

What I forgot to mention, my NPCs don’t really need to pathfind much; I already had obstacle simulation built into applyMovement. So if there’s a wall in the way, an agent can easily climb or avoid it. The thing is it looks awful silly to just have them Skyrim their way through mountains and such, that’s why I want to define some bounds for their movement.

So, I’m doing it like this.

They can still wander off their paths if need be, the navmeshes are just there to give them an idea of how to better navigate the environment.

so in any scheme, if you want to do this fast in python,

I would have the navmesh broken into pieces and pathfind those
and then from those pathfind the faces of the smaller chunks.

I believe this is called a octree in some engines.

[each ‘group’ owns 8 chunks, each chunk owns 8 objects, each object holds 8 faces and so on]

this way you don’t need to ever traverse the whole grid and it can make it quite a bit faster
pathfind chunks -> yields graph you need
A = [ chunkData , index ]

path [ C->A -> D]
is your path
sort by index = name of composite graph you need
chop off index

does graph[“A C D”] exist ?

if not generate it
(generating / graph zipping sounds expensive but it only happens 1 time and you can even save this data to disk and never generate it again unless conditions change)

The game is hardly 50MB in size so having a small cache here and there isn’t all that bad.
Meshes are already broken up so there’s only ever one navmesh per cell, but further chunking it down to separate zones by altitude or things like that might be a good idea.

Right now, rather than look at neighboring navmeshes when pathing I just draw a few lines to make an estimate of where the stitches are, and guide agents toward there – once they reach that area, I find a path towards the next stitch, and so on. Unlikely that I’ll ever need to path through more than two or three cells, and only if the player is close enough to see it, but still going to do it one a time.

**by stitch I mean an extra face or sometimes an empty that makes the navmeshes overlap. Once an agent steps on a new cell they start pathfinding on the navmesh that corresponds to it.

1 Like

Liebranca,

there’s also the “dog” system i imagined. Create on ur map a graph, your dog will only move on that graph . Your npc will “steering” to the dog. Once your npc is getting close to the dog, the dog runs to the next point on the graph. Ofc, if you are close to the npc, the npc will stop follow the dog but you :slight_smile:

So its like hacking the steering function to make the result more smooth