Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 5th, 2013, 02:39 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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 03:59 AM.

#2
April 5th, 2013, 05:56 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,116
Time spent in forums: 1 Month 3 Weeks 2 Days 3 h 2 m 43 sec
Reputation Power: 455
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!
__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : April 5th, 2013 at 06:03 PM.

#3
April 5th, 2013, 09:38 PM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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.

#4
April 5th, 2013, 09:42 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,116
Time spent in forums: 1 Month 3 Weeks 2 Days 3 h 2 m 43 sec
Reputation Power: 455

#5
April 5th, 2013, 09:49 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,116
Time spent in forums: 1 Month 3 Weeks 2 Days 3 h 2 m 43 sec
Reputation Power: 455
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
April 17th, 2013, 02:12 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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 06:50 AM.

#7
April 17th, 2013, 06:35 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
Yeah lol I am mainly directing my question at b4, he knows his stuff!!!

If I were hiring a programmer... *hint hint*

#8
April 17th, 2013, 10:45 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,116
Time spent in forums: 1 Month 3 Weeks 2 Days 3 h 2 m 43 sec
Reputation Power: 455
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
April 18th, 2013, 02:52 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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 04:51 AM.

#10
April 18th, 2013, 11:34 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,116
Time spent in forums: 1 Month 3 Weeks 2 Days 3 h 2 m 43 sec
Reputation Power: 455
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
April 19th, 2013, 03:10 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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.

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Help with Understanding Function