2

首先，很抱歉剪掉了冗长的代码，但我觉得所有代码都与理解问题相关。

我有一个 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)
4

1 回答 1

1

在尝试访问列表世界列表中的这些元素后，您似乎正在检查 [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])
于 2017-10-25T15:29:33.833 回答