Pythonで迷路ゲームを作ってみました.


1. はじめに

強化学習(Reinforcement Learning)の導入例(以下写真みたいな)でよく見る
迷路ゲーム(CUI)を作ってみました.
キーワードとしては以下になります。

  • 迷路自動生成機能
  • start/goal位置の自動設定

2. 開発に用いた環境/モジュール

  • Python 3.7
  • numpy
  • random
  • math
  • scipy

3. 全体のコード

Google Driveで共有します.
https://drive.google.com/open?id=1q0EkWOMs_PnlUT4mcdecKrXDnngpl6o2

4. 遊び方

4.1 起動コマンド

$ python play_game.py

4.2 ルール

  1. easy, normal, hardの3つから難易度を選択
    ⇒start位置、goal位置, MAPが自動生成される

  2. 極力はやくゴールへ向かう.
    *移動ステップごとに報酬が-1される.
    迷路での強化学習エージェントを演じるみたいな感じです.

5. ゲームの様子


6. 主要機能の紹介

6.1. 迷路自動生成機能

棒倒し法というアルゴリズムを用いて作成しました。

アルゴリズム
1. -1だけで構成されるM×M配列を生成(*Mは3以上の奇数)
2. M×M行列の(i,j)要素の内,i ,j∈(任意の奇数)である位置を壁(コードではmath.nan)とする.
例. 5×5行列(i=[0,1,2,3,4],j=[0,1,2,3,4])なら、
壁とみなす( i, j )の組み合わせは、 [(1,1),(1,3),(3,1),(3,3)]の4つ

6.2. start/goal位置の自動設定

  1. MAPとして用いるM×M行列の4隅を表す4点から、 正規分布(normal)を用いて20個ずつ乱数生成.
  2. 20個ずつある乱数から、MAPの位置になりえない、あるいは壁である部分を削除
  3. 2.の結果からランダムに1点ずつ抽出(計4点)
  4. 計4点のユークリッド距離行列をmeshgridを使って作成
  5. 4から最もユークリッド距離が遠くなる組み合わせをstart, goalとして設定する. (どちらがstart, goalかはランダム)

以下、start/goalの設定に使ったコード

def set_mainpos(self, MAP):


        size = (MAP.shape[0], MAP.shape[1])
        corners = [[0,0],[0,size[0]],[size[0],0],[size[0], size[0]]]
        flag = 0 #start, goalが同じにならないため ( なった例がある. )
        while flag == 0:

            candidate = []
            for k,v in corners:
                tmp = [normal(k,int(size[0]/3.3), 20).tolist(), normal(k,int(size[0]/3), 20).tolist()]
                tmp = [ [ i for i in tmp[0] if i < size[0] and i > 0 ], [ i for i in tmp[1] if i < size[0] and i > 0 ]]

                flag2 = 0
                while flag2 == 0: # nanをstart, goalにしないための処理
                    tmp2 = [int(choice(tmp[0])), int(choice(tmp[1]))]
                    if str(MAP[tmp2[0],tmp2[1]]) != str(nan):
                        flag2 = 1



                candidate.append([int(choice(tmp[0])), int(choice(tmp[1]))])

            shuffle(candidate)


            tmp_index = np.arange(np.array(candidate).shape[0])
            xx, yy = np.meshgrid(tmp_index, tmp_index)
            distances = np.linalg.norm(np.array(candidate)[xx]-np.array(candidate)[yy], axis=2) 

            index = np.where(distances==distances.max())[0].tolist(), np.where(distances==distances.max())[1].tolist()

            candidate[index[0][0]]

            self.main_pos["start"] = candidate[index[0][0]]
            self.main_pos["goal"] = candidate[index[0][1]]

            if  self.main_pos["start"] !=  self.main_pos["goal"]:
                flag = 1