## A* Pathfinding Help

### A* Pathfinding Help

My friend and I are trying to redo the pathfinding for our 2-d RPG but we are having trouble getting the algo to work properly, We went through a tutorial so we understnad how the algorithm works but not how to implement it properly

We are trying to make a script that can take a 2d array of (0's are empty, 1's are filled with an obstacle) and a start and finish and return a list of points creating the shortest path

Here is what our code looks like so far:

Code: Select all
`import numpy import ast import time   class Grid(object):     def __init__(self, array):         self.open_list = []         self.closed_list = []         self.grid = array       def getPoint(self, coords):         """         :param coords: [x, y]         :return: point in 2d array         """        return self.grid[coords[1]][coords[0]]       def setPoint(self, coords, value):         """         :param coords: [x, y]         :return: point in 2d array         """        self.grid[coords[1]][coords[0]] = value       def notClosed(self, node):         for closed_node in self.closed_list:             if closed_node["pos"] == node["pos"]:                 return False        else:             return True      def getAdjacents(self, node):         adj = []         vectors = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, 1], [1, -1], [-1, -1]]         for vector in vectors:             check_result = self.checkSide(node, vector)             if check_result and self.notClosed(check_result):                 adj.append(check_result)         return adj       def checkSide(self, node, vector):         slice_coords = [node["pos"][0] + vector[0], node["pos"][1] + vector[1]]         check_point = self.getPoint(slice_coords)         if check_point == 0:             new_node = self.getNode(slice_coords, node)         else:             return False        return new_node       def getNode(self, point, parent):         if not parent:             parent = {"gcost": 0, "pos": None}         return {"pos": point,                 "gcost": 0,                 "parent_g": parent["gcost"],                 "parent": parent["pos"]}       def processNode(self, node):         adj = self.getAdjacents(node)         self.open_list += adj         self.closed_list.append(node)         self.removeFromOpen(node)       def isDiagonal(self, node):         vector_sub = [abs(node["pos"][0] - node["parent"][0]), abs(node["pos"][1] - node["parent"][1])]         if sum(vector_sub) > 1:             return True        else:             return False      def getGCost(self, node):         gcost = node["parent_g"]         if self.isDiagonal(node):             gcost += 14        else:             gcost += 10        node["gcost"] = gcost         return gcost       def getHCost(self, node, dest):         node_pos = node["pos"]         return 10*(abs(node_pos[0] - dest[0]) + abs(node_pos[1] - dest[1]))       def getFCost(self, node, dest):         """         Calculates the "F cost" of a certain node         """        return self.getGCost(node) + self.getHCost(node, dest)       def removeFromOpen(self, node):         node_pos = node["pos"]         for index, node in enumerate(self.open_list):             if node["pos"] == node_pos:                 del self.open_list[index]                 return True        else:             return False      def getNextNode(self, dest):         f_costs = []         for index, node in enumerate(self.open_list):             node_fcost = self.getFCost(node, dest)             f_costs.append(node_fcost)         lowest_fcost = min(f_costs)         print lowest_fcost         next_node = self.open_list[f_costs.index(lowest_fcost)]         return next_node       def printGrid(self):         for line in self.grid:             print line   def astar(map, begin, dest):     # Setup map class and lists     grid = Grid(map)     current_pos = list(begin)     path = []     begin_node = grid.getNode(begin, None)     grid.processNode(begin_node)     while current_pos[0] != dest[0] or current_pos[1] != dest[1]:         current_node = grid.getNextNode(dest)         current_pos = current_node["pos"]         path.append(current_pos)         grid.processNode(current_node)       for coord in path:         grid.setPoint(coord, 3)     grid.printGrid()   if __name__ == "__main__":     n_list = ast.literal_eval(open("test_data.txt").read().replace('\n', ''))     begin = [15, 15]     dest = []     astar(n_list, [15, 25], [35, 25])`

the code gets stuck in the while loop because it never reaches the destination! we cant figure out whats wrong with it though!
ChristianCareaga

Posts: 54
Joined: Sat Jun 22, 2013 9:54 am

### Re: A* Pathfinding Help

Can you also post some example input?
I tried running it, but I get an IndexError and I don't feel like figuring out the correct input format.
What I can say from taking a quick look at your code is you're overcomplicating a lot of very simple things.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

### Re: A* Pathfinding Help

stranac wrote:Can you also post some example input?
I tried running it, but I get an IndexError and I don't feel like figuring out the correct input format.
What I can say from taking a quick look at your code is you're overcomplicating a lot of very simple things.

Here you can download this and it has test_data.txt for an example array

https://www.dropbox.com/sh/k8vlyjkrccfz ... hfYK-15OKa
ChristianCareaga

Posts: 54
Joined: Sat Jun 22, 2013 9:54 am

### Re: A* Pathfinding Help

Your open_list keeps growing infinitely.
I would guess the getAdjacents() method is the cause, but haven't tried confirming it.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

### Re: A* Pathfinding Help

here an example of my pathfinder with numpy
Code: Select all
`import numpydef distance_between(a, b):    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2def pathfinder(array, start, goal, neighbors='*'):    if neighbors == '*':        neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]    elif neighbors == '+':        neighbors = [(0,1),(0,-1),(1,0),(-1,0)]    elif neighbors == 'x':        if (start[0] + start[1])%2 != (goal[0] + goal[1])%2:            return False        neighbors = [(1,1),(1,-1),(-1,1),(-1,-1)]            close_set = set()    open_set = set()    came_from = {}    gscore = {start:0}    fscore = {start:distance_between(start, goal)}    open_set.add(start)        while len(open_set):        lowest_fscore = [(fscore[item], item) for item in open_set]        lowest_fscore.sort()        current = lowest_fscore[0][1]        if current == goal:            data = []            while current in came_from:                data.append(current)                current = came_from[current]            return data                    open_set.discard(current)        close_set.add(current)        for i, j in neighbors:            neighbor = current[0] + i, current[1] + j                        tentative_g_score = gscore[current] + distance_between(current, neighbor)            if 0 <= neighbor[0] < array.shape[0]:                if 0 <= neighbor[1] < array.shape[1]:                                    if array[neighbor[0]][neighbor[1]] == 1:                        continue                else:                    # array bound y walls                    continue            else:                # array bound x walls                continue                            if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):                continue                            if neighbor not in open_set or tentative_g_score < gscore.get(neighbor, 0):                came_from[neighbor] = current                gscore[neighbor] = tentative_g_score                fscore[neighbor] = tentative_g_score + distance_between(neighbor, goal)                open_set.add(neighbor)                    return Falsenmap = numpy.array([    [0,0,0,0,0,0,0],    [0,0,0,0,0,0,0],    [1,1,1,1,0,0,0],    [0,0,0,0,0,0,0],    [0,0,1,1,1,1,1],    [0,0,0,0,0,0,0],    [0,0,0,0,0,0,0]])    print pathfinder(nmap, (1,1), (6,6))`
Linux: won't find windows here.
Linux: the choice of a GNU generation.
https://github.com/DrakeMagi
DrakeMagi

Posts: 112
Joined: Sun May 12, 2013 8:36 pm

### Re: A* Pathfinding Help

stranac wrote:Your open_list keeps growing infinitely.
I would guess the getAdjacents() method is the cause, but haven't tried confirming it.

is the open_list supposed to be cleared each new move?
ChristianCareaga

Posts: 54
Joined: Sat Jun 22, 2013 9:54 am

### Re: A* Pathfinding Help

No, but if the number of nodes in the open list becomes more than the total number of nodes, that's a sign something is wrong.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

### Re: A* Pathfinding Help

fix my code, and added example with your test_data.txt
Code: Select all
`import numpyimport astdef distance_between(a, b):    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2def pathfinder(array, start, goal, neighbors='*'):    if neighbors == '*':        neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]    elif neighbors == '+':        neighbors = [(0,1),(0,-1),(1,0),(-1,0)]    elif neighbors == 'x':        if (start[0] + start[1])%2 != (goal[0] + goal[1])%2:            return False        neighbors = [(1,1),(1,-1),(-1,1),(-1,-1)]            close_set = set()    open_set = set()    came_from = {}    gscore = {start:0}    fscore = {start:distance_between(start, goal)}    open_set.add(start)        while len(open_set):        lowest_fscore = [(fscore[item], item) for item in open_set]        lowest_fscore.sort()        current = lowest_fscore[0][1]        if current == goal:            data = []            while current in came_from:                data.append(current)                current = came_from[current]            return data                    open_set.discard(current)        close_set.add(current)        for i, j in neighbors:            neighbor = current[0] + i, current[1] + j              tentative_g_score = gscore[current] + distance_between(current, neighbor)            if 0 <= neighbor[0] < array.shape[1]:                if 0 <= neighbor[1] < array.shape[0]:                                    if array[neighbor[1]][neighbor[0]] == 1:                        continue                else:                    # array bound x walls                    continue            else:                # array bound y walls                continue                            if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):                continue                            if neighbor not in open_set or tentative_g_score < gscore.get(neighbor, 0):                came_from[neighbor] = current                gscore[neighbor] = tentative_g_score                fscore[neighbor] = tentative_g_score + distance_between(neighbor, goal)                open_set.add(neighbor)                    return False# examplesnmap = numpy.array([    [0,0,0,0,0,0,0,0,0],    [0,0,0,0,0,0,0,0,0],    [1,1,1,1,1,0,0,0,0],    [0,0,0,0,0,0,1,1,1],    [0,0,1,1,1,1,1,0,0],    [0,0,0,0,0,0,0,0,0],    [0,0,0,0,0,0,0,0,0]])    path = pathfinder(nmap, (1,1), (7,4))for p in path:    nmap[p[1]][p[0]] = 9print pathprintprint nmapprintpath = pathfinder(nmap, (1,1), (7,4), '+')for p in path:    nmap[p[1]][p[0]] = 9print pathprintprint nmap# example with your datan_list = numpy.array(ast.literal_eval(open("test_data.txt").read().replace('\n', '')))path = pathfinder(n_list, (15,25), (35,25))[1:]print pathfor p in path:    n_list[p[1]][p[0]] = 9    printfor line in n_list:    print line[13:]`
Linux: won't find windows here.
Linux: the choice of a GNU generation.
https://github.com/DrakeMagi
DrakeMagi

Posts: 112
Joined: Sun May 12, 2013 8:36 pm

### Re: A* Pathfinding Help

DrakeMagi wrote:fix my code, and added example with your test_data.txt
Code: Select all
`import numpyimport astdef distance_between(a, b):    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2def pathfinder(array, start, goal, neighbors='*'):    if neighbors == '*':        neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]    elif neighbors == '+':        neighbors = [(0,1),(0,-1),(1,0),(-1,0)]    elif neighbors == 'x':        if (start[0] + start[1])%2 != (goal[0] + goal[1])%2:            return False        neighbors = [(1,1),(1,-1),(-1,1),(-1,-1)]            close_set = set()    open_set = set()    came_from = {}    gscore = {start:0}    fscore = {start:distance_between(start, goal)}    open_set.add(start)        while len(open_set):        lowest_fscore = [(fscore[item], item) for item in open_set]        lowest_fscore.sort()        current = lowest_fscore[0][1]        if current == goal:            data = []            while current in came_from:                data.append(current)                current = came_from[current]            return data                    open_set.discard(current)        close_set.add(current)        for i, j in neighbors:            neighbor = current[0] + i, current[1] + j              tentative_g_score = gscore[current] + distance_between(current, neighbor)            if 0 <= neighbor[0] < array.shape[1]:                if 0 <= neighbor[1] < array.shape[0]:                                    if array[neighbor[1]][neighbor[0]] == 1:                        continue                else:                    # array bound x walls                    continue            else:                # array bound y walls                continue                            if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):                continue                            if neighbor not in open_set or tentative_g_score < gscore.get(neighbor, 0):                came_from[neighbor] = current                gscore[neighbor] = tentative_g_score                fscore[neighbor] = tentative_g_score + distance_between(neighbor, goal)                open_set.add(neighbor)                    return False# examplesnmap = numpy.array([    [0,0,0,0,0,0,0,0,0],    [0,0,0,0,0,0,0,0,0],    [1,1,1,1,1,0,0,0,0],    [0,0,0,0,0,0,1,1,1],    [0,0,1,1,1,1,1,0,0],    [0,0,0,0,0,0,0,0,0],    [0,0,0,0,0,0,0,0,0]])    path = pathfinder(nmap, (1,1), (7,4))for p in path:    nmap[p[1]][p[0]] = 9print pathprintprint nmapprintpath = pathfinder(nmap, (1,1), (7,4), '+')for p in path:    nmap[p[1]][p[0]] = 9print pathprintprint nmap# example with your datan_list = numpy.array(ast.literal_eval(open("test_data.txt").read().replace('\n', '')))path = pathfinder(n_list, (15,25), (35,25))[1:]print pathfor p in path:    n_list[p[1]][p[0]] = 9    printfor line in n_list:    print line[13:]`

I made my own based on yours and it worked but its a bit slow for our game but we will figure something out thank you though !
ChristianCareaga

Posts: 54
Joined: Sat Jun 22, 2013 9:54 am

Return to Game Development

### Who is online

Users browsing this forum: No registered users and 1 guest