So I was thinking about some game concepts last week , stealing ideas from here and there etc. One thing I noticed tho , indie games with random maps really have an advantage over professional games with static content , especially when it comes to replay value of the game. Also random map generation is a must for sandbox games like Minecraft and Terraria right? Noone would like to play same sandbox game over and over again on same map ( unless it’s HUGE ie. Eve Online )
So I decided that I need a good random map generator more than everything else , if I have a good map generator , I can build any game on it right?!
After a little search , I found the awesome blog of Amit. I remember reading his A* algorithm articles a few years ago , but somehow I totally forgot about his blog after that. It seems he just posted a new little series about random map generation a few months ago ( September 2010 ) , based on Voronoi diagrams.
After reading his article and a little more about voronoi diagrams , I knew I had to do it myself so yea I have been working on it for a few days now. It’s extremely fun playing with Voronoi diagrams , shaping the land , rivers , mountains etc and create my own little island!
I’ll slowly blog about my process here , and the first step is obviously ;
So what is a Voronoi diagram?
Wikipedia says ;
In mathematics, a Voronoi diagram is a special kind of decomposition of a metric space determined by distances to a specified discrete set of objects in the space, e.g., by a discrete set of points.
Or we can simply say ; it divides an area based on a set of points. You take a field , then throw some points in it , then create zones around those points in a way that everywhere in that zone is closer to that point than any other. An image worths thousand words right?
Looks nice isn’t it? It’s a great diagram used for lots and lots of different stuff.
Now what we will do , is just throw in a few thousand dots , divide the area , then work on it as if it’s a grid. We’ll use areas to decided land type , edges to create rivers and coastline etc etc.
But since I’m more interested in creating a random map more than a basic Voronoi diagram , I decided to use a 3rd party Voronoi Diagram library to take care of that. But it turns out there isn’t many Voronoi implementations for .Net. The best I was able to find , is an implementation by BenDi , posted on CodeProject.
It’s doing a pretty good job , fast and reliable. The only problem I had , is that it only works on points and generated edges between them , there is no way to actually set area boundaries. I had to work it out myself , not a big problem but my temporary fix isn’t good enough so borders of the maps looks a bit silly. ( I’ll redo it later , I’m hardly bothered about the map borders at the moment , our island will be at the center anyway )
As I said I’ll blog more about this in future , and probably even post the project when I’m done with it.
My current process ;