Andrew Sayers wrote: > Before we talk about gradients, I've remembered some of the more > important things I need to ask you about... > > First, the random map generator. Could you tell me a bit about how it > works? It seems to be based on quite a complex algorithm - is it > something you made yourself, or based on known ideas? If it's your own, > could you explain some of the theory? If it's someone else's, could you > give me some information I can use to look up explanations?
* the random map generator: The random map generator is an algorithm of mine. As you most probably know, the "undemap" is a map which can contain either water, sand or grass. This is an array shifted by half a "case" on both axis compare to the tile "case" grid. This is a convenient tool, because you can draw on the undermap, like you paint pixels on a bitmap. Then, for each tile, you just convert a 4-under-map value into a tile value. Here is the way the random map generator *did* work: 1) Randomly write into the undermap, water, sand or grass, given the provided ratios. 2) Apply a simple blur filter on the undermap, as many times at the "smoothing" parameter. 3) Filter the undermap to add sand between the water and grass where it is needed. This is because we don't have tiles for direct transition from water to grass. 4) Generate the tile-map from the undermap. 5) Add some stuff on the tile-map, like resources and teams. The idea is to use a blurring effect to make islands-like areas, instead of having white-blur-looking maps. And I found it to make natural-looking shapes. The problem is that, the blurring will completely destroy the originally given ratios of water, sand and grass. The more blurring levels there are, the more important the distortion is. Let's take an example. Let's only use sand and grass. We start with 1/4 sand and 3/4 grass. The actual blur is more complex, but let's take the most simple blur, with 2 bitmaps, the old bitmap and the new bitmap. Take 4 pixels in a square, make the majority, and draw the result in the new map. Bases on the 4 possible pixels, there are 16 possible cases: (s==sand, g=grass, x=undefined) ssss, maj = s, prob = 1/256 sssg, maj = s, prob = 3/256 ssgs, maj = s, prob = 3/256 ssgg, maj = x, prob = 9/256 sgss, maj = s, prob = 3/256 sgsg, maj = x, prob = 9/256 sggs, maj = x, prob = 9/256 sggg, maj = g, prob = 27/256 gsss, maj = s, prob = 3/256 gssg, maj = x, prob = 9/256 gsgs, maj = x, prob = 9/256 gsgg, maj = g, prob = 27/256 ggss, maj = x, prob = 9/256 ggsg, maj = g, prob = 27/256 gggs, maj = g, prob = 27/256 gggg, maj = g, prob = 81/256 Overall, we have a such probability: maj = g, prob = 189/256 = 73.8% maj = x, prob = 54/256 = 21.1% max = s, prob = 13/256 = 5.1% If the undefined is shared, 1/4 sand and 3/4 grass, like originally aimed, we get: maj = g, prob = 89.8% max = s, prob = 10.2% Which, as you can see is not equal to the original ratios of 75% grass, and 25% sand. Worse, this effect is exponential, given the number of blurring levels. After 8 blurring, you will get 100% grass by all chances. The only case where you don't have this effect, is when you have equal ratios of all lands. For instance 1/3 water, 1/3 sand and 1/3 grass, will mostly end up into the same ratios after blurring. Now, to fix this problem you have to setup a small theory. Here is the way I remember it works: The goal is to find the starting ratios which will end up into the requested ration, after all blurring levels. You can visualise the problem into an unity cube. Each axis is one of the land-type: water, sand or grass. On each axis, 0 means 0% and 1 means 100% of each resource. One dot into the cube represents a probability of each land-type. Each blurring level is a math transformation of one point into the cube into another. To find how to go from one point to another, we can use the simulateRandomMap(), which will actually make a map, blur it and report final ratios, but into smaller (1/16) scale. The problem is that it's not reversible. That mean that you can only find the ending-ratios from the starting-ratios. We also have a math expression, but it is not really accurate, due to discrete effects. But it has the advantage to be formula-based, so we can get the starting-ratios from the desired ending-ratios, tough it is not accurate. Now, using both the math formula and the pragmatic simulateRandomMap(), we evolve using a newton-like algorithm, from the final-requested-ratios, to the starting-actual-ratios. The line 342 to 440, into bool Map::makeRandomMap(MapGenerationDescriptor &descriptor) of MapGenerator.cpp, are doing it (the for (int r=1; r<=smooth; r++) loop). Once found, the ratios are displayed into the console. For instance: makeRandomMap::old-base=(0.100000, 0.000000, 0.900000) makeRandomMap::new-base =(0.392261, 0.000000, 0.607739) Means that I want 90% grass and 10% water. The algorithm finds out that we need to start with 60.8% grass and 39.8% water. Once the A bit lower we can read: makeRandomMap::beforeCount=(0.385681, 0.000000, 0.614319) makeRandomMap::final count=(0.043945, 0.000000, 0.956055) Once created the map actually started with 38.6% of water instead of the 39.8%. This is because the random is random! The land-type is selected randomly for each of them. As a result, the map will actually end up with 4.4% of water instead of 10%. Oppositely, on another run, you can get ends up with higher ratio of water. Getting better results is possible, but it will need more computation. Still, the algorithm "cheats" during the blurring process in order to stabilize the exponential effect. To achieve this smoothly, it does bias the probability to make unwanted changes. That mean that the further we are of our ratios goals, the less likely a change is to occur. There is good chance that a better theory, could end up into a more simple algorithm. For instance, if someone finds the exact math expression to go from the wished-ration and number of blurring steps to the starting-ratios, then it would be faster and better. Is it all clear ? Luc-Olivier _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
