Sign in to follow this  

Placing random points on map

This topic is 2121 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
My current algoritm is something like this:

[code]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);
}
[/code]

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:
[url="http://dvdmandt.net/grand/rev39/terrain.png"]http://dvdmandt.net/grand/rev39/terrain.png[/url] - The heightmap
[url="http://dvdmandt.net/grand/rev39/terrain_provinces.png"]http://dvdmandt.net/grand/rev39/terrain_provinces.png[/url] - The heightmap with province results
[url="http://dvdmandt.net/grand/rev39/world.png"]http://dvdmandt.net/grand/rev39/world.png[/url] - Colored province results, also marks the points

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
[quote name='DvDmanDT' timestamp='1329930298' post='4915558']
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?
[/quote]

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.

Share this post


Link to post
Share on other sites

This topic is 2121 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this