Boidz Example -- UPDATED -- AGAIN ;)

bharling

21-04-2008 15:54:05

Right - last edit I promise -- have done some more tweakage and squeezed considerably more FPS out of this ( 1000 boids flocking at 25fps on my p4 2.8ghz ). Did some further optimizations to the octree, and verified that it IS actually speeding things up, although the difference is not huge from a brute force 'check every other boid' approach. Also, the octree should not lose objects any more. Would be interested to hear how it performs on various systems. personally I think this is actually quite good performance for python, considering c++ boids demos I've seen run 200 agents at around 100 fps. The code below is the latest updated version.

Just thought I'd share something I've been working on recently - not much to do at work today, so I managed to get it working quite nicely. Its a flocking simulation based on the standard 'boids' model, coupled with a dynamic self-modifying octree class which helps speed things up quite considerably. Save both files into your pythonOgre/demos/ogre folder and run boids.py.

Sadly, its not perfect, as objects are occasionally 'lost' by the octree ( I really do not know why ). Also the boids have no goal setting behaviour, so they will eventually coalesce into a spiral 'galaxy' formation, but that looks quite nice anyway!

I'd be grateful to anyone who can improve the code to post any such improvements back here. Of course I take absolutely no responsibility for any damage or disruption to your system ( or anything else ) that this code may cause, but TBH I haven't noticed anything go wrong with it so far. If its a bit slow, try reducing NUM_BOIDS. Oh, and you'll need psyco installed as well.

boids.py -:

import ogre.renderer.OGRE as ogre
import ogre.io.OIS as OIS
import SampleFramework as sf
from boids_octree import DynamicOctNode
import random
import time
import psyco
psyco.full()

NUM_BOIDS = 1000
BOID_MAX_SPEED = 20000.0


class Boid:
def __init__(self, pos, bbs=None):
self.velocity = ogre.Vector3(0,0,0)
self.pos = pos
self.moveVector = ogre.Vector3(0,0,0)
self.bb = bbs.createBillboard(self.pos)
self.parentNode = None
self.bb.setPosition(pos)
self.clumpVector = ogre.Vector3(0,0,0)
self.avoidVector = ogre.Vector3(0,0,0)
self.schoolVector = ogre.Vector3(0,0,0)

def think(self, boids):
sd = 0
self.clumpVector = ogre.Vector3(0,0,0)
self.avoidVector = ogre.Vector3(0,0,0)
self.schoolVector = ogre.Vector3(0,0,0)
if self.parentNode:
tests = self.parentNode.getNeighbours()
else:
tests = boids

# First, narrow down the number of boids to consider
nvel = self.velocity.normalisedCopy()
flockMates = []
nearestN = 5
for b in tests:
if nearestN == 0:
break
if self.pos.squaredDistance(b.pos) < 80:
if nvel.dotProduct( (b.pos - self.pos ).normalisedCopy() ) > 0.0:
if b is not self:
flockMates.append(b)
nearestN -= 1

# rules all in one
for boid in flockMates:
if boid is not self:
sd = self.pos.squaredDistance(boid.pos)
self.clumpVector = self.clumpVector + boid.pos #* (sd / 800.0) )
if sd < 20.0:
self.avoidVector = self.avoidVector - (boid.pos - self.pos)
self.schoolVector = self.schoolVector + boid.velocity


self.clumpVector = (self.clumpVector - self.pos) / 7.5
#self.schoolVector = (self.schoolVector - self.velocity) #/ 20.0
self.avoidVector = (self.avoidVector - self.pos) #* 1.5
self.velocity = self.velocity + self.clumpVector + self.avoidVector + self.schoolVector
self.limit_speed()
if self.parentNode:
self.parentNode.moveObject(self)

def setParentNode(self, node):
if not node:
print "Boid on BruteForce!!"
else:
if not self.parentNode:
print "Boid back in the Octree - Yay!"
self.parentNode = node

def move(self, timeSince):
self.pos += (self.velocity * timeSince)
self.bb.setPosition(self.pos)

def limit_speed(self):
speed = self.velocity.squaredLength()
if speed > BOID_MAX_SPEED:
self.velocity = self.velocity * (BOID_MAX_SPEED / speed)


class boidsListener(sf.FrameListener):
def __init__(self, rw, cam, boids):
sf.FrameListener.__init__(self, rw, cam)
self.boids = boids
self.bd = -1
self.WALL = 50
self.WALL_FORCE = 200
self.WIDTH = 2000
self.HALF_WIDTH = self.WIDTH / 2.0
self.clumpVector = ogre.Vector3(0,0,0)
self.schoolVector = ogre.Vector3(0,0,0)
self.goalVector = ogre.Vector3(random.uniform(-1,1),random.uniform(-1,1),random.uniform(-1,1))
self.goalTimer = 0
self.goalChangeTime = 5.0
self.goalStrength = 1.0

def frameStarted(self, event):
c = 6
self.goalTimer += event.timeSinceLastFrame
if self.goalTimer > self.goalChangeTime:
self.goalVector = ogre.Vector3(random.uniform(-1,1),random.uniform(-1,1),random.uniform(-1,1)) * self.goalStrength
self.goalTimer = 0

while c > 0 and self.bd < len(self.boids)-1:
c -=1
self.bd += 1
self.boids[self.bd].think(self.boids)

if self.bd == len(self.boids) -1:
self.bd = -1

for b in self.boids:
b.move(event.timeSinceLastFrame)
b.velocity += self.goalVector
self.simulate_wall(b)
return sf.FrameListener.frameStarted(self, event)

def simulate_wall(self, boid):
if boid.pos.x < -self.HALF_WIDTH:
boid.pos.x += self.WIDTH
if boid.pos.x > self.HALF_WIDTH:
boid.pos.x -= self.WIDTH
if boid.pos.y < -self.HALF_WIDTH:
boid.pos.y += self.WIDTH
if boid.pos.y > self.HALF_WIDTH:
boid.pos.y -= self.WIDTH
if boid.pos.z < -self.HALF_WIDTH:
boid.pos.z += self.WIDTH
if boid.pos.z > self.HALF_WIDTH:
boid.pos.z -= self.WIDTH

class boidApplication(sf.Application):
def __init__(self):
sf.Application.__init__(self)

def _createScene(self):
self.boids = []
bbs = self.sceneManager.createBillboardSet("bbsTest")
bbs.setMaterialName("Examples/Flare")
bbs.setDefaultDimensions(5.0, 5.0)
for i in range(NUM_BOIDS):
x = random.randint(-500, 500)
y = random.randint(-500, 500)
z = random.randint(-500, 500)
pos = ogre.Vector3(x, y, z)
self.boids.append(Boid( pos, bbs) )

# Enable Object Culling!
bOctRoot = DynamicOctNode(ogre.Vector3.ZERO, 4096, None, 0, self.boids)
n = self.sceneManager.getRootSceneNode().createChildSceneNode()
n.attachObject(bbs)

def _createFrameListener(self):
self.frameListener = boidsListener(self.renderWindow, self.camera, self.boids)
self.root.addFrameListener(self.frameListener)

if __name__ == "__main__":
app = boidApplication()
app.go()


boids_octree.py -:

# Boids Dynamic Octree

import ogre.renderer.OGRE as ogre
import random, time

class GameObject:
def __init__(self, pos):
self.pos = pos
self.hasMoved = False
self.parentNode = None

def update(self):
self.pos = self.getRandomPos()
if self.parentNode:
self.parentNode.moveObject(self)

def setParentNode(self, octNode):
self.parentNode = octNode


MAX_OBJECTS = 20 # Max objects in a leaf node
NUM_OCTNODES = 0 # Counter of nodes
OBJECTS_PLACED = 0 # Counter of object placement operations ( usually more than the number of objects )
MAX_DEPTH = 10

class DynamicOctNode:
def __init__(self, center, size, parent, depth=0, objects=[]):
self.parent = parent
self.objects = objects
self.center = center
self.children = []
self.index = []
self.size = size
self.isLeaf = True
self._setBounds()
self.depth = depth
#global NUM_OCTNODES
#NUM_OCTNODES += 1
if len(self.objects) > MAX_OBJECTS:
self._split()

def _setBounds(self):
halfsize = self.size / 2
self.left = self.center.x - halfsize
self.right = self.center.x + halfsize
self.top = self.center.y + halfsize
self.bottom = self.center.y - halfsize
self.front = self.center.z + halfsize
self.back = self.center.z - halfsize

def _checkMoved(self):
pass

def _distribute(self):
lost= []
numObjs = len(self.objects)
for b in self.objects:
for c in self.children:
if c._contains(b):
c.addObject(b)
numObjs -= 1
break
if numObjs > 0:# and self.parent:
#print "Lost", numObjs, "Objects!"
pass
else:
self.objects = []

def _contains(self, obj):
return (obj.pos.x > self.left and obj.pos.x < self.right and \
obj.pos.y < self.top and obj.pos.y > self.bottom and \
obj.pos.z < self.front and obj.pos.z > self.back)

def _split(self):
#print "Split", time.clock()
if self.depth < MAX_DEPTH:
offset = self.size / 4.0
newDepth = self.depth + 1
for x in [-1,1]:
for y in [-1,1]:
for z in [-1,1]:
newCent = self.center + ogre.Vector3(x * offset, y * offset, z * offset)
newNode = DynamicOctNode(newCent, offset * 2.0, self, newDepth, [])
self.children.append(newNode)
self.isLeaf = False
self._distribute()

def addObject(self, obj):
if self.isLeaf:
self.objects.append(obj)
obj.setParentNode(self)
if len(self.objects) > MAX_OBJECTS:
self._split()
else:
inObj = False
if self._contains(obj):
for c in self.children:
if c._contains(obj):
c.addObject(obj)
inObj = True
break
else:
if self.parent:
self.parent.addObject(obj)
else:
pass
#print "Object Lost!" # ARRGH, THIS SHOULDN'T HAPPEN!!

def getChildObjects(self):
if self.isLeaf:
return self.objects
else:
objs = []
for c in self.children:
objs += c.getChildObjects()
return objs

def getNeighbours(self):
return self.parent.getChildObjects()

def moveObject(self, obj):
# Always called from a gameObject so we
# can assume that this is a leaf node
if self._contains(obj):
# is the object still within this node?
obj.setParentNode(self)
else:
# Otherwise prune, and insert into parent
if obj in self.objects:
self.objects.remove(obj)
self.parent.addObject(obj)
else:
self.parent.parent.addObject(obj)



-- its quite mesmerising after a few runs, enjoy :wink: