CODEWITHSUNDEEP
algorithm
example
example

Reputation: 3419

creating a random form on a 2d-grid

I want to create a random world. For simplicity let's say that it is based on a two dimensional grid of cells with 1m edge length each.

Right now I use a simple algorithm to create random forms (for forests, lakes etc.):

1. fill a circle of radius r with the wanted property
2. choose 4 points on the edge of this circle and
3. goto (1.) with all those four points as center and r/1.3

I somewhat like this because it creates forms that have a random form and underlying form of the circle is usually not visible.

There are two problems though:

  1. at times (when the first four points are chosen too close to each other) is becomes apparent what basic forms the forests are made of
  2. the algorithm is terribly inperformant. Cells are filled over and over again because the circles always overlap + all those distance calculations etc.

so: Is there any algorithm that is successfully used to create random forms? I am sure I am not the first person who ever wanted to do this...

I thought about choosing random points and form their convex hull - but I don't want to limit myself to convex forms. Choosing random distances for different angles in polar coordinates creates only star domains - again a limitation that I do not want...

Upvotes: 2

Views: 601

Answers (2)

smocking
smocking

Reputation: 3709

Of course if you just want something that works, there are libraries that do this like Joachim Pileborg recommended. However, if you are looking to have a bit more fun and learn a little bit during this project, I would recommend looking into the random midpoint displacement fractal aka Diamond-square algorithm. It's very good at producing natural-looking landscapes. You should also read up on Perlin noise while you're at it; it's a bit more dated, but a good start for learning the basics.

Upvotes: 2

Some programmer dude
Some programmer dude

Reputation: 409216

You can use something like libnoise to create height-maps, but instead of using them for height-maps you use the different "heights" for different type of terrains. Using libnoise you can generate a small region of terrain, and when you need the next part it can generate a region which fits seamlessly in with the previous generated regions.

Upvotes: 1

Related Questions