Hi
I have an already made egg with a wall somewhere and I want to create a tab in memory corresponding to that map to calculate obstacle avoidances.
Please what is the way for that ?
David
What do you mean by a tab in memory?
So you are saying you have a field of grass with a wall in the middle and you want to go around it?
Douglas
Are you looking for pathfinding?
There isn’t a native panda way to do this. Chombee made a PandaSteer program that does obstacle avoidance but pathfinding (finding a path between points A and B with obstacle between them) is more difficult.
I’ve been working on an algorithm called A* (A star). I copied this mostly from a script in PyGame: pygame.org/projects/9/195/ but modified it to import a Gridmap image file so that it could be combined with a terrain generator like pro-rsoft’s PGMM to provide information about where the obstacles on the map are.
Here’s the test image file. (you’ll need to save this image to a “models” folder where you save this script)
It’s 32x32 (should be plenty of resolution for your environment) White is traverasable space- black is walls, obstacles, etc.
This script will find the pathway between two points in the Gridmap.
This script below works fine, but it’s just a draft. I’ll probably change things around as I incorporate it to interact closer to the PGMM for terrain generation.
from pandac.PandaModules import *
class Path: #it seems as if this path object is totally unnecessary- it could rather just be a List of Cells within another object.
def __init__(self,cells, totalCost):
self.cells = cells;
self.totalCost = totalCost;
def getCells(self): #function not used in the demo at any time.
return self.cells
def getTotalMoveCost(self): #function not used in the demo at any time.
return self.totalCost
class Cell: #Pathfinding Cell in the grid.
def __init__(self,location,mCost,lid,parent=None):
self.location = location # where is this cell located
self.mCost = mCost # total move cost to reach this cell
self.parent = parent # parent cell
self.score = 0 # calculated score for this cell
self.lid = lid # set the location id - unique for each location in the map
def __eq__(self, n):
if n.lid == self.lid:
return 1
else:
return 0
class AStar:
def __init__(self,maphandler):
self.mh = maphandler
def _getBestOpenCell(self):
bestCell = None
for n in self.on:
if not bestCell:
bestCell = n
else:
if n.score<=bestCell.score:
bestCell = n
return bestCell
def _tracePath(self,n):
cells = [];
totalCost = n.mCost; #'n' is the end pointcell.
p = n.parent;
cells.insert(0,n);
while 1:
if p.parent is None:
break
cells.insert(0,p)
p=p.parent #loop through everything- make a list of cells, insert the string of parents, with each parent at the beginning of the list working backward from the endpoint node.
return Path(cells,totalCost) #This is the only time in the script the Path object is called.
def _handleCell(self,cell,end):
i = self.o.index(cell.lid) #returns the place in the list where this cell is mentioned.
self.on.pop(i) #removes that entry in the open cell list
self.o.pop(i) #removes that entry in the list of location open id's
self.c.append(cell.lid) #adds that id to the list of closed cells
cells = self.mh.getAdjacentCells(cell,end)
for n in cells:
if n.location == end:
# reached the destination
return n
elif n.lid in self.c:
# already in close, skip this
continue
elif n.lid in self.o:
# already in open, check if better score
i = self.o.index(n.lid)
on = self.on[i];
if n.mCost<on.mCost:
self.on.pop(i);
self.o.pop(i);
self.on.append(n);
self.o.append(n.lid);
else:
# new cell, append to open list
self.on.append(n);
self.o.append(n.lid);
return None
def findPath(self,fromlocation, tolocation):
self.o = [] #list of open locations
self.on = [] #list of open nodes
self.c = [] #list of closed locations
end = tolocation
fcell = self.mh.getCell(fromlocation) #returns a Cell object if the location 1) is inside the grid boundaries AND 2) is not an obstacle valued cell. In which case it returns 'None'
self.on.append(fcell)
self.o.append(fcell.lid)
nextCell = fcell
while nextCell is not None: #Key pathfinding loop
finish = self._handleCell(nextCell,end) #Returns a cell if the nextCell is the end location, otherwise, returns None
if finish:
return self._tracePath(finish) #if a cell object was returned that means it was the endpoint so go ahead and trace the path to this cell
nextCell=self._getBestOpenCell() #find a new cell to run through the loop
return None
class SQ_Location:
"""A simple Square Map Location implementation"""
def __init__(self,x,y):
self.x = x
self.y = y
def __eq__(self, l):
"""MUST BE IMPLEMENTED"""
if l.x == self.x and l.y == self.y:
return 1
else:
return 0
class SQ_MapHandler:
"""A simple Square Map implementation"""
def __init__(self,mapdata,width,height):
self.m = mapdata
self.w = width #this is the grid width
self.h = height #this is the grid height
def getCell(self, location):
"""MUST BE IMPLEMENTED"""
x = location.x #This is a SQ_Location object. if this is changed to a Vec2 the function would be .getX()
y = location.y
if x<0 or x>=self.w or y<0 or y>=self.h:
return None
d = self.m[(y*self.w)+x]
if d == -1:
return None
return Cell(location,d,((y*self.w)+x)); #this has the weird ID value- I suggest str(x)+"-"+str(y)
def getAdjacentCells(self, curcell, dest):
"""MUST BE IMPLEMENTED"""
result = []
cl = curcell.location
dl = dest
n = self._handleCell(cl.x+1,cl.y,curcell,dl.x,dl.y) #all these use the SQ_location object. Need to change to Vec2
if n: result.append(n)
n = self._handleCell(cl.x-1,cl.y,curcell,dl.x,dl.y)
if n: result.append(n)
n = self._handleCell(cl.x,cl.y+1,curcell,dl.x,dl.y)
if n: result.append(n)
n = self._handleCell(cl.x,cl.y-1,curcell,dl.x,dl.y)
if n: result.append(n)
return result
def _handleCell(self,x,y,fromcell,destx,desty):
n = self.getCell(SQ_Location(x,y))
if n is not None:
dx = max(x,destx) - min(x,destx)
dy = max(y,desty) - min(y,desty)
emCost = dx+dy
n.mCost += fromcell.mCost
n.score = n.mCost+emCost
n.parent=fromcell
return n
return None
# Image to Pathfinding grid
def GeneratePathfindingGrid(image):
#The image should be a 32x32 pixel image.
GridImage=PNMImage()
GridImage.read(Filename(image)) #image should be the filename location of the image
array = []
for i in range(32*32):
array.append(0)
white = VBase3D(1,1,1)
black = VBase3D(0,0,0)
for y in range(32):
for x in range(32):
if GridImage.getXel(x,y) == white: v = 1 #this location is clear of obstacles
else: v = -1 #this location is an obstacle
locationid = (y*32+x) #This will give each cell a unique id number
array[locationid] = v #this assigns that cell a obstacle value
if v == 1 :print locationid,
else: print " ",
#print v,
#print GridImage.getXel(x,y)
#print white
print " "
return array
if __name__ == '__main__': #test case.
grid = GeneratePathfindingGrid('models/gridmap.png')
mh = SQ_MapHandler(grid, 32,32)
astar = AStar(mh)
start = SQ_Location(2,2)
end = SQ_Location(30,30)
path = astar.findPath(start,end)
print " "
print "Here's the pathway"
print " "
for n in path.cells:
print n.lid,To Douglas : yes I have an obstacle to avoid and want to calculate it in memory, the egg file is done with the obstacle : but wondering what is the way to do that.
Mavasher : yes this lead to pathfinding. I have read the Chombe and sandman codes, and also tend to port the Pygame code to Panda (from the Roaming ralp clik-to-go code).
I 've to admit that I did not tried the PGMM yet.
Nevertheless, your job of porting is realling interesting as try that port (as I said), I have some interogations :
- What is the reason of the 32x32 size ? for the simplicity of the example I suppose.
- Am I wrong or it seems that the code is not complete
In all case, thanks.
Yes, this code is not complete at all. All it does at the moment is print out to the console a text-base map of the grid and then shows you the names of the cells from point (2,2) to point (30,30). I was working on porting the Pygame stuff to one of my programs and had this working example when I saw your post, and I thought I happened to be working on what you were needing.
There is no need to limit it to 32 pixels. The only hard requirement is that you deal with a square image map. That’s because of the weird naming convention that the Pygame guy used. (If the x dimension of the image is greater than the y dimension of the image you’ll get errorenous results) This really isn’t that big of a deal though.
I have it set to 32 right now just because its probably enough resolution as it is. In a more recent edit of the script I just pull the resolution of the image and make sure it’s a square and forget about it.
Just to be clear PGMM is a terrain modeler, it doesn’t have anything to do with AI. What it does is take a greyscale image and builds a mesh of different heights to produce a terrain.
The reason I’d like to use this pathfinding script with PGMM is that the concept of using an image to hold information is already there:
A pathfinding supported terrain could be produced with a minimum of three textures.
- Image for the heightmap
- Image for the texturing of the heightmap mesh
- Image for the Gridmap (the pathfinding map)
Of course there are more complex methods that could be added- using an alpha map to blend different textures etc. They obviously would require more than the three textures listed above.
With this information built-in to the terrain itself, the AI modules in a program could query the terrain itself which could provide instruction to the AI module about clear passage between point A and B.
In fact, I should maybe add something about my view of path calculation :
I based it on memory cells to be able to compute AI layers :
- one for spatial reasoning
- another for influence map
- strategy (terrain analysis, line of fire for example)
This could correspond to the openness+occupancy+static cover layers described in the Paul Tozour paper in AI Game Wisdom 2.
As I am new to Panda, I thought the better should be to go from that Pygame A* Example, that is working very well and after could be reworked (smoothing the path for example).
For now, my Roaming Ralph reworked + draw.py patchwork taken from post here give me a litlle beginning
# Left click on the ground to move.
# Rotate the camera by moving the mouse pointer to the edges of the screen or
# with the left & right arrow keys.
# Zoom the camera with the mouse wheel or the up & down arrow keys.
import direct.directbase.DirectStart # Start Panda.
from pandac.PandaModules import * # Import the Panda Modules.
from direct.showbase.DirectObject import DirectObject # To handle Events.
from direct.task import Task # To use Tasks.
from direct.actor import Actor # To use animated Actors.
from direct.interval.IntervalGlobal import * # To use Intervals.
# We need to import this function for the player's rotation to work properly.
from direct.showbase.PythonUtil import closestDestAngle
from direct.gui.OnscreenText import OnscreenText
from direct.gui.OnscreenImage import OnscreenImage
import sys
from draw import *
class Controls(DirectObject):
def __init__(self):
base.disableMouse() # Disable default camera.
self.loadModels()
self.setupCollisions()
self.drawGrid()
# Declare variables.
self.position = None
self.playerMovement = None
self.movementSpeed = 6.0 # Controls how long it takes the player to
# move to the clicked destination.
self.speed = .10 # Controls the speed of the camera's rotation and zoom.
# Setup controls
self.accept("escape", sys.exit)
self.accept("player-stopped", self.stopWalkAnim)
self.accept("mouse1", self.moveToPosition)
self.accept("arrow_left", self.cameraTurn,[-1])
self.accept("arrow_right", self.cameraTurn,[1])
self.accept("arrow_up", self.cameraZoom,[-1])
self.accept("arrow_down", self.cameraZoom,[1])
self.accept("wheel_up", self.cameraZoom,[-1])
self.accept("wheel_down", self.cameraZoom,[1])
## self.accept("g",self.drawGrid)
textObject = OnscreenText(text = 'Du tExte', pos = (-1, 0.7), scale = 0.07)
taskMgr.add(self.edgeScreenTracking, "edgeScreenTracking")
# End __init__
def drawGrid(self):
# Create the static elements of the test environment. Use one Draw
# object for all the static elements.
d = Draw()
# Make a 30x30 grid centered at the origin, in Purple.
d.drawXYGrid(Vec2(-15.5,-15.2), numSquares=30,squareSize=1.03,color=(0.66,0,0.66,1))
# Draw a grey 100x100x100 cuboid, with the grid we previously drew as the floor of the cuboid.
d.drawCuboid(Vec3(-5,-5,0), Vec3(5,5,2.5), color=(0.2,0.3,0.9,1))
node = d.create() # A special GeomNode that draws the shapes.
np = NodePath(node)
np.reparentTo(render)
def loadModels(self):
# Load an environment
self.environ = loader.loadModel("models/terrain2.egg")
self.environ.reparentTo(render) # Place it in the scene.
self.environ.setPos(0, 0, 0)
self.environ.setHpr(0, 0, 0)
## texture = loader.loadTexture("models/rock03.jpg")
## self.environ.setTexture(texture)
# For the camera to rotate independently of the player a 'player dummy
# node' and a 'camera dummy node' need to be created. Both dummy nodes
# are then 'parented' to the 'player dummy node' making them "siblings"
# under the player dummy node. This means that any transformations
# performed on the dummy node will be inherited by the player model and
# the camera. Moving the player dummy node will move both the player
# model and the camera, but moving or rotating the player model itself
# won't effect the camera (because the camera isn't directly parented
# to it).
# Create the player's dummy node.
self.player_dummy_node = render.attachNewNode("player_dummy_node")
# Position the dummy node.
self.player_dummy_node.setPos(0, 0, 0)
self.player_dummy_node.setHpr(0, 0, 0)
# The terrain model was edited by hand to include a start position for
# the player. Use the Find command to locate it.
self.playerStart = self.environ.find("**/start_point").getPos()
# Now load the player model and its animations.
self.player = Actor.Actor("models/ralph",{"walk":"models/ralph-walk"})
# Set the player to the start position.
self.player.setPos(self.playerStart)
# Attach/parent the player model to the player dummy node.
self.player.reparentTo(self.player_dummy_node)
# The player model is too large, so scale it down by 50%.
self.player.setScale(.5)
# Now create the camera dummy node.
self.camera_dummy_node = render.attachNewNode("camera_dummy_node")
# Attach/parent the camera dummy node to the player dummy node.
self.camera_dummy_node.reparentTo(self.player_dummy_node)
# Attach/parent the main camera to the camera dummy node.
camera.reparentTo(self.camera_dummy_node)
# Position the main camera.
camera.setPos(0, -35, 18) # X = left & right, Y = zoom, Z = Up & down.
camera.setHpr(0, -25, 0) # Heading, pitch, roll.
# End loadModels
# Define a function to setup collision detection. We need two rays, one
# attached to the camera for mouse picking and one attached to the player
# for collision with the terrain. The rays must only cause collisions and
# not collide with each other so their Into bitMasks are set to allOff().
def setupCollisions(self):
# The terrain model was edited by hand to include the following tag:
# <Collide> Plane01 { Polyset keep descend }.
#Once we have the collision tags in the model, we can get to them using
# the NodePath's find command.
self.ground = self.environ.find("**/terrain")
# Set the model's Into collide mask to bit (0). Now only objects that
# have their From bitmask also set to (0) can collide with the terrain.
self.ground.node().setIntoCollideMask(BitMask32.bit(0))
# Create a CollisionTraverser for the picker ray. CollisionTraversers
# are what do the job of calculating collisions.
self.picker = CollisionTraverser()
# Create a handler for the picker ray
self.queue = CollisionHandlerQueue()
# Make a collision node for our picker ray
self.pickerNode = CollisionNode('mouseRay')
# Attach that node to the camera since the ray will need to be positioned
# relative to it.
self.pickerNP = camera.attachNewNode(self.pickerNode)
# Set the collision node's From collide mask. Now the ray can only cause
# collisions with objects that have bitMask(0) such as the terrain.
self.pickerNode.setFromCollideMask(BitMask32.bit(0))
# Set the collision node's Into collide mask to allOff so that nothing
# can collide into the ray.
self.pickerNode.setIntoCollideMask(BitMask32.allOff())
# Make our ray
self.pickerRay = CollisionRay()
# Add it to the collision node
self.pickerNode.addSolid(self.pickerRay)
#Register the ray as something that can cause collisions with the traverser
self.picker.addCollider(self.pickerNP, self.queue)
# Setup collision stuff to handle the player's collision with the terrain.
# Make a collision node for the player's ray.
self.groundCol = CollisionNode('playerRay')
# Make a collision ray for the player.
self.groundRay = CollisionRay()
# Attach the collision node to the player dummy node.
self.groundColNp = self.player_dummy_node.attachNewNode(self.groundCol)
# Set the height of the ray (7 units above the player's head)
self.groundRay.setOrigin(0, 0, 7)
# Set the rays direction (pointing down on the Z axis)
self.groundRay.setDirection(0, 0, -1)
# Add the collision node to the collision ray
self.groundCol.addSolid(self.groundRay)
# Set the collision node's From collide mask. Now the ray can collide
# with objects (like the terrain) that also have bitMask(0).
self.groundCol.setFromCollideMask(BitMask32.bit(0))
# Set the collision node's Into collide mask to allOff so that nothing
# can collide into the ray.
self.groundCol.setIntoCollideMask(BitMask32.allOff())
# Make a CollisionTraverser. This will be used in the correctPlayerZ
# function.
self.Zcoll = CollisionTraverser()
# Make a handler for the ground ray. This will be used in the
# correctPlayerZ function.
self.ZcollQueue = CollisionHandlerQueue()
# Register it as something that can cause collisions with the traverser.
self.Zcoll.addCollider(self.groundColNp, self.ZcollQueue)
# Uncomment this line to see the collisions
# self.Zcoll.showCollisions(render)
# Uncomment this line to see the collision rays
# self.groundColNp.show()
# End setupCollisions
# Define a task to monitor the position of the mouse pointer & rotate
# the camera when the mouse pointer moves to the edges of the screen.
def edgeScreenTracking(self,task):
# Check if the mouse is available
if not base.mouseWatcherNode.hasMouse():
return Task.cont
# Get the relative mouse position, its always between 1 and -1
mpos = base.mouseWatcherNode.getMouse()
if mpos.getX() > 0.99:
self.cameraTurn(1)
elif mpos.getX() < -0.99:
self.cameraTurn(-1)
return Task.cont
# End edgeScreenTracking
# Define the CameraTurn function.
def cameraTurn(self,dir):
self.camTurn = LerpHprInterval(self.camera_dummy_node, self.speed, Point3(self.camera_dummy_node.getH()-(10*dir), 0, 0))
self.camTurn.start()
# End cameraTurn
# Define the cameraZoom function.
def cameraZoom(self,dir):
self.camZoom = LerpPosInterval(camera, self.speed, Point3(camera.getX(), camera.getY()-(2*dir), camera.getZ()+(.8*dir)))
self.camZoom.start()
# End cameraZoom
# Define a function to correct the player's Z axis so that he follows the
# contours of the ground.
def correctPlayerZ(self, time):
startpos = self.player.getPos()
# Check for collisions
self.Zcoll.traverse(render)
#Gestion de la collision : Retir? au profit d'une d?claration d'obstacles
if self.ZcollQueue.getNumEntries > 0:
self.ZcollQueue.sortEntries()
point = self.ZcollQueue.getEntry(0).getSurfacePoint(self.environ)
self.player.setZ(point.getZ())
else:
self.player.setPos(startpos)
# End correctPlayerZ
# Define a function to get the position of the mouse click on the terrain.
def getPosition(self, mousepos):
self.pickerRay.setFromLens(base.camNode, mousepos.getX(),mousepos.getY())
# Now check for collisions.
self.picker.traverse(render)
if self.queue.getNumEntries() > 0:
self.queue.sortEntries()
# This is the clicked position.
self.position = self.queue.getEntry(0).getSurfacePoint(self.environ)
# Set its Z axis to remain on the ground.
self.position.setZ(0)
return None
# End getPosition
# Define a function to make the player turn towards the clicked position
# and then move to that position.
def moveToPosition(self):
# Get the clicked position.
self.getPosition(base.mouseWatcherNode.getMouse())
if self.position==None:
return
# Create a dummy node.
self.npLook = render.attachNewNode("npLook")
# Calculate its position.
self.npLook.setPos(self.player.getPos(render))
# Make it look at the clicked position.
self.npLook.lookAt(self.position)
# Prevent overturning or 'wrap-around' by adjusting the player's heading
# by 360 degrees.
reducedH = self.player.getH()%360.0
# Set the player's heading to that value.
self.player.setH(reducedH)
# Get the player's new heading.
currH = self.player.getH()
# Get the dummy node's heading.
npH = self.npLook.getH()
# Ralph was modeled facing backwards so we need to add 180 degrees to
# stop him walking backwards. If your model is not modeled backwards
# then delete the + 180.0.
newH = closestDestAngle(currH, npH + 180.0)
# Create a turn animation from current heading to the calculated new heading.
playerTurn = self.player.hprInterval(.2, Point3(newH, 0, 0))
# Calculate the distance between the start and finish positions.
# This is then used to calculate the duration it should take to
# travel to the new coordinates based on self.movementSpeed.
travelVec = self.position - self.player_dummy_node.getPos()
distance = travelVec.length()
# Create an animation to make the player move to the clicked position.
playerMove = self.player_dummy_node.posInterval((distance / self.movementSpeed), self.position)
# We create a LerpFunc Interval to correct the Z axis as we go along.
# So that the player stays on the ground.
playerPositionZ = LerpFunc(self.correctPlayerZ, duration=(distance / self.movementSpeed))
# Put the animations into a parallel sequence and set the doneEvent.
if self.playerMovement:
self.playerMovement.setDoneEvent("")
self.playerMovement = Parallel(playerTurn, playerMove, playerPositionZ)
self.playerMovement.setDoneEvent("player-stopped")
# Play the walk animation.
self.player.loop("walk")
self.playerMovement.start()
# End moveToPosition
def stopWalkAnim(self):
# This is called when the movement animation has finished.
# We can then stop the walk animation.
self.player.stop("walk")
self.player.pose("walk",17)
self.playerMovement = None
c = Controls()
run()As I said this is just a learning approach no code is mine and I still try to understand how to put a cube for each cekk that will be a wall as also the possibility to toggle the camera to a top-view(editor-type).
David