読者です 読者をやめる 読者になる 読者になる

経路探索アルゴリズムのA*法を書いてみた

python プログラミング

ちょっと前の記事で、苦難の末ダイクストラアルゴリズムの実装に成功しました。

しかし、ダイクストラアルゴリズムは無駄が多い。必ず全ての経路を探索するからだ。

A*法という、ダイクストラアルゴリズムに指向性を持たせたような進化版があることは前から知っていた。実装方法についてがなんか難しそうだったので敬遠していたのだが、

「ゲーム開発者のためのAI入門」という本に、手取り足取り載っていたのでここぞとばかりに実装してみた。

def a_star(self):
    pos = [self.y, self.x]  # プレイヤーのタイル座標
    target_pos = [self.target_y, self.target_x] # 目的地のタイル座標
    eval_map = copy.deepcopy(self.elementary_field)  # 評価対象のマップ。2次元リスト
    open_list = [pos]  # 調査の必要があるタイル
    closed_list = list()  # 調査が終わったタイル
    scan_node = list()  # 8方向の座標を保持する。
    current_node = []  # 現在いるタイル
    for x in range(self.height):
        for y in range(self.width):
            if eval_map[x][y] != 0:
                eval_map[x][y] = 99999  # 最大値

    while len(open_list):
        # 現在のノード = オープンリストの最も安価なノード
        low = 9999999
        for x in open_list:
            if eval_map[x[0]][x[1]] < low:
                current_node = x
                low = eval_map[x[0]][x[1]]
        if current_node == target_pos:
            # 経路の完成
            closed_list.append(current_node)
            closed_list.remove(pos)
            return closed_list
        else:
            open_list.remove(current_node)
            closed_list.append(current_node)
            # 現在のノードに隣接する各ノードを調べる
            scan_node.append([current_node[0] - 1, current_node[1]])  # 上
            scan_node.append([current_node[0], current_node[1] + 1])  # 右
            scan_node.append([current_node[0] + 1, current_node[1]])  # 下
            scan_node.append([current_node[0], current_node[1] - 1])  # 左
            scan_node.append([current_node[0] - 1, current_node[1] - 1])  # 左上
            scan_node.append([current_node[0] - 1, current_node[1] + 1])  # 右上
            scan_node.append([current_node[0] + 1, current_node[1] - 1])  # 左下
            scan_node.append([current_node[0] + 1, current_node[1] + 1])  # 右下
            for x in scan_node:
                if x not in open_list\
                    and x not in closed_list\
                        and not eval_map[x[0]][x[1]] == 0:
                            # オープンリストに移してコスト計算をする
                            c_direction = x.copy()
                            h_direction = x.copy()
                            c = 0  # 開始タイルから、そこへ到達するためのコスト
                            h = 0  # 特定のタイルから、最終タイルまでの歩数を測定したコスト
                            open_list.append(x)
                            while not c_direction == pos:
                                if pos[0] > c_direction[0]:
                                    c_direction[0] += 1
                                elif pos[0] < c_direction[0]:
                                    c_direction[0] -= 1

                                if pos[1] > c_direction[1]:
                                    c_direction[1] += 1
                                elif pos[1] < c_direction[1]:
                                    c_direction[1] -= 1
                                if self.field.field[x[0]][x[1]] == 4:
                                    c += 99999
                                else:
                                    c += 1

                            while not h_direction == target_pos:
                                if target_pos[0] > h_direction[0]:
                                    h_direction[0] += 1
                                elif target_pos[0] < h_direction[0]:
                                    h_direction[0] -= 1

                                if target_pos[1] > h_direction[1]:
                                    h_direction[1] += 1
                                elif target_pos[1] < h_direction[1]:
                                    h_direction[1] -= 1
                                h += 1
                            eval_map[x[0]][x[1]] = c + h
            scan_node = list()
    return False

本には、ちゃんとしたソースコードは載って無くて、簡単な擬似言語と解説が載っているのみで、結構困ったりしたので乗せておく。

実際動かしてみると、目的地に向かってアルゴリズムが流れていくのが楽しいかも。速度も、ダイクストラ法と比べると0.003秒、大体48%早かった(1000回の平均を取った)

そう、この本を買えば今すぐ貴方もゲーム開発者に(w

そういえば、エロゲ作っているはずなんだけど、全然エロいコードとか書いてない。頭が痛くなるアルゴリズムばっかりだなぁ

頑張ろ…