Archive for August, 2007

Map generation and the Hill algorithm.

August 16, 2007

The last couple have weeks have seen me busy on a random map generator. This will, eventually, become a separate binary able to generate maps for Fortress. It will have support for a couple height-map algorithms, different landscape generation, and hopefully also beginner-castle generation. The ultimate plan is to have this part of a map editing suite which will ship along side Fortress. Here is a screen shot of a map generated using the Hill algorithm. The Hill algorithm is pretty simple one. It creates a whole bunch of semi-circles (hill) stacked on one another which ultimately will resemble a hilly landscape.

  • Pick a random spot on the map (rx,ry)
  • Pick a random radius size (radius)
  • For each pixel on the map (x,y)
  • Apply the following equation ignoring negative values:
    • height[rx][ry] += radius^2 + ((x-rx)^2 – (y-ry)^2)
  • Rinse, Lather and repeat about 1000 times.

When this is all done, we normalize the data to bring it all between 0 and 1 and display it. In the case of the following screen shot I have chosen to display the heights using a color gradient from black (0,0,0) to white (1,1,1) where the darker colors are the peaks of the hills.

MapGenerator screenshot

Currently this takes rather long to render, since every time a new hill is added the ENTIRE grid is recalculated. One fix I must add soon is that only the affected pixels, basically, the pixels in a circle of size (2radius+2)*2) around center point (rx,ry) are analyzed each time a new hill is added. Anyway, this code is all in SVN, and new features will be added continuously.

On a final note, a birdy told me that Charlie is working his magic in the background, and the forums are showing signs of some new graphics and other tasty ideas. We are always looking for new contributors, so feel free to swing by and say hi.