# Breadth First Search help needed

THIS IS THE BFS PSEUDO CODE

Add the starting node to the open list
While the open list is not empty
{
current node = first node from open list
if current node = goal node then
path complete
else
move current node to the closed list
examine each node adjacent to the current node
for each adjacent node
if isn’t on the open list
and isn’t on the closed list
and it isn’t an obstacle then
move it to end of open list
}

AND HERE IS MY CODE

``````def BFS(self,startCol, startRow, targetCol, targetRow):
self.startNode = Node.Node(startCol, startRow,0)
self.endNode = Node.Node(targetCol, targetRow,0)
#adding starting point to the list
self.openlist.append(self.startNode)
#Loop while openList contains some data
while len(self.openlist) !=0:
#Loop while openList contains some data
self.currentNode=self.openlist[0]
#Check if node is Destination
if self.currentNode.row == targetRow and self.currentNode.col== targetCol:
#path complete
self.closedlist.append(self.endNode)
print "path complete"
else:

#move current node to the closed list
self.closedlist.append(self.currentNode)

self.closedlist.append( self.openlist.pop(0))

#examine each node adjacent to the current node
neighs = isneighbour(currentNode,endNode)
for item in neighs:
if not self.openlist:
if not self.closedlist:
if not self.maze.maze[row][col]==1:
self.openlist.append(item)

def isneighbour(self,currentNode,endNode):
#to do
``````

how do i write the function isneighbour so it will examine each node adjacent to the current node?

hi, and welcome to the panda3d forum.

before anything else a few hints:
-there are code-tags like [ code ] to post codeblocks, you should use them or all indentation for python is lost, which makes it hardly readable.

-although you posted pseudocode and code aswell it would be nice if you could post what you want the code to do. means what’s your situation or what problem you’r trying to slove. sometimes it’s hard to figure from just the code.

from what i can guess, you seem to be working on some kind of maze. and it looks like you’r trying to do pathfinding from one point of the maze to the exit.

what i dont really get is what you mean by adjacent but if you’r looking for neighburs you “might” have the following options (since i dont know how you set up your scene and stuff)

``self.neighbourNode = Node.Node(startCol+x, startRow+y,0)``

and iterate over x= -1 ,+1 same for y.

``nodepath.getDistance(anotherNodepath)``

might be of use,too. if you want to check if 2 of your nodes are close enough to gether to actually be neighbours.

there might be a lot more sollutions.depends a little on how you’r doing things.

greetings,
thomas

thx for the tip thomas , firstly you are right , i am doing the ghost code in a maze game.i am trying to apply bfs pathfinding to the ghost class so it will find the shortest distance to reach the player.

``````
#BFS

#Add the starting node to the open list
#While the open list is not empty
def BFS(self,startCol, startRow, targetCol, targetRow):
self.startNode = Node.Node(startCol, startRow,0)
self.endNode = Node.Node(targetCol, targetRow,0)
#adding starting point to the list
self.openlist.append(self.startNode)
#Loop while openList contains some data
while len(self.openlist) !=0:
#Loop while openList contains some data
self.currentNode=self.openlist[0]
#Check if node is Destination
if self.currentNode.row == targetRow and self.currentNode.col== targetCol:
#path complete
self.closedlist.append(self.endNode)
print "path complete"
else:

#move current node to the closed list
self.closedlist.append(self.currentNode)

self.closedlist.append( self.openlist.pop(0))

#examine each node adjacent to the current node
##neighs = self.isneighbour(self.currentNode,self.endNode)
self.neighbourNode = Node.Node(startCol+x, startRow+y,0)
neighs = []
neighs.append(self.neighbourNode)
for item in neighs:
if not self.openlist:
if not self.closedlist:
if not self.maze.maze[row][col]==1:
self.openlist.append(item)``````

i am still abit confused on the get neighbour tiles part… i hope you dont mind helping abit more
[/code]