### Thread: Help with Understanding Function

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6

#### Help with Understanding Function

Alright this problem is about an A* algorithm function. I do know how A* works because I recently designed a script following a Youtube tutorial (here's a link to the Pythonista project thread with more details) but this particular script is giving me problems because I can't understand it!

If you don't know A* (also known as "A Star Pathfinding"), it checks through a grid for the shortest path, using only a few variables and a heuristic, and can be used to walk around obstacles. It's mainly used in games, which is what I'm using it for.

It came from a StackOverflow thread.

Code:
```def aStar(self, graph, current, end):
openList = set()
closedList = set()

def retracePath(c):
def parentgen(c):
while c:
yield c
c = c.parent
result = [element for element in parentgen(c)]
result.reverse()
return result

while openList:
current = sorted(openList, key=lambda inst:inst.H)[0]
if current == end:
return retracePath(current)
openList.remove(current)
for tile in graph[current]:
if tile not in closedList:
tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10
tile.parent = current
return []```

The problem I am having is what are the input types and values. Could anyone please give me an example calling the function that returns a working path, that would be fantastic. I could modify the function to fit my needs.

I think the graph contains a list of class objects which each has an x, y, H, and parent value. But I can't get a script that actually returns an output and I know it's due to my inexperience..

Thanks for any help
Last edited by eliskan; April 5th, 2013 at 02:59 AM.
2. I think you'd be better off starting with
http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

For one thing, you'd be able to define the graph in a way that fits your needs.

otherwise, it uses the same terminology as the algorithm you found.

aStar does not use its first parameter, self. It was probably ((100-epsilon)% certainly) a method in a class. But it shouldn't be. I removed the argument and shoved aStar over to the left hand margin.

aStar is lazy. It generates the heuristic only when needed. Why does it multiply by 10? Unknown, I remove the factor. The heuristic gives minimal taxi-cab distance (that is, walks on the sidewalks doesn't fly over the buildings) and that's why I chose square tiles. You know, if the blocks were rectangular as in Manhattan you could represent that by multiplying the difference in x by 4, for example.

Well, I made the code even lazier. I don't bother generating Tile objects until they are needed. So here it is, I made it work. The input graph is a 2-dimensional Boolean array. I generated random integers 0, 1, 2, or 3 for each cell of an array, and used "array not equal 0" followed with minor editing.
Code:
```'''
Problem: find a path from (0,0) to (0,7).
ones are tiles.  zeros are illegal squares.
tiles are square (boring!) and connect with
GRAPH   NB. with coordinates.
1 1 1 1 1 1 | 7
1 0 1 0 1 1 | 6
1 1 1 1 1 1 | 5  ^
0 1 1 0 1 1 | 4  |  y
1 1 1 1 1 1 | 3
1 1 0 1 1 1 | 2
1 1 1 1 1 1 | 1
1 1 1 1 0 0 | 0
-----------
0 1 2 3 4 5   x->

+/,GRAPH  NB. there are 41 tiles
41
'''

import pprint

class Graph:

def __init__(self,g):
self.g = g

def __getitem__(self,item):
(x, y) = (item.x, item.y)
g = self.g
Y = y
for dx in (-1, 1):
X = x+dx
if -1 < X:
try:
if g[Y][X]:
yield Tile(X,Y)
except IndexError:
pass
X = x
for dy in (-1, 1):
Y = y+dy
if -1 < Y:
try:
if g[Y][X]:
yield Tile(X,Y)
except IndexError:
pass

class Tile:

def __init__(self,x,y):
self.x = x
self.y = y
self.H = 0
self.parent = None
self.hash = hash((x,y))

def __str__(self):
return 'Tile({},{})'.format(self.x,self.y)

def __hash__(self):
return self.hash

def __eq__(self,other):
try:
return (self.x == other.x) and (self.y == other.y)
except:
pass
raise TypeError('comparing {} and {} failed'.format(self,other))

#import pdb

def aStar(graph, current, end):
openList = set()
closedList = set()

def retracePath(c):
def parentgen(c):
while c:
yield c
c = c.parent
result = [element for element in parentgen(c)]
result.reverse()
return result

#pdb.set_trace()
while openList:
current = sorted(openList, key=lambda inst:inst.H)[0]
if current == end:
return retracePath(current)
openList.remove(current)
for tile in graph[current]:
if tile not in closedList:
tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))
tile.parent = current
return []

g = Graph((
(1,1,1,1,0,0,),
(1,1,1,1,1,1,),
(1,1,0,1,1,1,),
(1,1,1,1,1,1,),
(0,1,1,0,1,1,),
(1,1,1,1,1,1,),
(1,0,1,0,1,1,),
(1,1,1,1,1,1,),),)

pprint.pprint(list(map(str,aStar(g,Tile(0,0),Tile(0,7)))))
# output
#['Tile(0,0)',
# 'Tile(0,1)',
# 'Tile(0,2)',
# 'Tile(0,3)',
# 'Tile(1,3)',
# 'Tile(1,4)',
# 'Tile(1,5)',
# 'Tile(0,5)',
# 'Tile(0,6)',
# 'Tile(0,7)']```

• eliskan agrees : Awesome help! Thanks a ton for your advice and showing the data types for this code. I did notice it's a lot like the A* pseudocode on wikipedia which is why I wanted to use it, since it's already written in Python and it was optimized. Ty again!
Last edited by b49P23TIvg; April 5th, 2013 at 05:03 PM.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6
Awesome help as always b4. You really are an incredibly helpful person

Now that I can actively test the code out, I will be formatting it into my graph's proper datatype (my graph contains is simply an array of tiles, very similar to how this one is set up). You showed me some cool tricks with how to use classes in this.

All around thanks alot again for your help. I hope you don't mind if I return with any problems further down the line

As a side question, do you have an iPad or iPhone? I have been programming all these things in Pythonista, an app for iOS that lets you write Python programs, and I was just curious if you've heard of it or if you're interested in getting the app. Someone like you would be a godsend for developing apps in Python.
5. Wait! That aStar search is not optimized. Instead of sorting the frontier each time
sorted(openList, key=lambda inst:inst.H)
the code should store the frontier on a min heap.
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6
Alright I was trying my best to avoid asking more questions, but I am struggling..

I almost have this implemented. Almost. I just cant figure out how to work out this one part of the code that keeps throwing the error. The code isn't much changed, I have only added my data types which I am trying to switch from yours. Because they're the ones already built into the game and used heavily in tilemapping and graphics, I have to stick with those formats. The ones in the game hold much more data:

Code:
```from random import choice
import pprint

CLIFF, SAND, MTN, GRASS, MTN_TO_WATER, WATER, SAND_TO_WATER = 0, 1, 2, 3, 4, 5, 6
g_x, g_y = 3,3
#Each 'node' contains data about its location and type
class node (object):
def __init__(self, location):
self.x, self.y = location.x, location.y
self.H = 0
self.type = choice([MTN,MTN_TO_WATER,SAND])

class Point (object):
def __init__(self, x, y):
self.x, self.y = x, y

def aStar(graph, current, end):
openList = set()
closedList = set()

def retracePath(c):
def parentgen(c):
while c:
yield c
c = c.parent
result = [element for element in parentgen(c)]
result.reverse()
return result

while openList:
#current becomes the best one available, based on heuristic
current = sorted(openList, key=lambda inst:inst.H)[0]
if current == end:
return retracePath(current)
openList.remove(current)

#Neighbors of current node
for tile in graph[current]:
if tile not in closedList:
#Heuristic is manhattan distance
tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))
tile.parent = current
return []

newG = []
for x in xrange(g_x):
for y in xrange(g_y):
newG.append(node(Point(x,y)))

#Print graph.
#for nodes in newG:
#    print "Pos: ("+str(nodes.x)+", "+str(nodes.y)+"), Type: "+str(nodes.type)

target_list = aStar(newG,newG[0],newG[-1])```

Traceback (most recent call last):
File "C:/Python26/Scripts/a_star-b49P23TIvg-3.py", line 57, in <module>
target_list = aStar(newG,newG[0],newG[-1])
File "C:/Python26/Scripts/a_star-b49P23TIvg-3.py", line 40, in aStar
for tile in graph[current]:
TypeError: list indices must be integers, not node

So right now it's just a random map of different types. 4 (MTN_TO_WATER) is the impassable terrain but others will also be different passability. That's not the problem, I believe I can work that into the heuristic easily.

What I'm struggling with is the line that says "for tile in graph[current]:" ... I don't understand the __getitem__ function, but I know it's creating the neighbors and checks if they're not 0 to know they're passable. I need help working that into my nodes class. Does each node need to record its index value?

I really appreciate help with this. I am a newbie programmer, but hey if you ever need any design or photoshop work done, I'm not half bad in that

((I did investigate the minheap suggestion and I agree it's better 100%, but for now I'd rather not bite off more than I can chew. I can't even get this working >.<))
Last edited by eliskan; April 17th, 2013 at 05:50 AM.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6
Yeah lol I am mainly directing my question at b4, he knows his stuff!!!

If I were hiring a programmer... *hint hint*
8. The graph input to aStar post 2 this thread is a Graph object. That object supports a __getitem__ . __getitem__ returns a list of Tile objects accessible from the tile supplied as the item argument to __getitem__ .

Working on the lazy theme, I decided to write __getitem__ as a generator. The program is also supposed to support piers. Untested. The graph shouldn't need to be rectangular. That's why I chose exception traps around index error. Other methods can work too. I expect my code would work using a map of valid squares like
Code:
```g = Graph((
(1,1,1,1,0,0,),
(1,1,1,1,1,1,),
(1,1,0,1,1,1,),
(1,1,1,1,1,1,1,1,1,1,1),
(0,1,1,0,1,1,),
(1,1,1,1,1,1,1,1,1,0,1,1),
(1,0,1,0,1,1,1,0,1,1,1),
(1,1,1,1,1,1,),),)```
Clearly I thought Tile objects needed to support some features as well. hash so they can be used in sets--- hashing based on the coordinate tuple made sense to me; str for reasonable display; and aStar also tests for equality.
if current == end:
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6
Thanks again for the help b4. I finally got it working and am now in the process of importing it into my game so I can test the function in a runtime environment!

I did notice that this search is doing the same thing that my old A* search did - a greedy first search. It will sacrifice the shortest path because the manhattan heuristic needs tweaking.

The way I solved this in my last A* pathfinder was that the heuristic was added onto the parents heuristic, so each step further from the start is a larger heuristic. That rewards shortest paths and makes the walk path much more direct and effective. It does however (usually) increase the number of nodes that will be searched. Still I think this is how true A* is implemented. I will probably try to get that working in this script as well.

Thanks again. You should be a Python teacher, you know too much!

edit: wow it was super easy to make that change. Just right after the line where it defines H, I added on current.H (which is going to become the parent) and it works like a charm. Straight lines for the win!

I know this file has a few flaws, but b4 you're welcome to peek at it! I had to.. dummy things down because I am simply not able to comprehend your coding. It's my fault lol but I learn every time I study your programs.

http://gist.github.com/eliskan/5411098

edit2: Noticed serious problems when the tiles (or I call them nodes) weren't cleaned if you called aStar a second time. The H values and parents need to be reset or the program will crash in an infinite loop.
Last edited by eliskan; April 18th, 2013 at 03:51 AM.
10. Since I can't count to 7, I'd go with
Code:
`CLIFF, SAND, MTN, GRASS, MTN_TO_WATER, WATER, SAND_TO_WATER = range(len('CLIFF, SAND, MTN, GRASS, MTN_TO_WATER, WATER, SAND_TO_WATER'.split(',')))`
11. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
43
Rep Power
6
Haha I think you're better off just counting!

You're crazy, in the best of ways.

Seriously if you need some design work done let me know, I will help you out. It's the least I can do, this aStar was a trick to comprehend. I am getting more familiar with it as I use it in my program.
12. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Location
Japan
Posts
20
Rep Power
0
This is exactly what I am trying to work with myself, but not sure how to integrate it with what I am doing. Rather that plotting along a set grid, I was wondering how one would modify this for a sprite moving through the screen and avoiding walls.

For purposes of experimenting, I grabbed this program (its not mine, but looked like it would be a good skeleton to work with while trying to wrap my head around this):

python Code:
```
import pygame

black  = (  0,  0,  0)
white  = (255,255,255)
blue   = (  0,  0,255)
green  = (  0,255,  0)
red    = (255,  0,  0)
purple = (255,  0,255)

# This class represents the bar at the bottom that the player controls
class Wall(pygame.sprite.Sprite):
# Constructor function
def __init__(self,x,y,width,height, color):
# Call the parent's constructor
pygame.sprite.Sprite.__init__(self)

# Make a blue wall, of the size specified in the parameters
self.image = pygame.Surface([width, height])
self.image.fill(color)

# Make our top-left corner the passed-in location.
self.rect = self.image.get_rect()
self.rect.y = y
self.rect.x = x

# This class represents the bar at the bottom that the player controls
class Player(pygame.sprite.Sprite):

# Set speed vector
change_x = 0
change_y = 0

# Constructor function
def __init__(self,x,y):
# Call the parent's constructor
pygame.sprite.Sprite.__init__(self)

# Set height, width
self.image = pygame.Surface([15, 15])
self.image.fill(white)

# Make our top-left corner the passed-in location.
self.rect = self.image.get_rect()
self.rect.y = y
self.rect.x = x

# Change the speed of the player
def changespeed(self,x,y):
self.change_x+=x
self.change_y+=y

# Find a new position for the player
def update(self,walls):
# Move left/right
self.rect.x += self.change_x

# Did this update cause us to hit a wall?
block_hit_list = pygame.sprite.spritecollide(self, walls, False)
for block in block_hit_list:
# If we are moving right, set our right side to the left side of the item we hit
if self.change_x > 0:
self.rect.right = block.rect.left
else:
# Otherwise if we are moving left, do the opposite.
self.rect.left = block.rect.right

# Move up/down
self.rect.y += self.change_y

# Check and see if we hit anything
block_hit_list = pygame.sprite.spritecollide(self, walls, False)
for block in block_hit_list:

# Reset our position based on the top/bottom of the object.
if self.change_y > 0:
self.rect.bottom = block.rect.top
else:
self.rect.top = block.rect.bottom

# This creates all the walls in room 1
def setupRoomOne():
# Make the walls. (x_pos, y_pos, width, height)
wall_list=pygame.sprite.Group()

# This is a list of walls. Each is in the form [x, y, width, height]
walls = [ [0,0,20,250,white],
[0,350,20,250,white],
[780,0,20,250,white],
[780,350,20,250,white],
[20,0,760,20,white],
[20,580,760,20,white],
[390,50,20,500,blue]
]

# Loop through the list. Create the wall, add it to the list
for item in walls:
wall=Wall(item[0],item[1],item[2],item[3],item[4])

# return our new list
return wall_list

# This creates all the walls in room 2
def setupRoomTwo():
# Make the walls. (x_pos, y_pos, width, height)
wall_list=pygame.sprite.Group()

walls = [ [0,0,20,250,red],
[0,350,20,250,red],
[780,0,20,250,red],
[780,350,20,250,red],
[20,0,760,20,red],
[20,580,760,20,red],
[190,50,20,500,green],
[590,50,20,500,green]
]

for item in walls:
wall=Wall(item[0],item[1],item[2],item[3],item[4])

return wall_list

# This creates all the walls in room 3
def setupRoomThree():
# Make the walls. (x_pos, y_pos, width, height)
wall_list=pygame.sprite.Group()

walls = [ [0,0,20,250,purple],
[0,350,20,250,purple],
[780,0,20,250,purple],
[780,350,20,250,purple],
[20,0,760,20,purple],
[20,580,760,20,purple]
]

for item in walls:
wall=Wall(item[0],item[1],item[2],item[3],item[4])

for x in range(100,800, 100):
for y in range(50, 451, 300):
wall = Wall(x, y, 20, 200,red)

for x in range(150,700, 100):
wall = Wall(x, 200, 20, 200,white)

return wall_list

score = 0
# Call this function so the Pygame library can initialize itself
pygame.init()

# Create an 800x600 sized screen
screen = pygame.display.set_mode([800, 600])

# Set the title of the window
pygame.display.set_caption('Maze Runner')

# Create a surface we can draw on
background = pygame.Surface(screen.get_size())

# Used for converting color maps and such
background = background.convert()

# Fill the screen with a black background
background.fill(black)

# Create the player paddle object
player = Player( 50,50 )
movingsprites = pygame.sprite.Group()

current_room = 1
wall_list = setupRoomOne()

clock = pygame.time.Clock()

done = False

while done == False:
# ALL EVENT PROCESSING SHOULD GO BELOW THIS COMMENT
for event in pygame.event.get():
if event.type == pygame.QUIT:
done=True

if event.type == pygame.KEYDOWN:
if event.key == pygame.K_LEFT:
player.changespeed(-5,0)
if event.key == pygame.K_RIGHT:
player.changespeed(5,0)
if event.key == pygame.K_UP:
player.changespeed(0,-5)
if event.key == pygame.K_DOWN:
player.changespeed(0,5)

if event.type == pygame.KEYUP:
if event.key == pygame.K_LEFT:
player.changespeed(5,0)
if event.key == pygame.K_RIGHT:
player.changespeed(-5,0)
if event.key == pygame.K_UP:
player.changespeed(0,5)
if event.key == pygame.K_DOWN:
player.changespeed(0,-5)
# ALL EVENT PROCESSING SHOULD GO ABOVE THIS COMMENT

# ALL GAME LOGIC SHOULD GO BELOW THIS COMMENT
player.update(wall_list)
if player.rect.x < -15:
if current_room == 1:
wall_list = setupRoomThree()
current_room = 3
player.rect.x = 790
elif current_room == 3:
wall_list = setupRoomTwo()
player.rect.x = 790
current_room = 2
else:
wall_list = setupRoomOne()
player.rect.x = 790
current_room = 1

if player.rect.x > 801:
if current_room == 1:
wall_list = setupRoomTwo()
current_room = 2
player.rect.x = 0
elif current_room == 2:
wall_list = setupRoomThree()
current_room = 3
player.rect.x = 0
else:
wall_list = setupRoomOne()
current_room = 1
player.rect.x = 0

# ALL GAME LOGIC SHOULD GO ABOVE THIS COMMENT

# ALL CODE TO DRAW SHOULD GO BELOW THIS COMMENT
screen.fill(black)

movingsprites.draw(screen)
wall_list.draw(screen)
# ALL CODE TO DRAW SHOULD GO ABOVE THIS COMMENT

pygame.display.flip()

clock.tick(40)

pygame.quit()```

So yeah, that works fine as it is, what I would like to do is to take the A* thing you have there and use it to plot a path for the little square. Instead of using the keyboard for input, I would swap out a mouse click to get an x,y location and then send the square on its way. For purposes of this, it would move one axis at a time, just x or y. What I would like it to do is keep heading straight until it bumps into a wall, then go around it. This one right now is puttering along at 5 pixels a frame, but I suppose that could be set to pretty much anything and work the same. So instead of a graph array like you guys have set up, is it possible to do with groups of sprite rects? Somehow replace the graph class with the walls list, and end in the astar function being the spot you click? I am sorry that I dont have much to work with. I have been reading A* theory all day and while I get what it is supposed to do, the implementation bit completely eludes me.