Skip to main content
 首页 » 编程设计

python之A* python 麻烦,目标永远找不到

2025年01月19日14grandyang

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

我有一个 grid.txt 文件(见以下链接)https://ufile.io/9e6hm 存储二维单元格网格,填充 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])