[Python] コンソールで遊べる簡単なゲームを作る - 迷路

# はじめに

Python の勉強のため簡単なゲームを作りましたので備忘録としてまとめておきます.
とりとめのない個人的な記事ではありますが、python を勉強するどなたかの参考になりましたならば幸いです.
環境は Python 3.13.1、Windows 11、コマンドプロンプトです.

# 完成品

```text:コンソール
+---+---+---+---+---+---+---+---+
| 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.
|>
```

<details>
<summary>ソースコード</summary>

```python: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
```
</details>

# 説明

## メッセージループ
メインの処理はコードの一番下に描かれている関数 `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](https://ja.wikipedia.org/wiki/クラスカル法) などを見てもらうこととして、ここでは `Maze._kruskal` でやりたいことのイメージをざっくり示す.

```text:クラスカル法のイメージ
初期状態:
+---+---+---+---+
|  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](https://ja.wikipedia.org/wiki/素集合データ構造) でも見てもらえばよいと思うが、
`UnionFind` が持っている機能は以下のようなものである:

```python: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()` で使っているだけであるが.

```python: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` を使うと、初めてアクセスするタイミングで勝手に設定してくれる.

```python: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方向へ移動できる迷路を考えてみるのもいいかもしれない.

```text:6方向へ移動できる迷路
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  S  |              X              |                 |     |
+--+  +--+--+  +--+--+--+  +--+--+--+  +--+  +--+--+  +  +--+
   |     |     |     |           |     |     |           |
+--+  +--+--+  +--+  +  +--+--+  +--+--+  +--+  +--+--+  +--+
|           |     |     |           |     |           |     |
+--+--+  +--+--+  +--+  +--+  +--+--+  +--+--+  +--+--+  +--+
   |           |     |     |     |     |           |     |
+--+--+  +--+  +  +--+--+  +--+  +  +--+  +--+--+--+--+--+--+
|           |     |           |     |                    G  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
```

上のように、馬目地状にマスを並べることで各マスが左上、右上、右、右下、左下、左の6方向のマスと隣接するようにできる.
移動操作は wasd に倣って uikmnh とかがよいのではないか.