Pythonでプログラミング-右手法

迷路ゲームを解く時の手法で右手法というのありますがこれを自分なりに理解してみたいと思います。

maze = [
   [9, 9, 9, 9, 9, 9, 9, 9, 9],
   [9, 0, 0, 0, 9, 9, 0, 9, 9],
   [9, 0, 9, 9, 0, 0, 0, 0, 9],
   [9, 0, 0, 0, 0, 9, 9, 9, 9],
   [9, 9, 0, 9, 0, 9, 0, 1, 9],
   [9, 0, 0, 9, 0, 0, 0, 9, 9],
   [9, 0, 9, 0, 0, 9, 0, 0, 9],
   [9, 9, 9, 9, 9, 9, 9, 9, 9]
]と

という迷路がある場合の解法です。右側を伝っていけばゴールにたどり着くというもの。ここでは"9"が壁"1"がゴールです。スタートは

maze = [1,1]

進行方向は上下左右あるので

d = [[0, -1], [-1, 0], [0, 1], [1, 0]]

として方向を現在の位置と初期値は

x,y = [1,1]

これに加算して動かしていきます。方向は

dir = 0

としてこれに方向を示す"d"のデータを0から3の数字で指定します。実際に動かす配置として変数moveを宣言してx,yそれぞれにデータを入れて動かしてゴールに向かいます。

move = d[(dir + 1) % 4]
x += move[0]
y += move[1]

として、右側へと誘導していきます。これは"d[1]"となるのでリストとしては

d =  [-1, 0]

が入って行くので迷路にこの位置情報を

maze[x + move[0]][y + move[1]] != 9:

でチェックします。するとmaze[0,1]となり、そこは"9"となっているので移動はできません。なので以下の処理を行い"9"でないところを探すようにします。

 dir = (dir + 3) % 4

dir = 3となってまたループします。

方向を変えてリストの場所を表示してみると

nmaze = [2,1]

になります。

ループは、迷路mazeのゴール"1"になれば終了。それまでは繰り返します。

while maze[x][y] != 1:こ

壁を伝っていくので壁のない真ん中にゴールがある場合はこの手法ではうまくいきません。

参考：プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング＆アルゴリズム