As you probably know, A* algorithm is based on grid: some parts of the grid are open for movement, some are occupied by barriers (simplified explanation, I know). I would like to implement A* in Panda, but I don’t know how to find whether the cell is occupied or not, and if it is then what is in it.
For example, I have a building of very complicated shape in the middle of the map. How do I know which cells does it occupy?
I believe A* has already been implemented into Panda by some users (I think mavasher and _Hypnos)
Here are two related topics:
discourse.panda3d.org/viewtopic.php?t=3414
discourse.panda3d.org/viewtopic.php?p=16720
I don’t know if he already has published it, I couldn’t find any other posts.
I have written several, but the easiest way is simply to have a 2-dimensional array lookup table, at least for square grids 
have a function that will fill the table based upon model’s position, or whenever you move a model, update the table (faster). This uses up a lot of memory based upon map size, so I usually just store the “special” places-those that are blocked and/or have special movement properties and assume everything else is free (the default). This can be stored in a sorted array to be accessed by the pathfinder. I have also used a dictionary and constructed the keys of the x-y-z values so that you can simply plug in a coordinate and have the dict look for a match, but this is slow if there is no match. It is a trade off of memory verses speed, and different approaches are better for different things. I almost always rewrite my pathfinding code for every application because this allows for optimization and a perfect fit…hope this helped!
Hi mindstormss. Thank you, it is very valuable advice! I am very interested in your other ideas about it, if possible. Also, what do you think about my current algorithm (below)?
My setting is like this: more or less flat ground (city), and it’s not possible to get on top of any object (i.e. one can’t get on top of a car, or to the upper floor of the building and so on). There are no walkable areas above other walkable areas. Therefore, I will use 2D grid/array.
I will use rectangular shape for a cell with size of 1x1 unit (unit = minimal distance an NPC can get through). Each cell has 8 parameters: accessible from top-left, top, top-right, right, lower-right, lower, lower-left and left adjacent cell. These parameters are in binary format (0 means the way is blocked, 1 means it is free). Cells can be either blocked (all the above eight parameters are equal to 0) or free.
I am going to use collision detection to set these eight parameters. There will be 5 collision spheres with diameter of 1 unit located like this: 1) 0x0 - in the top-left corner of the cell, 2) 0x1 - in the top-right corner, 3) 0.5x0.5 - in the middle of the cell, 4) 1x0 - in the lower-left corner, 5) 1x1 - in the lower-right corner. When these spheres intersect with any static geometry, it means that the corresponding way is blocked. Like this: when sphere 1 is colliding, the top-left way is blocked, if the spheres 1 and 2 are colliding, the top-left, the top and the top-right ways are blocked, and so on.
This information I want to use in 2D table (columns and rows correspond to the cell coordinates) filled with - ! - 8-bit binary numbers. Each of the eight parameters will have its position in the binary number, for example, like this: one cell - 11111000 (the cell is not accessible from the lower, the lower-left and the left adjacent cells, and accessible from other cells), another cell - 00000111 (the cell is accessible from the lower, the lower-left and the left adjacent cells, and not accessible from other cells), and so on.
Here goes the question: how can I read/write/save binary numbers in Python?
There is the BitMask32 class for panda that you can set bits on and off, but to simply use an int as a grouping of bits (flagged on or off) is in my opinion easier (and probably faster?).
How many bits are used to store usual decimal number that consists of 8 characters? I guess more then eight
Using binary numbers instead of decimal ones would allow to keep hundreds of thousands cells using small memory.
BTW, maybe, I should use 8-bit grayscale images to save such grid maps… 
mathematically it would require 24 bits. would result in a 32bit int if i guess.
using images for this purpose is a good idea. in case you can access and convert the values fast enough (in case you need to read tons of data from the image every frame)
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496778
might help you
using png images to store the data makes storage on disk quite efficient. they are compressed and lossless so you wont loose any data.
i have created A* for a 3d (2d with layers) environment a while ago. it does work fine. BUT, i’d really recommend to write this in c++, because pathfinding is a heavy mathemathical operation where python is very bad in comparison to c++. (it can take severals seconds to find a path in a 3layer 256x256 grid).
I handled a dynamic environment (a terrain with objects i can place) with a starting map (the terrain waycost), which i overlay with maps from a object (like a building). i did this using PIL (python image library), i think it also could be done with panda3d image functions but i have more experience with pil. (actually i dont remember how i did this last time, but i’d think it should work this way)
One thing you really have to take care of, is that you write you’re A* in python: Make it non blocking!!!
A* will take a while to calculate (in python), it is ok if a unit thinks 1-2 seconds which way to take. It is really really bad, if there is no visual update during this time (0.5fps???)…
How can I convert a set of eight characters (0s and 1s) into the grayscale value, and then back?
For example, I have a number 11111000. I want to convert it into certain value that will be saved in an 8-bit grayscale image. Then I will read the image, supply x, y coordinates for a pixel, retrieve its grayscale value, and convert back to original number.
I thought there are no replies because I have asked unclear question. So, here is more detailed question.
I am preparing the code that will traverse the loaded map and at the end save 8-bit grayscale PNG image with “barrier map”.
As you can see, now it returns a list of eight numbers. I need to know:
old useless code was herebyte = bit[0]* 1 + bit[1] * 2 + bit[2] * 4 + bit[3] * 8…
maybe you can also use the BitMask32 of panda?
I have not checked the image editing capabilities of panda3d yet. but pnmimage should be able read/write images. Maybe you directly want to work within a texture buffer.
I have used PIL often, as it’s “the image editor” of python. On the other hand it’s bad because it’s not panda3d compatible. At least i have never found out how to directly import a pil image into a panda3d texture (without save/load).
The problem solved!
First, I thought about string.atoi() function. But it has one problem: if I supply it with decimal number, it won’t return the binary one. But fortunately, the solution was found thanks to the author of this: aspn.activestate.com/ASPN/Cookbo … ipe/111286
I have made it a separate module of his code and imported it into my code. The code now works fine and looks like this:
old useless code was hereHere is working code. Barrier map is 2D grid saved as grayscale 8-bit PNG image. Requires additional module (baseconvert.py, posted after the main code). Works only with rectangular maps. Currently, only maps with flat (even) ground are suitable, but I am going to add support for uneven terrain.
import direct.directbase.DirectStart
from pandac.PandaModules import *
from direct.task.Task import Task
from baseconvert import *
import sys
# Set the minimal distance between objects,
# which allows actor to move in between.
cellSize = 1.0
# Set x, y coordinates of the top-left corner of the map.
topLeft = (-10, 10)
# Set x, y coordinates of the lower-right corner of the map.
lowerRight = (10, -10)
# Lift collision spheres above the ground by ... units.
liftBy = 0.1
# Do not change.
mXSize = lowerRight[0] - topLeft[0]
mYSize = topLeft[1] - lowerRight[1]
bmXSize = mXSize / cellSize
bmYSize = mYSize / cellSize
class Map():
def __init__(self):
'''self.barrier = loader.loadModel("collisionBox")
self.barrier.reparentTo(render)
self.barrier.setCollideMask(BitMask32.bit(1))'''
self.barrier = render.attachNewNode("barrier")
self.barrierCN = CollisionNode("barrierCN")
self.barrierSolid = CollisionTube(-2, 2, 0.5, 2, -2, 0.5, 1)
self.barrierCN.addSolid(self.barrierSolid)
self.barrierCN.setIntoCollideMask(BitMask32.bit(1))
self.barrierCNP = self.barrier.attachNewNode(self.barrierCN)
class Traveller():
def __init__(self):
# First, setup collisions.
self.setupCollisions()
# Cell row/column.
self.cellCoord = [0, 0]
# Define the first position of the cell.
self.cellPos = [topLeft[0]+self.radius, topLeft[1]-self.radius]
# Create an image for the barrier map.
self.mapImage = PNMImage(bmXSize, bmYSize)
self.mapImage.makeGrayscale()
# Analyze the cell.
taskMgr.add(self.analyzeCell, "analyzeCellTask")
def setupCollisions(self):
self.cTrav = CollisionTraverser()
self.handler = CollisionHandlerQueue()
self.cell = render.attachNewNode("cell")
self.radius = cellSize / 2.0
self.cn_c = self.cell.attachNewNode(CollisionNode("cn_c"))
self.cn_c.setPos(0, 0, 0)
self.cn_c.node().addSolid(CollisionSphere(0, 0, 0, self.radius))
self.setCMaskAddCollider(self.cn_c)
self.cn_tl = self.cell.attachNewNode(CollisionNode("cn_tl"))
self.cn_tl.setPos(-self.radius, self.radius, 0)
self.cn_tl.node().addSolid(CollisionSphere(0, 0, 0, self.radius))
self.setCMaskAddCollider(self.cn_tl)
self.cn_tr = self.cell.attachNewNode(CollisionNode("cn_tr"))
self.cn_tr.setPos(self.radius, self.radius, 0)
self.cn_tr.node().addSolid(CollisionSphere(0, 0, 0, self.radius))
self.setCMaskAddCollider(self.cn_tr)
self.cn_lr = self.cell.attachNewNode(CollisionNode("cn_lr"))
self.cn_lr.setPos(self.radius, -self.radius, 0)
self.cn_lr.node().addSolid(CollisionSphere(0, 0, 0, self.radius))
self.setCMaskAddCollider(self.cn_lr)
self.cn_ll = self.cell.attachNewNode(CollisionNode("cn_ll"))
self.cn_ll.setPos(-self.radius, -self.radius, 0)
self.cn_ll.node().addSolid(CollisionSphere(0, 0, 0, self.radius))
self.setCMaskAddCollider(self.cn_ll)
def setCMaskAddCollider(self, cn):
cn.node().setFromCollideMask(BitMask32.bit(1))
cn.node().setIntoCollideMask(BitMask32.allOff())
self.cTrav.addCollider(cn, self.handler)
def analyzeCell(self, task):
# Set the position of the self.cell.
self.cell.setPos(self.cellPos[0], self.cellPos[1], self.radius+liftBy)
# Run traverser.
self.cTrav.traverse(render)
self.recordCollisions()
self.plotPixel()
# Define row/column of the next cell.
self.cellCoord[0] += 1
if self.cellCoord[0] == bmXSize:
self.cellCoord[0] = 0
self.cellCoord[1] += 1
# Define position of the next cell.
self.cellPos[0] += cellSize
if self.cellPos[0] > lowerRight[0]:
self.cellPos[0] = topLeft[0]+self.radius
self.cellPos[1] -= cellSize
# If the next cell is within the map, continue the task,
# if not - finish the task.
if self.cellPos[1] > lowerRight[1]:
return Task.cont
else:
self.saveAndExit()
def recordCollisions(self):
self.entries = []
for i in range(self.handler.getNumEntries()):
self.entry = self.handler.getEntry(i).getFromNodePath()
self.entries.append(self.entry)
self.cellParamBinary = ["1"]*8
if self.entries.__contains__(self.cn_c):
# 0 means blocked
self.cellParamBinary[0] = "0"
else:
# 1 means free
self.cellParamBinary[0] = "1"
if self.entries.__contains__(self.cn_tl):
self.cellParamBinary[1] = "0"
else:
self.cellParamBinary[1] = "1"
if self.entries.__contains__(self.cn_tr):
self.cellParamBinary[2] = "0"
else:
self.cellParamBinary[2] = "1"
if self.entries.__contains__(self.cn_lr):
self.cellParamBinary[3] = "0"
else:
self.cellParamBinary[3] = "1"
if self.entries.__contains__(self.cn_ll):
self.cellParamBinary[4] = "0"
else:
self.cellParamBinary[4] = "1"
delimiter = ""
self.cellParamBinary = int(delimiter.join(self.cellParamBinary))
self.cellParamDecimal = baseconvert(self.cellParamBinary, BASE2, BASE10)
self.cellParamDecimal = int(self.cellParamDecimal)
print self.cellCoord, ":", self.cellParamBinary, self.cellParamDecimal
def plotPixel(self):
self.mapImage.setGrayVal(self.cellCoord[0],
self.cellCoord[1],
self.cellParamDecimal)
def saveAndExit(self):
self.mapImage.write(Filename("barrierMap.png"))
sys.exit()
m = Map()
t = Traveller()
run()baseconvert module:
BASE2 = "01"
BASE10 = "0123456789"
BASE16 = "0123456789ABCDEF"
def baseconvert(number, fromdigits, todigits):
""" converts a "number" between two bases of arbitrary digits
The input number is assumed to be a string of digits from the
fromdigits string (which is in order of smallest to largest
digit). The return value is a string of elements from todigits
(ordered in the same way). The input and output bases are
determined from the lengths of the digit strings. Negative
signs are passed through.
Source: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/111286
decimal to binary
>>> baseconvert(555,BASE10,BASE2)
'1000101011'
binary to decimal
>>> baseconvert('1000101011',BASE2,BASE10)
'555'
integer interpreted as binary and converted to decimal (!)
>>> baseconvert(1000101011,BASE2,BASE10)
'555'
base10 to base4
>>> baseconvert(99,BASE10,"0123")
'1203'
base4 to base5 (with alphabetic digits)
>>> baseconvert(1203,"0123","abcde")
'dee'
base5, alpha digits back to base 10
>>> baseconvert('dee',"abcde",BASE10)
'99'
decimal to a base that uses A-Z0-9a-z for its digits
>>> baseconvert(257938572394L,BASE10,BASE62)
'E78Lxik'
..convert back
>>> baseconvert('E78Lxik',BASE62,BASE10)
'257938572394'
binary to a base with words for digits (the function cannot convert this back)
>>> baseconvert('1101',BASE2,('Zero','One'))
'OneOneZeroOne'
"""
if str(number)[0]=='-':
number = str(number)[1:]
neg=1
else:
neg=0
# make an integer out of the number
x=long(0)
for digit in str(number):
x = x*len(fromdigits) + fromdigits.index(digit)
# create the result in base 'len(todigits)'
res=""
while x>0:
digit = x % len(todigits)
res = todigits[digit] + res
x /= len(todigits)
if neg:
res = "-"+res
return res