A * pythonのトラブル、目標が決して見つかりません

Question

まず、長いコードを残念に思いますが、すべてのコードが問題を理解するのに関連していると感じます。

grid.txtファイル（次のリンクを参照）https://ufile.io/9e6hm は、0、100、または-1のいずれかで塗りつぶされたセルの2次元グリッドを格納します。 0は空き、100と-1は占有されています。

My 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) 

Answer 1

あなたは[xx]は、[YY]リストの世界のリストにそれらの要素にアクセスしようとし後境界内にあるかどうかをチェックされて表示されます。その結果、xxとyyが範囲外になると、IndexError: list index out of rangeになります。

また、maxxとmaxyのチェックは1つオフになっています。 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])