Lets try plugging this into this...

My last two assignments (Java, Web coding) were very straightforward and boring, so I've decided to make my life interesting by using a combination of Oracle 10g Express, CLSQL, and Gentoo Linux for my database assignment. Neither officially supports any of the others, but they should fit together. Let's see...

Lisp software renderer

My pet Lisp project has been languishing on my laptop recently; I've had a fiddle with the Linux Framebuffer Device interface, and it's occured to me I might more usefully bind to that than the PTC library. Potentially it could be a non X based graphical backend to the McCLIM. Someone is already working on an Open GL backend and that code could map over quite nicely...the fonts would be some kind of awful hack, though...

Bitmap Fonts, Java, Wingdings and Unicode

After my brush with the script-fu I thought I'd go back to basics and do the bitmap font creator as a Java app. I have whipped up this app for knocking up old school bitmap fonts. The gradient fills haven't really surrvived Pay attention to the picture, as it shows at what code points to find the Wingdings glyphs in the Unicode set. It's not 0..255, as has puzzled many Java coders before!

Bitmap fonts and the script-fu.

Despite my rant against script-fu, it must be acknowlgeded it's highly useful for getting game art knocked out in double quick time for example, bitmap fonts. Here's a script that can knock one up in a jiffy - it's just a sligtly modified version of a standard script. I'm somewhat dismayed by the size of the .png file.

Script-fu

Today I delved into the realm of Gimp, SIOD, Script-fu; and let me tell you it's the least productive environment I've hit since the ZX81. I mean (set! variable value) is your assignment operator, so like a good lisp monkey I try (set! (aref string 1) "A"). Does that work? No. You use something called (aset string 1 65) why doesn't it have a bang, eh?

So, I want to create an array. Now I created a list with make-list, so, of course, I want to use make-array. No? Gotcha again! It's cons-array. Arrgh!

Add that to the fact that pressing the escape key closes the script-fu console window; which is something I do quite a lot, as it's hardwired into me that Escape means "clear the input" and that the documentation is just a scrappy list of functions that makes it hard to find what you need, that's a recipie for a very frustrating morning. The tragedy is that this is going to be some peoples first exposure to a lisp-like language..it could be so much better; the scintilla component could have been embedded in, there could be a much better tutorial and reference; but I guess someone would have to be paid for that..

Sony are in so much trouble..

This story just runs and runs. Not only do Sony release a rootkit that installs itself onto Windows PC's without telling people, and get discovered, it turns out that the rootkit is a GPL violation! This one is going to run and run...are Sony trying to replace Microsoft as the Evil Empire? They seem to be taking a pretty good shot at it!

Package du Jour: Dia

I've been playing with Dia and been moderately impressed with what I've found. I've been using it as part of my course; being able to export to .pngs is good. It's happy with a wide range of diagrams: mostly I am using it for entity relationship diagrams and UML. There's even a uml to code generator for it which I intend to try using for my Java assignment. While I can't say it's as good as Visio (when did that become part of Microsoft Office), it's a cheap way for students to explore UML and "good enough" for most small projects, and it has an interesting quirky diagram set: isometric game tiles - houses, railways, fields - which can be used to layout a small toy town. It might even be a game prototyping tool one day; with the right tileset..

Change of Direction

It might seem strange to some people that I have recently left Reflections and decided to enroll on a Masters degree course; it's a strange thing to do at 38 years of age. Even stranger, the Masters course is not strictly games-oriented. Well it's not as big a jump into the unknown as it looks: many of the new mobile platforms use Java, databases are increasingly important - both as repositories for the huge number of assets used in game development, and for the backend of MMPORG's as well as their more humble play-by-web cousins.

The web itself is probably the most interesting platform around today: it's a mass medium based on a mishmash of standards and technologies that can be bent to do almost everything; a giant laboratory free from the restrictions of proprietary console platform development.

I'm beginning to suspect a much better (as in scalable, among other things) platform for games development can be assembled out of some of the emergent technologies available now; a distributed, social system capable of handling vast amounts of assets, and large numbers of distributed collaborators. It's my intention to try and assemble a platform capable of this, and offer it as a model for further research.

It's also my intention to learn as much as possible in a short time whithout my brain exploding; as this is the most challenging course my local university has to offer, that might be hard. Still, onwards...

More newbie thoughts on Lisp

It's become obvious with the code I've been writing recently that Lisp's strength and weaknesses are all tied to it's lack of syntax. The fact it has very little in the way of syntax leads to a combinatorial explosion - there are an almost infinite number of ways to do simple things: it makes me wonder if the whole purpose of strong syntax in languages isn't simply to prevent this, and guide the energies of programmers into productive channels. It certainly was the case in C and Fortran where syntax was carefully constructed to enable mapping high level language to machine instructions a straightforward transformation.

However the lack of syntax has to be an achilles heel: the huge number of idioms that could be applied to simple programs means no two coders are going to write anything neccesarily similar. I'm assming the full set of coders of all levels of competence here. I expect a smaller set of seasoned coders would converge on similar solutions given similar problems. Which makes it a devastating weapon in the hands of a sesoned coder, but probably in a team of mixed abilities it would lead to much higher communication oveheads.

Project Madness

I simply have to back off, I'm trying to do too many bloody things at once.

Here's my long list

Get deeply enought into web/database tech to get a small play-by-web game running.

Update the Omega rougelike game for the SDL & modern multiplatform code.

Update Blah, a roguelike skeleton that fell off the net many moons ago, with SDL graphics and Lua scripting.

Finish the LISP software renderer.

Create a tool for parsing C into sexp's with an eye to auto-generating UFFI or CFFI bindings.

Some unspecified Java app, just to keep my hand in : possibly a Blogger to Live-Journal migration tool.

Some more games that have been bubbling under the radar for what seems like years.

Lunch with Laura - a graphic novel. Nothing to do with coding, but it competes for time.

Clearly, something has to give, somewhere..

XEmacs Wins

Mostly because you can configure it seven hundred ways to Sunday, and after lots of fiddling I arrived at an init.el I kind of liked. It has room for improvement. It probably shouldn't rely on cscope for tagging, becasue that's platform specific. It probably should fall back on plain old tags. Onwards to do some actual coding then: programmers are the only people who can get so preoccupied with sharpening an axe they forget about the damn tree.

Grand Text Editor

I find myself prevaricating between editors. I know I have to pick one and stick to it, but I can't make up my mind which. I've narrowed it down to a few promising candidates, all cross-platform.

Emacs.

XEmacs is pretty much *the* editor if I want to code in Lisp, as it has Slime, one of the most interactive and potentially productive programming environments I've ever seen. The Emacs Code Browser gives me IDE-like organisation and navigation. It integrates nicely with gdb and the shell. The con side is that the tagging is poor, and requiring more than three keystrokes to do anything useful makes it difficult and "slow;" feeling to work with. It's so configurable it's difficult to zero in on a single working style with it. The learning curve seems endless.

Gvim.

Vi - Improved. Another editing heavyweight, and the keystrokes are both brief and seared into my brain as I've been exposed to it on and off throughout my career. Frankly, if it wasn't for the amount of Lisp I do, it'd be my editor of choice. It doesn't have anything like ECB - but it does have sessions - a collection of settings that can be quickly saved and restarted. Which is fine for keeping track of different projects. It also as a huge collection of scripts and customisations, like Emacs..The keyword completion is wicked, but it's not context sensitive like Intellisence.

JEdit.

JEdit is another contender. It handles sessions and tags pretty much as well as Vi and XEmacs do. It's set of plugins are not as comprehensive as vim or XEmacs, but there's enough for the job. It's main benefit is a more modern gui and a slicker feel. Comfort is an important factor. The plugins are very Java-centric, and I suspect this editor would be a powerhouse for a Java coder, but I'm not so sure about how it would pan out for a C++/Lisp coder.

Visual Slick Edit.

The only commercial editor of the bunch, and the slickest. It intelligently does completion of structure and class members, parameter lists, and does incremental tagging in the background: as a result I'm more productive when coding in C/C++ with this editor. It gave me a real competitive advantage over my Visual Studio bound colleagues back in the days of Visual Studio 6. Although they have since caguht up. It can handle Python and there is a script for Lisp support on the website, which I haven't tried.Lack of Lisp is a major minus, otherwise this would ne a no-brainer. Although, perhaps I could use this in conjunction with the LispWorks IDE.

So which one do I pick? They all have something I want, and they all miss something else. Can anyone spot anything I've missed? Some plugin or mode that would give one an advantage over the other? Shorter XEmacs keystrokes? Intellisense for vim or JEdit? A good Lisp mode for Visual Slick Edit?

Goodbye Slackware

One of the first things I've done with my newfound freedom since leaving Reflections is to review all my Linux installs. For a long time I've been soldiering on with the redoubtable Slackware. However, I resolved to give Debian a try, and frankly I'm amazed by what I've seen. Compared to Slackware install was fast, friendly and trouble-free: network, video, and sound were all auto-detected, and the graphical login came up first time.

Gnome is gorgeous, too, all point and click and "just works". Even this post came straight from the desktop blogging tool, rather than via Firefox.

Every time I revisit a mainstream distro, I'm amazed by the progress. Frankly, if something like this came pre-installed, damn few people would touch a Windows PC. Mind you, Steve Jobs has probably recently come to the same conclusion, so there maybe hope, yet...meanwhile, it's back to my Lisp rendering follies, I guess.

Lisp, the language that does your coding for you..

Well, not quite - but almost. After reading Rogue Malcontents nifty post where he uses macros to wrap simple-arrays with structure - like syntax (very handy for interacting with APIs like OpenGL), I went back and looked at my code with a fresh eye. I found I was writing lots of forms like this :-

(red (get-red p0) (funcall red-interpolator))
(blue (get-blue p0) (funcall blue-interpolator))
(green (get-green p0) (funcall green-interpolator))
(alpha (get-alpha p0) (funcall alpha-interpolator))

..where the same form was wrapped around each colour channel of a pixel. So I thought "Hmm, time for a macro". My first attempt was something like this:

(defmacro with-pixel-colour-list (body)
  (list 
     `list 
   (replace-symbol 'get-pixel 'get-red body)
   (replace-symbol 'get-pixel 'get-blue body)
   (replace-symbol 'get-pixel 'get-green body)
   (replace-symbol 'get-pixel 'get-alpha body)))

Where replace-symbol was a utility function of my own devising which car'd its way through a form, replacing a matching symbol as it went - given here for completeness. So the form fed to with-pixel-colour list gets replicated four times - the first time with the get-pixel call replaced with a get-red call, the second time get-pixel replaced by a get-green call, and so forth. So I only have to write one form once, rathte than four times, and the compiler does the rest of the work for me, macro-expanding the code before compiling it.

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defun replace-symbol (sym1 sym2 list)
 (cond 
   ((null list)
    nil)
   ((null (car list))
    (replace-symbol sym1 sym2 (cdr list)))
   ((symbolp (car list)) 
    (if (string= (symbol-name sym1) (symbol-name (car list)))
     (cons sym2 (replace-symbol sym1 sym2 (cdr list)))
     (cons (car list) (replace-symbol sym1 sym2 (cdr list)))))
   ((listp (car list))
    (cons (replace-symbol sym1 sym2 (car list))
    (replace-symbol sym1 sym2 (cdr list))))
   (t (cons
    (car list)
    (replace-symbol sym1 sym2 (cdr list)))))))

So, (with-pixel-colours *my-pixel*) expands nicely to (LIST (GET-RED *MY-PIXEL*) (GET-BLUE *MY-PIXEL*) (GET-GREEN *MY-PIXEL*) (GET-ALPHA *MY-PIXEL*)) and I can write things like:

(defun sum-colours (pixel)
  (apply #'+ (with-pixel-colours (get-pixel pixel))))

(setf *my-pixel* (make-pixel 1 1 1 0))

(sum-colours *my-pixel*)

3

Fantastic - but there has to be a wider application than this - so my next task was to generalise it a bit. More in the next post. :)

I do get the feeling I'm re-inventing a well known technique, as I'm a newbie, and this kind of thing is just too useful. Any experienced Lisp coders care to comment?

Ion Drive

I've never found a window manager I've been 100% happy with - KDE and Gnome are far to slow to live on my old P600 Laptop, Afterstep, while asethetically pleasing, had too many menus, too many different feels and options and and I never could settle on a consistent set. Ratpoison was my most recent discovery, and while I liked it for it's simplicity, it was a bit too simple - it handled modal dialogs like mozillas download manager dialog badly - putting them in a whole window. At last I've discovered Ion - a tad more sophisticated than Ratpoison, but not much, so it still responds instantly on a clapped out laptop. It just handles dialogs much better, and works on the same principe - you should be able to treat your window manager in exactly the same way as you treat your text editor window - by having multiple windows and frames you can split, delete, create, and traverse between via simple keystrokes. If you dislike mice, it's worth giving it a try..

The only problem is -- there will never be a Windows version. It'd be interesting to see what a Mac user would make of it, though..

And now colour it in..

Added coloured tris to my renderer yesterday - it's coming along nicely. Started out as a "learn lisp" exercise, but now it's taking on a life of it's own.

Dynamic game difficulty adjustment.

Some thoughts after reading The Psychology Behind Games by Anders Hejdenberg.

Should a game adjust it's difficulty level based on the players observed ability in the game? Possibly, but it's an artificial device. Response to changes in the players ability should probably err on the cautious side when making the game easy and on the converse side when making the game harder. It's important to have player profiles, too. Visual feedback of the current setting and a manual override would be nice, too. Some people don't want things to be too easy and for the game to "surrender", but other people would use such a mechanism to cheat, or just plain want to go through the game quickly.

Feedback and control are the watchwords, as ever.

Brand new Baby Bouncing Triangle

At last cl-ptc (the Lisp software renderer) plots a nice, clean triangle, after weeks of fiddling around with interpolator functions, it's a relief. It's my first ever time as a lisp, so I'm proud to present my first ever bit of Lisp porn..

Lisp gets it right

After playing with lots of different methods of linearly interpolating the edges of triangles (well, 3 - DDA, MAI, & Bressenham) in Lisp, I settled for the straight add the gradient to the minor axis. Madness, I hear you say - not really, because Lisp doesn't represent the result of integer division as a float, but as a pair of integers that represent a ratio, so even doing it this way means I can reserve the FPU for perspective - correct texture mapping the way Intel intended. Obviously, the representation of this ratio is implementation dependent, but I'd really hope that in an implemenation with 32 bit fixnums, the ratio is expressed as a 64 bit fixed point integer..of course it's also probably possible to get LISP to use 16 bit integers for coordinates and 32 bit integers for the ratios, but I haven't got that far into the type sysetem, yet.

Lisp Software Renderer, Redux

Of course, it's impossible to leave a challenge I got so close to completing, and so I dust off the Lisp software renderer and return to the fray. I've had to grapple a bit with ASDF and learnt the hard way why upper case file names and lower case package names don't mix. Also, trying to write a tail-recursive Bressenham was interesting..only a few more bugs to wrinkle out and it can hit common-lisp.net.

Then I can go onto the freenode #lisp channel and get a critique, I hope. 123 notes at an (optimize (speed 3)) sounds like there's still a lot of work ahead..

CL-Ncurses

I was playing with this at the weekend. And it's a nice solution for whipping up testbeds for simulations that can get away with a simple text interface. The trouble is it needs a bit of work, and the maintainer has dissapeared...

I'd really like to submit a patch but there doesn't seem to be any point. I wish there was some kind of policy on common-lisp.net for dealing with such orphaned projects. The same as with sourceforge, I guess.

LISP Software Renderer RIP

I gave up on my quest to write a software renderer in Lisp - I got as far as creating nice antialiased clipped lines, but was driven to the conclusion that the only sane language for such a beast is assembler...even C doesn't get quite close enough to the metal without generous helpings of inline assembler - which kind of misses the point..

I did discover that a LISP compiler with a decent static type system, vectorisation, SSE/SIMD support, and inline assembler could do just about as good a job as C. Trouble is, there's no LISP system like that in existence. There's at least two good open source Lisps that could be persuaded to do it, though..

Debug versus Release builds

This applies to fairly strongly and/or statically typed languages only, obviously:

The way I think of it, the difference between release and debug is the difference between trying to fly a plane with no instruments at all, and a possibly dodgy engine that won't neccessarily give you any warning that it's about to burn, versus a nice modern jet with thoroughly checked over engines and wiring, a full array of instrumentation and autopilots for everything you could possibly need.

Now - it's your backside in the plane - which do you want to fly?

Visual Studio and Standard Environments.

Just what is it that people see in it? Working with it as an editor is like swimming through treacle. Without the Visual Assist plugin it's auto completion is limited and without lengthy compile times, it can't manage to tag a project well. You can only really edit three languages with it, and use only the hand full of source code control systems that implement a Microsoft API. It's scripting facilities are ripe for viral attack, and poor tools for automation.

The wizards to help programmers who don't know how to do basic things ignore their ignorance, though. I'm just a little pissed off about this "standard environment" that' s been imposed on everybody at work. The a component of the last "standard environment" was the slowest and most broken source control system I've ever worked with.

When carrying 500kilo weights is the standard environment for the Olympic High Jump, then all this will make sense. I think. Standard environments might be great for managers as they reduce programmers to the lowest common interchangable denominaters, but for programmers looking for an edge and a chance to develop great software, they are a positive handicap.

Somewhere there is a cutoff point where staying within the standard environment becomes ultimately more punishing than the leap forward out of it. I just hope I can recognise that point.

Progress with Lisp

So far my initial enthusiasm for LISP is wearing off a bit. I can see it's practical potential, but the main upshot of my learning it, so far is that I've switched to Emacs from Vi.

Perhaps my problem is that I'm just put off by the constant fiddling needed with free Linux implementations and the unavailabilty of a good free as in beer Win32 implementation. I miss the ease of integration with a lot of useful libraries I'm used to working with in both Python & C++, as well as all the new idioms I have to absorb.

I can see the language can do things that Python only vaguely aspires to, though. I'm just not sure that in the cases when I don't need the extra grunt of Lisp that I'll be able to prototype as rapidly as I could in Python.

More Fun With Dungeon Generation

Much improved. Doesn't guarantee interconnection, though,

############               ####       ## ###  ##################

############               ####        # ##   ##################

                          ####                   ##############

### ##                 #   ####        #          ##############

### ########           #   #######  #             ##############

   ########          ##  ######                  ##############

############# #          ####      ###           ##############

  ########### #      #   ####          ##        ##############

# ###########    # ###   ################        ##############

#                #       ################        ##############

#  #########     #####   ######################################

   #########     ##      ######################################

#   #########    ##  #  ########################################

#   ###########  ## ##       ###################################

# # ###########          ### ###################################

    ##########     ######## ###################################

####  ###################### ###################################

##### ###################### ###################################

##### ###################### ###################################

##### ###################### ###################################

     ###################### ###################################

# ########################## ###################################

# #####################      ###################################

# #####################    #####################################

# ######################## #####################################

# #####      ############# #####################################

# #####      ####            ###################################

# #####      #### # ######## ###################################

#                            ###################################

            ####     ##########################################

            ######## #                   ######################

# #### #### #########   ################# ######################

      #### ############################# ######################

#           ######    ################### ######################

# ################ ## ################### ######################

 ################ ## ################### ######################

################# ## ################### ######################

   ############## ## ################### ######################

### ##############    ###################   ####################

### ################  ##################### ####################

### ################  ##################### ####################

### ################  ##################### ####################

### ################  ####  ############### ####################

### ################  ####  ############### ####################

### ################  ##    ############### ####################

### #################    ## #########       ####################

### ################# ##### ######### ##########################

### #################           ##### ##########################

### ###################### ###    ### ##########################

### ###################### ###    ### ##########################

#   ###################### ###        ##########################

 ######################## ###              ####################

    ##################### ### ############ #######  ###########

 ## ##################### ### ############          ###########

#  # ##################### ### ############    ## ##  ##########

## # #####################     ############ ## ## ### ##########

##   #####################  ############### ## ## ### ##########

################                ########### ## ## ### ##########

#########    ### #######        ########### ## #      ##########

#########    ### #######        ########### ##    ##  ##########

#########    #   #######        ########### ##    ##    ########

#########       ##########  #  ##########         ## ## ########

#########    ##             #  ##########  ######    ## ########

#########    ## #############  #################################

import Numeric

import whrandom

import math



class Burrower:

   def __init__(self, x, y, lifetime = 0, dx = 0, dy = 0):

       self.data = [ x, y, lifetime, dx, dy ]





   def burrower_is_dead(self):

       return self.data[2] == -1



   def kill_burrower(self):

       self.data[2] = -1



   def tick_burrower(self,b):

       self.data[2] = self.data[2] + 1



   def pick_random_motion(self, allow_diagonals):

       motion = whrandom.randrange(0,3)

       if motion == 0:

           dx =    - 1

           dy = self.data[4]

           if not allow_diagonals:

               dy = 0

       elif motion == 1:

           dx = 1

           if not allow_diagonals:

              dy = 0

       elif motion == 2:

           dy = -1

           if not allow_diagonals:

               dx = 0

       elif motion == 3:

           dy = 1

           if not allow_diagonals:

               dx = 0

       # don't double back on yourself

       if dx == -self.data[3] and dy == self.data[4]:

           dy = dx

           dx = self.data[4]

       if dy == -self.data[4] and dx == self.data[3]:

           dx = dy

           dy = self.data[3]

       self.data[3] = dx

       self.data[4] = dy



   def clip_burrower(self, minx, miny, maxx, maxy):

       if self.data[0] < minx:

           self.data[0] = minx

       if self.data[0] > maxx:

           self.data[0] = maxx

       if self.data[1] < miny:

           self.data[1] = miny

       if self.data[1] > maxy:

           self.data[1] = miny



   def un_move_burrower(self, minx, miny, maxx, maxy, allow_diagonals):

       self.data[0] = self.data[0] - self.data[3]

       self.data[1] = self.data[1] - self.data[4]

       self.clip_burrower(minx, miny, maxx, maxy)

       self.pick_random_motion(allow_diagonals)



   # move the burrower one cell, carving as you go along

   # to do  rather than randomly pick a direction, randomly *change* a direction (more control of twistiness, etc)

   def move_burrower(self, minx, miny, maxx, maxy, changeprob, allow_diagonals):

       if whrandom.random() < changeprob:

           self.pick_random_motion(allow_diagonals)

       # am i dead ? if so I should be concenrating on a nice firm rigor mortis

       if self.burrower_is_dead():

           return

       self.data[0] = self.data[0] + self.data[3]

       self.data[1] = self.data[1] + self.data[4]

       if self.data[0] < minx:

           self.data[0] = 0

           self.data[3] = 1

       if self.data[1] < miny:

           self.data[1] = 0

           self.data[4] = 1

       if self.data[0] > maxx:

           self.data[0] = maxx

           self.data[3] = -1

       if self.data[1] > maxy:

           self.data[1] = maxy

           self.data[4] = -1

       return



class Dungeon:

   TileIdNumber = { "granite" : 0 , "room" : 1, "corridor" : 2 }



   def __init__(self,  width, depth):

       self.tiles = Numeric.zeros((width, depth))

       self.width = width

       self.depth = depth

       self.room_centres = [ ]



   def room_too_close(self, x, y, min_room_distance):

       for r in self.room_centres:

           dx = r[0] - x

           dy = r[1] - y

           dist = math.sqrt(x * x + y * y)

           if (dist < min_room_distance):

               return True

       return False



   def burrower_room_create(self, b, broom_prob, max_room_width, max_room_depth, min_room_distance, burrower_index):

       # we have a room

       if whrandom.random() > broom_prob:

           return 0

       room_width = whrandom.randrange(max_room_width / 2) + 1

       room_depth = whrandom.randrange(max_room_depth / 2) + 1

       if self.room_too_close(b.data[0], b.data[1], min_room_distance):

           return 0

       self.room_centres.append((b.data[0], b.data[1]))

       for x in range (b.data[0] - room_width, b.data[0] + room_width):

           for y in range (b.data[1] - room_depth, b.data[1] + room_depth):

               if (x >= 0) and (x < self.width) and (y >= 0) and (y < self.depth):

                   self.tiles[x][y] = burrower_index

       return 1



   def burrower_birth(self,bbirth_prob):

       return whrandom.random() < bbirth_prob



   def baby_burrower(self, b):

       return Burrower(b.data[0] + whrandom.randrange(2), b.data[1] + whrandom.randrange(2), 0, 0, 0)



   def print_dungeon(self):

       for y in range(0,self.depth):

           s = ""

           for x in range(0,self.width):

               if self.tiles[x][y] == Dungeon.TileIdNumber["granite"]:

                   s = s + "#"

               else:

                   s = s + " "

           print s

   #

   # burrowers start on one side of the level, on each turn they can either split (birth prob),

   # create a room (die), have a max lifetime, and the algo terminates when room_count is reached

   #

   def generate(self, burrower_total, room_total, birth_prob, turn_prob, room_prob, lifetime, max_room_width, max_room_depth, min_room_distance, allow_diagonals):

       # set up burrowers

       burrowers = []

       for i in range(0,burrower_total):

           side = whrandom.randrange(0,4)

           if side == 0:

               burrower = Burrower( 0, whrandom.randrange(0, self.depth) , 0, 1, 0 )

           elif side == 1:

               burrower = Burrower( self.width-1, whrandom.randrange(0, self.depth) , -1, 0, 0 )

           elif side == 2:

               burrower = Burrower( whrandom.randrange(0,self.width), 0, 0, 0, 1 )

           else:

               burrower = Burrower( whrandom.randrange(0,self.width), self.depth-1 , 0, 0, -1 )

           burrowers.append(burrower)

       room_count = 0

       burrower_alive = True

       i = 0

       while burrower_alive:

           print "Generation " , i

           print "Rooms # ", room_count

           print "Burrowers ", len(burrowers)

           self.print_dungeon()

           print

           burrower_alive = False

           birth_list = []

           burrower_index = 1

           for b in burrowers:

               if not b.burrower_is_dead():

                   burrower_alive = True

                   b.move_burrower(0, 0, self.width-1, self.depth-1, turn_prob, allow_diagonals)

                   # if the burrower reaches another corridor, kill it

                   burrower_tile = self.tiles[b.data[0]][b.data[1]]

                   if (burrower_tile != Dungeon.TileIdNumber["granite"]) and (burrower_tile != burrower_index):

                       b.un_move_burrower(0,0, self.width-1, self.depth-1, allow_diagonals)

                       b.data[2] = b.data[2] + 1

                       if b.data[2] > lifetime:

                           b.kill_burrower()

                   self.tiles[b.data[0]][b.data[1]] = burrower_index

                   if self.burrower_birth(birth_prob):

                       birth_list.append(self.baby_burrower(b))

                   room_count = room_count + self.burrower_room_create(b, room_prob, max_room_width, max_room_depth, min_room_distance, burrower_index)

               burrower_index = burrower_index + 1

           if birth_list:

               burrowers.extend(birth_list)

           if room_count >= room_total:

               birth_prob = 0.0

               room_prob = 0.0

           i = i + 1

       return



if __name__=="__main__":

   dungeon = Dungeon(64,64)

   dungeon.generate(16, # burrower total

                    12, # room total

                    0.009, # birth probability

                    0.25, # turn probability

                    0.03, # room probability

                    2, # lifetime (max non self - hits allowwd)

                    9,  # max_room_depth

                    9, # max room width

                    6, # min room distance

                    False)

Fun With Dungeon Generation

One of the more preinnal topics of roguelike game design, or general dungeon cralws is "How do I generate that funky dungeon procedurally?". There's an unbelievable number of algorithms, but this one is my favourite...

import Numeric

import whrandom



class Burrower:

   def __init__(self, x, y, lifetime = 0, dx = 0, dy = 0):

       self.data = [ x, y, lifetime, dx, dy ]



   def burrower_is_dead(self):

       return self.data[2] == -1



   def kill_burrower(self):

       self.data[2] = -1



   def tick_burrower(self,b):

       self.data[2] = self.data[2] + 1



   def pick_random_motion(self, allow_diagonals):

       motion = whrandom.randrange(0,3)

       if motion == 0:

           self.data[3] =  - 1

           if not allow_diagonals:

               self.data[4] = 0

       elif motion == 1:

           self.data[3] = 1

           if not allow_diagonals:

               self.data[4] = 0

       elif motion == 2:

           self.data[4] = -1

           if not allow_diagonals:

               self.data[3] = 0

       elif motion == 3:

           if not allow_diagonals:

               self.data[3] = 0

           self.data[4] = 1





   # move the burrower one cell, carving as you go along

   # to do  rather than randomly pick a direction, randomly *change* a direction (more control of twistiness, etc)

   def move_burrower(self, minx, miny, maxx, maxy, changeprob, allow_diagonals):

       if whrandom.random() < changeprob:

           self.pick_random_motion(allow_diagonals)

       # am i dead ? if so I should be concenrating on a nice firm rigor mortis

       if self.burrower_is_dead():

           return

       self.data[0] = self.data[0] + self.data[3]

       self.data[1] = self.data[1] + self.data[4]

       if self.data[0] < minx:

           self.data[0] = 0

           self.data[3] = 1

       if self.data[1] < miny:

           self.data[1] = 0

           self.data[4] = 1

       if self.data[0] > maxx:

           self.data[0] = maxx

           self.data[3] = -1

       if self.data[1] > maxy:

           self.data[1] = maxy

           self.data[4] = -1

       # up lifetime count

       self.data[2] = self.data[2] + 1

       return



class Dungeon:

   TileIdNumber = { "granite" : 0 , "empty" : 1, "corridor" : 2 }



   def __init__(self,  width, depth):

       self.tiles = Numeric.zeros((width, depth))

       self.width = width

       self.depth = depth







   # die, maybe, if lifetime expired, die with a whimper,

   # else die with a bang and create a room

   # returns count of rooms created so we can track them

   # to do : probability of generating "special" rooms?

   #

   def burrower_death(self, b, bdeath_prob, lifetime, max_room_width, max_room_depth):

       result = 0

       # if out of time, just die quietly

       if b.data[2] > lifetime:

           b.kill_burrower()

       # if random chance of death turns up, burst into a room

       if whrandom.random() < bdeath_prob:

           # we have a room

           room_width = whrandom.randrange(max_room_width / 2) + 1

           room_depth = whrandom.randrange(max_room_depth / 2) + 1

           for x in range (b.data[0] - room_width, b.data[0] + room_width):

               for y in range (b.data[1] - room_depth, b.data[1] + room_depth):

                   if (x >= 1) and (x < self.width-1) and (y >= 1) and (y < self.depth-1):

                       self.tiles[x][y] = Dungeon.TileIdNumber["empty"]

#           b.kill_burrower()

           result = 1

       return result



   def burrower_birth(self,bbirth_prob):

       return whrandom.random() < bbirth_prob



   def baby_burrower(self, b):

       return Burrower(b.data[0] + whrandom.randrange(2), b.data[1] + whrandom.randrange(2), 0, 0, 0)



   def print_dungeon(self):

       for y in range(0,self.depth):

           s = ""

           for x in range(0,self.width):

               if self.tiles[x][y] == Dungeon.TileIdNumber["granite"]:

                   s = s + "#"

               else:

                   s = s + " "

           print s

   #

   # burrowers start on one side of the level, on each turn they can either split (birth prob),

   # create a room (die), have a max lifetime, and the algo terminates when room_count is reached

   #

   def generate(self, burrower_total, room_total, birth_prob, death_prob, turn_prob, lifetime, max_room_width, max_room_depth, allow_diagonals):

       # set up burrowers

       burrowers = []

       for i in range(0,burrower_total):

           side = whrandom.randrange(0,4)

           if side == 0:

               burrower = Burrower( 0, whrandom.randrange(0, self.depth) , 0, 1, 0 )

           elif side == 1:

               burrower = Burrower( self.width-1, whrandom.randrange(0, self.depth) , -1, 0, 0 )

           elif side == 2:

               burrower = Burrower( whrandom.randrange(0,self.width), 0, 0, 0, 1 )

           else:

               burrower = Burrower( whrandom.randrange(0,self.width), self.depth-1 , 0, 0, -1 )

           burrowers.append(burrower)

       room_count = 0

       burrower_alive = True

       i = 0

       while burrower_alive:

           print "Generation " , i

           print "Rooms # ", room_count

           self.print_dungeon()

           print

           burrower_alive = False

           birth_list = []

           for b in burrowers:

               if not b.burrower_is_dead():

                   burrower_alive = True

               b.move_burrower(0, 0, self.width-1, self.depth-1, turn_prob, allow_diagonals)

               if (self.tiles[b.data[0]][b.data[1]] == Dungeon.TileIdNumber["corridor"]):

                   b.kill_burrower()

               self.tiles[b.data[0]][b.data[1]] = Dungeon.TileIdNumber["corridor"]

               if self.burrower_birth(birth_prob):

                   birth_list.append(self.baby_burrower(b))

               room_count = room_count + self.burrower_death(b, death_prob, lifetime, max_room_width, max_room_depth)

           if birth_list:

               burrowers.extend(birth_list)

           if room_count == room_total:

               birth_prob = 0

               death_prob = 0

       return



if __name__=="__main__":

   dungeon = Dungeon(64,32)

   dungeon.generate(16, 32, 0.01, 0.005, 0.05, 1024, 16, 16, False)