python - A * python麻烦，永远找不到目标

首先，对冗长的代码被打断感到抱歉，但是我觉得所有代码都与理解问题有关。

我有一个grid.txt文件（请参见以下链接）https://ufile.io/9e6hm
存储2D单元格网格，其中填充有0、100或-1。 0为空闲，100和-1被占用。

我的A *必须找到从给定起点到目标的路径。

当我删除以下检查某个单元格是否被占用的邻居条件时，这种方法可以正常工作：

if (world[yy][xx]!=0):
                    continue

但是，当尝试计算考虑到占用单元格的路径时，我的代码似乎并没有产生结果。

任何帮助将不胜感激，因为我真的很想了解这个问题。我的代码如下：

#!/usr/bin/env python
import math
import json
from time import time
t = time()

start = [1,1]
size = [600,600]

stuff = open('grid.txt','r')

world = json.loads(stuff.read())


size[0]=len(world[0])
size[1]=len(world)

goal = [600,600]

print("World size: %sx%s" % (size[0],size[1]))


def astar():

    pq = []
    pq.append(([start],0))

    print("Definitely getting here")
    hits = []

    while (pq[0][0][-1] != goal):

        currentpath = pq.pop(0)[0][:]
        hits.append(currentpath[-1])

        for n in neighbours(currentpath[-1]):
            if n in hits:
                continue

            newPath=currentpath[:]
            newPath.append(n)
            heur=len(currentpath) + heuristic(n)
            print("newPath: %s (%s)" % (newPath,heur))
            pq.append((newPath,heur))

        pq=sorted(pq, key=lambda path: path[1])

    print("Done!")

    return pq[0][0]

def neighbours(coords): # [4,5]
    x = coords[0]
    y = coords[1]
    maxx = size[0]
    maxy = size[1]
    n=[]
    for i in range (-1,2):
        for j in range(-1,2):
            if (i==0 and j==0):
                continue
            else:
                xx = x + i
                yy = y + j

                if (world[yy][xx]!=0):
                    continue

                if (xx >= 0 and yy >= 0):
                    if (xx <= maxx):
                        if (yy <= maxy):
                            n.append([xx,yy])
    return n


def heuristic(n):
    dx = abs(n[0] - goal[0])
    dy = abs(n[1] - goal[1])
    return math.sqrt(dx * dx + dy * dy)


print(astar())

print (time() - t)

最佳答案

似乎您在尝试访问列表的世界列表中的那些元素后正在检查[xx]，[yy]是否在界限内。结果，当xx和yy超出范围时，您最终得到IndexError: list index out of range。

同样，您的maxx和maxy检查也相减一。如果尝试访问world[maxy][maxx]，则始终会出现IndexError。

在访问列表元素之前，请确保事物处于边界内，并且您应该可以：

xx = x + i
yy = y + j

if ( xx >= 0 and
     yy >= 0 and
     xx < maxx and
     yy < maxy and
     world[yy][xx] == 0 ):

     n.append([xx,yy])