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

    Join Date
    Nov 2012
    Posts
    43
    Rep 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
    
        openList.add(current)
        while openList:
            current = sorted(openList, key=lambda inst:inst.H)[0]
            if current == end:
                return retracePath(current)
            openList.remove(current)
            closedList.add(current)
            for tile in graph[current]:
                if tile not in closedList:
                    tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                    openList.add(tile)
                    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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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
           adjacent tiles sharing an edge.
           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
    
        openList.add(current)
        #pdb.set_trace()
        while openList:
            current = sorted(openList, key=lambda inst:inst.H)[0]
            if current == end:
                return retracePath(current)
            openList.remove(current)
            closedList.add(current)
            for tile in graph[current]:
                if tile not in closedList:
                    tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))
                    openList.add(tile)
                    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)']

    Comments on this post

    • 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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    I downloaded the android simulator and development environment.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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
    
        openList.add(current)
        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)
            closedList.add(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))
                    openList.add(tile)
                    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.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

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

    If I were hiring a programmer... *hint hint*
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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:
    [code]Code tags[/code] are essential for python code and Makefiles!
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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 03:51 AM.
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    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(',')))
    [code]Code tags[/code] are essential for python code and Makefiles!
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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.

IMN logo majestic logo threadwatch logo seochat tools logo