はじめに
Python の勉強のため簡単なゲームを作りましたので備忘録としてまとめておきます.
とりとめのない個人的な記事ではありますが、python を勉強するどなたかの参考になりましたならば幸いです.
環境は Python 3.13.1、Windows 11、コマンドプロンプトです.
完成品
コンソール
+---+---+---+---+---+---+---+---+
| X | |
+---+ +---+---+---+ + + +
| | | | | |
+ + + +---+ +---+---+ +
| | | |
+ +---+ +---+ + + + +
| | | | | | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|> right
+---+---+---+---+---+---+---+---+
| S X | |
+---+ +---+---+---+ + + +
| | | | | |
+ + + +---+ +---+---+ +
| | | |
+ +---+ +---+ + + + +
| | | | | | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|> right
+---+---+---+---+---+---+---+---+
| S X | |
+---+ +---+---+---+ + + +
| | | | | |
+ + + +---+ +---+---+ +
| | | |
+ +---+ +---+ + + + +
| | | | | | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|> regenerate
+---+---+---+---+---+---+---+---+
| X | | | |
+ +---+ + +---+---+ + +
| | | | | |
+ +---+ +---+ +---+---+ +
| | | | |
+---+ + + +---+ + +---+
| | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|> down
+---+---+---+---+---+---+---+---+
| S | | | |
+ +---+ + +---+---+ + +
| X | | | | |
+ +---+ +---+ +---+---+ +
| | | | |
+---+ + + +---+ + +---+
| | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|> down
+---+---+---+---+---+---+---+---+
| S | | | |
+ +---+ + +---+---+ + +
| | | | | |
+ +---+ +---+ +---+---+ +
| X | | | |
+---+ + + +---+ + +---+
| | G |
+---+---+---+---+---+---+---+---+
プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)
ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.
|>
ソースコード
maze.py
from random import randrange, shuffle
# DisjointSetDataStructure は長いので UnionFind と名付ける
class UnionFind:
# array[i] : 要素 i を含む集合の代表元. i 自身が代表であるとき、その集合の大きさの反数.
# 木の高さを持つのが正しい union-find だが、配列ひとつで簡単に扱えるよう集合の大きさを使う.
array: list[int]
size: int
def __init__(self, size):
self.size = size
self.array = [-1] * size
def union(self, i, j) -> bool:
'''
i と j を合併する
Returns:
合併に成功した場合 True. さもなくば False.
'''
rooti = self.find(i)
rootj = self.find(j)
if rooti == rootj:
return False
if self.array[rooti] < self.array[rootj]:
# i を含む集合の方が大きいので、{ i, ... } に { j, ... } を加える
s = self.array[rootj]
self.array[rootj] = rooti
self.array[rooti] += s
else:
# v.v.
s = self.array[rooti]
self.array[rooti] = rootj
self.array[rootj] += s
return True
def same(self, i, j) -> bool:
'''
i と j が同じ集合に含まれるかを調べる
Returns:
同じ集合に含まれる場合 True. さもなくば False.
'''
return self.find(i) == self.find(j)
def find(self, i) -> int:
'''
i を含む集合の代表元を得る
Returns:
i を含む集合の代表元
'''
if self.array[i] < 0:
return i
else:
root = self.find(self.array[i])
self.array[i] = root
return root
def size_for(self, i) -> int:
'''
i を含む集合の大きさを得る
Returns:
i を含む集合の大きさ
'''
return -self.array[self.find(i)]
def sets(self) -> list[list[int]]:
'''
集合の集合を得る
Returns:
集合の集合
'''
from collections import defaultdict
ss = defaultdict(list)
for i in range(self.size):
ss[self.find(i)].append(i)
return list(ss.values())
# # 実質的に次と等しい
# ss = [[] for _ in range(self.size)]
# for i in range(self.size):
# ss[self.find(i)].append(i)
# return [s for s in ss if len(s) != 0]
class Maze:
board: grid[int] # 盤面
width: int
height: int
player: int # 現在位置(インデックス)
start: int # 開始位置(インデックス)
goal: int # 終了位置(インデックス)
# [[ 定数 ]]
# 右へ移動可能
OPEN_EAST = 1
# 下へ移動可能
OPEN_SOUTH = 2
# 移動方向
LEFT = (-1, 0)
RIGHT = ( 1, 0)
UP = ( 0, -1)
DOWN = ( 0, 1)
def __init__(self, width, height):
# 大きさが 3x4 であるとき:
# ,-------- 0 列目
# | ,------ 1 列目
# | | ,---- 2 列目
# | | | ,-- 3 列目
# v v v v
# grid [ a b c d e f g h i j k l ]
# ------- ******* -------
# row 0 row 1 row 2
self.width = width
self.height = height
# クラスカル法によって迷路を構築する.
# 内部で使うため、width/height の設定後に呼び出す.
self.grid = self._kruskal()
self.start = 0 # 左上スタート
self.goal = width * height - 1 # 右下ゴール
self.player = self.start
def _kruskal(self):
n = self.width * self.height
directions = [Maze.UP, Maze.DOWN, Maze.LEFT, Maze.RIGHT]
grid = [0] * n
uf = UnionFind(n)
# edges has (index, is_down) := マス index から下方向へ伸びる辺 if is_down else マス index から右方向へ伸びる辺
edges = [(self.index(x,y), False) for x in range(self.width-1) for y in range(self.height)]
edges += [(self.index(x,y), True) for x in range(self.width) for y in range(self.height-1)]
shuffle(edges)
for i,is_down in edges:
x, y = self.coordinate(i)
if is_down:
nx, ny = x,y+1
else:
nx, ny = x+1,y
j = self.index(nx, ny)
if not uf.same(i, j):
uf.union(i, j)
if is_down:
grid[i] |= Maze.OPEN_SOUTH
else: # i.e. if is_right:
grid[i] |= Maze.OPEN_EAST
return grid
def generate(self):
self.grid = self._kruskal()
self.player = self.start
def index(self, x, y):
return x + y * self.width
def coordinate(self, index):
y = index // self.width
x = index - self.width * y
return (x, y)
def at(self, x, y):
return self.grid[self.index(x, y)]
def on_board(self, x, y) -> bool:
'''
盤上のマスか？
'''
return 0 <= x < self.width and 0 <= y < self.height
def show(self):
def stringify_cell(x, y):
index = self.index(x, y)
cell_state = self.grid[index]
east = '|' if (cell_state & Maze.OPEN_EAST) != Maze.OPEN_EAST else ' '
match index:
case self.player:
return ' X ' + east
case self.start:
return ' S ' + east
case self.goal:
return ' G ' + east
case _:
return ' ' + east
def stringify_south_of_cell(cell_state):
return '---' if (cell_state & Maze.OPEN_SOUTH) != Maze.OPEN_SOUTH else ' '
print('+' + ''.join('---+' for _ in range(self.width)))
for y in range(self.height):
print('|' + ''.join(stringify_cell(x, y) for x in range(self.width)))
print('+' + '+'.join(
stringify_south_of_cell(cell_state)
for cell_state in self.grid[y * self.width:(y + 1) * self.width]
) + '+')
def reset(self):
self.player = self.start
def regenerate(self):
self.generate()
def move(self, direction) -> bool:
'''
プレイヤー(X) を移動させる.
Args:
direction: (x: int, y: int) なる単位ベクトル.
Returns:
移動に成功したか？
Examples:
>> maze.move(Maze.UP)
>> maze.move(Maze.DOWN)
'''
vx, vy = direction
if abs(vx) + abs(vy) != 1:
raise ValueError('direction must be a unit vector')
px, py = self.coordinate(self.player)
# nx, ny: 移動後のマスの位置
nx = px + vx
ny = py + vy
if not self.on_board(nx, ny):
return False
match (vx, vy):
case (v, 0):
left = nx if v < 0 else px
if self.at(left, py) & Maze.OPEN_EAST == 0:
return False
case (0, v):
upper = ny if v < 0 else py
if self.at(px, upper) & Maze.OPEN_SOUTH == 0:
return False
self.player = self.index(nx, ny)
return True
def game_over(self):
return self.player == self.goal
def process_message(maze):
'''
メッセージループの処理
Returns:
処理を終了する場合 True
'''
maze.show()
print('プレイヤー(X) をどの方向に動かすかを入力してください(up, down, left, right)')
print('ゲームを終了する場合、quit; スタート地点に戻る場合 reset; 迷路を再生成する場合 regenerate.')
success_to_move = True
match input('|> '):
case 'up':
success_to_move = maze.move(Maze.UP)
case 'down':
success_to_move = maze.move(Maze.DOWN)
case 'left':
success_to_move = maze.move(Maze.LEFT)
case 'right':
success_to_move = maze.move(Maze.RIGHT)
case 'quit':
return True
case 'reset':
maze.reset()
case 'regenerate':
maze.regenerate()
case _:
print('入力を読み取れませんでした')
return False
if not success_to_move:
print('そちらには移動できません')
if maze.game_over():
maze.show()
print('ゲームクリア！')
return True
return False
# メインの処理
maze = Maze(8, 4)
while(True):
if process_message(maze):
break
説明
メッセージループ
メインの処理はコードの一番下に描かれている関数 process_message と、それを呼び出す無限ループである.
process_message で行っていることを大まかに分ければ
print で入力形式などを表示する
input で入力を受け取る
入力に応じた処理
のみっつで、移動操作やゴール判定は Maze クラスに任せている.
Maze クラス
内部表現
盤面の内部表現
二次元リストで問題はないのだが、何となく一次元リストを使って grid: list[int] としている.
grid[i] は 0 ビット目に右へ移動できるか、1 ビット目に下へ移動できるかを持っている.
書いておいてなんだが、素直に tuple[bool,bool] の形や隣接リストの形で持った方が簡潔だと思う.
中身はコンストラクタのコメントに書いてある通り、0 行目の情報、1 行目の情報、... となっている.
その他にスタート地点、ゴール地点、プレイヤーの現在位置も持っている.
二次元的な x,y を使ってアクセスするには index(self, x, y) や at(self, x, y) を使うようにしている.
x,y が盤面の内側であることを確かめるために on_board(self, x, y) を用意している.
ゴール到達の判定は game_over(self) で行っている.
迷路の生成
迷路の生成にはいくつかの方法があるけれど、ここではクラスカル法に倣ったやり方で生成している.
ゴールは固定で右下としているので、ゴールの奥に到達不能なマスができる可能性もある.
生成方法を見直すか、ゴールの位置設定を見直すかするとより迷路ゲームらしくなると思う.
クラスカル法
クラスカル法の詳しい話は Wikipedia などを見てもらうこととして、ここでは Maze._kruskal でやりたいことのイメージをざっくり示す.
クラスカル法のイメージ
初期状態:
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5| 6| 7|
+---+---+---+---+
| 8| 9| 10| 11|
+---+---+---+---+
| 12| 13| 14| 15|
+---+---+---+---+
マス 5 から右の壁を壊すことを考える(これはランダムに選ぶ. ここではシャッフルした edges を使うことでランダムにしている).
今は 5 と右隣の 6 はつながっていないので、実際にこの壁を壊す.
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5 6| 7|
+---+---+---+---+
| 8| 9| 10| 11|
+---+---+---+---+
| 12| 13| 14| 15|
+---+---+---+---+
マス 10 から下の壁を壊すことを考える.
今は 10 とその下の 14 はつながっていないので、実際にこの壁を壊す.
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5 6| 7|
+---+---+---+---+
| 8| 9| 10| 11|
+---+---+ +---+
| 12| 13| 14| 15|
+---+---+---+---+
マス 5 から下の壁を壊すことを考える.
今は 5 とその下の 9 はつながっていないので、実際にこの壁を壊す.
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5 6| 7|
+---+ +---+---+
| 8| 9| 10| 11|
+---+---+ +---+
| 12| 13| 14| 15|
+---+---+---+---+
マス 9 から右の壁を壊すことを考える(これはランダムに選ぶ. ここではシャッフルした edges を使うことでランダムにしている).
今は 5 とその下の 9 はつながっていないので、実際にこの壁を壊す.
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5 6| 7|
+---+ +---+---+
| 8| 9 10| 11|
+---+---+ +---+
| 12| 13| 14| 15|
+---+---+---+---+
マス 6 から下の壁を壊すことを考える(これはランダムに選ぶ. ここではシャッフルした edges を使うことでランダムにしている).
今は 6 とその下の 10 はつながっている(実際に 6 → 5 → 9 → 10 として移動できる).
よって、この壁は壊さない.
+---+---+---+---+
| 0| 1| 2| 3|
+---+---+---+---+
| 4| 5 6| 7|
+---+ +---+---+
| 8| 9 10| 11|
+---+---+ +---+
| 12| 13| 14| 15|
+---+---+---+---+
このように適当な壁を選び、両側のマスがつながっていなければ壁を壊してつなげる、つながっていればスルーする、ということをすべての壁に対して行うのがクラスカル法である.
例えば、正解のルートにある壁をあらかじめ壊しておいてからクラスカル法を使うことで、迷路を解くと絵が浮かび上がるような問題を作ることもできる.
クラスカル法で重要となるのは壁の両隣がつながっているかどうかの判定であり、UnionFind はこれを実現する.
UnionFind
UnionFind は素集合データ構造の実装のひとつである.
詳しくは Wikipedia でも見てもらえばよいと思うが、
UnionFind が持っている機能は以下のようなものである:
UnionFind の使用例
uf = UnionFind(10)
print(f'{uf.sets()=}')
# uf.sets()=[[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]]
print('0 と 5 をつなげる')
uf.union(0, 5)
print(f'{uf.sets()=}')
# uf.sets()=[[0, 5], [1], [2], [3], [4], [6], [7], [8], [9]]
print('3 と 7 をつなげる')
uf.union(3, 7)
print(f'{uf.sets()=}')
# uf.sets()=[[0, 5], [1], [2], [3, 7], [4], [6], [8], [9]]
print('7 と 5 をつなげる')
uf.union(7, 5)
print(f'{uf.sets()=}')
# uf.sets()=[[0, 3, 5, 7], [1], [2], [4], [6], [8], [9]]
print('0 と 3 はつながっているか？')
print(f'{uf.same(0, 3)=}')
# uf.same(0, 3)=True
print('8 と 3 はつながっているか？')
print(f'{uf.same(8, 3)=}')
# uf.same(8, 3)=False
UnionFind で行っていることのイメージを書いてみる.
最初は全員が個別の班であるとする.
各班には一人だけ班長がおり、その班のメンバーの数を記憶している.
班長でないメンバーは、同じ班の自分でないメンバーを一人だけ記憶している.
ここで、あるメンバーに「あなたの班の班長は誰？」と訊くことができる (find(i)).
自身が班長であれば「私だ」と答えて終わり.
そうでない場合、自分が記憶しているメンバーに「この班の班長は？」と訊く.
答えが返ってきたとき、元々覚えていたメンバーのことは忘れて班長のことだけを記憶する (self.array[i] = root).
あるふたりが同じ班であるかどうか (same(self, i, j)) は、そのふたりの班の班長が同じ人物であるかどうかで判定できる (どの班も班長はひとりだけであるため).
ふたつの班を合併する (union(self, i, j)) ことは、一方の班の班長が班長をやめ、相手方の班長を覚えることで実現できる.
引き続き班長をやる側は、自分が覚えていた班の人数に相手方の班の人数を足し合わせることになる.
素集合データ構造としてはどちらが班長をやってもよいのだが、今回の実装ではより大きな班を率いていた方が引き続き班長となるようにしている.
移動
Maze.player を更新することで移動を表現する.
ただし、盤外に出たら移動失敗.
Board.grid は右/下へ移動できるかしか記憶していないので、左/上へ移動するには「左のマスから右へ移動できるか？」というようなことを参照しなければならなくなってしまった.
迷路の描画
show(self) で盤面を描画している.
一行目は上端の壁 (+---+---+---+---+---+---+---+---+) を書く.
その後、その行にあるマスと下側の壁を同時に書いていく.
プレイヤーがいるマスには X、スタート地点は S、ゴール地点は G をそれぞれ書く.
プレイヤーがスタートやゴールにいるときは X のみを書くこととしている.
Python の勉強ポイント
この部分を書いて勉強になった点のまとめ
デフォルト値を持つ辞書 (collections.defaultdict)
迷路の処理には一切使っていない UnionFind.sets() で使っているだけであるが.
UnionFind より抜粋
def sets(self) -> list[list[int]]:
'''
集合の集合を得る
Returns:
集合の集合
'''
from collections import defaultdict
ss = defaultdict(list)
for i in range(self.size):
ss[self.find(i)].append(i)
return list(ss.values())
Python では辞書の実装として dict というのがあるが、まだ使用していないキーでアクセスするとエラーとなってしまう.
defaultdict を使うと、初めてアクセスするタイミングで勝手に設定してくれる.
defaultdict の例
from collections import defaultdict
d0 = dict()
# # d0[0] はまだ何も入っていないので KeyError となる
# d0[0] += 1
# print(f'{d0[0]=}')
# # d0[1] はまだ何も入っていないので KeyError となる
# print(f'{d0[1]=}')
# setdefault(key, default_value) を使うと、
# d0[key] が存在する場合はなにもしない. 存在しない場合は d0[key] = default_value を実行する.
# Java で考えれば Map.putIfAbsent(K, V).
d0.setdefault(2, 0)
d0[2] += 1
print(f'{d0[2]=}')
d0.setdefault(3, 0)
print(f'{d0[3]=}')
# defaultdict の第一引数は関数である点に注意.
# d1 = defaultdict(int) としてもよい(int() == 0 であるため)
d1 = defaultdict(lambda: 0)
d1[0] += 1
print(f'{d1[0]=}')
print(f'{d1[1]=}')
おまけ
思いついただけで実装はしていないが、以下のような6方向へ移動できる迷路を考えてみるのもいいかもしれない.
6方向へ移動できる迷路
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| S | X | | |
+--+ +--+--+ +--+--+--+ +--+--+--+ +--+ +--+--+ + +--+
| | | | | | | |
+--+ +--+--+ +--+ + +--+--+ +--+--+ +--+ +--+--+ +--+
| | | | | | | |
+--+--+ +--+--+ +--+ +--+ +--+--+ +--+--+ +--+--+ +--+
| | | | | | | |
+--+--+ +--+ + +--+--+ +--+ + +--+ +--+--+--+--+--+--+
| | | | | G |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
上のように、馬目地状にマスを並べることで各マスが左上、右上、右、右下、左下、左の6方向のマスと隣接するようにできる.
移動操作は wasd に倣って uikmnh とかがよいのではないか.