Operation KiWi

一生使える言語はPythonだと信じてる

Python3でRPGを作る時に使えそうな技術の断片 -最短経路アルゴリズム-

f:id:sakage24:20170717182936j:plain

経路探索は、ゲーム開発とは切っても切れない関係です。敵キャラがマップ上に配置してある障害物や侵入不可能なエリアを避けられない、あるいは透過して突っ込んできたら間違いなく萎えるでしょう。

今回は、今までのように単純にプレイヤーの座標に向かって進んでくるAIとは別に、障害物などを検知して迂回したり出来るような、ちょっとだけインテリジェンスなアルゴリズムをご紹介します。

最短経路アルゴリズムは色々ある

  1. LOS追跡
  2. ベルマン-フォード法
  3. ダイクストラ法
  4. A*法

代表的なのはこれらですね。番号が若いほど、単純で計算時間は少ないです。逆にA*法は結構複雑で、さらに移動の度に再計算をする必要があるので、重い処理になります。

A*法

今回はもっとも賢い最短経路アルゴリズム、A*法を実装していきましょう。A*法はターゲットまでの単純な直線距離と地形コストを計算して、常に最適な経路を導き出します。

ちなみに「ゲーム開発者のためのAI入門」に載っていますので買いましょう。何故かA*法だけ擬似言語で書かれていてソースコードが載っていないため、解説と最低限の情報だけが書かれた疑似言語を解読してなんとかPython上で動かせるようになりましたw

ゲーム開発者のためのAI入門

ゲーム開発者のためのAI入門

ソースコード

a_star()関数は、多次元配列のリスト、それに探索開始位置と目標位置をリストで渡すことで、最短経路を求めます。ダイクストラ法と似ていますが、ダイクストラ法が結果に関わらずマップ上の全てを探索するのに対し、A*法は指向性を持って探索を行い、目的位置にたどり着くと処理を終了します。

from copy import deepcopy


# 高機能な追跡アルゴリズム
def a_star(maps, start_pos, target_pos):
    height = len(maps)
    width = len(maps[0])
    eval_map = deepcopy(maps)
    linked_map = deepcopy(maps)
    open_list = [start_pos.copy()]
    closed_list = [start_pos.copy()]
    current_position = [start_pos.copy()]
    while open_list:
        # 現在のノード = オープンリストの最も安価なノード
        low = 99999
        for x in open_list:
            if eval_map[x[0]][x[1]] < low:
                current_position = x
                low = eval_map[x[0]][x[1]]
        if current_position == target_pos:
            # 経路完成
            current_pos = target_pos.copy()
            shortest_route = []
            # ゴールからlink_mapの中身を覗いていって、スタート地点までの道のりをshortest_routeに格納していく処理
            while start_pos != current_pos:
                current_pos = linked_map[current_pos[0]][current_pos[1]]
                shortest_route.append(current_pos)
            routes = shortest_route[::-1]
            routes.append(target_pos)
            return routes
        else:
            open_list.remove(current_position)
            closed_list.append(current_position)
            next_to_nodes = [
                [current_position[0] - 1, current_position[1] - 1],
                [current_position[0] + 1, current_position[1] + 1],
                [current_position[0] - 1, current_position[1] + 1],
                [current_position[0] + 1, current_position[1] - 1],
                [current_position[0], current_position[1] - 1],
                [current_position[0], current_position[1] + 1],
                [current_position[0] + 1, current_position[1]],
                [current_position[0] - 1, current_position[1]],
            ]
            for nodes in next_to_nodes:
                if nodes[0] >= 0 and nodes[1] >= 0 and nodes[1] < height and nodes[1] < width:
                    try:
                        if nodes not in open_list and nodes not in closed_list and maps[nodes[0]][nodes[1]] != 999:
                            # オープンリストに移してコスト計算をする
                            c_direction = nodes[:]
                            h_direction = nodes[:]
                            linked_map[nodes[0]][nodes[1]] = current_position[:]
                            open_list.append(nodes)
                            c = 0  # 開始タイルから、そこへ到達するためのコスト
                            h = 0  # 特定のタイルから、最終タイルまでの歩数を測定したコスト
                            while not c_direction == list(start_pos):
                                if start_pos[0] > c_direction[0]:
                                    c_direction[0] += 1
                                elif start_pos[0] < c_direction[0]:
                                    c_direction[0] -= 1

                                if start_pos[1] > c_direction[1]:
                                    c_direction[1] += 1
                                elif start_pos[1] < c_direction[1]:
                                    c_direction[1] -= 1
                                if maps[nodes[0]][nodes[1]] == 999:
                                    c += 99999
                                else:
                                    c += 1

                            while not h_direction == list(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[nodes[0]][nodes[1]] = c + h
                    except IndexError:
                        pass
    return False


if __name__ == '__main__':
    from pprint import PrettyPrinter
    maps = [[0 for x in range(10)] for y in range(10)]
    for i in range(9):
        maps[5][i] = 999
    result = a_star(maps, [0, 0], [9, 4])
    pp = PrettyPrinter()
    print(result)
    for g in result:
        maps[g[0]][g[1]] = "9"
    for i in range(10):
        for j in range(10):
            if 999 == maps[i][j]:
                print("壁", end='')
            elif 1 == maps[i][j]:
                print("村", end="")
            elif 0 == maps[i][j]:
                print("ー", end="")
            else:
                print("☆", end="")
        print()

>>> 実行結果
[[0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 9], [6, 8], [7, 7], [7, 6], [8, 5], [9, 4]]
☆ーーーーーーーーー
ー☆ーーーーーーーー
ーー☆ーーーーーーー
ーーー☆ーーーーーー
ーーーー☆☆☆☆☆ー
壁壁壁壁壁壁壁壁壁☆
ーーーーーーーー☆ー
ーーーーーー☆☆ーー
ーーーーー☆ーーーー
ーーーー☆ーーーーー

壁を避けてますね~。これで壁抜けして突っ込んでくる悲しいAIはいなくなります。LOS追跡、ブレゼンハムのアルゴリズムと組み合わせて、状況に合わせて動作を切り替えたりすると、より軽く、速くなるかもしれませんね。

www.kiwi-bird.xyz

www.kiwi-bird.xyz

終わり

めっちゃ大変だったけど、出来て良かった~。次は何をやるかまだ決めてません。何かリクエストがあればコメントでお願いします。

オススメの教科書類

指定教科書

入門 Python 3

入門 Python 3

これ無しでPython開発は無理です。私的にはあまり演習問題の類は解かずに知りたいことがあったら読む、辞書的な感じで使っています。

  • スライスって何?
  • リスト内包表記って何なんだよあれ?
  • リストとタプルはどう違うの?
  • そもそも集合って何に使うの?

少しでも上記に当てはまるなら購入しましょう。せっかくPythonを使っているんですから、有効に使えるようにしてみませんか?

副読本

Effective Python ―Pythonプログラムを改良する59項目

Effective Python ―Pythonプログラムを改良する59項目

  • 他言語を得意としているプログラマがPythonを書いた時にやりがちなこと…
  • ゲームの保存に使えるpickle
  • この機能はこう使うべきである
  • while, for文のelseを使うべきではない理由
  • Pythonでセッター, ゲッターを使うべきではない理由

みたいに、様々な事例とともにPythonのベストノウハウ、やってはいけないアンチパターンが紹介されています。pycon2016でも確か推されてましたw

初心者から上級者まで、手元に置いておくべき本です。

副読本2

退屈なことはPythonにやらせよう ―ノンプログラマーにもできる自動化処理プログラミング

退屈なことはPythonにやらせよう ―ノンプログラマーにもできる自動化処理プログラミング

ノンプログラマー向けとありますが、経験者の方も結構アイディアを貰える本でした。 序盤は文法の解説ですので、読み飛ばせます。後半は様々な局面で使えそうな自動化処理の書き方が載っていました。

ゲームの所持アイテムを辞書で表現しよう…みたいにゲームプログラマーに役立つ演習もありましたw

副読本3

ゲーム開発者のためのAI入門

ゲーム開発者のためのAI入門

C言語での解説が主ですが、しっかりとした説明があるので、だいたい分かりました。Pythonでも使える知識がほとんどです。ただ、ファジー理論など、数学的な要素は私にはどうともしがたい躓きポイントでしたw

ローグライクゲームに使える最短経路探索法やAIの作成法、確率の基本まで教えてもらえる良本でした!!