Lachlan's misadventures in games programming

Sunday, 7 September 2014

A* Pathfinding in Python

9/07/2014 03:12:00 am Posted by Lachlan , No comments
I thought the following might be helpful to some of you. It's a snippet of code in Python to perform A* Pathfinding.

I've been avoiding writing it for ages, but have been yet again impressed by how little Python gets in the way of what I'm doing. I remain impressed by the language.

Again, method was found on http://www.policyalmanac.org/games/aStarTutorial.htm

It's reasonably well commented, and should slot it fairly easily into any grid-based environment. It doesn't support weighting yet - but it would be trivial to add (include the weight when adding distance for g).

I apologise for my inconsistent naming conventions. I started the project with no idea about Python, and the A* had to fit into that dodgy area. Essentially, you'll have to replace self.x and self.y with the starting potion and replace reference to self.currentMap.Walkable with where to get a boolean value of the walkability of the position.

And again, this is released under my modified UnLicense:
Lachlan's Very Public Licence - which is a slightly modified Unlicense
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or distribute this software, either in source code form or as a compiled binary, for any purpose, commercial or non-commercial, and by any means.
In jurisdictions that recognize copyright laws, the author or authors of this software dedicate any and all copyright interest in the software to the public domain. We make this dedication for the benefit of the public at large and to the detriment of our heirs and successors. We intend this dedication to be an overt act of relinquishment in perpetuity of all present and future rights to this software under copyright law.
If you use the source, the Author (Lachlan Kingsford) would actually like to know - but it's by no means necessary. Feel welcome to provide a copy of what you do via email, or comment on www.nerdygentleman.com. Attribution is also nice and appreciated, but again, by no means necessary. Donations via paypal are also nice.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


    def GetRoute(self, dest):
        # Performs an A* search to find route to go somewhere
        # Input:
        #   x, y - from self.x and self.y
        #   self.currentMap.Walkable(x,y) - returns if can walk at x,y
        #   dest - (x, y) tuplet of destination
        #
        # Returns a list of (x, y) tuplets
        # 
        # From <http://www.policyalmanac.org/games/aStarTutorial.htm>
        # 1) Add the starting square (or node) to the open list.
        # 2) Repeat the following:
        #   a) Look for the lowest F cost square on the open list. We refer to this as the current square.
        #   b) Switch it to the closed list.
        #   c) For each of the 8 squares adjacent to this current square 
        #      If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           
        #      If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 
        #      If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
        #   d) Stop when you:
        #      Add the target square to the closed list, in which case the path has been found (see note below), or
        #      Fail to find the target square, and the open list is empty. In this case, there is no path.   
        # 3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
        
        # ORTH_DISTANCE and DIAG_DISTANCE are for weights of travelling between the cells orthogonally
        # and diagonally respectively. If diagoanal is further in game, then DIAG_DISTANCE should be 14
        # As the distances are the same in mine, they're weighted evenly
        ORTH_DISTANCE = 10
        DIAG_DISTANCE = 10
        
        # Heuristic for calculating h is Manhattan Distance - 
        #   abs(pos.x - dest.x) + abs(pos.y - dest.y)
        
        # OpenLists consists of tuplets with (
        #   [0]: Position.x, 
        #   [1]: Position.y,
        #   [2]: ParentPosition.x, 
        #   [3]: ParentPosition.y,
        #   [4]: g (distance to get here from parent),
        #   [5]: h (heuristic distance to destination) )
        OpenList = [(self.x, self.y, self.x, self.y, 0, abs(self.x-dest[0]) + abs(self.y-dest[1]))]     
        ClosedList = []
        while (len(OpenList) > 0 and (len([k for k in OpenList if k[0] == dest[0] and k[1] == dest[1]]) == 0)):             
            # Find entry in OpenList with lowest F score
            # F = G + H                     
            Current = min(OpenList, key=lambda i:i[4]+i[5])         
            OpenList.remove(Current)
            ClosedList.append(Current)
            Active = [(Current[0] - 1,  Current[1],     Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] - dest[1])),
                (Current[0] + 1,    Current[1],     Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] - dest[1])),
                (Current[0] - 1,    Current[1] - 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] - 1 - dest[1])),
                (Current[0] + 1,    Current[1] - 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] - 1 - dest[1])),
                (Current[0] - 1,    Current[1] + 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] - 1 - dest[0])   + abs(Current[1] + 1 - dest[1])),
                (Current[0] + 1,    Current[1] + 1, Current[0], Current[1], Current[4] + DIAG_DISTANCE, abs(Current[0] + 1 - dest[0])   + abs(Current[1] + 1 - dest[1])),
                (Current[0],        Current[1] - 1, Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] - dest[0])       + abs(Current[1] - dest[1] - 1)),
                (Current[0],        Current[1] + 1, Current[0], Current[1], Current[4] + ORTH_DISTANCE, abs(Current[0] + dest[0])       + abs(Current[1] - dest[1] + 1))]
            for i in Active:
                # If point not in closed list and is walkable
                if (len([j for j in ClosedList if j[0] == i[0] and j[1] == i[1]]) == 0) and self.currentMap.Walkable(i, True):
                    # Look for point in open List
                    Candidate = [j for j in OpenList if j[0] == i[0] and j[1] == i[1]]
                    # If point not in open list                 
                    if(len(Candidate) == 0):
                        # Add point to the open list
                        OpenList.append(i)
                    else:
                        # Otherwise, check to see if this path to the square is shorter, using G. If so, replace square with current route (changing parent and g) 
                        if Candidate[0][4] > i[4]:
                            OpenList.remove(Candidate[0])
                            OpenList.append(i)
                
        # If no path found, return empty route
        if len([k for k in OpenList if k[0] == dest[0] and k[1] == dest[1]]) == 0:
            return []
        else:
            # Add path to route
            Route = []  
            CurSquare = [j for j in OpenList if j[0] == dest[0] and j[1] == dest[1]][0]
            # Iterate until we reach the starting point
            while (not(CurSquare[0] == CurSquare[2] and CurSquare[1] == CurSquare[3])):                 
                CurSquare = [j for j in (OpenList+ClosedList) if j[0] == CurSquare[2] and j[1] == CurSquare[3]][0]
                Route.insert(0, CurSquare)
            return Route

0 comments:

Post a Comment