Dungeon Generation in Diablo 1

Diablo 1 is a classic 1996 hack and slash rogue-like. It was one of the first popular attempts at bringing roguelikes to the masses, from the niche ascii art. It’s spun a host of sequels, and imitators. It’s known for a dark, moody atmosphere that intensifies as the player descends into the dungeon beneath the town of Tristram. It was one of the first games I played with procedurally generated maps, and it blew me away that generating such convincing areas was even possible.

I recently discovered that thanks to the discovery of various debug symbol files accidentally left lying around, several fans took it upon themselves to reverse-engineer the source code and clean it up into a good guess at what the original game is like. Thus began a week long deep dive into how exactly did lead developer, David Brevik, actually craft these levels. It may have taken away some of the magic of the game, but I learnt lots of techniques I think are applicable to anyone developing a similar game, which I share with you below.

Continue reading

Blue Noise Particles

I’ve released a plugin generates a random arrangement of particles with a blue noise distribution. This is also known as Poisson Disk Sampling.

Shows blue noise distributed particles in comparison to other options

This distribution of particles guarantees no two particles are very near each other. It’s often considered a higher quality particle arrangement than Blender’s default uniform sampling. It’s particularly useful for organic arrangements, and randomly arranging meshes without collisions.

Axaxaxas


I’ve released a Python based string parser on GitHub. This was part of a much more ambitious project that fell through, but I extracted the good part.

Axaxaxas is a Python 3.3 implementation of an Earley Parser. Earley parsers are a robust parser that can recognize any context-free grammar, with good support for amiguous grammars. They have linear performance for a wide class of grammars, and worst case O(n^3).

The main goals of this implementation are ease of use, customization, and requiring no pre-processing step for the grammar. You may find the Marpa project better suits high performance needs.

Documentation can be found at: http://axaxaxas.readthedocs.org

Celtic Knots

I’ve created a Blender plugin generates 3d beziers curves in elaborate “celtic” style knotwork, based off of a framework mesh. Tested with Blender 2.68a. It’s available on github.

Celtic Knots are a intricate decorative design found in Celtic and other cultures mosaics and manuscripts. The knots often include elaborate variations and unusual angles that the plugin does not attempt to create, so touching up the resulting path in blender may be necessary for some designs.

Refer to the tutorial for some instructions on how to use the plugin, and the gallery for some examples of what is possible.

Tileset Roundup

Following my development of Resynth Tileset, I’ve been doing some thinking on the nature of tilesets, and the possible ways to auto tile them – that is, to paint tiles as is with a brush and letting the computer do the tile selection. Let’s review a few possible ways of doing so.

Just to be clear, I’m only interested at the moment in square, non-rotatable tiles. Rotation is another discussion, but excludes the more interesting tilesets. Adding alternative tiles is also not considered, though it is pretty easy to add in.

Continue reading