~ DAGOVAR :: A VISUAL BASIC GAME ~
Creating a random terrainRandom terrains are generated by various kinds of algorithms which make use of random functions with the purpose of simulating certain landscaping rules. Concepts such as flood, frequency and attraction are the ones that come to my mind right now. I will try to explain the best I can these concepts, so you can understand them and hopefully manage to create your own algorithms for creating random tile-based terrains.
FloodThese algorithms are used to invade - hence their name - a given area for diverse purposes, by using replication methods. Some well known examples of the use of these algorithms are painting software, when you use that icon with a paint cannister to turn all the area inside a mask with a certain color, or those board games where you have to click groups of elements to remove them from the board. In both cases the algorithm is the same; the first example works with pixels while the second example works with tiles. To start the flood algorithm, we need a source point to start scanning; in the first example this would be the pixel where we click with the paint cannister and in the second example it would be the tile where we click to remove a group of tokens. To end the flood algorithm we need some kind of limit; in the first example it would be either the path of the mask edges or the limits of the image, while in the second example it would be either the absence of the required tokens or the limits of the board.
For me, the tag that better describes the operation of this algorithm is the concept of encirclement; the algorithm is constantly encircling elements to study every of its adjacent elements. So we start by one single element, then we study any adjacent element and if any elements with the desired characteristics are found, we add them to an array, this is, a list. We will do the same process with every tile added to the list, and repeat this until no more elements with the required characteristics are to be found. Now I will describe a basic process of flood in detail:
- Create a dynamic array to store the identification data of the elements that will be scanned (these are usually tiles, if we are talking about games).
- Create a dynamic array to store the number of scanning passes that have been done so far, every time that an element is added to the first array. This will associate each added element with the number of the scanning pass on which that element was added to the list.
Instead of using two individual arrays you can use a single array using an user defined type which stores both data.
- Create a numeric variable to count the number of scanning passes the algorithm has done so far. Initialize it to zero if necessary.
- Choose an element as starting point; resize the first array with a new cell and write on it the identification data of that first element. In the second array, add a new cell as well and write on it the number of scanning passes performed so far - it should be zero, anyways -.
- Add one to the count of scanning passes.
- For that first element, check every element that lies around it, for a certain condition that you want the scanned elements to comply.
- If an element complies with the condition, resize the first array with a new cell and write on it the identification data of that element. In the second array, add a new cell as well and write on it the number of scanning passes performed so far. This time it should be one.
- When all the surrounding elements have been checked (these are usually eight, for pixels or square tiles, or six, when using hexagonal tiles) add one to the count of scanning passes. The first pass has finished and the second pass will begin.
- Now make a scanning on the second array; for each cell on that array whose value stored is equal to the count of scanning passes performed so far, make a check on every surrounding element for the element that is located in the same position on the first array.
- If an element complies with the condition, resize the first array with a new cell and write on it the identification data of that element. In the second array, add a new cell as well and write on it the number of scanning passes performed so far. This time it should be two.
- When all the surrounding elements for each of the elements scanned on the first pass have been checked add one to the count of scanning passes. The second pass has finished and the third pass will begin.
- Repeat this process until there is not any cell on the second array whose value is equal to the count of scanning passes; this means that during the last scanning pass no element was found as complying the condition, and therefore no element was added to the list. End of the story.
- On the end, we should have now on the first array a list with all of the elements that were caught on the flood... Now we can perform on all of these the operation that we want... for instance, change their color if they are pixels in a painting software or make them disappear from the board, if we are making one of those Match-3 derivatives...
Those two examples that I mentioned before would be solved technically by using an algorithm like this one; the flood algorithm is used as well for pathfinding techniques, particularly that one known as A* pathfinding... But well, that's another story. It is time to start seeing how this relates to random terrain generation.
When we want to create random areas in a field of tiles, such as patches of grass or lakes, we can use a similar algorithm to create them; in this case, the first element around which the rest of the patch grows would be adequatly called the seed. For instance, when creating lakes, I used two variables to determine how their presence would be on the maps: quantity and size.
Quantity would be related with the concept of frequency. For doing this, a practical way would be to set quantity values from 1 to 10. Then we would run a loop through every tile on the map and generate, for instance, a random number between 1 and 10; if the generated number is lesser or equal than quantity, we would put one seed on that tile, this means, we would set that tile to be a water tile. It is obvious that if chosen quantity were 10, then we would have all tiles converted in seeds and hence we would end with a full sea instead of lakes. You can leave it this way or adjust it differently if you don't want a chance for so much water in your maps.
Size would be related to the number of passes that the algorithm would perform around the seed tile. When I programmed ScenEdit I used a fixed number of passes for each selected size value; the higher the average size of lakes, the higher the number of passes. It would be simple to set size as a value from 1 to 10 and then perform a number of passes equal to the selected size value. So instead of using lists to keep track of scanned tiles, I just programmed the algorithm to effectuate the scanning passes through all the map; the higher the chosen size, the higher the amount of passes. On each pass, if a tile is of water type, then for each surrounding tile it will be chosen randomly if it will be turned to water as well or not; the probabilities to turn it have to be high, of course. They could be 1 out of 2, 1 out of 3, 1 out of 4, or so... Then what we are achieving here is that on each pass, we will have more water tiles on the map. And on each pass their number will grow faster and faster. The randomness of the shapes for the lakes will depend on how you adjust the random operations. It is clear that if you reduce the probabilities to turn adjacents tiles to water, you will need more passes to achieve a certain size. This could also affect the shapes of the lakes, but this aspect is hardly predictable; you would have to do trial and error to approximate the desired result.
Frequency and attractionFrequency will determine how much abundant will be on the map a certain type of terrain or object, which is directly related to the probabilities that we assign for it to be placed on the map, by means of adjusting the parameters of random functions. For instance, if we want to place on a map random abandoned objects, such a rusty bidon, we would use a very low probability for that object to appear on the map, let's say for example, 1 out of 1000, which would be the same to say that an abandoned bidon would average one appearance on the map for each 1000 square tiles... Yes, I don't want people throwing garbage on the nature, damn... If instead on abandoned rubish the object would be a chaparral, then the probabilities would be much higher, let's say per example, 100 out of 1000 - or 10 out 100, or 1 out of 10, as you prefer... -, which would be the same to say that chaparrals would average one appearance on the map for each 10 square tiles... Yes, chaparrals are everywhere, and I love them, damn...
Attraction will affect frequency taking as reference certain rules that we observate on the real world. For instance, in a desert terrain, trees should be less frequent than in a grassy terrain. This is a simple case of frequency. However, near an isolated water source, this is, an oasis, trees should be quite frequent, even surrounding the lake. This is attraction, and it is created by just increasing the probabilities of an object to be placed on specific areas of the map. Another example of attraction would be stones; these would be quite frequent in the surroundings of large rocks, because they become detached from these, but less frequent far from these. Another example would be trees; trees attract another trees to them, because of the seeds that they drop. We can simulate this effect on our maps by doing something similar to what I explained for creating the lakes, but perhaps changing the strenght of the attraction, by reducing probabilities of surrounding trees. We don't want only patches of trees, we need more isolated trees as well, so our maps can look more natural.
You can see how my random maps look by visiting this page: Random maps
~ About Dagovar ~
~ Defining characters ~
~ Desert Vixens 2 maps ~
~ Desert Vixens 3 maps ~
~ Tile-based terrains ~
~ Random maps ~
~ Screenshots ~
~ Algorithms ~
~ API functions for games ~
~ Source code examples ~
Return To Index