Tag: Polygons

Map Generation, Land Allocation

      2 Comments on Map Generation, Land Allocation

Leaps and bounds! After yesterday’s breakthrough with the Voronoi polygon generation, I’ve made significant improvements. One of the things that I was getting stuck on was the proper distribution of landmass using a Perlin noise library. I ended up stumbling upon a clue hidden in the code of someone else who had been doing something similar, which incorporated the noise with the distance of the polygon to the center of the map, combined with a factor of the land vs water ratio. I couldn’t easily incorporate what I had found into my own script, but once I stumbled across it, it was like inception, it was only a matter of time. Take a look below at an example. These are 4000 random polygon sites on a 1024×768 canvas, looped twice through the Lloyds relaxation algorithm.

Voronoi polygons run through a Perlin noise generator. 4000 polygons on a 1024×768 field.

I’ve been able to identify land, water (ocean) and water (lake), and I also have elevation down. Many people suggest that I shouldn’t let elevation depend on Perlin, but let it depend on the distance to an ocean, but for now I’m going to go with the randomly generated noise and see where that takes me. If it doesn’t work out I can always come back to it. Hopefully tomorrow I’ll be able to use that elevation and generate a moisture variable for each polygon and combines those into different biomes.

 Momentum and forward motion is everything with projects like these, so hopefully I’ll have more tomorrow. :)

Map Generation, Voronoi Debugging

      2 Comments on Map Generation, Voronoi Debugging

After a solid week of debugging and reworking a php library I had found that generated a Voronoi diagram, I finally managed to hammer out the last kinks. It turns out that the two itterations of the Lloyds relaxation algorithm I used were sometimes coming up with sites that lay outside of the bounding box, which ended up causing all kinds of trouble. I now finally have a Voronoi polygon generator that a) I understand, and b) is performing fast enough for me to continue with.

Recreating Randomness
In order to properly debug the problem, I had to be able to recreate the problem properly. Initially, I used the PHP rand() function to create 1000 random points within a 1024×768 canvas. Each time the problem came up and I reloaded the script, it would come up with another 1000 random points, different each time. After first coming up with a half-arsed solution whereby I also outputting the coordinates for the 1000 points, I found out that you can set a seed with PHP’s srand() function. This allowed me to either generate a random number based on the system time, or just supply a number of my own. I made a little form that allowed me to generate a diagram based on a supplied number or generate one randomly and display the seed for that diagram. That way I could flip through random diagrams until I found one that was broken and simply keep generating that same diagram with the given seed. That made things much, much easier.

In the meantime, I also incorporated some code that wrote all the relevant information for the diagram into an XML file with which I could also once again recreate the diagram, without having to calculate everything again.

Up Next
Now that I’ve finally been able to find the flaws in the PHP library that I was working with and the code that I was using to call the library, I will continue exploring the finished code a bit, seeing if I can make some tweaks and do some cleaning up. I will also try to post the finish product of what I ended up making, perhaps with some more interactivity (the ability to set the canvas size, adjust the number of random sites, and perhaps also the amount of Lloyd iterations it does) so that people can play with it.

Then I’ll start looking at using a Perlin library to start creating a rudimentary shape for the map that I want to eventually create. Once I’m happy with that, elevation and moisture will come into play, which in turn means we’ll be able to make individual biomes.

I’m sure there’s still much more to do, but I have to say that even though the going was tough the last week — to the point that I was even dreaming about Voronoi polygons — it’s really rewarding to achieve breakthroughs and to persist into success.

Anyway,  I’ll try to get my script up tomorrow.

Map Generation, Cont’d

      No Comments on Map Generation, Cont’d

While my voronoi generation still displays some problems, I’ve moved on for the time being to determining land from sea. I’m using a perlin class that I previously created, but it’s really not cluttering the way I had hoped it would. I’m playing around with it, but this is what I have so far.

Voronoi polygons run through a Perlin noise generator. 1000 polygons on a 1024×768 field.

Map Generation

      2 Comments on Map Generation

A while back, my brother told me about a guy in his class who was busy with a random map generator. I started to play around with the idea as well and I took a careful look at different Perlin libraries in order to come up with some random shapes. After coding around for a while, I ended up with some disappointing results. While Perlin allowed me to generate noise that wasn’t completely random, but in which each coordinate had some relation to the coordinates adjacent to it, the results were made little sense to me, despite them looking quite organic. I basically used the noise to determine elevation. Each negative value meant water, each positive value meant land. Using some simple math I could also assign different colours to different depths and altitudes. Looked kind of neat, but took an awful lot of processing power. I was playing around with this on a twelve hour flight from Amsterdam to San Francisco, and my little netbook felt like it would melt through my tray table.

A random map generated using a Perlin noise library.

What killed the performance was the sheer amount of data points to calculate and display. I rendered it in HTML, using DIVs, later using an SVG, but it really didn’t matter. The Perlin performance was poor and the amount of data points required to get anything fun was gigantic. I dropped the project for a few months, until I discovered a post on polygonal map generation written by Amit Patel and it really opened my eyes. The organic feel that I was trying to achieve using Perlin could also be achieved using a Voronoi diagram and the amount of actual datapoints would be much less. The relationships between bordering polygons was also built into the concept of the diagram and on top of that, the input needed was relatively small (depending on how many polygons you want to generate); just a bunch of coordinates for the polygon sites.

I found several libraries generating Voronoi diagrams, but the one PHP library that I found was a messy port of brilliant Javascript library done by Raymond Hill, who showed me the power of HTML5 and Javascript as a tool for data presentation! (For example; take a look at these mind boggling examples of data visualisation!) I ended up porting the Javascript library myself and creating raw PNG output. It took me a while to really figure out how all of it worked, but tonight I had somewhat of a breakthrough and I managed to solve some persistent bugs in my code. Below is an example of an 1920×1200 image with 1000 randomly generated polygon sites. One of the things to keep in mind is that the randomly generated points have been adjusted with two passes of the Lloyd relaxation to make the points a little more evenly spaced apart.

An automatically generated 1920×1200 image with 1000 random polygon sites.

The next step will be to start figuring out land from water, assigning elevation and creating some sensible colours for the polygon cells. I’ll let my new best friend Amit Patel lead the way in logic; immitation, emulatio, creatio. I don’t quite understand all the logic behind everything yet, but if I take it one step at a time and tenaciously plug away, I’m sure that eventually my brain (made of obsidian, coated in teflon and impervious to the uptake of knowledge!) will eventually make this information his.