Oct. 11, 2008

I've been re-visiting some code I wrote quite a while ago which generates a virtually infinite number of generic 2D RPG maps, with grass, sand, road, trees, and water, like this:

Perlin Noise based 2D RPG map

Here's the algorithm I have used, implemented in Python, using a Perlin Noise generator:

detail = abs(perlin.Noise2D(x / 300.0, y / 300.0))
desert1 = -perlin.Noise2D(x / 100.0, y / 100.0)
desert2 = perlin.Noise2D(x / 10.0, y / 10.0)
desertp = desert1 * detail + desert2 * (1.0 - detail)
waterp = perlin.Noise2D(x / 150.0, y / 150.0)
roadsp = (abs(perlin.Noise2D(x / 50.0, y / 50.0)))
treep = max(0, perlin.Noise2D(x / 300.0, y / 300.0)) + perlin.Noise2D(x / 3.0, y / 3.0)

oasis = desertp > 0.95
lake = desertp < -0.6
river = desert1 < 0.6 and abs(waterp) < 0.075
desert = desertp > 0.6 and desertp < 1.0 or desert1 > 0.8
roads = abs(roadsp) < 0.05
riversideRoads = desertp < 0.6 and abs(waterp) < 0.11 and abs(waterp > 0.08)
trees = treep > 1.15

if lake or river or oasis:
    DrawWater(x, y)
elif roads or riversideRoads:
    DrawRoad(x, y)
elif desert:
    DrawDesert(x, y)
elif trees:
    DrawGrass(x, y)
    DrawTrees(x, y)
else:
    DrawGrass(x, y)

One problem is that I couldn't find a decent perlin noise generator for Python that was easy to install, so I had to roll my own, and it's dog slow (apologies to any dogs who are reading this). I even tried re-implementing it as a Python extension in C but it was still only twice as fast. Psyco also did nothing to help the situation, which basically means it isn't slow because of bad optimisation but because the algorithm is very CPU intensive. The good news is that a few nights ago, while I couldn't sleep, I think I came up with a really quick way of generating random fractal based landscapes by caching the results of previous, higher order position lookups. If I'm right, it kind of turns the Perlin algorithm inside out to prevent redundant calculations. Of course, it will trade off speed for higher memory usage, but that's ok in this situation. I haven't tested my idea out yet, but hopefully I will get around to it and make my map algorithm much faster.

Another problem is that my existing maps won't wrap onto a torus without discontinuities, which means you have to have infinitely large maps for people to explore, which go on and on forever. I'd rather the maps wrapped so I could wrap them around planets and stuff. Fortunately, I think that with the judicious use of modulus operators my new algorithm should wrap pretty nicely.

Characters

I came up with these vector art characters which I think would be suitable for a 2D RPG style game.

Vector art RPG characters

They're SVGs made in Inkscape, which is highly scriptable, so I am thinking about prototyping a character creator screen which will allow you to deck them out in different colours, clothes, accessories, etcetera, and then use Inkscape to render variations in the background.