Check if space is empty

Hello,

I’m working on some A* code here and want to get a path through the level.
The level is not grid based, and the player can move in any direction he or she wishes, so I’m trying to spawn a bunch of CollideSphere()'s to see if a step along the way is “walkable”.

Here is the problematic part for my litte Path class:

	
	def walkable( self, spot, size ):
		cs = CollisionSphere( 0,0,0,self.osize)
		cnp = render.attachNewNode(CollisionNode("TmpCollNode"))
		cnp.node().addSolid(cs)
		cnp.setPos(spot)
		queue = CollisionHandlerQueue()
		traverser = CollisionTraverser('TmpTraverser')
		traverser.addCollider(cnp, queue)
		traverser.traverse(render)
		for i in range(queue.getNumEntries()):
			entry = queue.getEntry(i)
			print entry
			
		cnp.show() # For debug reasons
		# cnp.removeNode() #I want to see the sphere

It’s not working, and I think I don’t fully understand collisions. :slight_smile:
Could anyone help me out a little? I want it to return True or False depending on if the sphere hit something.

The spheres shows up, but I get this error in the console:

I’m not using a ray there, do I? I do use some mouse picking code I found here yesterday, might that be interfering a bit?

I was able to remove the “:collide(error):”, but the function still doesn’t find collisions:

	def walkable( self, spot, size ):
		cs = CollisionSphere( spot[0],spot[1],spot[2], size)
		cnp = render.attachNewNode(CollisionNode("TmpCollNode"))
		cnp.node().addSolid(cs)
		#cnp.setPos(spot)
		cnp.node().setFromCollideMask(BitMask32(0x10))
		cnp.node().setIntoCollideMask(BitMask32(0))
		queue = CollisionHandlerQueue()
		traverser = CollisionTraverser('TmpTraverser')
		traverser.addCollider(cnp, queue)
		traverser.traverse(render)
		#for i in range(queue.getNumEntries()):
		#	entry = queue.getEntry(i)
		#	print entry
		cnp.show() # For debug reasons, show where it collided
		if queue.getNumEntries() > 0: return False
			
		cnp.removeNode() # Doesn't need it anymore. No collision was found anyway.
		return True

it’s possible I’m not getting 100% what you need but if you just need to move a puppet around you definitely have to download and study this simple example where a puppet moves with the classic wasd keys in a room and clicking here you got another with a point-n-click mechanic. Hope it helps.

Thank you, but not realy what I want. :slight_smile:

I want to see if a position is empty like this:

  if walkable( current_position+Vec3(-1,0,0), 0.25 ):
    # The position to my left is empty, and I can go there. 

Kind off. I want to use it in my pathfinding code. And I want this code to work no matter what model I use as a level for the game.

At the moment I’m trying to get it to work with CollisionSphere() but I have a problem with that it doesn’t register any collisions. I think it is because I have misunderstood how collision masks work. Currently re-reading the manual for the n-th time and is hoping that my english skills is up to the task, this time.

if you need to understand better how to perform pathfinding and pseudo AI in general you should appreciate this code sample

Thank you, will have a look at it. Here is another nice tutorial on A* pathfinding: policyalmanac.org/games/aStarTutorial.htm

But the pathfinding algorithm isn’t the problem for me. The problem is to get collisions in the first place. :confused:

Finally, got it working. Below is my classes if somebody would like to see them.
Very much unoptimized indeed! Probably a bunch of bugs as well.
There is most likely better ways of doing it!
But it works, and speed isn’t an issue in my case (even if it takes forever for my class to find a distance that is more than a few meters away :stuck_out_tongue:)

from pandac.PandaModules import *

class PNode:
	def __init__(self, g,h, pos, parent ):
		self.g = g
		self.h = h
		self.pos = pos
		self.f = self.g + self.h
		self.parent = parent

def sortPNode( x,y ):
	return int(x.f-y.f)

class Path:
	def __init__(self, startp, endp, gsize, osize ):
		self.startp = startp
		self.endp = endp
		self.gsize = gsize
		self.osize = osize

	def visited( self,pos ):
		for n in self.open:
			if n.pos == pos:
				return True
		return False
		
	def findInOpen( self,pos ):
		index = 0
		for n in self.open:
			if n.pos == pos:
				return n,index
			index+=1
		return None,None
		
	def calculate(self):
		self.open = []
		self.closed = []
		self.startn = PNode(0,0,self.startp,None)
		self.open.append( self.startn )
		while len(self.open) > 0:
			current = self.open.pop(0)
			self.closed.append(current)
			if (current.pos - self.endp).length() < self.gsize*1.5: # Are we there yet?
				fp = []
				while current.parent != None:
					fp.insert( 0,current.pos )
					current = current.parent					
				fp.append( self.endp )
				return fp

			for x in range(-1,2):
				for y in range(-1,2):
					for z in range(-1,2):
						self.examinePos(current, x,y,z)
				
		# We were unable to find a path
		return None

	def examinePos(self, current, xo,yo,zo ):
		if xo == 0 and yo == 0 and zo == 0: return
		cost = 10
		if (xo!=0 or yo!=0 or zo!=0) and (xo == yo or yo == zo or zo == xo): cost = 15
		
		np = current.pos+Vec3(self.gsize*xo,self.gsize*yo,self.gsize*zo)
		if not self.visited(np) and self.walkable( np, self.osize ):
			heur = int(abs(self.endp[0]-np[0]) + abs(self.endp[1]-np[1]) + abs(self.endp[2]-np[2]))*10
			on,index = self.findInOpen( np )
			if not on:
				self.open.append( PNode(current.g+cost,heur,np,current) )
				self.open.sort(sortPNode)
			else:
				if on.g > current.g+cost:
					self.open[index] = PNode(current.g+cost,heur,np,current) 
					self.open.sort(sortPNode)

			
	def walkable( self, spot, size ):
		self.cs = CollisionSphere( spot[0],spot[1],spot[2], size)
		self.cnp = render.attachNewNode(CollisionNode("TmpCollNode"))
		self.cnp.node().addSolid(self.cs)
		self.cnp.node().setCollideMask(BitMask32.allOff())
		self.cnp.node().setCollideMask(BitMask32.bit(20))
		self.queue = CollisionHandlerQueue()
		self.traverser = CollisionTraverser('TmpTraverser')
		self.traverser.addCollider(self.cnp, self.queue)
		self.traverser.traverse(render)
		self.cnp.removeNode()
		if self.queue.getNumEntries() > 0: 
			return False
			
		return True

Small usage tutorial:

# Each node is 1 unit away, and the object passing through has 0.5 units in radius
planner = Path( Vec3(0,0,0), Vec3(4,5,2), 1, 0.5 )
path = planner.calculate()
# Unless path is None, we have a list of positions to travel through...
movseq = Sequence(name="MovePlayer")
for n in path:
  movseq.append( player.node.posInterval(0.25,n) )
movseq.start()

Please note that the code is ripped out of my current object and untested here.
Next on the todo list: Make calculate spawn a task that plans the path a few steps at a time so the game doesn’t freeze. :stuck_out_tongue:
And later I will see if I can come up with some code to remove unnecessary nodes in the path. (only have start, end and corner points)

EDIT: updated it. It should be a bit quicker now. (Still very slow over large areas)