こんにちは
konoです。今回の白鷺祭ではオセロAIのようなものを作ろうと頑張っていましたが、どうしてもアルゴリズムの実装がうまくいかなかったので急遽代わりのものを作ることになりました。うーんどうしようかなーーそうだ！
迫りくるマッチョから逃げるゲームを作ろう！
まずフィールド作りから始めることにしました。すぐ終わるやろと思っていたわけですがフィールドを作っていたら白鷺祭の日になっていましたね。ほにゅ...？
ゲームを完成させることはできませんでしたが、フィールドをつくっただけでもきっとえらいです。というわけでこの記事は、後々作る（かもしれない）ゲームのためのフィールド作成プログラムを書いたよ、というものです。
ポケダンを目標に
フィールドを作るにあたって参考にしたのがポケモン不思議のダンジョン、略してポケダンシリーズです。
ポケダンではダンジョンがランダムに生成されます。同じ名前のダンジョンを訪れても毎回フィールドの形が違うんですね。こんなランダムなダンジョン生成に憧れて、似たようなものを作ろうと頑張りました。手順
ポケダンのようなプレイするたびにマップやダンジョンが新たに作られるゲームは「ローグライクゲーム」と言うらしいです。ローグライクゲームでは普通、
① 大きい長方形を複数の長方形に分ける
② 分けられた長方形の中に部屋を作る
③ 部屋をつなぐ道を作る
という手順で地形が作られるらしいです。むずそーー。
プログラムを書く
うおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおお
！！！！！！！！！！！！！！！！！！！！！！！！！！！！
！！！！！！！！！！！！！！！！！！！！！！！！！！！！
！！！！！！！！！！！！！！！！！！！！！！！！！！！！
書いた
書きました。できたものがこちらになります。
中身
プログラムはPython3.9で書きました。Unityとかなんにもわかりませんので。可読性が低くバグの潰し方が汚いソースコードですが、まあ素人の書くコードなんてこんなものでしょう。 うごけばええねん。 去年作ったブラックジャックのプログラムの汚さと比べれば100倍マシです。
ソースコード
from copy import deepcopy
from random import randint, shuffle
from time import sleep
def create_field(H, W):
field = [[0, H, 0, W]]
return field
def divide_area(area_edge, area_index):
# 分割する領域
edges = area_edge.pop(area_index)
# 分割できないくらい領域が小さい時はそのまま返す
if min(edges[1] - edges[0], edges[3] - edges[2]) < 9 or max(edges[1] - edges[0], edges[3] - edges[2]) < 15:
area_edge.append(edges)
return area_edge
# 分割する
divided_area_1 = deepcopy(edges)
divided_area_2 = deepcopy(edges)
if edges[1] - edges[0] > edges[3] - edges[2]:
new_edge = randint(edges[0] + 7, edges[1] - 8)
divided_area_1[1] = new_edge
divided_area_2[0] = new_edge + 1
else:
new_edge = randint(edges[2] + 7, edges[3] - 8)
divided_area_1[3] = new_edge
divided_area_2[2] = new_edge + 1
area_edge.append(divided_area_1)
area_edge.append(divided_area_2)
return area_edge
def divide_field(area_edge, number):
count = 0
while len(area_edge) < number:
count += 1
if count == 3000:
return 0
area_edge = divide_area(area_edge=area_edge, area_index=randint(0, len(area_edge) - 1))
area_edge.sort()
return area_edge
def create_rooms(area_edge):
count_1 = 0
while True:
# 無限ループ対策その１
count_1 += 1
if count_1 == 2000:
return 0
room_edge = []
for area in area_edge:
count_2 = 0
while True:
# 無限ループ対策その２
count_2 += 1
if count_2 == 2000:
return 0
room = [0, 0, 0, 0]
room[0] = randint(area[0] + 1, area[1] - 6)
room[1] = randint(room[0] + 3, min(area[1] - 3, room[0] + 10))
room[2] = randint(area[2] + 1, area[3] - 6)
room[3] = randint(room[2] + 3, min(area[3] - 3, room[2] + 10))
'''
if (room[1] - room[0] < (area[1] - area[0]) * 0.6) and \
(room[3] - room[2] < (area[3] - area[2]) * 0.6):
continue
if (room[1] - room[0] < (area[1] - area[0]) * 0.35) or \
(room[3] - room[2] < (area[3] - area[2]) * 0.35):
continue
if not (0.55 <= (room[1] - room[0]) / (room[3] - room[2]) <= 1.8):
p = randint(1, 100)
if p <= 100:
continue
'''
break
room_edge.append(room)
flag = True
for i in range(4):
edge_set = set()
for r in room_edge:
edge_set.add(r[i])
if len(edge_set) != len(room_edge):
flag = False
if flag:
break
room_edge.sort()
return room_edge
def edge_to_grid(room_edge, H, W):
r = room_edge
keep_out = keep_out_set(room_edge)
grid = [[""] * W for _ in range(H)]
for i in range(H):
for j in range(W):
ok = False
for k in range(len(r)):
if r[k][0] <= i <= r[k][1] and r[k][2] <= j <= r[k][3]:
ok = True
grid[i][j] = "."
break
if not ok:
grid[i][j] = "#"
if (i, j) in keep_out:
grid[i][j] = "x"
return grid
def edge_coordinate(room_edge):
edge_list = [[[] for j in range(4)] for i in range(len(room_edge))]
# 部屋i
for i in range(len(room_edge)):
r = room_edge[i]
for h in range(r[0], r[1] + 1):
if h == r[0]:
for w in range(r[2], r[3] + 1):
edge_list[i][0].append((h, w))
edge_list[i][2].append((h, r[2]))
edge_list[i][3].append((h, r[3]))
elif h == r[1]:
for w in range(r[2], r[3] + 1):
edge_list[i][1].append((h, w))
edge_list[i][2].append((h, r[2]))
edge_list[i][3].append((h, r[3]))
else:
edge_list[i][2].append((h, r[2]))
edge_list[i][3].append((h, r[3]))
return edge_list
def edge_set(room_edge_coordinate):
coordination_set = set()
for room_i in room_edge_coordinate:
for udlr in room_i:
for yx in udlr:
coordination_set.add(yx)
return coordination_set
def keep_out_set(room_edge):
keep_out = set()
for room_i in room_edge:
keep_out.add((room_i[0] - 1, room_i[2] - 1))
keep_out.add((room_i[0] - 1, room_i[3] + 1))
keep_out.add((room_i[1] + 1, room_i[2] - 1))
keep_out.add((room_i[1] + 1, room_i[3] + 1))
return keep_out
def divide_keep_out(room_edge):
keep_out = [[] for _ in range(4)]
for room_i in room_edge:
keep_out[0].append((room_i[0] - 1, room_i[2] - 1))
keep_out[1].append((room_i[0] - 1, room_i[3] + 1))
keep_out[2].append((room_i[1] + 1, room_i[2] - 1))
keep_out[3].append((room_i[1] + 1, room_i[3] + 1))
return keep_out
def print_field(field_grid):
H = len(field_grid)
W = len(field_grid[0])
print(" ", end="")
for j in range(W):
if j <= 9:
print(j, end=" ")
else:
print(j, end="")
print()
for i in range(H):
if i <= 9:
print(i, end=" ")
else:
print(i, end=" ")
for j in range(W):
print(field_grid[i][j], end=" ")
print()
print()
def DFS_connect(field_grid, now, past):
H = len(field_grid)
W = len(field_grid[0])
if field_grid[now[0]][now[1]] != ".":
dydx = ((-1, 0), (1, 0), (0, -1), (0, 1))
can_go = []
for dy, dx in dydx:
next = (now[0] + dy, now[1] + dx)
if (not 0 <= next[0] <= H - 1) or (not 0 <= next[1] <= W - 1):
return field_grid
if (field_grid[next[0]][next[1]] == "|" or field_grid[next[0]][next[1]] == ".") and next != past:
can_go.append(next)
for next in can_go:
DFS_connect(field_grid, next, now)
if field_grid[now[0]][now[1]] == ".":
field_grid[past[0]][past[1]] = "."
return field_grid
else:
return field_grid
def arrange_grid(field_grid):
for h in range(len(field_grid)):
for w in range(len(field_grid[0])):
if field_grid[h][w] != ".":
field_grid[h][w] = "#"
return field_grid
def add_straight_road(field_grid, room_edge_coordinate):
H = len(field_grid)
W = len(field_grid[0])
r = room_edge_coordinate
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
front = [[(-1, -1), (-1, 1)], [(1, 1), (1, -1)], [(1, -1), (-1, -1)], [(1, 1), (-1, 1)]]
for i in range(len(r)):
# 部屋iから道をつくっていく
for d in range(4): # ４方向について
now = list(r[i][d][randint(0, len(r[i]) - 1)])
# もし道をつくることで道が太くなるなら飛ばす
flag = False
for dy, dx in front[d]:
if field_grid[now[0] + dy][now[1] + dx] == "." or field_grid[now[0] + dy][now[1] + dx] == "|":
flag = True
break
if flag:
continue
dy, dx = direction[d]
start = now
dfs_start = (now[0] + dy, now[1] + dx) # 後のDFSで使う
while True:
next = [now[0] + dy, now[1] + dx]
# 範囲外ならbreak
if (not 0 <= next[0] <= H - 1) or (not 0 <= next[1] <= W - 1):
break
# 通れないならbreak
if field_grid[next[0]][next[1]] == "x":
break
# どこかと繋がったら道を作ってからbreak
if field_grid[next[0]][next[1]] == "." or field_grid[next[0]][next[1]] == "|":
# DFSで繋ぐ
try:
field_grid = DFS_connect(field_grid, now=dfs_start, past=start)
except RecursionError:
return 0
break
field_grid[next[0]][next[1]] = "|"
now = [next[0], next[1]]
field_grid = arrange_grid(field_grid)
return field_grid
def narrow_road(field_grid, keep_out, room_edge_set):
H = len(field_grid)
W = len(field_grid[0])
direction = [[(-1, 0), (0, -1)], [(-1, 0), (0, 1)], [(1, 0), (0, -1)], [(1, 0), (0, 1)]]
front = [[[(-1, -1), (-1, 1)], [(-1, -1), (1, -1)]],
[[(-1, -1), (-1, 1)], [(-1, 1), (1, 1)]],
[[(1, -1), (1, 1)], [(-1, -1), (1, -1)]],
[[(1, -1), (1, 1)], [(-1, 1), (1, 1)]]]
for c in range(4):
# ４つの角について
# 左上、右上、左下、右下の順
for corner in keep_out[c]:
# ある方向にあるkeepoutのマスすべてについて
# 左上、右上、左下、右下の順
for d in range(2):
# keepoutのマスの、調べなければならない方向２つについて
# direction[c] は [(-1, 0), (0, -1)]
# direction[c][d] は (-1, 0)
dy, dx = direction[c][d][0], direction[c][d][1]
now_y, now_x = corner[0], corner[1]
if field_grid[now_y + dy][now_x + dx] != ".": # 異常なし
continue
else: # バグの可能性
while True:
# front[c][d] は [(-1, -1), (-1, 1)]
if not (0 <= now_y + front[c][d][0][0] <= H - 1 and 0 <= now_x + front[c][d][0][1] <= W - 1):
break
if not (0 <= now_y + front[c][d][1][0] <= H - 1 and 0 <= now_x + front[c][d][1][1] <= W - 1):
break
look_1 = field_grid[now_y + front[c][d][0][0]][now_x + front[c][d][0][1]]
look_2 = field_grid[now_y + dy][now_x + dx]
look_3 = field_grid[now_y + front[c][d][1][0]][now_x + front[c][d][1][1]]
if (now_y + dy, now_x + dx) in room_edge_set:
break
elif look_2 != ".":
break
elif look_1 == look_3 == ".":
now_y, now_x = now_y + dy, now_x + dx
continue
elif look_1 == look_3 == "#":
break
else:
field_grid[now_y + dy][now_x + dx] = "#"
now_y, now_x = now_y + dy, now_x + dx
if not (0 <= now_y <= H - 1 and 0 <= now_x <= W - 1):
break
return field_grid
def road_start_point(field_grid, room_edge_coordinate):
dydx = ((-1, 0), (1, 0), (0, -1), (0, 1))
start_point = list()
r = room_edge_coordinate
for i in range(len(room_edge_coordinate)): # 部屋番号
for j in range(4): # 方向
dy, dx = dydx[j]
for y, x in r[i][j]: # (y, x) は部屋の縁の座標
if field_grid[y + dy][x + dx] == ".":
start_point.append((y + dy, x + dx, y, x))
return start_point
def DFS_make_up(field_grid, now, past, room_edge_set):
dydx = ((-1, 0), (1, 0), (0, -1), (0, 1))
can_go = []
for dy, dx in dydx:
next = (now[0] + dy, now[1] + dx)
if field_grid[next[0]][next[1]] == ".":
if next != past:
can_go.append(next)
if len(can_go) == 0:
next = (now[0] + (now[0] - past[0]), now[1] + (now[1] - past[1]))
field_grid[next[0]][next[1]] = "."
can_go.append(next)
for next in can_go:
if next in room_edge_set:
return field_grid
DFS_make_up(field_grid, next, now, room_edge_set)
return field_grid
def make_up_lacking_part(field_grid, road_start, room_edge_set):
try:
for y_s, x_s, y_r, x_r in road_start: # 道の根本を全部見ていく
field_grid = DFS_make_up(field_grid, (y_s, x_s), (y_r, x_r), room_edge_set)
except RecursionError:
return 0
return field_grid
# 最終的に、これだけ実行してマップを作れるようにする
def generate():
while True:
# まず大枠をつくる
while True:
H = randint(28, 32)
W = randint(32, 40)
# 枠づくり
edge = create_field(H, W)
# いくつに分割するかをきめる
number_of_area = [8] * 100
number = number_of_area[randint(0, 99)]
# 分割
area_edges = divide_field(edge, number)
if area_edges == 0:
continue
room_edges = create_rooms(area_edges)
if room_edges == 0:
continue
else:
break
field_grid = edge_to_grid(room_edges, H, W)
# 次に部屋をつなぐ道をつける
shuffle(room_edges)
room_edge_coordinate = edge_coordinate(room_edges)
field_grid = add_straight_road(field_grid, room_edge_coordinate)
if field_grid == 0:
continue
room_edge_set = edge_set(room_edge_coordinate)
# バグって太い道を細くする
field_grid = narrow_road(field_grid, divide_keep_out(room_edges), room_edge_set)
# バグって欠けた道を修復する
road_start = road_start_point(field_grid, room_edge_coordinate)
field_grid = make_up_lacking_part(field_grid, road_start, room_edge_set)
if field_grid == 0:
continue
# 完成！！！！！！！！！
break
for i in field_grid:
print(*i)
print("\n")
while True:
generate()
sleep(1.8)
がんばったところ
色々あるのですがなんと言っても部屋をつなぐ道づくりです。ごめん頑張ったので長くなります。どうやって道をつなげようか調べていた時に見つけたサイトでは、
① 繋ぐ２つの部屋を決める
② ２部屋から道を伸ばし、
③ 部屋の属する領域同士の境界線上でつなぎ合わせる
という方法が書かれていました。文ではわかりづらいですが、上のイラストのような部屋のつなぎ方ですね。
確かにこの方法でできる道はとてもポケダンらしい見た目なのですが、自分はちょっとこの方法で上手くいく気がしなかったので、以下の方法で道を作りました。
① ひとつの部屋を選ぶ
② その部屋から上下左右４方向に道（仮）を伸ばす
③ 道（仮）が他の部屋に当たれば道（仮）をちゃんとした道にする、
他の部屋に当たらなかったらとりあえず道（仮）を放置
④ 他の部屋からも４方向に道（仮）を伸ばし、他の部屋や他の部屋からの道（仮）に当たれば
道（仮）をちゃんとした道にして部屋同士をつなげる
⑤ ④を残りのすべての部屋について施す
④以降で道をつなげる時、「深さ優先探索」といわれるアルゴリズムを用いたのですが、僕はこのアルゴリズムがとっても苦手です。記事の最初に「アルゴリズムの実装ができなくてオセロAI作りを断念した」と書きましたが、そのアルゴリズムであるアルファベータ法は再帰（関数の定義に同じ関数を利用すること）を利用して強い手を探すというものです。
僕は再帰がめちゃくちゃ嫌いでできるだけ避けて生きてきたのですが、今回必要になった深さ優先探索も不幸なことに再帰を利用するアルゴリズムです。再帰から逃げてきたのに再帰に回り込まれてしまいました。仕方ないので泣く泣く深さ優先探索と向き合います。
なんとか⑤まで終わらせると、今度は怒涛のバグ潰しが待っていました。
まずなんか道が太くなってました。なんやかんやで原因をつきとめ、どうにもならんので太い道を作らないことを諦め、太くなった道を細くする方向で頑張りました。
頑張った結果、なんか道がちぎれてました。どうしようか考えましたが
深さ優先探索で補正するのが一番よさそうでした。
このバグ10回に１回も起きやんし、正直もう放置でよくないですか？そう言う悪魔を必死に抑えつつもう一度深さ優先探索を書きました。もう自分でも何を書いているのか分からなかったですがなんか上手く動いたのでOKです。
改善したい点
ひとつとてもわかりやすいバグがあります。上の動画を注意深く見ていた人は気づいたかもしれません。
このマップ生成方法だと、なんと他のどの部屋にも道が繋がっていない部屋、つまり孤立した部屋がごく稀にできてしまうんですね。マッチョから逃げるゲームを作るときにこのバグが残ったままだと、主人公のスポーン地点がその孤立部屋だった場合、どれだけ放置してもそこにマッチョが来ることがないという状況になってしまいます。
解決策は浮かんでいますがこの記事を書いている現在11月５日(土)の朝５時半ということで、バグを直してまた実行の様子をキャプチャしてうんぬんかんぬんする元気は僕にはありません。ゆるして。
もうひとつ絶対にどうにかしたい部分が、最初に示した全体の手順
① 大きい長方形を複数の長方形に分ける
② 分けられた長方形の中に部屋を作る
③ 部屋をつなぐ道を作る
の①と②の部分、つまり部屋づくりですね。今回、部屋の個数と大きさをランダムで良い感じに決まるようにしたかったのですが、大きさを良い感じにすることができませんでした。（部屋の数を良い感じのランダムにすることはできましたが、上のコードでは見栄えが良くなるように一旦部屋の数を８個に固定しています。）
動画を見てもらえればわかる通り、部屋の大きさが全体的に小さいです。一応部屋の大きさをランダムにすることはできていますがその自由度が低いんですね。なんとかしたいです。
感想
バグを直したところからまた別のバグが発生するというあるある(？)を体験できたのが楽しかったですね。今回書いたプログラムは400行くらいで僕にとってはとても大変だったのですが、ガチでプログラミングをする人は何千行何万行、多い時は何十万行のプログラムを書くこともあるらしくて戦慄しています。化け物か？
あと、変数名や関数名が同じようなものばかりになってどの変数に何が格納されているのかわからないことが多々ありました。読みやすいプログラムを書くにはどうしないといけないのか勉強していかないといけませんね。
作るものが途中で変更になりましたが、なんとか展示時間までに作品を形にできてよかったです。最後に、魅力的な作品がたくさんある中、文字ばっかりで長ったらしいこれを読んでくださり、ありがとうございました。
