# Random dungeon generator

I'm learning Python by converting a BASIC (BlitzPlus) program I wrote based on article at http://gamedeveloper.texterity.com/gamedeveloper/201002?pg=42#pg43 for random dungeon generation.

I've basically used Google and trial and error to get this script to where it is now (which is a working program).

However, I'd like to know if it's "Pythonic" or just a hybrid BASIC to Python translation.

``````# Random Dungeon - use TKInter to draw
from Tkinter import *
import random
master=Tk()
random.seed()

def notConnected(x,y):
uncon=False
if (cellArray[x,y]['u']==0) and (cellArray[x,y]['d']==0) and (cellArray[x,y]['l']==0) and (cellArray[x,y]['r']==0):
uncon=True
return uncon

def pickNeighbour(x,y,d):
done=0
tries=0
while done==0:
if d==1:
if y>0:
if notConnected(x,y-1):
cellArray[x,y]['u']=cellArray[x,y-1]['n']
cellArray[x,y-1]['d']=cellArray[x,y]['n']
newx=x
newy=y-1
done=1
else:
d+=1
if d==5:
d=1
tries+=1
if tries==4:
done=2
else:
d+=1
if d==5:
d=1
if d==2:
if x<cellsX-1:
if notConnected(x+1,y):
cellArray[x,y]['r']=cellArray[x+1,y]['n']
cellArray[x+1,y]['l']=cellArray[x,y]['n']
newx=x+1
newy=y
done=1
else:
d+=1
if d==5:
d=1
tries+=1
if tries==4:
done=2
else:
d+=1
if d==5:
d=1
if d==3:
if y<cellsY-1:
if notConnected(x,y+1):
cellArray[x,y]['d']=cellArray[x,y+1]['n']
cellArray[x,y+1]['u']=cellArray[x,y]['n']
newx=x
newy=y+1
done=1
else:
d+=1
if d==5:
d=1
tries+=1
if tries==4:
done=2
else:
d+=1
if d==5:
d=1
if d==4:
if x>0:
if notConnected(x-1,y):
cellArray[x,y]['l']=cellArray[x-1,y]['n']
cellArray[x-1,y]['r']=cellArray[x,y]['n']
newx=x-1
newy=y
done=1
else:
d+=1
if d==5:
d=1
tries+=1
if tries==4:
done=2
else:
d+=1
if d==5:
d=1

if done==1:
return newx,newy
elif done==2:
return -1,-1

def drawCells():
offsetX=10
offsetY=10
for y in range(cellsY):
for x in range(cellsX):
#draw cells grid
x0=(x*50)+offsetX
y0=(y*50)+offsetY
x1=x0+49
y1=y0+49
canvas.create_rectangle(x0,y0,x1,y1)
canvas.create_text(x0+23,y0+22,text=str(cellArray[x,y]['n']).zfill(2))
#draw rooms
if not(notConnected(x,y)):
rx0=x0+10
ry0=y0+10
rx1=rx0+29
ry1=ry0+29
canvas.create_rectangle(rx0,ry0,rx1,ry1,outline='red')
#draw connections
if cellArray[x,y]['r']!=0:
cx0=rx1
cy0=ry0+15
cx1=rx1+21
cy1=cy0
canvas.create_line(cx0,cy0,cx1,cy1,width=5)
if cellArray[x,y]['d']!=0:
cx0=rx0+15
cy0=ry1
cx1=cx0
cy1=ry1+21
canvas.create_line(cx0,cy0,cx1,cy1,width=5)

#main program
cellsX=10
cellsY=10
done=False
cellArray={}
fillPercent=80
gridWidth=(cellsX*50)
gridHeight=(cellsY*50)
count=-1
connected=0
canvas=Canvas(master,width=gridWidth+50,height=gridHeight+100)
canvas.pack()

for y in range(cellsY):
for x in range(cellsX):
count+=1
cellArray[x,y]={'x':x,'y':y,'u':0,'d':0,'l':0,'r':0,'n':count}

#pick random start cell and direction
rx=random.randint(0,cellsX-1)
ry=random.randint(0,cellsY-1)
rd=random.randint(1,4)
startCell='Start cell: '+str(cellArray[rx,ry]['n'])
connected+=1

while not(done):
nx,ny=pickNeighbour(rx,ry,rd)
if nx==-1:
#see what percent filled
pcf=int(float(connected)/float(cellsX*cellsY)*100)
if pcf>=fillPercent:
endCell='End cell: '+str(cellArray[rx,ry]['n'])
done=True
else:
found=False
while not(found):
rx=random.randint(0,cellsX-1)
ry=random.randint(0,cellsY-1)
if not(notConnected(rx,ry)):
found=True
else:
rx=cellArray[nx,ny]['x']
ry=cellArray[nx,ny]['y']
connected+=1
rd=random.randint(1,4)

drawCells()
canvas.create_text(10,gridHeight+30,text=startCell,justify='right',anchor=W)
canvas.create_text(10,gridHeight+60,text=endCell,justify='right',anchor=W)
master.mainloop()
``````
-
First thought? Separation of concerns. Generating a random dungeon does not equal drawing a random dungeon. Separate your functionality into a part that generates a data structure that represents a dungeon and a part that turns that data structure into a graphical representation. The code will be cleaner, easier to debug, and (not just more pythonic, but) have a better design in general. –  Joel Cornett Jul 28 '12 at 20:22
Second thought? I see that you're repeating a lot of code. If you find yourself typing (almost) the same code over and over again (my rule of thumb is three or more times) try and see if you can 1) do it in a loop. 2) create a separate function that contains that code. –  Joel Cornett Jul 28 '12 at 20:25
Thanks for the replies everyone. I will take those on board and try to make it a proper Python program. In the BASIC version (which I need to look at again), the generation functions became an 'include' file, with main program handling drawing sprites etc to make the dungeon look nice. That's my aim with this version as well (probably in PyGame), but thought I'd nail the generation first (and simple drawing in Tkinter). –  user15289 Jul 29 '12 at 11:46

It reads very much as a Basic program, but it's a reasonable first(ish) python program.

Steps to improve it: Turn your existing global code into a "main" function, and call it via

``````if __name__ == "__main__":
main()
``````

Move all your global variables into the main function. You'll have to add a load of parameters to other functions, which seems like a backward step, but it'll help. You'll notice a lot of repeated parameters, which indicates they should be packaged together into a structure of some sort.

Concerning the cellArray map, the items are currently a dictionary of exits, id and position. Instead, make it into a `Cell` class with separate position and connections objects. As an added bonus, it even has a method `notConnected()`, although please change it's name to something positive, using not(notConnected()) is confusing. Other 'obvious' structures are the maze, xy coordinate, display.

PickNeighbour is far more involved than it needs to be. Creating an `InBounds` function will simplify it a bit, creating a map from direction to "cell offset" will flatten it to just a general case.

Apart from the above:

• Separate out your functions into ones that do a single thing, rather than several.
• Use constants for your "magic numbers".
• You can return different types from functions, so use `None` as a 'failure' value (even `()`), rather than a tuple with an invalid first item. This will test to false.

Because I was in the mood, I adapted your program to how I'd do it. It's a bit over-engineered and it's not 'there' yet, but should give you several ideas.

``````# Random Dungeon - use TKInter to draw
from tkinter import *
import random

class Cell:
def __init__( self, pos = None ):
self.pos = pos
self.connection = {}
def IsConnected( self ):
return len( self.connection ) > 0

def ShiftPosition( pos, offset, scale = (1,1) ):
(x,y) = pos
(ox,oy) = offset
(sx,sy) = (scale,scale) if type(scale) != type(()) else scale
return (x+ox*sx),(y+oy*sy)

class CellExits:
def __init__( self, offsets, side = 0 ):
if ( len(offsets) % 2 ) != 0:
raise IndexError
self.side = side
self.offsets = offsets
self.side_count = len( self.offsets )
def __len__( self ):
return self.side_count
def Set( self, side ):
self.side = side%self.side_count
def Next( self ):
self.Set( self.side + 1 )
def Offset( self ):
return self.offsets[self.side]
def BackOffset( self ):
back_offset = (self.side + self.side_count//2)%self.side_count
return self.offsets[back_offset]

class CellMaze:
def __init__( self, side_x, side_y, cell_exits ):
self.side_x = side_x
self.side_y = side_y
self.cell_exits = cell_exits
self.cellArray = {}
def Cell( self, pos ):
if self.InBounds(pos):
return self.cellArray[pos]
return None
def __len__( self ):
return len( self.cellArray )
def Cells( self ):
for cell in self.cellArray.values():
yield cell
def InBounds( self, pos ):
return pos in self.cellArray
def RandomPosition( self, connected = True ):
while True:
rx = random.randrange( self.side_x )
ry = random.randrange( self.side_y )
rpos = (rx,ry)
cell = self.Cell( rpos )
if self.InBounds( rpos ) and ( cell.IsConnected() == connected ):
break
return rpos
def SetRandomDirection( self ):
rd = random.randrange( len(self.cell_exits) )
self.cell_exits.Set( rd )
def TryDirection( self, pos ):
offset = self.cell_exits.Offset()
newpos = ShiftPosition( pos, offset )
if self.InBounds( newpos ):
if not self.cellArray[newpos].IsConnected():
backoffset = self.cell_exits.BackOffset()
self.cellArray[pos].connection[ offset ] = newpos
self.cellArray[newpos].connection[ backoffset ] = pos
return newpos
return None
def PickNeighbour( self, pos ):
self.SetRandomDirection()
for tries in range( len( self.cell_exits ) ):
newpos = self.TryDirection( pos )
if newpos:
return newpos
self.cell_exits.Next()
return None

def CreateRectangularMaze( side_x, side_y ):
offsets = [ (0,-1), (1,0), (0,1), (-1,0) ]
cell_exits = CellExits( offsets )
maze = CellMaze( side_x, side_y, cell_exits )
for y in range( side_y ):
for x in range( side_x ):
pos = (x,y)
maze.cellArray[pos] = Cell( pos )
return maze

def CreateMaze( side_x, side_y, ShapeGenerator ):
target_fill_percent = 80
maze = ShapeGenerator( side_x, side_y )
#pick random start cell
startpos = rpos = maze.RandomPosition( False )
connected = 1
done = False
while not(done):
newpos = maze.PickNeighbour( rpos )
if newpos:
rpos = newpos
connected += 1
else:
#see what percent filled
pcf = 100*connected/len(maze)
if pcf >= target_fill_percent:
done = True
else:
rpos = maze.RandomPosition( True )
return maze,startpos,rpos

class Rect:
def __init__( self, l, t, r = None, b = None ):
if r is None:
self.rect = ( l[0], l[1], t[0], t[1] )
else:
self.rect = ( l, t, r, b )
def MidPoint( self ):
( l, t, r, b ) = self.rect
return ( l + r )/2,( t + b )/2
def TopLeft( self ):
return self.rect[0],self.rect[1]
def BottomRight( self ):
return self.rect[2],self.rect[3]

class GameBoard:
BORDER = 10
LINE_HEIGHT = 30
CELL_SIZE = 50
CELL_BORDER = 5
STATUS_LINES = 3
def __init__( self, cellx, celly ):
self.master = Tk()
grid_w = cellx*self.CELL_SIZE
grid_h = celly*self.CELL_SIZE
width = 2*self.BORDER+grid_w
status_start = 2*self.BORDER+grid_h
status_height = self.STATUS_LINES*self.LINE_HEIGHT
#
self.grid_area = Rect(self.BORDER,self.BORDER,self.BORDER+grid_w,self.BORDER+grid_h)
self.status_area = Rect(self.BORDER,status_start,self.BORDER+grid_w,status_start+status_height)
self.canvas = Canvas( self.master, width=width,
height = self.BORDER+status_start+status_height )
self.canvas.pack()
def Run( self ):
self.master.mainloop()
def StatusText( self, line, text ):
xy = ShiftPosition( self.status_area.TopLeft(), (0,line*self.LINE_HEIGHT) )
self.canvas.create_text( xy, text = text, anchor = W )
def DrawConnections( self, cell, rect ):
start = rect.MidPoint()
#draw connections
for direction in cell.connection:
end = ShiftPosition( start, direction, self.CELL_SIZE )
self.canvas.create_line( start, end, width = 5 )
def DrawCellLabels( self, cell, text, rect ):
if cell.IsConnected():
start = ShiftPosition( rect.TopLeft(), (1,1), self.CELL_BORDER )
end = ShiftPosition( rect.BottomRight(), (1,1), -self.CELL_BORDER )
self.canvas.create_rectangle( start, end, fill="yellow", outline="red" )
self.canvas.create_text( rect.MidPoint(), text=text )
def DrawCells( self, maze ):
origin = self.grid_area.TopLeft()
for cell in maze.Cells():
x,y = cell.pos
xy0 = ShiftPosition( origin, (x,y), self.CELL_SIZE )
xy1 = ShiftPosition( xy0, (1,1), self.CELL_SIZE )
self.canvas.create_rectangle( xy0, xy1 )
self.DrawConnections( cell, Rect(xy0, xy1) )
for cell in maze.Cells():
x,y = cell.pos
xy0 = ShiftPosition( origin, (x,y), self.CELL_SIZE )
xy1 = ShiftPosition( xy0, (1,1), self.CELL_SIZE )
self.DrawCellLabels( cell, str(cell.pos), Rect(xy0, xy1) )

#main program
def main():
random.seed()
cellsX = 10
cellsY = 10
maze,startpos,endpos = CreateMaze( cellsX, cellsY, CreateRectangularMaze )
g = GameBoard( cellsX, cellsY )
g.DrawCells( maze )
g.StatusText( 1, 'Start cell: ' + str(startpos) )
g.StatusText( 2, 'End cell: '+str(endpos) )
g.Run()

if __name__ == "__main__":
main()
``````
-
+1 a bit over-engineered indeed. –  James Khoury Aug 2 '12 at 2:44