迷路を描く

Python 裏技っぽい何かAdvent

もう裏技かどうか関係ないような気もしてきましたが、乱数で迷路を描いてみることにします。
年賀状のネタにしようかな。迷路って何となくヘビっぽいし...
別冊だったころのマイコンBASICマガジンとか読んで理解した (あー歳がー) 迷路生成法の「壁延ばし法」を微かな記憶を頼りに焼きなおしてみます。

import random
from PIL import Image, ImageDraw

vect = [(1, 0), (0, -1), (-1, 0), (0, 1)]

def drange(n0, n1):
  d = cmp(n1, n0)
  return xrange(n0, n1+d, d)

class Maze:

  def __init__(self):
    self.wall = 
    self.joint = set()

  def setwall(self, x, y):
    if isinstance(x, tuple):
      for px in drange(*x):
        self.joint.add( (px, y))
    elif isinstance(y, tuple):
      for py in drange(*y):
        self.joint.add( (x, py))
    self.wall.append( (x, y))

  def walk(self, x, y, addvect=):
    t = Maze()
    while (x, y) not in self.joint:
      vs = [v for v in vect+addvect if (x+v[0], y+v[1]) not in t.joint]
      if not vs:
        return False
      v = random.choice(vs)
      t.setwall( (v[0] and (x, x+v[0]) or x), (v[1] and (y, y+v[1]) or y))
      x += v[0]
      y += v[1]
    else:
      self.wall.extend(t.wall)
      self.joint.update(t.joint)
      return True

def printmaze(file, data, pwid, wwid):
  w = pwid + wwid
  img = Image.new('RGB', (n*w+wwid,n*w+wwid), '#ffffff')
  draw = ImageDraw.Draw(img)
  for x, y in m.wall:
    if isinstance(x, tuple):
      draw.line([(x[0]*w,y*w), (x[1]*w,y*w)], width=wwid, fill='#000000')
    elif isinstance(y, tuple):
      draw.line([(x*w,y[0]*w), (x*w,y[1]*w)], width=wwid, fill='#000000')
  img.save(file)


if __name__ == '__main__':
  n = 64

  # 入口と出口を作る
  m = Maze()
  m.setwall( (1, n), 0)
  m.setwall( (0, n-1), n)
  m.setwall(0, (0, n))
  m.setwall(n, (0, n))

  # 先に少し壁を作っておく
  while not m.walk(n / 4, n / 4 * 3, addvect=[(0,-1),(0,-1),(0,-1),(1,0)]):
    pass
  while not m.walk(n / 4 * 3, n / 4, addvect=[(0,1),(0,1),(0,1),(-1,0)]):
    pass
  #printmaze('maze-hint.jpg', m.wall, 7, 1)

  # 壁を埋める
  for x in xrange(1, n):
    for y in xrange(1, n):
      while (x, y) not in m.joint:
        m.walk(x, y)

  printmaze('maze.jpg', m.wall, 7, 1)


壁延ばし法の「仮の壁を作る」というところを、別に迷路インスタンスを作って壁を作り、失敗したらそのインスタンスは破棄、成功したら本番の迷路インスタンスに書き込むということをやっていますが、あまりクラスを作る意味ないですね。これじゃwall、joint、temp_wall、temp_jointでもいいような。
壁のデータの持たせ方は、wallにベクターっぽいデータを入れ、壁とぶつかったかどうかの判定はjointの方でやるという感じです。wallだけでも壁の有無の判定はできそうですが、何となく難しそうだったので、直感的に分かる方法にしました。

「先に少し壁を作っておく」というのは、これがないとほとんどゴールまで一直線で行ける迷路ができてしまうためです。この壁によって、迷路の無駄な部分が少なくなるよう正解のルートを誘導しています。試しに直後のコメントアウトをはずしてmaze-hint.jpgを出力すると、どういう壁が作られたか分かります。
m.walk()が失敗のときTrue、成功のときFalseを返すのは直感に反してますね。まあ「while ...:pass」でリトライさせたかったので。このあたりが一番「裏技っぽい」かも... 【後日修正】やはり直感に反しているので、成功==Trueで「while not ...: pass」ループに変更しました。