A* Pathfinding Help

A* Pathfinding Help

Postby ChristianCareaga » Thu Jul 10, 2014 5:25 pm

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: 52
Joined: Sat Jun 22, 2013 9:54 am

Re: A* Pathfinding Help

Postby stranac » Thu Jul 10, 2014 8:56 pm

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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: A* Pathfinding Help

Postby ChristianCareaga » Fri Jul 11, 2014 7:58 am

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: 52
Joined: Sat Jun 22, 2013 9:54 am

Re: A* Pathfinding Help

Postby stranac » Fri Jul 11, 2014 12:44 pm

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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: A* Pathfinding Help

Postby DrakeMagi » Fri Jul 11, 2014 2:05 pm

here an example of my pathfinder with numpy
Code: Select all
import numpy

def distance_between(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def 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 False

nmap = 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

Postby ChristianCareaga » Fri Jul 11, 2014 11:53 pm

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: 52
Joined: Sat Jun 22, 2013 9:54 am

Re: A* Pathfinding Help

Postby stranac » Sat Jul 12, 2014 8:10 am

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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: A* Pathfinding Help

Postby DrakeMagi » Sat Jul 12, 2014 3:30 pm

fix my code, and added example with your test_data.txt
Code: Select all
import numpy
import ast

def distance_between(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def 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

# examples
nmap = 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]] = 9

print path
print
print nmap
print

path = pathfinder(nmap, (1,1), (7,4), '+')
for p in path:
    nmap[p[1]][p[0]] = 9

print path
print
print nmap

# example with your data
n_list = numpy.array(ast.literal_eval(open("test_data.txt").read().replace('\n', '')))
path = pathfinder(n_list, (15,25), (35,25))[1:]
print path

for p in path:
    n_list[p[1]][p[0]] = 9
   
print
for 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

Postby ChristianCareaga » Sun Jul 13, 2014 9:28 pm

DrakeMagi wrote:fix my code, and added example with your test_data.txt
Code: Select all
import numpy
import ast

def distance_between(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def 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

# examples
nmap = 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]] = 9

print path
print
print nmap
print

path = pathfinder(nmap, (1,1), (7,4), '+')
for p in path:
    nmap[p[1]][p[0]] = 9

print path
print
print nmap

# example with your data
n_list = numpy.array(ast.literal_eval(open("test_data.txt").read().replace('\n', '')))
path = pathfinder(n_list, (15,25), (35,25))[1:]
print path

for p in path:
    n_list[p[1]][p[0]] = 9
   
print
for 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: 52
Joined: Sat Jun 22, 2013 9:54 am


Return to Game Development

Who is online

Users browsing this forum: No registered users and 3 guests