[SOLVED] Procedurally generating a navigation mesh

gerakinis · October 10, 2011, 6:09am

Hi All,

I’m hoping to use the built-in pathfinding code from pandaAI with a mesh that I am procedurally generating. The only documentation I can find on the pathfinding system suggests that the only way to create navmeshes is to export them from a 3d package. I’m already generating a flat plane made of triangles, so it seems silly to duplicate this. And, as the tile system is dynamic I’d like the navmesh to be as well.

Has anyone had any experience with setting up a navmesh without using blender/max/maya? I’d prefer not to have to roll my own solution as this will definitely need to be done in c++ and it is a whole can of worms I’d love to avoid. (I’m stuck somewhere in the initial compile process now … )

A question that comes to mind if this is possible: does each tile need to be its own geom to retain a walkable/unwalkable flag? I’m currently flattening things before rendering.

Thanks in advance!

gerakinis · October 10, 2011, 9:09pm

I’m going to half-way answer my own question. My solution isn’t implemented yet so I will update this thread later.

I just found the write egg file functionality:

data = EggData()
data.writeEgg(Filename("wedge.egg"))

I’m currently generating my tile mesh procedurally only because I’m lacking a tile map definition, disk format, and creation tool. I’ve been hoping to background this task until later in development.

It seems reasonable that I’ll be able to use a mesh that I’m generating now, write it out and use the existing tools for pathfinding on it and then switch to static model loading for this map.

Once I get to try this out I’ll update the thread.

PS. Sorry to do my learning publicly. I hope someone else along this path gets some use out of me filling up forum space =)

KnolanCross · October 12, 2011, 12:30am

If you are going to use an editor in future I believe you only need a example map right now, correct?
If that is the case, you can use the models/navmeshs that come with the PandAI examples.

gerakinis · October 12, 2011, 3:06am

Thanks for the tip, I hadn’t seen those. Im trying to define and break in a pipeline so I’ll probably see if it is possible to use meshes via the save egg functionality. But in terms of moving forward with seeing if the functional level of the panda library is good enough, that will do the trick.

Cheers!

gerakinis · October 13, 2011, 2:44am

Ok, an update:

I have successfully generated a 128X128 tile mesh, saved it as a bam file and converted it to an egg. Then with the PandAi meshgen tool I have created a navmesh.csv file and followed the instructions from the manual to load everything in.

It works!

Or, at least sort of. I get no errors, the files all load and the character paths upon calling the pathFindTo function. BUT, it only paths to a single location. Here is my code for the pathing

def __getMousePos(self): 
        if base.mouseWatcherNode.hasMouse(): 
            mpos = base.mouseWatcherNode.getMouse() 
            pos3d = Point3() 
            nearPoint = Point3() 
            farPoint = Point3() 
            base.camLens.extrude(mpos, nearPoint, farPoint) 
            if self.plane.intersectsLine(pos3d, render.getRelativePoint(globals.mainCam._gameCam, nearPoint), \
                render.getRelativePoint(globals.mainCam._gameCam, farPoint)):
                print pos3d
                globals.actors['ralph']._AIbehaviors.pathFindTo(pos3d)

That print gives me the correct coords every time I click, but the pathing module sends me to a single destination and/or says ‘couldnt find destination’.

Some random facts:
I used the same egg file for my main mesh and my collision mesh in my meshgen call.
My navmesh.csv prints ‘grid size: 50’ at the top even though the mesh has 128x128 geoms. (pairs of triangles forming squares.)

If you need anymore information please feel free to ask!
Thanks in advance!

PS - here is the code for making the mesh… maybe my construction style is confusing the meshgen tool:

class mesh:
    def __init__(self, tiles):
        self._geomNode = GeomNode('map')
        self._size = (128,128)
        self._tiles = [] 
        self._gvd = GeomVertexData('map_maker', GeomVertexFormat.getV3t2(), Geom.UHStatic)   
        self._vertex_writer = GeomVertexWriter(self._gvd, 'vertex') 
        self._texcoord_writer = GeomVertexWriter(self._gvd, 'texcoord')
        
        for x in xrange(0,self._size[0]):
            self._tiles.append([])
            for z in xrange(0,self._size[1]): 
                geom = Geom(self._gvd)
                prim = GeomTriangles(Geom.UHStatic)
                
                self._vertex_writer.addData3f(x, 0, z) 
                self._texcoord_writer.addData2f(0, 0) 
                self._vertex_writer.addData3f(x, 0, z+1) 
                self._texcoord_writer.addData2f(0, 1) 
                self._vertex_writer.addData3f(x+1, 0, z+1) 
                self._texcoord_writer.addData2f(1, 1) 
                self._vertex_writer.addData3f(x+1, 0, z) 
                self._texcoord_writer.addData2f(1, 0)  
                d = ((x*self._size[0]) + z) * 4
                prim.addVertices(d, d + 2, d + 1) 
                prim.addVertices(d, d + 3, d + 2)
                prim.closePrimitive()
                geom.addPrimitive(prim) 
                i = randint(0, len(tiles)-1)
                self._tiles[x].append( {
                                        'geom':geom,
                                        'prim':prim,
                                        'tile':tiles[i],
                                        'geomIndex': d/4
                                        }
                                      ) 
        rock = loader.loadTexture('assets/img/modifiers/rock.png') 
        rock.setMagfilter(Texture.FTLinearMipmapLinear) 
        rock.setMinfilter(Texture.FTLinearMipmapLinear)
        
        for x in self._tiles:
            for z in x:
                self._geomNode.addGeom(z['geom']) 
                attrib = TextureAttrib.make(z['tile']._tex)
                if z['geomIndex'] % 15 == 0:
                    stage = TextureStage('modifiers')
                    stage.setMode(TextureStage.MDecal)
                    attrib = attrib.addOnStage(stage, rock)
                    
                self._geomNode.setGeomState(z['geomIndex'], self._geomNode.getGeomState(z['geomIndex']).addAttrib\
                                            (attrib))

gerakinis · October 13, 2011, 6:57pm

I guess my options now are to debug the meshgen tool, use blender/maya to generate my maps, or roll in my own pathfinding code.

Not particularly thrilled about any of those =p

gerakinis · October 14, 2011, 2:04am

When you export an egg from maya does it leave the coordinates alone or does it convert them to the panda coordinate space?

The reason I ask is it seems like one possibility for my problems is that my navmesh.csv is generate a structure of nodes on a different plane axis than the one that my model is on. IE my model plane is XZ and the meshgen tool is assuming that the coordinates are actually XY.

If anyone knows off hand that this is likely it may solve my problems. Otherwise I’ll recompile the meshgen tool and switch the coords.

Thanks!

gerakinis · October 14, 2011, 2:45am

Hrm, coords seem to add up.

I got the meshgen tool to recognize my entire 128,128 grid. and the csv file looks accurate with matching coords to the grid node centers. All this required was shifting my mesh to have a center at 0,0,0

So, now everything looks legitimate in the csv file, but ALL calls to actors[‘ralph’]._AIbehaviors.pathFindTo(pos3d)
send ralph on this vector (0,0,-1) and he continues that direction until he hits the last node on in that direction. In other words all paths lead to (0,0,-63.5) in the case that I have a grid of 128X128. Paths are found for almost every click within my grid, but they all direct him to the node that is at the very bottom of the screen.

Le sigh… has anyone else run into something similar to this.
Thanks!

gerakinis · October 14, 2011, 6:09am

Finally got it to work - if anyone is reading this later the major hitching points that are not documented well, or at all are:

You must use the axes that they’ve assumed. Z is your height axis - all data entered here will be ignored. Thus:

class mesh:
    def __init__(self, tiles):
        self._geomNode = GeomNode('map')
        self._size = (128,128)
        self._tiles = [] 
        self._gvd = GeomVertexData('map_maker', GeomVertexFormat.getV3t2(), Geom.UHStatic)   
        self._vertex_writer = GeomVertexWriter(self._gvd, 'vertex') 
        self._texcoord_writer = GeomVertexWriter(self._gvd, 'texcoord')
        
        i = 0
        
        for x in xrange(-self._size[0]/2,self._size[0]/2):
            self._tiles.append([])
            for y in xrange(-self._size[1]/2,self._size[1]/2): 
                geom = Geom(self._gvd)
                prim = GeomTriangles(Geom.UHStatic)
                
                self._vertex_writer.addData3f(x, y, 0) 
                self._texcoord_writer.addData2f(0, 0) 
                self._vertex_writer.addData3f(x, y+1, 0) 
                self._texcoord_writer.addData2f(0, 1) 
                self._vertex_writer.addData3f(x+1, y+1, 0) 
                self._texcoord_writer.addData2f(1, 1) 
                self._vertex_writer.addData3f(x+1, y, 0) 
                self._texcoord_writer.addData2f(1, 0)  
                prim.addVertices(i, i + 2, i + 1) 
                prim.addVertices(i, i + 3, i + 2)
                prim.closePrimitive()
                geom.addPrimitive(prim) 
                j = randint(0, len(tiles)-1)
                self._tiles[x+self._size[0]/2].append( {
                                        'geom':geom,
                                        'prim':prim,
                                        'tile':tiles[j],
                                        'geomIndex': i/4
                                        }
                                      ) 
                i += 4
                
        rock = loader.loadTexture('assets/models/maps/img/modifiers/rock.png') 
        rock.setMagfilter(Texture.FTLinearMipmapLinear) 
        rock.setMinfilter(Texture.FTLinearMipmapLinear)
        
        for x in self._tiles:
            for z in x:
                self._geomNode.addGeom(z['geom']) 
                attrib = TextureAttrib.make(z['tile']._tex)
                if z['geomIndex'] % 15 == 0:
                    stage = TextureStage('modifiers')
                    stage.setMode(TextureStage.MDecal)
                    attrib = attrib.addOnStage(stage, rock)
                    
                self._geomNode.setGeomState(z['geomIndex'], self._geomNode.getGeomState(z['geomIndex']).addAttrib\
                                            (attrib))

Is my new trial code for writing the mesh. Note that I am now shifting the mesh to center it on the origin (the meshgen tool ignores translations) and that I am also only using the x and y values of the positions. Stuff in z is written to the egg and thte csv files but totally ignored. This also means you have to shift your plane for mouse click collisions.

globals.actors[‘ralph’]._AIbehaviors.pathFindTo(pos3d, ‘addPath’)

If you don’t use ‘addPath’ you will never get more than a single successful call to pathFindTo. Maybe I just missed it, but that wasn’t clear to me from the docs. EDIT: they say ‘if you want to pathfind continuously’ you should use ‘addPath’ this made me think that it would immediately need a new destination. This really means if you want to pathfind with the same character again in the future, ever.

With those stipulations I have a very rudimentary path finding system in place. I hope this long thread of self-posts helps someone in the future…