9 replies to this topic

[DvDmanDT]

Hi!

I have generated a heightmap which will serve as terrain for my strategy game. Now I want to distribute points randomly on this map in order to create provinces. The game will use irregularly shaped regions as provinces (ie no rectangles or hexagons). I have an algorithm which given a set of points and a terrainmap (heightmap) divides areas into regions, but it's dependent on randomly distributed points. A problem is that I want much denser point clouds on land than on sea (as in 16-64 times more dense on land).

At the moment, I use some brute force algorithm to place a number of points on the map and make sure they are not too close. This is quite slow but gives really good results.

I was wondering if anyone has a better algorithm for this?

[jwezorek]

Could you go into a little more detail ...How do you have the border between the land and sea represented? e.g. is this tile-based or do you have polygonal continents?, etc.

[DvDmanDT]

I have a bitmap-ish structure (2D array of 'MapPoint' which contains height, terrain type, province etc). I want to create an array/list of points with integer coordinates which can be used as lookup to this bitmap.

[taz0010]

Start by adding points randomly to the terrain, and then gradually remove points until you achieve the desired density. You can use spatial hashing techniques to divide your region up into equal sized squares, allowing you to query the points in a square and it's neighbours very quickly. Then you can take all the points within a fixed distance of the query point, and replace them with a single point whose position is the average of it's neighbours. Increase the threshold distance if the points in question are on water.

Depending on how you tweak it, you might end up with no points being closer than a certain distance. Or if you prefer, you could randomly decide whether to merge points, in order to allow points to occasionally be close together, but not often.

[jwezorek]

Actually, if I understand the problem correctly I think the OP should just maintain two arrays of indices into the MapPoint array, one containing just indices of land and the other just indices of sea.

Then given the sizes of these two arrays, it is trivial to generate a random sampling of points from each that has whatever density is desired, where by density I mean the ratio num random points / num map points. If you need a more complicated definition of density i.e. one involving how close the points are together, then you need a more complicated algorithm. I, however, would at least try what I am suggesting: sometimes random number generators and probability will surprise you and you don't need to design in as much as you think you do.

If you do need strict bounds on how close the sampled points are together, I'd try a greedy approach: place a point then randomly place another point that is within the correct distance, then place another point that is within the correct distance, etc. Do this for the land and the sea separately. -- kind of like a randomized floodfill.

[cignox1]

What about generating a random point and then discarding/accepting it according to where the point is (land/sea or distance with nearby existing points)?

newPos = generateRandomPos()

if(newPos.isOnLand())
{
if(random() < 0.05)
return;
}
else
{
//on sea
if(random() > 0.05)
return;
}

acceptPos(newPos)

[DvDmanDT]

My current algoritm is something like this:

for(i = 0; i < NUM; i++)
{
numTriesLeft = 10000;
do
{
p = GetRandomPoint();
land = IsLand(p);
} while(--numTriesLeft > 0 && IsClosestPointCloserThan(p, (land ? 400 : 1600), pointlist))

if(numTriesLeft <= 0)
break;

AddPoint(pointlist, p);
}

I suppose it would be alot faster if I used an optimized IsClosestPointCloserThan() with grids or similar..

I have considered something similar to what jwezorek is suggesting, but it doesn't really help me apart from deciding how many land and how many sea provinces to place. It would pretty much require me to run the above algorithm twice, once for land and once for sea, but with p = GetRandomPointFromArray(land ? landArray : seaArray).

Here's an example of what I'm doing:
http://dvdmandt.net/grand/rev39/terrain.png - The heightmap
http://dvdmandt.net/grand/rev39/terrain_provinces.png - The heightmap with province results
http://dvdmandt.net/grand/rev39/world.png - Colored province results, also marks the points

[jwezorek]

Can't you...

1. Generate uniformly distributed points (without any special filtering based on distance from neighbors)
2. Create provinces
3. iterate through through provinces and extract pixel area of each via floodfill (or maybe you aleady have area from when they were generated)
4. If a province is too small in area union it on to a randomly selected neighbor. Repeat in a loop until it is big enough.
5. if a province is too big split in two (by selecting two internal points and computing the vornoi diagram or whatever you are using fro province generation)

This will also give you the possibility of ending up with some provinces that aren't convex which will be more realistic looking. In fact you could run the above on much more densely packed seed points then what you are using now, expecting to have to union together several seed provinces for each output province.

[DvDmanDT]

I already get provinces that aren't convex, the problem with your suggestion is that I want provinces to be fairly even-sized, and for water in particular, I want them to be fairly regular (except next to land). I've thought about splitting and merging provinces, in particular where there are provinces that are pretty much single pixels etc..

I suppose I should implement province merging/splitting, then I could try out your idea. But wouldn't it create very regularily placed points? If not, how do I place the points randomly and fairly equally distanced?

[jwezorek]

I already get provinces that aren't convex, the problem with your suggestion is that I want provinces to be fairly even-sized, and for water in particular, I want them to be fairly regular (except next to land). I've thought about splitting and merging provinces, in particular where there are provinces that are pretty much single pixels etc..

I suppose I should implement province merging/splitting, then I could try out your idea. But wouldn't it create very regularily placed points? If not, how do I place the points randomly and fairly equally distanced?

Why don't you do split-merge for land and for water either (a) just overlay an even triangular grid of points maybe, slightly perturbed, and generate water provinces from that or (b) run the same algorithm as for land but scale down the input mappoints first, generate seed points on scaled down map, scale up seed points, and generate provinces.

What are using for province generation? I thought the province maps were vornoi diagrams because I didn't look at full resolution, but now I see you have concave provinces in there.