2

A *パスファインディングアルゴリズムと、それをPythonプログラムに実装する方法を理解しようとしています。アルゴリズム自体がどのように機能するかを説明し、いくつかのサンプルコードを提供する、かなり良い仕事をしているこのWebサイトを見つけました。

これが私が立ち往生しているところです：

def make_graph(mapinfo):

nodes = [[AStarGridNode(x, y) for y in range(mapinfo.height)] for x in range(mapinfo.width)]
graph = {}
for x, y in product(range(mapinfo.width), range(mapinfo.height)):
    node = nodes[x][y]
    graph[node] = []
    for i, j in product([-1, 0, 1], [-1, 0, 1]):
        if not (0 <= x + i < mapinfo.width): continue
        if not (0 <= y + j < mapinfo.height): continue
        graph[nodes[x][y]].append(nodes[x+i][y+j])
return graph, nodes

graph, nodes = make_graph({"width": 8, "height": 8})
paths = AStarGrid(graph)
start, end = nodes[1][1], nodes[5][7]
path = paths.search(start, end)
if path is None:
    print "No path found"
else:
    print "Path found:", path

「 mapinfo」オブジェクトがどのように表示されるのかわかりません。mapinfo変数をいくつかの数値に置き換えることでプログラムが機能するように管理しましたが、特に壁を含めたい場合は、リスト全体がどのように機能するかを理解できません。いくつかの説明/例を提供できますか？

4

1 に答える 1

2

オブジェクト（mapinfo指定されたコードに示されている）は、関数に渡される辞書引数make_graph()であり、検索するグリッドの次元（幅と高さ）を格納するために使用されています。

関数呼び出しの前に定義してから、次のように関数に渡すことができます。

mapinfo = {"width": 8, "height": 8}
graph, nodes = make_graph(mapinfo)

問題は、関数がとの値に直接（byなど）make_graph()アクセスしようとするため、例外が発生することです。widthheightmapinfomapinfo.heightAttributeError: 'dict' object has no attribute 'height'

私が考えることができる2つのオプションは次のとおりです。

  • ステートメントを変更してmake_graph()、属性ではなくキーで辞書要素にアクセスします。すべてmapinfo.heightをに変更しmapinfo['height']、同様に幅を変更します）、または

  • 必要な属性を使用してMapInfoクラスを作成し、そのインスタンスをmake_graph()ディクショナリではなく関数に渡します。

    class MapInfo(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height

# ...

mapinfo = MapInfo(width=8, height=8)
graph, nodes = make_graph(mapinfo)

壁などの通行できない地形を含める場合は、さらに多くのことを行う必要があります。

おそらく、MapInfo別の属性を指定してクラスを拡張します。

def __init__(self, width, height, impassable=[]):
    """Create a MapInfo object representing the search area and obstacles.

        Args:
            width: Integer representing the width of the area
            height: Integer representing the height of the area
            impassable: List of (x, y) tuples representing impassable obstacles.
    """
    self.width = width
    self.height = height
    self.impassable = impassable

make_graph()次に、ターゲット領域が通過できない場合にのみ2つのグリッドスペースの間にエッジを追加するように関数を変更する必要があります。

for i, j in product([-1, 0, 1], [-1, 0, 1]):
    # Check that we are inside the grid area.
    if not (0 <= x + i < mapinfo.width): continue
    if not (0 <= y + j < mapinfo.height): continue
    # Check if the target area is impassable.
    if (x + i, y + j) in mapinfo.impassable: continue
    # All looks good. Add target space as reachable from current (x, y) space.
    graph[nodes[x][y]].append(nodes[x+i][y+j])

mapinfo次に、必要に応じて、追加の通行不能領域を使用してインスタンス定義を変更します。

impassable = [(3, 3), (3, 4), (3, 5)]  # modify to your needs
mapinfo = MapInfo(width=8, height=8, impassable=impassable)
于 2013-01-18T01:56:23.010 に答える