PandaSteer 2

Edit 2009-05-16: I’ve uploaded the all latest PandaSteer code (including contributions) to my github account: github.com/seanh/PandaSteer/ Thanks to Astelix for packaging the code.

Screenshot

Movie

I’ve been updating my previous steering behaviors demo to steer animated, 3D characters over uneven terrain. These steering behaviors can be used to create point-and-click keyboard or mouse controlled player avatars, or mobile non-player characters. They allow a character to move around an environment in an intentional way – going to some location, following or pursuing or evading another character, and avoiding obstacles and collisions with other characters.

There’s still work to be done on this, particularly some efficiency considerations, but they say release early, release often, so here it is. So far I have seek and flee, pursue and evade, arrive, follow, wander, and collision avoidance translated from the old version. Still need to do obstacle avoidance. Update: the code is much more efficient now (thanks to ynjh_jo and drwr) and obstacle avoidance steering is finished

PandaSteer is plugin-oriented, so you can easily write your own steering demos and steering behaviors with PandaSteer, without having to modify PandaSteer itself.

Thanks to ThomasEgi, pro-rsoft and others for their help on the IRC channel, and ynjh_jo, drwr and others on the forums. And thanks to tiptoe, ynjh_jo and cyan for their work in this thread which I’ve studied and found very useful.

As well as steering, this demo also has:

• The diamond-square algorithm for heightfield generation, implemented in Python.

• Using Panda’s Egg interface to construct a terrain model

• Lighting and fog

• Using Panda’s collision system

• Starting and stopping different Actor animations and varying the animation playrate depending on what the character is doing

• Keyboard controls, including controlling the camera

• and probably other stuff I’m forgetting

Don’t actors use loadModelCopy as default ?

Have you visualize the collisions ? “base.cTrav.showCollisions(render)”
It would help seeing these flaws :

1. only the last defined Character has collision detection. Increase the terrain height and you’ll see. (->FIXED)
2. collision ray’s origin too low, the origin too easily sinks under the terrain (->FIXED, now using segment to avoid collision detection against many more triangles underneath the character)
3. collision (ray) against the actor’s geometry (->FIXED)
4. TOTAL[memory leakage (5MB in each complete plugins cycle) + performance loss upon plugin switch], garbage-collecting doesn’t work, because you only use detachNode on Character instances, not removeNode. To use removeNode, first remove :

• the colliders and floorhandlers
• characters’ step task
• the actor
  To remove them, first, the references must be kept. (->FIXED)

new steer.py

Wow, great work ynjh_jo!

I’ve merged your fixes into my branch, they were spot on, every one of them

Your fixes have revealed another serious problem though: using a CollisionSegment (or CollisionRay) and CollisionHandlerFloor for each Character seems to be very inefficient.

On my machine (2.4GHz, 1GB RAM, Nvidia Quadro4 900XGL, using proprietary Nvidia driver on Ubuntu 6.10) the “wandering pedestrians” demo, which has 10 Characters, now runs at 5fps. If I disable the CollisionFloorHandlers it runs at a nice 30.5fps. Even the “arrive” demo with one character runs at about 30fps with the CollisionHandlerFloor, about 70fps without.

Ultimately I’d like to have 10-12 Characters, each using different models, and on a much larger terrain with some static models for obstacles too, and it’ll need to run at at least 15fps, preferably 30fps. So the current situation is not encouraging.

I tried having a single global CollisionHandlerFloor shared by all Character’s, with each Character adding its own CollisionSegment. But this was no improvement.

Surely colliding a single line segment against some simple terrain should be pretty cheap? There must be a more efficient way to do this?

Perhaps I can write my own query function which returns the Z-position of the terrain at a given (X,Y)-position, and simply use this instead of Panda’s collision system.

But I’d appreciate any help with this issue.

More improvements to come from me too! Perhaps when I recover from the cold I’m coming down with…

In my experience, whenever I’ve had any problems with performance of collisions, it’s generally because my collision solids are attempting to collide with far more than I thought they were.

How simple is your floor terrain? Dozens of polygons? Or thousands? Thousands of polygons look nice for rendering, but you really only want to collide with dozens. If you haven’t done it already, you may need to have a reduced-complexity version of your floor for the purposes of collisions.

Also, the showCollisions() step is useful for lighting up the polygons that it’s testing against. Make sure that it’s only a handful.

David

Hmm… I had wondered if I would need to generate my terrain to be more efficient. But it is a pretty small and simple terrain in this demo, dozens or maybe hundreds of polys, and each CollisionSegment is only colliding with a handful.

Screenshot showing wireframe and collisions: panda3dprojects.com/chombee/ … isions.jpg

Really? It looks like a 32 x 32 grid in the screenshot. That’s 1,024 quads–2,048 triangles. And since it’s all one mesh, the collision traverser will have to test each of those 2,048 trianglse against each CollisionRay.

At the very least, you should subdivide the mesh into several smaller pieces, so the collision traverser can rule out large parts of it based on the bounding volume.

David

how about adding a internal octree-like structure for collidable meshes if a certain number of vertices is reached? subdivide them in groups and subdivide them again if a sub-group is still above the limit. (just as idea for some future panda versions).
could help with the collission detection of detailed meshes.
might be intresting for culling/clipping of large objects like environments etc. so you wouldnt have to splitt it ourself while creating the stuff.
my idea would’ve been something like
model = loader.loadOctreeModel(“path/to/model”,optional vertex count for splitting groups)

This is the result (my edited code above) on my 2.8GHz HyperThreading :

• 1 arrive char : 70 fps
• 10 wandering chars : 8 fps

Then I created 2 terrains, 1 for rendering, 1 for collision. The one for collision consists of a bunch af geomnodes, 1 geomnode built of simply 1 rectangle.

Result :

• 1 arrive char : 165 fps
• 10 wandering chars : 28 fps

in makeTerrain (scene.py):

    # Now create a terrain model from the heightmap.
    tnp = render.attachNewNode("Terrain")
    data4Rendering = EggData()
    vp = EggVertexPool('Terrain vertex pool')
    # for collision geometries
    tCollNP = tnp.attachNewNode("Terrain4Collision")
    for i in range(0,len(midpoints)-1):
        for j in range(0,len(midpoints)-1):
            # vertexpool for 1 collision geomnode
            vCollpool = EggVertexPool('TerrainCollision vpool')
            bl = Point3D(i,j,midpoints[i][j])
            tr = Point3D(i+1,j+1,midpoints[i+1][j+1])
            br = Point3D(i+1,j,midpoints[i+1][j])
            tl = Point3D(i,j+1,midpoints[i][j+1])
            poly, polyColl = makeRectangle(vp,vCollpool,bl,tr,br,tl)
            data4Rendering.addChild(poly)
            # data for collision terrain, 1 rectangle per geomnode
            data4Collision = EggData()
            data4Collision.addChild(polyColl)
            rectNode = loadEggData(data4Collision)
            tCollNP.attachNewNode(rectNode)
    pandaNode = loadEggData(data4Rendering)
    tnp.attachNewNode(pandaNode)
    return tnp, tCollNP

makeRectangle (scene.py):

def makeRectangle(vp,vCollpool,bl=None,tr=None,br=None,tl=None):
    if bl is None: bl = Point3D(-10,-10,0)
    if tr is None: tr = Point3D(10,10,0)
    if br is None:
        l = tr.getX() - bl.getX()
        br = bl + Vec3D(l,0,0)
    if tl is None:
        w = tr.getY() - bl.getY()
        tl = bl + Vec3D(0,w,0)
    poly = EggPolygon()
    polyColl = EggPolygon()
    for corner in [bl,br,tr,tl]:
        v = EggVertex()
        v.setPos(corner)
        vC = EggVertex()
        vC.setPos(corner)
        poly.addVertex(vp.addVertex(v))
        polyColl.addVertex(vCollpool.addVertex(vC))
    poly.recomputePolygonNormal() # Use faceted not smoothed lighting
    return poly, polyColl

SteerTest (steer.py) :

        # Make some terrain and colour, scale and position it.
        tnp, terrain4Coll = makeTerrain(h=8)
        tnp.setColor(0.6,0.8,0.5,1)
        tnp.setPos(tnp,-50,-50,0)
        tnp.setScale(3)
        terrain4Coll.setCollideMask(floorMASK)
        terrain4Coll.hide()

It’s BLAAZZZZIN’ now !

Note that, as long as you are creating geometry specifically for collisions, you might as well create CollisionNodes instead of GeomNodes (which are optimized for collisions instead of rendering, and so are faster for the collision test).

Easiest way to do this, since you are already using the egg library, is to put the CollisionPolygons under a GroupNode, and add the “barrier” object type to that group, like this:

data4Collision = EggData()
gn = EggGroup('group')
data4Collision.addChild(gn)
gn.addObjectType('barrier')
gn.addChild(polyColl)
rectNode = loadEggData(data4Collision)

Note that optimal number of quads per group is probably a bit more than one.

David

Well, I was planning to rewrite the terrain model generation function to group the nodes in an octree, but it looks like you are well ahead of me! Those framerates sound fantastic ynjh_jo, and thanks for the hints drwr

I think I get the gist of what you have done with the terrain generation, but I won’t be sure I understand it until I can run the code and visualize your collision terrain. I’ll try it out next time I’m at my (fast) computer.

I have been working on improvements of my own, making the demo interactive through mouse-clicks to control the characters, and updating the obstacle avoidance behaviour from the last version. It’s simple enough with the existing code in vehicle.py to get some obstacles into the scene and get the characters avoiding them, but although I think the steering is fine the collision detection routines I wrote for it are not too robust I feel it needs to be updated to work with Panda’s collision detection system instead, which I’m starting to get the hamg of. I should have a significant update before too long. In the meantime, feel free to jump ahead of me

Thanks again for getting involved! You’ve really improved this code. When it’s finished I think this code could be a really great thing to have available on the forums. As well as the instructive steering behaviours demo and code for reuse, I could put together an example game using it. I’m thinking of a scene with some terrain, trees, buildings, streetlamps, etc., and about 12 characters with different models wandering around (or maybe it could be some sort of weird clone town of Ralph people). The player controls one character by pointing and clicking and the camera follows, and the player can walk up to any of the non-player characters and initiate a ‘conversation’, which would be drawn in speech bubbles using DirectGUI. The player could give the NPCs instructions like ‘Follow character X’, ‘Chase character X’, ‘Run away from character X’, ‘Go get X and bring it/him/her to me’, etc. So it wouldn’t really be much of a game, but it would be a pretty good base on which to build an adventure-style game.

I splitted the collision terrain into small pieces, currently 3x3 grid of quads, and it’s adjustable.
screenshot showing the rendered & randomly colored 3x3 quads collision nodes.

    # Now create a terrain model from the heightmap.
    tnp = render.attachNewNode("Terrain")
    data4Rendering = EggData()
    vp = EggVertexPool('Terrain vertex pool')
    # nodepath to hold collision nodes
    tCollNP = tnp.attachNewNode("Terrain4Collision")
    # supply the eggGroup & eggVPool for the first node
    vCollpool = EggVertexPool('TerrainCollision vpool')
    collGroup = EggGroup('collQuads')
    collGroup.addObjectType('barrier')
    # we use (numQuadGrid x numQuadGrid) quads for 1 collision node
    numQuadGrid=3
    # the modulo of (size-2)/numQuadGrid, to mark when the quads must be built into 1 geom
    edgeMod=(size-2)%numQuadGrid
    for i in range(0,len(midpoints)-1, numQuadGrid):
        # limit nextIrange to avoid it from jump over the edge
        nextIrange=min(numQuadGrid,len(midpoints)-1-i)
        for j in range(0,len(midpoints)-1):
            for nextI in range(0,nextIrange):
                bl = Point3D(i+nextI,j,midpoints[i+nextI][j])
                tr = Point3D(i+nextI+1,j+1,midpoints[i+nextI+1][j+1])
                br = Point3D(i+nextI+1,j,midpoints[i+nextI+1][j])
                tl = Point3D(i+nextI,j+1,midpoints[i+nextI][j+1])
                poly, polyColl = makeRectangle(vp,vCollpool,bl,tr,br,tl)
                data4Rendering.addChild(poly)
                # add a quad for collision terrain
                collGroup.addChild(polyColl)
                # build the collision node geom
                if j%numQuadGrid==edgeMod and nextI==nextIrange-1:
                   data4Collision = EggData()
                   data4Collision.addChild(collGroup)
                   rectNode = loadEggData(data4Collision)
                   cNP=tCollNP.attachNewNode(rectNode.getChild(0).getChild(0))
                   # uncomment the next line to see the collision geom
                   #cNP.show()
                   # supply the eggGroup & eggVPool for the next node
                   collGroup = EggGroup('collQuads')
                   collGroup.addObjectType('barrier')
                   vCollpool = EggVertexPool('TerrainCollision vpool')
    pandaNode = loadEggData(data4Rendering)
    tnp.attachNewNode(pandaNode)
    return tnp, tCollNP

Thanks for the pointer, David, now it can hit 39 fps !

ynjh_jo: just tried out both of your efficiency improvements. Although I’m not sure I understand your code exactly, it’s a major enhancement! I’m getting a smooth 30FPS with 10 characters on screen at once now, and 65-75FPS in all the other demos (with 1-3 characters). Fantastic work!

Let me see if I understand your enhancements correctly.

So for your first improvement, you create two terrain models, one for rendering and one for colliding, instead of just using the renderable terrain for collisions. The collision terrain is constructed slightly differently from the rendering terrain, because the render terrain is all one big model, it’s all in one EggData. Whereas with the new collision terrain, you made a separate model, a separate EggData and EggVertexPool, for every four-vertex block of the terrain. And this is the reason for the speed improvement? Do I have it right?

Then Panda would only need to test the bounding box of each of those collision models, and can discard most of them without actually having to test against the polygons, right?

And for your second improvement, if I understand correctly, you have collected every 3x3 group of collision models together under an EggGroup? This allows Panda to discard entire EggGroups at once by testing against the bounding box of the whole group, so is even faster. Do I have it right?

I think that if even more efficiency was needed for a larger terrain, these EggGroups could be further collected into groups of EggGroups, forming a hierarchical structure like an octree. But that doesn’t seem necessary at the moment, as the framerates I’m already getting with your improvements are more than enough.

Thanks again for the great work!

Yes, I believe Panda’s collision system works on geomnode level, checking the bounding vol first before testing any intersection with the polys.
uhm…, sorry, I edited the last code above, check it again if you’d like to compare it.

I just noticed that the number of cracks increases as the hilliness. Then I realized it’s not your code’s fault, it’s the work of Panda’s auto triangulation against concave polygons. Some of the quads must not be triangulated correctly.
So, I just created those tris manually, and no more cracks now. Weird, this old flaw is still here…

Sorry, which code did you edit? I don’t see it.

It’s the 3x3 splitting. Lucky me, it wasn’t exposed then…

Right, uploaded a new version of the whole thing: Download.

The download link in my first post has been updated too.

This new release includes all of ynjh_jo’s improvements up to this point, plus:

• Now supports mouse-clicking. Click event is passed to plugin. Some of the plugins allow you to control a character by clicking, others ignore it. Picking code is taken from Tiptoe, Cyan and ynjh_jo elsewhere on this forum.

• For some steering behaviours the target that the character is steering towards is drawn (as an orange jack-o-lantern). This is achieved by merging class Marker from some code that Tiptoe, Cyan and ynjh_jo worked on elsewhere in this forum

• Plugins are now loaded in order of filename, so you can control the plugin order by changing their filenames

• Added pandaSteerPlugin.py with ‘abstract’ class PandaSteerPlugin that all plugins should inherit from (just structural cleanup really)

• Other minor changes and bugfixes

• Correction of some outdated comments

I’m still working on porting the obstacle avoidance code.

Many thanks to everyone that’s given tips or enhancements or commented on IRC, or whose code I’ve made use of. Wouldn’t be here without the Panda3D community!

That’s nice, but…you haven’t fixed the terrain cracks !

                poly1,poly2, polyColl1,polyColl2 = makeTriangles(vp,vCollpool,bl,tr,br,tl)
                data4Rendering.addChild(poly1)
                data4Rendering.addChild(poly2)
                # add a quad for collision terrain
                collGroup.addChild(polyColl1)
                collGroup.addChild(polyColl2)

I changed makeRectangle to makeTriangles, added 1 more loop of course :

    poly1 = EggPolygon()
    poly2 = EggPolygon()
    polyColl1 = EggPolygon()
    polyColl2 = EggPolygon()
    for corner in [bl,br,tr]:
        v = EggVertex()
        v.setPos(corner)
        vC = EggVertex()
        vC.setPos(corner)
        poly1.addVertex(vp.addVertex(v))
        polyColl1.addVertex(vCollpool.addVertex(vC))
    for corner in [bl,tr,tl]:
        v = EggVertex()
        v.setPos(corner)
        vC = EggVertex()
        vC.setPos(corner)
        poly2.addVertex(vp.addVertex(v))
        polyColl2.addVertex(vCollpool.addVertex(vC))
    poly1.recomputePolygonNormal() # Use faceted not smoothed lighting
    poly2.recomputePolygonNormal()
    return poly1,poly2, polyColl1,polyColl2

… and remove “terrain4Coll.hide()” (in steer.py), or else the collision terrain would be never showed up (it overrides the show() in scene.py).

Ok, updated again: download.

Added obstacle avoidance steering behaviour and a couple more plugins to demonstrate it. The code is pretty rough at the moment but obstacle avoidance works really well with Panda’s collision system, it’s very fast and robust, I’m pretty happy with it.

I used a Panda CollisionTube, projected ahead of each character, to detect upcoming collisions with obstacles, represented as Panda CollisionSpheres. Since the manual says CollisionTube is good only as an into object I used it as such, and used the static CollisionSpheres as from objects, even though conceptually, the CollisionTube is the thing that’s moving so would seem the logical choice as the from object. When a collision occurs between a character’s CollisionTube and a CollisionSphere, a steering force is applied to steer away from the obstacle.

Some work needs to be done:

• If the target a character is trying to arrive at (for example) is inside an obstacle the character will run round and round the obstacle

• Worse, if the target is just in front of an obstacle, the character may arrive at the target and stop, but then the CollisionTube may be colliding with the obstacle, which will cause the character to run around needlessly trying to avoid the obstacle

The best way to fix this I think would be to vary the length of the character’s CollisionTube frame-by-frame according to the character’s speed, so that when the character comes to rest at a target location the CollisionTube will shrink to a sphere around the character and not collide with any obstacles beyond the target. I had trouble implementing this though and have given up for now.

The collision avoidance (that is, avoiding other moving characters, not static obstacles) behaviour could be improved a bit. It does not use pandas collision system to detect upcoming collisions but my own code, and collisions seem to occur fairly often with a lot of characters in a small space. Is it possible to collide two CollisionTubes against eachother? If so, the characters CollisionTubes could be used to detect character-character collisions also.

The ‘follow’ steering behaviour needs improvement. The character needs to follow a good distance behind the target so as not to collide with the target, needs to avoid blocking the path of the target, and needs to avoid bumping into other followers. Ultimately it should be more like the demo here: red3d.com/cwr/steer/LeaderFollow.html

yjnh_jo: thanks a lot for your fix for the cracks in the terrain. It’s definitely going to be crucial for me in the future. I haven’t had time to merge the fix into my own download yet, but will do so as soon as I can.

Thanks, and enjoy!

I’ve downloaded your steer code. Just want to say great work. I have a couple of questions/suggestions.

-The obstacle class currently only allows spheres. it seems like boxes or rectangles would be more useful for many applications.

-There are many applications for the current 2D steer class. Have you thought about making a separate 3D steer class with the same behaviors?

keep up the good work.

Another update. The Panda3DProjects site where I put all my downloads seems to be down right now, so this download is on my own server: download.

Changes:

• I fixed a bug in the collision avoidance code. The characters thought they had radius 1, but it should be more like 3. They’re much better at not bumping into each other now, Collisions are pretty rare even in the very crowded demo.

• I merged ynjh_jo’s latest fix, preventing cracks from appearing in the terrain. If you run scene.py you’ll get a test scene that generates 4 terrain models with different hilliness values and chains them together into one terrain. There’s some very incomplete DirectGUI stuff thrown in for playing with the fog and lighting. There are no cracks in the models now. Thanks again ynjh_jo!

(P.S. to get the steering demo, run steer.py).

I feel obliged to point out again that this steering code is heavily derived from the C++ steering code of OpenSteer. A fair number of my functions, particularly with collision avoidance steering, are just translated from opensteer to python/panda and then tuned.

PandaSteer seems to be working pretty well now. The code still needs much cleaning up inside, and I’m sure there are bugs I’ve yet to find. There is the issue of the Character’s CollisionTube varying in length frame by frame depending on the Character’s speed, that should be possible with CollisionTube.setPointB but I haven’t got it right yet. That would be a good fix.

Enjoy!

ynjh_jo: the terrain looks different now with your fix. It’s made of pairs of triangles instead of rectangles, and so is shaded differently, which slightly spoils the blocky graphical style I was going for. Is it possible to build the terrain out of rectangles instead of triangles, and not get cracks? Or does your fix rely on changing to triangles instead of rectangles?