▲
top
top
Pythonのtkinterで迷路の制作を目指す
迷路制作（３）
アルゴリズム[1]の実装
実行結果まで読み飛ばす
アルゴリズム[1]を実装するにあたり、具体的な方法を決める。
① １マスおきに設置した壁から上下左右からランダムに選んだ方向に新たな壁を生やす。また、この手順で生成した迷路には経路の空きが多すぎる（迷路が簡単すぎる）ため、各壁において一定の確率でもう一度手順１を行い２個目の壁を生やす。
② 壁の当たり判定を実装し、ユーザーを移動させる関数に組み込む。
③ 壁の生成とユーザーの位置を初期化する関数と、新たに生成した壁を全て破壊する関数を追加する。
④ 迷路ウィンドウとは別に、迷路の生成と乱数の調整が行えるウィンドウを実装する。（なんとなくそっちの方が格好良いから）
※以下より、２個目の壁を生成する際に使用する変数のことを「重複変数」と呼ぶ。
この重複変数がnである時、２個目の壁が生成される確率は1/(n+1)になる。
では上の方法通りにコードを作成していく。
等間隔に置かれた壁から新たな壁を生やす関数：
（limは重複変数、wallsは壁の座標、entはtkinter.Entryのインスタンス）
lim = 10
def ram():
global walls, ent, lim
try:
lim = int( ent.get() )
except:
lim = 10
walls = []
for x in xs_z:
for y in ys_z:
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
if( random.randint( 0, lim ) == 0 ):
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
sel = lambda : 25 if( random.randint( 0, 1 ) == 0 ) else -25
def ram():
global walls, ent, lim
try:
lim = int( ent.get() )
except:
lim = 10
walls = []
for x in xs_z:
for y in ys_z:
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
if( random.randint( 0, lim ) == 0 ):
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
sel = lambda : 25 if( random.randint( 0, 1 ) == 0 ) else -25
新たに生成した壁をユーザーが貫通できないようにコードを加筆したユーザーの移動関数：
def left( event ):
global x0, y0, x1, y1, walls
if( x0 > 0 ) and not ( ( xs[x0-1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0-1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 -= 1
x1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def right( event ):
global x0, y0, x1, y1, walls
if( x1 < 21 ) and not ( ( xs[x0+1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0+1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 += 1
x1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def up( event ):
global x0, y0, x1, y1, walls
if( y0 > 0 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0-1] in zs[1] ) ) and not ( [ xs[x0], ys[y0-1] ] in walls ):
canvas.delete( 'rec' )
y0 -= 1
y1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def down( event ):
global x0, y0, x1, y1, walls
if( y1 < 21 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0+1] in zs[1] ) ) and not ( [ xs[x0], ys[y0+1] ] in walls ):
canvas.delete( 'rec' )
y0 += 1
y1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
global x0, y0, x1, y1, walls
if( x0 > 0 ) and not ( ( xs[x0-1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0-1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 -= 1
x1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def right( event ):
global x0, y0, x1, y1, walls
if( x1 < 21 ) and not ( ( xs[x0+1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0+1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 += 1
x1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def up( event ):
global x0, y0, x1, y1, walls
if( y0 > 0 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0-1] in zs[1] ) ) and not ( [ xs[x0], ys[y0-1] ] in walls ):
canvas.delete( 'rec' )
y0 -= 1
y1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def down( event ):
global x0, y0, x1, y1, walls
if( y1 < 21 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0+1] in zs[1] ) ) and not ( [ xs[x0], ys[y0+1] ] in walls ):
canvas.delete( 'rec' )
y0 += 1
y1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
バインドされた入力により、新たに生成した壁を全て破壊し再びアルゴリズム[1]を実行する関数：
バインドについての説明
バインドとは紐付けのようなもので、bind()関数を用いて特定の関数と特定の操作を紐付けすることである。 今回は以下のreset()関数をキーボードのEnterキー、及び画面上のボタンにバインドしている。
def reset( event ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
ユーザーがゴールに到達した際に、新たに生成した壁を全て破壊し再びアルゴリズム[1]を実行する関数：
def restart( x, y ):
if( x == res_p - 1 ) and ( y == res_p - 1 ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
if( x == res_p - 1 ) and ( y == res_p - 1 ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
壁の再生成と、重複変数の変更ができるウィンドウの定義：
man = t.Tk()
man.title( 'manager' )
man.geometry( '200x120' )
man[ 'background' ] = '#ffffff'
lab = t.Label( man, text = u'壁の重複変数', font = ( 'Arial', 15 ), background = '#ffffff' )
lab.place( x = 10, y = 10 )
ent = t.Entry( man, font = ( 'Arial', 15 ), width = 8, justify = t.CENTER )
ent.insert( 0, '4' )
ent.place( x = 105, y = 9 )
btn = t.Button( man, text = u'迷路の再生成\n[ Enter ]', font = ( 'Arial', 18 ), background = '#d0ffd0' )
btn.place( x = 10, y = 45, width = 180, height = 60 )
btn.bind( '<Button-1>', reset )
man.bind( '<Return>', reset )
man.mainloop()
man.title( 'manager' )
man.geometry( '200x120' )
man[ 'background' ] = '#ffffff'
lab = t.Label( man, text = u'壁の重複変数', font = ( 'Arial', 15 ), background = '#ffffff' )
lab.place( x = 10, y = 10 )
ent = t.Entry( man, font = ( 'Arial', 15 ), width = 8, justify = t.CENTER )
ent.insert( 0, '4' )
ent.place( x = 105, y = 9 )
btn = t.Button( man, text = u'迷路の再生成\n[ Enter ]', font = ( 'Arial', 18 ), background = '#d0ffd0' )
btn.place( x = 10, y = 45, width = 180, height = 60 )
btn.bind( '<Button-1>', reset )
man.bind( '<Return>', reset )
man.mainloop()
以上で実装するべき機能は完成である。下の折り畳み欄にプログラムの全文を記載した。
プログラム全文
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import tkinter as t, random
pad = [ 3, 3 ]
res_p = 21
xs, ys = [ pad[0] + x * 25 for x in range( res_p + 1 ) ], [ pad[1] + y * 25 for y in range( res_p + 1 ) ]
lim = 10
def alert():
print( '\a', end='' )
def left( event ):
global x0, y0, x1, y1, walls
if( x0 > 0 ) and not ( ( xs[x0-1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0-1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 -= 1
x1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def right( event ):
global x0, y0, x1, y1, walls
if( x1 < 21 ) and not ( ( xs[x0+1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0+1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 += 1
x1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def up( event ):
global x0, y0, x1, y1, walls
if( y0 > 0 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0-1] in zs[1] ) ) and not ( [ xs[x0], ys[y0-1] ] in walls ):
canvas.delete( 'rec' )
y0 -= 1
y1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def down( event ):
global x0, y0, x1, y1, walls
if( y1 < 21 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0+1] in zs[1] ) ) and not ( [ xs[x0], ys[y0+1] ] in walls ):
canvas.delete( 'rec' )
y0 += 1
y1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def ram():
global walls, ent, lim
try:
lim = int( ent.get() )
except:
lim = 10
walls = []
for x in xs_z:
for y in ys_z:
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
if( random.randint( 0, lim ) == 0 ):
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
sel = lambda : 25 if( random.randint( 0, 1 ) == 0 ) else -25
def reset( event ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
def restart( x, y ):
if( x == res_p - 1 ) and ( y == res_p - 1 ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
app = t.Tk()
app.title( '迷路' )
app.geometry( '530x530' )
app.resizable( False, False )
canvas = t.Canvas( app, width = 525, height = 525 )
canvas.place( x = 0, y = 0 )
x0, y0, x1, y1 = 0, 0, 1, 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
canvas.create_rectangle( xs[20], ys[20], xs[21], ys[21], tag = 'goal', fill = '#50ff50', outline = '#000000' )
xs_z = [ xs[i] for i in range( len(xs) ) if i % 2 != 0 ]
ys_z = [ ys[i] for i in range( len(xs) ) if i % 2 != 0 ]
zs = xs_z, ys_z
for x in xs_z:
for y in ys_z:
canvas.create_rectangle( x, y, x+25, y+25, tag = 'default', fill = '#000000', outline = '#000000' )
ram()
app.bind( '<Key-Left>', left )
app.bind( '<Key-Right>', right )
app.bind( '<Key-Up>', up )
app.bind( '<Key-Down>', down )
app.bind( '<Return>', reset )
man = t.Tk()
man.title( 'manager' )
man.geometry( '200x120' )
man[ 'background' ] = '#ffffff'
lab = t.Label( man, text = u'壁の重複変数', font = ( 'Arial', 15 ), background = '#ffffff' )
lab.place( x = 10, y = 10 )
ent = t.Entry( man, font = ( 'Arial', 15 ), width = 8, justify = t.CENTER )
ent.insert( 0, '4' )
ent.place( x = 105, y = 9 )
btn = t.Button( man, text = u'迷路の再生成\n[ Enter ]', font = ( 'Arial', 18 ), background = '#d0ffd0' )
btn.place( x = 10, y = 45, width = 180, height = 60 )
btn.bind( '<Button-1>', reset )
man.bind( '<Return>', reset )
app.mainloop()
man.mainloop()
# -*- coding: utf-8 -*-
import tkinter as t, random
pad = [ 3, 3 ]
res_p = 21
xs, ys = [ pad[0] + x * 25 for x in range( res_p + 1 ) ], [ pad[1] + y * 25 for y in range( res_p + 1 ) ]
lim = 10
def alert():
print( '\a', end='' )
def left( event ):
global x0, y0, x1, y1, walls
if( x0 > 0 ) and not ( ( xs[x0-1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0-1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 -= 1
x1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def right( event ):
global x0, y0, x1, y1, walls
if( x1 < 21 ) and not ( ( xs[x0+1] in zs[0] ) and ( ys[y0] in zs[1] ) ) and not ( [ xs[x0+1], ys[y0] ] in walls ):
canvas.delete( 'rec' )
x0 += 1
x1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def up( event ):
global x0, y0, x1, y1, walls
if( y0 > 0 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0-1] in zs[1] ) ) and not ( [ xs[x0], ys[y0-1] ] in walls ):
canvas.delete( 'rec' )
y0 -= 1
y1 -= 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def down( event ):
global x0, y0, x1, y1, walls
if( y1 < 21 ) and not ( ( xs[x0] in zs[0] ) and ( ys[y0+1] in zs[1] ) ) and not ( [ xs[x0], ys[y0+1] ] in walls ):
canvas.delete( 'rec' )
y0 += 1
y1 += 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
restart( x0, y0 )
else:
alert()
def ram():
global walls, ent, lim
try:
lim = int( ent.get() )
except:
lim = 10
walls = []
for x in xs_z:
for y in ys_z:
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
if( random.randint( 0, lim ) == 0 ):
if( random.randint( 0, 1 ) == 0 ):
x_p, y_p = sel(), 0
else:
x_p, y_p = 0, sel()
canvas.create_rectangle( x + x_p, y + y_p, x+25 + x_p, y+25 + y_p, tag = 'walls', fill = '#000000', outline = '#000000' )
walls.append( [ x + x_p, y + y_p ] )
sel = lambda : 25 if( random.randint( 0, 1 ) == 0 ) else -25
def reset( event ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
def restart( x, y ):
if( x == res_p - 1 ) and ( y == res_p - 1 ):
global x0, y0, x1, y1
canvas.delete( 'walls' )
canvas.delete( 'rec' )
x0, y0, x1, y1 = 0, 2, 1, 3
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
ram()
app = t.Tk()
app.title( '迷路' )
app.geometry( '530x530' )
app.resizable( False, False )
canvas = t.Canvas( app, width = 525, height = 525 )
canvas.place( x = 0, y = 0 )
x0, y0, x1, y1 = 0, 0, 1, 1
canvas.create_rectangle( xs[x0], ys[y0], xs[x1], ys[y1], tag = 'rec', fill = '#ff5050', outline = '#000000' )
canvas.create_rectangle( xs[20], ys[20], xs[21], ys[21], tag = 'goal', fill = '#50ff50', outline = '#000000' )
xs_z = [ xs[i] for i in range( len(xs) ) if i % 2 != 0 ]
ys_z = [ ys[i] for i in range( len(xs) ) if i % 2 != 0 ]
zs = xs_z, ys_z
for x in xs_z:
for y in ys_z:
canvas.create_rectangle( x, y, x+25, y+25, tag = 'default', fill = '#000000', outline = '#000000' )
ram()
app.bind( '<Key-Left>', left )
app.bind( '<Key-Right>', right )
app.bind( '<Key-Up>', up )
app.bind( '<Key-Down>', down )
app.bind( '<Return>', reset )
man = t.Tk()
man.title( 'manager' )
man.geometry( '200x120' )
man[ 'background' ] = '#ffffff'
lab = t.Label( man, text = u'壁の重複変数', font = ( 'Arial', 15 ), background = '#ffffff' )
lab.place( x = 10, y = 10 )
ent = t.Entry( man, font = ( 'Arial', 15 ), width = 8, justify = t.CENTER )
ent.insert( 0, '4' )
ent.place( x = 105, y = 9 )
btn = t.Button( man, text = u'迷路の再生成\n[ Enter ]', font = ( 'Arial', 18 ), background = '#d0ffd0' )
btn.place( x = 10, y = 45, width = 180, height = 60 )
btn.bind( '<Button-1>', reset )
man.bind( '<Return>', reset )
app.mainloop()
man.mainloop()
では実際に遊んでみよう。
最後にこのアルゴリズムの良かった点と悪かった点を列挙する。
良かった点：
・実装が容易であった。
・迷路の生成が高速に行える。
悪かった点：
・スタートから出れなかったりゴールが壁に囲まれていたりするなど、絶対にクリアできない迷路を生成することがある。
・スタートからゴールまでの道筋が複数できることがあり、迷路としての難易度が低い。
これでアルゴリズム[1]の実験は完了である、次は経路主体で迷路を生成するアルゴリズム[2]の実装に取り掛かろうと思う。
次： 迷路制作（４） 思い出しがてらアーキテクチャの見直し
迷路制作のページ： １ ２ ３ ４ ５
にっきのページに戻る