LoginSignup
0
4

More than 5 years have passed since last update.

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

Posted at

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. ゲームの様子

m1.PNG
m2.PNG

m3.PNG

m4.PNG

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



0
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
4