Pathfinding: A*-related question

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:
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 :slight_smile: 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 :slight_smile:
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… :unamused:

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)
might help you :slight_smile:

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:

  • how to convert this list into 8-bit binary number,
  • how to convert this binary number into grayscale value,
  • how to restore the binary number from the grayscale value,
  • how to read each bit in this binary number separately from other bits (I don’t want to convert it into list, because then it takes much more space in the memory).
old useless code was here

byte = 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! :slight_smile:
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: … 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 here

Here is working code. Barrier map is 2D grid saved as grayscale 8-bit PNG image. Requires additional module (, 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 = render.attachNewNode("barrier")
        self.barrierCN = CollisionNode("barrierCN")
        self.barrierSolid = CollisionTube(-2, 2, 0.5, 2, -2, 0.5, 1)
        self.barrierCNP = self.barrier.attachNewNode(self.barrierCN)

class Traveller():
    def __init__(self):
        # First, setup collisions.
        # 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)
        # 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.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.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.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.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))

    def setCMaskAddCollider(self, cn):
        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.
        # 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

    def recordCollisions(self):
        self.entries = []
        for i in range(self.handler.getNumEntries()):
            self.entry = self.handler.getEntry(i).getFromNodePath()

        self.cellParamBinary = ["1"]*8
        if self.entries.__contains__(self.cn_c):
            # 0 means blocked
            self.cellParamBinary[0] = "0"
            # 1 means free
            self.cellParamBinary[0] = "1"
        if self.entries.__contains__(self.cn_tl):
            self.cellParamBinary[1] = "0"
            self.cellParamBinary[1] = "1"
        if self.entries.__contains__(self.cn_tr):
            self.cellParamBinary[2] = "0"
            self.cellParamBinary[2] = "1"
        if self.entries.__contains__(self.cn_lr):
            self.cellParamBinary[3] = "0"
            self.cellParamBinary[3] = "1"
        if self.entries.__contains__(self.cn_ll):
            self.cellParamBinary[4] = "0"
            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):
    def saveAndExit(self):

m = Map()
t = Traveller()


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.


    decimal to binary
    >>> baseconvert(555,BASE10,BASE2)

    binary to decimal
    >>> baseconvert('1000101011',BASE2,BASE10)

    integer interpreted as binary and converted to decimal (!)
    >>> baseconvert(1000101011,BASE2,BASE10)

    base10 to base4
    >>> baseconvert(99,BASE10,"0123")

    base4 to base5 (with alphabetic digits)
    >>> baseconvert(1203,"0123","abcde")

    base5, alpha digits back to base 10
    >>> baseconvert('dee',"abcde",BASE10)

    decimal to a base that uses A-Z0-9a-z for its digits
    >>> baseconvert(257938572394L,BASE10,BASE62)

    ..convert back
    >>> baseconvert('E78Lxik',BASE62,BASE10)

    binary to a base with words for digits (the function cannot convert this back)
    >>> baseconvert('1101',BASE2,('Zero','One'))

    if str(number)[0]=='-':
        number = str(number)[1:]

    # make an integer out of the number
    for digit in str(number):
       x = x*len(fromdigits) + fromdigits.index(digit)

    # create the result in base 'len(todigits)'
    while x>0:
        digit = x % len(todigits)
        res = todigits[digit] + res
        x /= len(todigits)
    if neg:
        res = "-"+res

    return res