思考ノイズ

無い知恵を絞りだす。無理はしない。

ランダム迷路をコーディング

モチベーション

昔よく遊んだゲームで「トルネコの大冒険」というのがありました。いわゆるローグ系の走りで毎回変わるダンジョンの配置に驚かされたものです。今回はそのダンジョンをランダムに作る・・・と思ったのですが、頭で考えた限りではちょっと設定がめんどくさそうかなぁと。そこで、トルネコのダンジョンのかなり下の階にでてくる、ランダム迷路をつくってみようかと思いました。いまの私の実力にちょうどいい。よし、それをPythonでやってみようぞ!

まずは結果から

こんなんを出力しました。にょきにょき伸びていく感じがなんとも気持ち悪くて俺好みですよ。 f:id:bython-chogo:20170608232524g:plain

きちんと迷路になっています。定義としてはループをつくらない、マスを全部埋めていく、ということを念頭においてました。まあ、よくみると埋まっていないますもあるのですが、まあ、おおめに見てください。

全部のコード

import numpy as np
import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import matplotlib.patches as patches
%matplotlib inline
from IPython.display import HTML

class MakeMaize():
    def __init__(self):
        self.size = [60,60]
        self.holes = [[[1,1,1,1] for i in range(self.size[1])] for j in range(self.size[0])]
        self.holes[0][0] = [0, 0, 1, 1]
        self.driller = []
        self.died = []
        self.dlog = []

    #上下左右のマスに動けるかチェック。[下、左、上、右]でいけたら1
    def check_available(self, plr):
        direction = [1,1,1,1]
        
        # 今来た道は戻れない
        direction[(plr["f"]-2)%4] = 0
        # 壁にいるときは壁側に移動できない
        if plr["p"][0] == 0: direction[1] =0
        if plr["p"][1] == 0: direction[0] =0
        if plr["p"][0] == self.size[0] - 1: direction[3] = 0
        if plr["p"][1] == self.size[1] - 1: direction[2] = 0

        # それ以外で、すでに埋まっている場所を確認(holesに記録)
        x = plr["p"][0]; y = plr["p"][1];
        for i, d in enumerate([[0,-1],[-1,0],[0,1],[1,0]]):
            dx = x + d[0]; dy = y + d[1];
            if direction[i] ==1:
                #print "DX:DY:", dx, dy, self.holes[dx][dy]
                ix = 1
                for j in self.holes[dx][dy]:
                    ix *= j
                direction[i] = ix
        # 結果を返す
        return direction
    # 3から9までの値をランダムに返す。分岐、折れ曲がりのタイミングを設定
    def ran_gene(self):

        return random.choice(range(3,10))
        
    # ルーティン drillerが場所を定義
    def step_forward(self, c):
        def direc(f, p, g):
            x, y = 0, 0
            if f == 0: y = - 1
            if f == 1: x = - 1
            if f == 2: y = 1
            if f == 3: x = 1
            
            while len(self.dlog) != c+1:
                self.dlog.append([])
                

            self.dlog[c].append([[p[0], p[0]+x], [p[1], p[1]+y]])

            return [p[0]+x, p[1]+y]
        
        # Drillerの1ステップ
        for d, drl in enumerate(self.driller):

            # 現在の動ける場所を確認
            av_dire = self.check_available(self.driller[d])
            # 動ける場所がない場合は動ける場所にワープ
            if av_dire == [0, 0, 0, 0]:
                cands = []
                # 過去ログ中からランダムに動ける場所に移動
                pick = random.choice(self.dlog)
                random.shuffle(pick)
                for p in pick:
                    cand = self.holes[p[0][0]][p[1][0]]
                    if sum(cand) > 0:
                        ordr = [0, 1, 2, 3]
                        random.shuffle(ordr)
                        for o in ordr:
                            if cand[o] == 1:
                                self.driller[d]["f"] = o
                                self.driller[d]["p"] = [p[0][0], p[1][0]]
                                break
                        if self.driller[d]["p"] == [p[0][0], p[1][0]]: break
                        
                    
            # ターン、分岐のカウントを一つずつ減らす
            self.driller[d]["tc"] -= 1
            self.driller[d]["sc"] -= 1
            # 現在の進む向き
            f = self.driller[d]["f"]
            av_dire[(f-2)%4] = 0

            # 現在の向きに進める場合、ターンするカウントが0出ない場合
            # 現在の方向に一つ進む
            if av_dire[f] == 1 and self.driller[d]["tc"] != 0:
                self.driller[d]["p"] = direc(f, self.driller[d]["p"], d)
                av_dire[f] = 0
                
            # 進める方向からランダムに一つ方向をえらぶ
            # 前に進めない場合の対処
            way = []           
            for i, v in enumerate( av_dire):
                if v == 1:
                    way.append(i)

            if len(way) > 0:
                af = random.choice(way)

                # ターンカウントが0のとき
                # 進める方向にターンする
                if self.driller[d]["tc"] <= 0:
                    self.driller[d]["p"] = direc(af, self.driller[d]["p"], d)
                    self.driller[d]["f"] = af

                # 分岐カウントが0のとき
                # 新しいdrillerを作成してリスト追加、進める方向に進ませる
                elif self.driller[d]["sc"] <= 0:
                            
                    #print "\tAF", af, av_dire, 
                    
                    self.driller.append({
                            #"p": direc(f, self.driller[d]["p"]),
                            "p": self.driller[d]["p"],
                            "f": af,
                            "sc": self.ran_gene(),
                            "tc": self.ran_gene()
                        })

                av_dire[af] = 0

            else:
                if d not in self.died:
                    self.died.append(d)

            # 各カウントが0になったときにランダムに値を設定
            if self.driller[d]["tc"] == 0:
                self.driller[d]["tc"] = self.ran_gene()
            if self.driller[d]["sc"] == 0:
                self.driller[d]["sc"] = self.ran_gene()
                    
            self.holes[self.driller[d]["p"][0]][self.driller[d]["p"][1]] = list(av_dire)
        return 0

    # ログの表示
    def print_now(self, c):
        print c
        log = []
        for i, drl in enumerate(self.driller):
            
            print "   ", "PLY", i, "P:", drl["p"], "F:", drl["f"], "SC:", drl["sc"], "TC", drl["tc"]
            log.append(drl["p"])
        self.logs.append(log)
            
    def start(self):
        # 初期のdrillerの配置
        self.driller.append({"p": [0, 0], "f": 3, "tc": self.ran_gene(), "sc": self.ran_gene()})
        #self.driller.append({"p": [self.size[0]-1, self.size[1]-1], "f": 1, "tc": self.ran_gene(), "sc": self.ran_gene()})

        # 各drillerを動かす。
        c = 0
        while(True):
            
            #self.print_now(c)
            code = self.step_forward(c)
            if code < 0:
                break

            if len(self.died) == len(self.driller):
                break
            c += 1
            
            if c == 500:
                break
        
        dlog = []
        p_old = []

        print len(mm.dlog) 

これを使って可視化します。

mm = MakeMaize()
mm.start()

fig = plt.figure()
ax = plt.gca(axisbg='black')
ax.set_xlim(-1, mm.size[0]+1)
ax.set_ylim(-1, mm.size[1]+1)
fig.patch.set_facecolor('black')

def init():
    #line.set_data([0,0], [0,0])
    #return line,
    return []

def animated(i):
    patches = []
    for xy in mm.dlog[i]:
        x, y = xy
        patches.append(ax.add_patch(
                plt.Rectangle((x[0], y[0]), x[1]-x[0], y[1]-y[0], 
                color="white", edgecolor="white", linewidth="2.5")))

    return patches



ani = animation.FuncAnimation(fig, animated, frames=len(mm.dlog), init_func=init, interval=100, blit=True)
ani.save("makemaize.gif",writer='imagemagick')
HTML(ani.to_html5_video())