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*
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)
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 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.
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
So its like hacking the steering function to make the result more smooth
The default navmeshes caused crashes on the build I was working with at the time so I never tested. Being honest I don’t remember all the details of how this works. But the main idea is you break up the map into chunks and parent a navmesh (just some polys forming pathways) to each one of them.
The trick here is each object knows which cell it is standing on through a downwards raycast, so it always knows which navmesh corresponds to that cell. When you order them to move, they pathfind towards the polygon that’s closest to the actual goal. If the goal happens to be outside of the cell, there’s polys leading them outside. By the time they get there, the raycast registers the cell change and so a different navmesh is used to do the next path calculation.
