PandaSteer 2


#15

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


#16

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! :slight_smile:


#17

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).


#18

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! :slight_smile:


#19

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.


#20

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?


#21

mavasher: thanks for trying out the code and getting back to me :slight_smile:

In theory the Character’s should be able to steer to avoid any ‘from’ object in the Panda collision system, which could be a sphere, inverse sphere, or plane, and you could use six planes together to make a cube or rectangle. It is just a case of writing new obstacle classes on the model of the existing sphere obstacle class. All that matters to the Character is that it gets a CollisionEvent with a position and surface normal for the collision from the Panda collision system, so you shouldn’t need to edit Character to get it to steer round obstacles of different shapes. In theory.

Personally I think spheres will work fine. You can roughly make any shape you want by chaining many spheres together.

For my purposes I only need 2D steering over uneven terrain. If you wanted 3D steering for flying vehicles and the like, much of the code would translate very easily, just replace Vec2 with Vec3, but some of the functions in vehicle.py and steerVec.py contain linear algebra that may get a lot more difficult in 3D compared to 2D. I’m probably not going to do 3D myself as I don’t need it.


#22

Alright, go back to your makeRectangle, it can be fixed without creating the triangles directly.
First, we have to check the triangulation process, if it failed, simply reverse it’s vertex order and disable backface culling for that quad only. Thus we still get (double-sided) convex quad, not concave one :laughing: .
Insert these lines after creating the quad :

    egn=EggGroupNode()
    if not poly.triangulateInto(egn,0):
       print 'triangulation failed...',
       poly.reverseVertexOrdering()
       poly.setBfaceFlag(1)
       polyColl.reverseVertexOrdering()
       polyColl.setBfaceFlag(1)
       print ' , but fixed :)'

#23

I’ve been playing around with animations switch. I think synchronizing the next anim’s start frame to the current one’s frame must help to avoid sudden weird body parts movement, especially the legs. No blending here, so it’s still rough.
And I tried playing the walk anim when switching to stand pose, instead of simply posing the actor. The start frame uses the walk anim’s current frame, but “mirrored” relative to the middle of the anim’s number of frames. It’s to get the start frame for the shortest anim length to the stand pose frame (i.e. frame 6 for ralph, as you’ve used since the beginning), while maintaining body parts’ position as close as possible to the current walk frame.

To get the most acceptable result, I switched it to stand pose after the velocity length went below .05. Less than that, the actor will slide for a while (due to small playrate) before playing the anim.

    def storeLastPose(self):
        currAnim=self.actor.getCurrentAnim()
        numFrames=self.actor.getNumFrames(currAnim)
        animFrame=self.actor.getCurrentFrame(currAnim)
        self.lastPose=float(animFrame)/float(numFrames)
        self.actor.stop(currAnim)
        #print currAnim, self.lastPose

    def loopFromPose(self,animName):
        self.actor.pose(animName, frame=self.lastPose*self.actor.getNumFrames(animName))
        self.actor.loop(animName, restart=0)

    # FSM State handlers. Called when transitioning to a new state.
    def enterRun(self):  self.loopFromPose("run")
    def exitRun(self):   self.storeLastPose()
    def enterWalk(self): self.loopFromPose("walk")
    def exitWalk(self):  self.storeLastPose()
    def enterStand(self):
        standPoseFrame=6    # frame 6 (the most acceptable stand pose)
        numFrames=self.actor.getNumFrames("walk")
        lastFrame=self.lastPose*numFrames
        # "mirror" the frame to bring it closer to the most acceptable stand pose
        if lastFrame>.5*(numFrames-1):
           lastFrame=numFrames-1-lastFrame
        #----------------------------------------------
        frameDiff=standPoseFrame-lastFrame
        # if already at stand pose, don't do anything
        if frameDiff==0:
           return
        # forward animation playback
        if frameDiff>=0:
           fromFrame=lastFrame
           toFrame=standPoseFrame
        else:
        # backward animation playback
           fromFrame=standPoseFrame
           toFrame=lastFrame
        #----------------------------------------------
        playDir=2*frameDiff/numFrames
        self.actor.setPlayRate(playDir,"walk")
        self.actor.play("walk", fromFrame=fromFrame, toFrame=toFrame)
        #print 'switch to stand pose'

#24

Aow…, after you added collision sphere around each char and added sphere obstacles, why haven’t you done clean removal of them ? Simply removing/detaching them doesn’t do any removal, because the traverser is still using them ALL, so there are still references to each of them.
To view the report, try to print out the number of currently active colliders :

        print 'ACTIVE COLLIDERS :',base.cTrav.getNumColliders()

at the very bottom of restart method.
Then rapidly restart the plugin or switch to the next one.
And you’ll see it’s increasing 'till thousands (10 chars or +obstacles plugin), and keep watching your memory meter to see your free mem crawling down.

All you need to do is removing them from the traverser :

  • in characters removal loop :
            base.cTrav.removeCollider(character.spherecnp)
  • in obstacles removal loop :
            base.cTrav.removeCollider(obstacle.cnp)

If no leakage, there should be only [ numChars*2 (sphere&segment) + numObstacles + 1 (mouse ray) ] active colliders.
Running memory meter all the time is very helpful and makes me feel better. :smiley:


#25

Thanks a lot ynjh_jo, more fantastic work!

Okay, another update: download. (I’ve moved the download back onto panda3dprojects.com, which seems to be up and running again).

Merged the last three improvements from ynjh_jo, and a couple from me:

  • Make the terrain out of rectangles again, not triangles, triangulation of polygons fixed in makeRectangle. Thanks ynjh_jo.

  • Improvement to the animation of Ralph from ynjh_jo (see ynjh_jo’s explanation above).

  • Fix for memory leak from ynjh_jo: Destroy CollisionSphere and CollisionTube of Character and CollisionSphere of Obstacle when destroying Characters and Obstacles. This code really belongs in the Character and Obstacle classes, not in the class that is using Character and Obstacle.

I’ve made some notes about refactoring the code and have a plan ready, there are many changes I want to make when I have time that will make the code much nicer on the inside, but nothing really major.

  • Scaled the size of markers used to show characters’ targets, big enough to see but not so big as to get in the way as before
  • Fix wrapping of characters when they leave the terrain (it’s more accurate now)
  • I think I recently shrunk the radius of Character’s CollisionTube from 3 to 2.5 (making it fit Ralph more tightly). I don’t know why but this seemed to introduce a bug where, in the obstacle avoidance demos, characters would get stuck running round and round the largest obstacle, or even get inside the obstacle. So I changed the radius of the tube back to 3 again and this doesn’t happen.

I have to concentrate on some non-Panda3D work now, maybe for a month or two, so major updates might not be coming for a while, though I can still do minor fixes if people post them or point out bugs. I’ll definitelty continue to work on pandasteer full time soon.


#26

Minor update, a few more fixes and improvements from the amazing ynjh_jo and me: download (Update: removed imports of no-longer-existent obstacle.py)

Some minor refactoring and tidying up from me (chombee) and fixes from ynjh_jo. The major refactoring jobs are still to be done.

Me:

  • Split out makeHeightMap (diamond-square algorithm) from makeTerrain
  • Set self.reticle = None at the start of self.step() in Vehicle, for each
    frame, reticle is only drawn if steering behaviour used that frame sets
    reticle. Prevents reticle from being drawn in the wrong place some frames.
  • Got rid of fromCol function in steer.py (not needed)
  • Added destroy functions to SphereObstacle and Character
  • Removed toggleSolids function in steer.py (not needed, in time
    toggleCollisions should become a general toggleAnnotation function).
  • General tidying of code and comments

ynjh_jo:

  • Character should switch to the walk animation at speed .05 or below, not .005
  • Don’t need to remove character.tube from the collision traverser in
    character.destroy() (we never added it in the first place).
  • Fixed comment describing what’s going on with the triangulation workaround in makeQuad()

Note that there’s a detailed changelog in changelog.txt in the download.


#27

Man, I can just say - awesome, breathtaking.

Keep up the good work! :slight_smile:


#28

Chombee,

I’ve been working on a 3D version of your code. Things are going well, your code was written such that it’s been pretty easy.

I noticed in your latest version you’re referencing the Panda collision system instead of your own collision detection.

Using your older collision system as a guide I rewrote the code so that five probes were produced (forward,right,left, up, down) for collision detection instead of the three that Vehicle.py had.

My point in telling you all this is that I see that you’re using collision tubes now. It seems like with more vehicles you’re going to have some serious performance issues. I wonder if a five-probe-CollisionRay system would work better for performance. I have code for generating four probes each 45 degrees out from the forward vector like a pyramid with the position as the apex.

Also, a somewhat unrelated question. It looks like in the code that you’re assigning all the collision objects to the collision Traverser- It looks like the SphereObstacles are “from” objects instead of “into” objects. Is there a reason for this?


#29

Great! I can’t wait to see it :slight_smile: My code is due for a refactoring, it will be much more clearly written when I have time to finish it up! Maybe you can implement some of the steering behaviours that I haven’t yet, such as path following, proper leader following and flocking (separation, alignment and cohesion).

Possibly. I’ll worry about that if and when I get performance issues. There’s no problem with 10 characters and half a dozen or so obstacles, as in the last demo in the current version, so that’s a good sign. I’m using Panda’s collision system to collide spheres into tubes, and spheres are the fastest type of collision solid, so I’m hopeful that it will be quite fast. And my experience with the collision ray used to keep my characters feet on the ground and the help I got with the efficiency of that from drwr and ynjh_jo (in this thread) tells me that the key efficiency concern with collisions is to make sure that each collision solid is only being tested against the collision solids it really needs to be tested against, and not a single one more. That and arranging the collision solids in an efficient way in the scene graph, like an octree.

But switching from tubes to rays might be an option for greater efficiency, yes, although I want to stick with tubes if at all possible because they are just perfect for the job. Another possibility would be to use planes, each tube would now be a cuboid represented by six collision planes, that might be fast.

Yeah, Panda doesn’t support using tubes as into objects, only as from, but spheres can be either from or into. So I know it’s a little counter-intuitive, but the tubes are the from objects because they have to be.

Any other questions about the code please feel free to ask!


#30

Come to think about it maybe it would just make the system more complex processing-wise to have to test 5 simple objects (rays) instead of 1 slightly more complex object (a tube).

As far as new behaviors I could probably help. I’m not a programmer really. I’m a medical student and I’ve just been playing around with panda. I can probably help more with the math than the actual programming.

Path Following: I’m not sure how you would want to implement this. I’d probably pass a list of waypoints to the behavior. Then, pass a variable for whether or not to loop the waypoints or finish at the last one. Once the vehicle got within a certain distance that waypoint could be declared “cleared” and the target could move to the next one. This could be fairly easy. Use “seek” and “obstacle avoid” and cycle through waypoints as the targets.

Proper leader following: You’ve got most of this coded already. The separation is the only thing that really needs to be added. Separation would probably involve having a larger collision sphere and looking for collisions then applying a force normal to the collision surface.


#31

Yeah that would work, but would not be quite as good as the implementation I linked to. The vehicles would move in a more or less straight line toward each waypoint then turn suddenly as they passed each waypoint.

What you need for a better implementation is a Path class with a nearestPointOnPath(Point3) method that returns the nearest point on the path given some point in space. The vehicle makes a prediction of its future position x time units in the future, with x increasing or decreasing depending on vehicle speed (using the already implemented Vehicle.predictFuturePosition()). The vehicle calls path.nearestPointOnPath(futurePos) on the path that it’s following. If the distance between the vehicles predicted position and the nearest point on the path from that future position becomes greater than some constant value (the width of the path) then the vehicle corrects by seeking toward a point further down the path (obtained by calling path.pointFurtherAlong()). That would produce a nice smooth sort of path following like here: red3d.com/cwr/steer/PathFollow.html and any object with a nearestPointOnPath and a pointFurtherAlong method can be used as a path to follow.

You could probably implement such a Path class by defining a path as a series of waypoints, and interpolating between waypoints to implement the nearestPointOnPath and pointFurtherAlong methods. That would produce a polyline path just like the one in the demo above.

Yeah this one should be really easy picking right now. Separation steering would be needed and I agree with you about how it should be implemented. You’d also need a ‘get out of the way’ behaviour, where if a follower vehicle finds itself inside the CollisionTube of the leader vehicle it gets out of the way fast. Then I think you just combine steering behaviours with the following priority: 1. Get out of the way 2. Separation 3. Arrival, with the target being a point behind the leader.


#32

maybe you can by-pass the whole function to search for the closest point and go directly to finding the distance between the line and the point. http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

You’re still going to have to cycle through the waypoints. If you look at the JAVA applet there are points when the future point is around the corner from the vehicle but still within the path, so for the vehicle to actually travel to that point it would cut through the corner. The applet still checks the point against the correct line segment in the path and not the path in its entirety.

I would have tried to code some of it today but I was busy.


#33

Just digged this again.

OMG, how come ? Tell me, how did you do it ?
in Vehicle.step :

        tube=self.tubenp.node().getSolid(0)
        tube.setPointB(Point3(tube.getPointA()+Point3(0,15.*self._velocity.length(),0)))

Since the tubes’ length are not uniform anymore, it looks more natural. The slow char wouldn’t steer away excessively before reaching make-sense distance to the obstacle.

It’s not possible, since nobody has written tube-tube intersection for Panda yet. There are open source physics engines which have anything-anything intersection algo, if you like to “learn” it.
However, you have created a sphere around each char, right ? What is it used for ? Why don’t you use it to collide with the tube ? Just need to change it’s bit mask.

  1. cleanup() the FSM before deleting the actor to prevent exception error

  2. there is still memory leakage at vehicle level, around 100 KB for each restart (10/12 chars). It’s the neighbors list !

        for v in self.plugins[self.plugin].vehicles:
            v.neighbors = None

It’s not critical, but kept scratching my head.


#34

Sweet! :smiley:

Thanks alot ynjh_jo, I’ll be checking out those suggestions as soon as I’m next at my development machine (tomorrow, probably).

1., I think I was setting both the X and Y values of the CollisionTube’s point B according to speed, not just the Y value as you do, and this was causing the tube to vary in a really indescribable but wrong way because I had evidently made some mistake. I may also have been confused about the local<->global transform. I can see how your way would be the correct answer…

I can’t wait to see this!

  1. I have to look back at the code, but I think you’ve picked up on an old comment that I should have removed. Collisions don’t occur between characters very often any more, since I fixed a bug in the collision avoidance code. Actually before that I did try colliding the CollisionTubes of characters against the CollisionSpheres of characters and then just employing the same steering as used to avoid static obstacles to get moving characters to avoid eachother. This doesn’t work very well however, the characters tend to steer into eachother and otherwise do the wrong thing. It turns out collision avoidance steering is quite different from obstacle avoidance steering. Steering to avoid collisions involves comparing the velocities of both characters to find out if they will collide in the future, and if so steering to avoid the point of collision, so comparing one character’s velocity (CollisionTube) against the other’s position (CollisionSphere) would not achieve the same effect.

  2. Cheers!

  3. Thanks again. What exactly do you use to spot all these memory leaks by the way? Do you have some utility?