PandaSteer 2

[chombee]

Ok, new revision uploaded: download.

• Committed ynjh_jo’s above fix for the flickering DirectLabels

Running pandaSteer.py you shouldn’t see any other difference, but if you run terrain.py or the new scene.py you will see new stuff. This code is still very rough right now, so any pointers welcome:

• perlin.py module – contains a couple of utility functions for producing Perlin noise using Panda’s Perlin2 class (thanks to Hypnos in this thread: discourse.panda3d.org/viewtopic.php?t=2648)

• terrain.py module has been revised to be a little more object-oriented (new Terrain class), and now trees can be placed on the terrain using Perlin noise. You pass a parameter (a float from 0 to 1) determining how many trees a terrain model should have, and the exact number and placement of trees is computed using Perlin. Run terrain.py to see a demo with four terrain models each with different hilliness and trees values.

• New scene.py module – a demo scene with terrain, trees, wandering non-player Ralph characters and a point-and-click controlled player character, and an EdgeScreenTracker camera following the player (camera code is from tiptoe, ynjh_jo and cyan in this thread: discourse.panda3d.org/viewtopic.php?t=2577)

The characters in the scene steer to avoid the trees and to remain on the island. Actually I think the Container object is not even positioned properly so they may wander off the island, but trust me this works if you just position the container right.

Another problem is that the fractal terrain has dips in it as well as hills, so I’ve had to float the terrain above the sea to prevent too many ‘lakes’ appearing where the terrain dips below sea level. The characters don’t avoid these lakes. Any ideas for how to get rid of unwanted lakes welcome. I’m thinking of trying out Panda’s PerlinNoise as a heightmap generator.

Although the characters do a fair job of steering around individual trees, they do not steer to avoid ‘forests’ (groups of trees). Instead of going round a forest they will thread their way through it, and since they can only really steer to avoid one obstacle at a time, they sometimes hit trees when there are many close together.

Since I’m using a blocky, grid-like terrain map (and you might notice that I place every tree in the centre of one of the maps quads and have only one tree per quad) a good solution to this might be a simple pathfinding algorithm. Simply represent each quad of the terrain in a 2D list as True (you can walk here) or False (for some reason you can’t walk here, e.g. there is a tree in this quad). Then run an A* search over this grid to find paths from A to B. You could ofcourse represent other obstacles like buildings or lakes or high hills in the map in the same way.

Does anyone know if Panda has any search algorithms built in? Or can anyone point me to a good implementation of A* in Python? Ideally the search function should be implemented in C for speed though.

To get characters to follow a path a new path-following steering behaviour would be needed, but this would be easy for simple polyline paths and I think it’s already been discussed in this thread.

That would more-or-less replace the arrival steering behaviour. But for steering behaviours like pursue, evade, follow and wander it doesn’t make much sense to be following a path, so it might be necessary to add a ‘no penetration’ steering constraint to prevent characters from steering into obstacles. Or just ignore it. For wandering, you could combine path-following and wander and have characters wander along a path (you could, for example, repeatedly compute a path from A to a random quad B then wander along it, or you could use pre-defined paths to wander on).

[enn0x]

Or can anyone point me to a good implementation of A* in Python?

I found this in my bookmarks. It claims to be a simple python implementation of A*. The demo required PyGame, but the algorithm itself is vanilla (no dependencies). I never tested the code, only marked it for future interest.

http://arainyday.se/projects/python/AStar/

EDIT: If this algorithms suits your needs I would offer to do (or at least try to do) a quick C++ implementation via Pyrex.

enn0x

[chombee]

Thanks for that. I haven’t looked into it yet to determine whether I’d want to use it. I’ll get back to you on that!

Related, I found this essay by none other than Guido Van Rossum about graphs and searching in Python: python.org/doc/essays/graphs/ It gives a very simple search algorithm which he claims is “close to optimal”, but I’m not sure what he means by that, because at a glance it looks like a breadth-first search to me.

Also found Dijkstra’s algorithm for shortest paths in the Python cookbook: aspn.activestate.com/ASPN/Cookbo … ipe/119466

Also there is a Python implementation of boids in 2D here: aspn.activestate.com/ASPN/Cookbo … ipe/502240

[chombee]

Fixed the filename of the skin in tree1.egg so that trees are now skinned: chombee.panda3dprojects.com/Pand … v54.tar.gz

Think I need to use loadModelCopy and loadTextureCopy or something on the trees. Will do.

P.S. the tree model and texture are from mavasher’s island/minimaps et al code linked to above. Thanks mavasher!

[ynjh_jo]

If the assets structure was not changed, could you split the assets-script download ? It’s not fun DLing 6 megs over & over again.
Thx.

[chombee]

Update: lots of minor tweaking:

chombee.panda3dprojects.com/Pand … v59.tar.gz
chombee.panda3dprojects.com/Pand … v59.tar.gz

As you can see I’ve split the code from the assets as ynjh_jo requested. The assets download contains a models folder which you must extract into the PandaSteer2 folder from the first download. The assets download has not changed since my previous release (rev54).

• All characters start on the island now and will stay on it
• Characters avoid trees better because they have a greater maximum steering force, but optimally they may need even more force. Try fiddling with the maxforce settings in scene.py if you want.
• Camera settings and controls
• Better character-character collision avoidance (Vehicle radius was not being set)
• Tried some efficiency improvements: once all trees have been ‘planted’ on a terrain object it disables the collision traverser for trees (no longer needed) and calls flattenStrong on the trees (which are all attached to a trees node). Not sure I got much out of it though, and may have introduced a bug (see below).

Run scene.py to see the island scene. You can rotate the camera left/right by moving the mouse to the left/right edges of the window or pressing the left/right arrow keys, rotate it up/down by mousing to the top/bottom edges of the window, zoom it in and out by pressing the up/down arrow keys. You can zoom in close to see your character or far out to see the whole scene. To move your player click on the terrain with the mouse. To toggle annotation of the steering behaviours and collisions press ‘C’.

As usual pandaSteer.py and terrain.py can also be run to see other stuff (but they have not been updated in this revision).

If you want to help out, there’s now a list of known issues in knownIssues.txt in the download. The main one right now is this, which may have been introduced recently due to my efficiency improvements:

Sometimes none of the trees seem to get added to the collision detection
system. No collisions between characters’ collision tubes and trees’ collision
spheres occur, characters walk right through trees. Framerate is much better

Sometimes only some of the trees get added to the collision system.

Is this something to do with flattenStrong?

If you don’t think the characters are steering to avoid the trees, please kill the program and start it again. You can press ‘C’ to see the collisions visualised, which makes it very obvious when the characters are attempting to steer round trees. If they run right through trees with no collisions being visualised then you are seeing the above bug.

Any contributions that get at the known issues, or efficiency and robustness improvements, or new features, more than welcome.

Where I’m going with this code:

• I’d like the player to be able to right-click on a non-player character to cause the player character and the NPC to walk up to each other and start a ‘conversation’.
• The ‘conversation’ would bring up a simple DirectGUI dialog with which the player can tell the non-player character what to do: wander, go to X, follow Y, flee from Z, etc. Go find A and bring them to C. All the things that can be done with the steering behaviours.
• I’d like some objects to be scattered around the island that the characters can pick up and carry and pass between eachother. One of the Panda3D samples shows how to get actor models to carry other models like teapots, swords etc. attached to their hands.

[ynjh_jo]

Sometimes none of the trees seem to get added to the collision detection system. Sometimes only some of the trees get added to the collision system.
Is this something to do with flattenStrong?

I believe so. I tried to use forceRecomputeBounds, but didn’t work. So I placed each sphere after the trees planted completely. The sphere’s size is based on the tree’s tight bounds.

Sometimes character models fall under the terrain model. Could it be that the CollisionRay used with CollisionHandlerFloor is on rare occasions shooting right through a tiny gap in the terrain model? Though I don’t see why there should be gaps in the terrain model, this problem did occur with placing trees, leading to code that ‘wiggles’ a tree until its ray hits some terrain. Maybe try using the characters collision sphere to detect the height of the terrain and set the Z accordingly? (i.e. don’t use collisionhandlerfloor)

You’re right. If the ray exactly hits the tri’s edge, it wouldn’t be considered as collision. You solved it by offsetting each “missed shot” tree randomly. It means you need an extra coll detection pass, at least it costs you 1 frame time. Why not offsetting the collision terrain since the 1st place ? It cost you only 1 pass, with less transform on your bunch of tree nodes. And you can shift it back after flattening the trees, if you like. So shaking the tree method only serves as “spare bullet”.

new terrain.py

[chombee]

Thanks ynjh_jo, I’ve commited those. New download (code only): chombee.panda3dprojects.com/Pand … v62.tar.gz

Interesting, I don’t find this NodePath.getTightBounds function that you used anywhere in the online documentation on this site, or by running Python’s help function on NodePath. I guess you have to look into the C++ source to find that? Could you explain it? I wonder why when I scale the model to a different size the bounding sphere doesn’t end up a different size as well.

I searched the source code, and found getTightBounds in NodePath_extensions.py. It seems to just be an accessor for NodePath.calcTightBounds, which is in the API:

Description: Calculates the minimum and maximum vertices of all Geoms at this NodePath’s bottom node and below. This is a tight bounding box; it will generally be tighter than the bounding volume returned by get_bounds() (but it is more expensive to compute).
The return value is true if any points are within the bounding volume, or false if none are.

I can’t help noticing that the scene without characters (run terrain.py) gets 75fps, while the same scene with 10 characters (scene.py) gets 10-15fps. A bit worrying.

Oh, I changed a couple of other things. Tweaked the size of collision spheres on trees and the maximum steering force for characters in scene.py, seems quite good for running around the trees now.

[Liquid7800]

Great work chombee, and thanks for sharing!

Interesting, I don’t find this NodePath.getTightBounds function that you used anywhere in the online documentation on this site, or by running Python’s help function on NodePath.

I had wondered that myself, when I was working on the eggNbowl physics demo in this forum.
ynjh_jo, kindy mentioned that it is:

getTightBounds is a method in Panda, find it in pandac\libpandaModules.py. …getTightBounds returns the tight bounds of a geometry under the given node, by iterating through the vertices to find the outermost vertices. It respects the node’s transformation, and the result is in render coordinate space. For example, say you have a cube of 1,1,1 in size. If you change it’s heading to 45, you would get (1.41421, 1.41421, 1) bounds, the AABB.

Hope this sends you in the right direction

[ynjh_jo]

@chombee

I wonder why when I scale the model to a different size the bounding sphere doesn’t end up a different size as well.

The stored radius in the Python tag is based on the bounds of the default scale. If you’d like to scale each tree randomly, why didn’t you multiply the radius by it’s parent’s randomized scale ?

    if models.has_key(path):
        model = models[path].copyTo(parent)
        scale=0.75+random.random()/2
        model.setScale(scale)
        model.setPythonTag('radius',model.getPythonTag('radius')*scale)

correction about the result of tight bounds in the quote above :
it’s not in render coord space, but in the node’s parent’s coord space.

about the crawling performance :
it must due to the abundant coll spheres which are packed under a single flat collision node structure. Then they must be spatially splitted apart.

[chombee]

Update (code only, download assets above): chombee.panda3dprojects.com/Pand … v63.tar.gz

Run pandaSteer.py to see the new stuff.

• Added a pathfinding steering behaviour. Characters can follow a pre-defined path and get round obstacles and other characters that intersect the path

• Added a non-penetration constraint. Even if steering fails to avoid an obstacle or collision, characters will never, ever overlap with obstacles or other characters, instead they will slide along each other. It’s much less noticeable than overlapping on the rare occasions that steering fails to avoid a collision, and it prevents weird stuff like characters getting stuck inside obstacles. Currently only works with spherical objects.

• Characters now complain or apologise to eachother when they collide!

The pathfinding plugin is using LineSegs to draw the paths so you can see what’s happening. But I haven’t had time to get it to nicely undraw the paths when you move to another plugin then redraw them when you move back yet.

[chombee]

Another code only revision: chombee.panda3dprojects.com/Pand … v65.tar.gz

• The non-penetration constraint now works in scene.py as well as pandaSteer.py. I realised when I activated it in scene.py that, because it was using my own little sphere-sphere collision detection and looping over every sphere in the scene in Python, it destroyed the framerate. So I had to rewrite the function to use Panda’s collision detection instead. Which was more difficult than expected. So many into and from masks flying around. For some reason it sort of vibrates characters along obstacles now instead of smoothly sliding, which is not as nice as before, but at least it doesn’t seem to affect the framerate.

• Also totally fixed up the placing of collision spheres over trees of different sizes.

Still haven’t done anything about the 10fps framerate in scene.py. I’m thinking that in pandaSteer.py, the plugins with 10-12 actors run at 12-17fps sort of thing. The ones with 2 or 3 actors get 50-75fps. scene.py has 10 actors (I think) plus 4 terrain models instead of one, all those trees, sea and skybox, and it’s getting 10fps. Perhaps not so surprising? I have a bad feeling it’s the actors that are slowing everything down.

ynjh_jo: I’ve been thinking about removing the efficient scene graph structuring you built into the terrain generator and instead just saving the whole terrain, trees and collision spheres and all, to an egg, then running it through the egg-octree function someone posted on this forum. Think it would help?

ynjh_jo:

The stored radius in the Python tag is based on the bounds of the default scale

See, I thought that because

bounds=model.getTightBounds()

comes after

model.setScale(scale)

, the bounds retrieved would be the bounds of the scaled model. And that does in fact seem to be the case.

The problem seems to have been that the block of code that does the setPythonTag is only called once per model. Once the tree model is loaded the first time, another block of code that uses copyTo is executed for every other tree. (the two blocks form an if/else statement in terrain.py/loadModel).

Here’s the function now (works nicely):

models = {} # dict of {pathToModel:model}

def setRadiusTag(model):
    """Set a tag on the given model storing the models XY radius (ignoring how
    short or tall it is in the Z dimension).
    
    This radius tag can be retrieved later to (for example) create a collision
    sphere that will bound the model
    
    Arguments:
    model -- the model to tag
    
    """
    # Get the two points (in a list) that define the axis-aligned bounding
    # box of the scaled model.
    bounds=model.getTightBounds()
    # Now subtract the two, giving a vector from one to the other, the
    # length of which is the diameter of the aabb
    vector=(bounds[1]-bounds[0])
    # Take the greatest of the X and Y components of this vector, ignoring
    # the Z component, and halve it go get the X/Y radius of the aabb
    radius=max(vector[0],vector[1])*.5
    # Store the radius in a tag attached to the model
    model.setPythonTag('radius',radius)


def loadModel(path,parent):
    """Load a model from the file given by path, parent it to the given parent
    node and return the NodePath to the newly loaded model.
    
    Maintains a global dictionary of loaded models and if a model if called
    twice for the same model the model is instanced instead of being loaded
    again.
    
    """
    global models
    if models.has_key(path):
        model = models[path].copyTo(parent)
        scale = 0.75+random.random()/2
        model.setScale(scale)
        setRadiusTag(model)
    else:
        modelRoot = loader.loadModelCopy(path)
        # New models are loaded in a non-standard way to allow flattenStrong
        # to work effectively over them.
        model = P.NodePath('model')
        scale = 0.75+random.random()/2
        model.setScale(scale)
        modelRoot.getChildren().reparentTo(model)
        model.reparentTo(parent)
        setRadiusTag(model)
        models[path] = model
    return model

[mavasher]

Great work Chombee,

This is coming together nicely. I’ve been having the same fps problems you describe.

I think it is the Actor class. Could be wrong though.

Also, just a tip, the trees tend to line up in grids. It seems like you could add a tiny random factor for placement of the tree model within the grid cell. This may make it harder for the characters to negotiate the forests though. Maybe that’s why you kept them in a strict grid.

But again great work.

[ynjh_jo]

Hey, in my last snippet above, for every (already loaded) tree, I only update the tag to respect the random scale. And now you end up with calculating the bounds for each of them, it means : thousand times for exactly the same model. If your tree is built of a lot more vertices, you’d halt the loading time.

@chombee

ynjh_jo: I’ve been thinking about removing the efficient scene graph structuring you built into the terrain generator and instead just saving the whole terrain, trees and collision spheres and all, to an egg, then running it through the egg-octree function someone posted on this forum. Think it would help?

Sure, try everything possible.

[chombee]

This is coming together nicely. I’ve been having the same fps problems you describe.

I think it is the Actor class. Could be wrong though.

On the other hand, each character in PandaSteer has three CollisionSolids attached: a tube, a sphere, and a ray. And they’re colliding with a lot of stuff: the spheres of other characters, the spheres around each of the couple of hundred or so trees, and the many quads of the terrain models. So it may not be the Actor class that is slow, but all the collision detection associated with each actor in PandaSteer.

I’ll have a go at improving the collision efficiency, though I don’t know much about it, I think the egg-octree code might be good for it, and it might be possible to get rid of the CollisionRays entirely and collide the spheres against the terrain instead.

[mavasher]

That’s all true.

The collision against the terrain seems a little overkill to me. Can’t you just pass the Z value from the terrain to the character. I used this method in the minimap island. Or do you have a special reason to use collision detection? Using the current system every character collides with the terrain every frame. It’s a lot of potential collisions buts it’s also just a lot of actual collisions, the characters each have to cycle through all the collisions and find which one is theirs. That’s a lot of processing.

[chombee]

Trouble is, I’d have to do some sort of interpolation to get the Z-value at any particular point on the terrain. The terrain is made out of triangles, so I’d need a function that, given an (X,Y), would:

• determine which triangle of the terrain the position lies in
• determine how close to each vertex of the triangle the position is
• interpolate between the three vertices to figure out the height at the position and return it

I didn’t know how to do that off the top of my head so I used Panda instead. But yeah if that could be done efficiently it would probably be great, because the terrain could be removed from the collision system entirely. And it’d probably be more robust too – using a CollisionRay with a CollisionHandlerFloor seems to result in characters falling through the terrain sometimes.

Did you have to solve the same interpolating between three vertices problem in your island demo? Do you have some code for it? I don’t suppose it would be too difficult. I would look at your code myself but I have to post this and run right now.

[mavasher]

Well, I was using Panda’a heightfield so there was a function for interpolating. It just did it on its own.

Here’s the part of the code I used. I’m sure you have this somewhere:

def Elevation(self,objectx,objecty):
		ele = self.mHeightFieldTesselator.getElevation(objectx/self.scale,-objecty/self.scale)
		return ele

so every frame the characters just referenced the island’s Elevation function and set their Z to the value that Elevation returned.

I think you’d need to write something similar if you wanted to do this.

I think the trick is to make sure you are only using a limited number of lines of code per frame. for loops are killers here because they could potentially be very large especially when every character has it’s own task.

[madprocessor]

HI there,

just tried pandasteer but i get some errors about models missing:

where can i get them?

greetz

E:\Panda3D-1.3.2\samples\PandaSteer2>ppython pandaSteer.py
DirectStart: Starting the game.
Warning: DirectNotify: category ‘Interval’ already exists
Known pipe types:
wglGraphicsPipe
(3 aux display modules not yet loaded.)
:util(warning): Adjusting global clock’s real time by 0.648984 seconds.
Instantiating plugin from <module ‘1_seekAndFlee’ from ‘plugins\1_seekAndFlee.pyc’>
Instantiating plugin from <module ‘2_pursueAndEvade’ from ‘plugins\2_pursueAndEvade.pyc’>
Instantiating plugin from <module ‘3_arrive’ from ‘plugins\3_arrive.pyc’>
Instantiating plugin from <module ‘4_wander’ from ‘plugins\4_wander.pyc’>
Instantiating plugin from <module ‘5_follow’ from ‘plugins\5_follow.pyc’>
Instantiating plugin from <module ‘6_obstacleAvoidance’ from ‘plugins\6_obstacleAvoidance.pyc’>
Instantiating plugin from <module ‘7_collisionAvoidance’ from ‘plugins\7_collisionAvoidance.pyc’>
Instantiating plugin from <module ‘8_combinedAvoidance’ from ‘plugins\8_combinedAvoidance.pyc’>
Instantiating plugin from <module ‘9_pathFollowing’ from ‘plugins\9_pathFollowing.pyc’>
:loader(error): Couldn’t load file models/ralph: not found on model path (which is currently: “.;/e/Panda3D-1.3.2/etc/…;/e/Panda3D-1.3.2/etc/…/model
s”)
Traceback (most recent call last):
File “pandaSteer.py”, line 268, in ?
p = PandaSteer()
File “pandaSteer.py”, line 161, in init
self.restart()
File “pandaSteer.py”, line 219, in restart
avoidObstacles=False,avoidVehicles=False)
File “/home/s0094060/sync/svn-clean/PandaSteer2/character.py”, line 75, in init
File “E:\Panda3D-1.3.2\direct\src\actor\Actor.py”, line 164, in init
self.loadModel(models, copy = copy)
File “E:\Panda3D-1.3.2\direct\src\actor\Actor.py”, line 1358, in loadModel
raise StandardError, “Could not load Actor model %s” % (modelPath)
StandardError: Could not load Actor model models/ralph

[chombee]

Sorry it´s a bit confusing. For anyone trying to download pandasteer, there are two downloads you need, the code, and the models. Here are the latest:

Code: chombee.panda3dprojects.com/Pand … v65.tar.gz
Models: chombee.panda3dprojects.com/Pand … v59.tar.gz

The assets download contains a models folder which you must extract into the PandaSteer2 folder from the code download. I´ll be more clear in future releases.