In the previous post about random name generation (which can be found here) I have mentioned an improvement of the described method, and now I have it implemented.
I have modified the original implementation, so that it uses the last two letters for choosing the new letter. I also had to modify the first phase of the algorithm which makes the statistical representation of the "language", now it calculates the probabilities that a letter in a word follows two previous letters.
The names generated with this modified method are more similar to the original sample names, and it happens more often, that it is one of the samples - though it can be helped by using more samples. The length of the generated names is also more close to the average length of the samples, so I have removed the part that generates a new name until the length is neither too short nor too long.
The source code is available as before, and you can try it with the previous sample names for comparison:
Procedural content generation is usually used for making maps, terrains, plants, etc., but names can also be generated procedurally.
Back in university I studied language technology among others, and during this course we were taught an interesting method for generating random words based on the statistical characteristics of a given language. These words looked similar to the real words of the language at first sight, but they did not necessarily belong to the language.
This method consists of two phases. In the first phase we make a statistical representation of the words of the language. For this we need a sample set of words. We have to iterate through every word in the set, and calculate the probability that a letter in a word follows another letter. For example if we have only the word 'abacac' in the set, then the probabilities are:
a word starts with letter 'a' with probability 1
letter 'a' is followed by 'b' with prob. 1/3 and by 'c' with prob. 2/3
letter 'b' is followed by 'a' with probability 1
letter 'c' is followed by 'a' with probability 1/2, and ends the world with probability 1/2
In the second phase we can generate words based on the probabilities. First we choose a starting letter, and then we repeatedly choose a letter that can follow the previous letter until we choose to end the word (if possible). Staying with the previous example:
we have to chose 'a' as the first letter
the second letter can be 'b' with prob. 1/3 and by 'c' with prob. 2/3; if we throw a dice we choose 'b' if the number is 1 or 2, and 'c' otherwise; let's say we got 4, so our word so far is 'ac'
'c' can be followed by 'a' or end the word; 1 to 3 on the dice means we choose 'a', 4 to 6 means the word ends; let's say the number is 2, thus our word becomes 'aca'
we have to choose a letter that follows 'a' again, let's say we threw 6, so our word is 'acac' now
now a successor to 'c' is needed again, suppose our number is 5, so we are finished, our final word is 'acac'
This example does not show the power of this method, it's just to demonstrate the algorithm. With a large set of words much better results can be achieved.
The method can be simply used to generate names, this can be really useful for games. For example we know lots of elven names, and with this algorithm we can generate similar random names that we can give to NPCs or help the player choose a name. It can also be used for names of cities, animal races, etc.
Since sometimes the names can be too short or very long based on the samples, my implementation generates a new name until a name is found which is neither too short nor too long.
An improvement of this method might choose a letter based not on the last generated character, but on the last 2, 3, ...N characters. This way the words are more similar to the original words, but more samples are needed to achieve good results.
I have implemented this method in Javascript, so that it can be embedded into the blog. The source code is available for download.
You can also try it: enter the sample names into the textbox separated by spaces, and click 'Generate new name' to (surprisingly) generate a new name.
There are already several methods for procedural terrain generation (perlin noise, fractals, diamond-square algorithm, etc.). All of them has it's advantages, disadvantages, I do not want to judge or compare them, I just want to describe yet another method I came up with. I think it's main advantage is it's simplicity, it is very easy to implement, yet produces interesting terrains.
The algorithm starts with a flat heightmap, i.e. every cell of the map has a height of 0. Then in a number of iterations it modifies the heightmap, creating the final terrain. In every iteration step a line is generated which crosses the map region, this is achieved by randomly choosing two defining points in the map area. Then the height of every cell of the map on one side of the line is increased by a given value (practically by 1). That is, we repeatedly cut the map into two halves randomly, and raise the level of one of them.
After several iterations the heightmap has enough variation. The height values are between 0 and the number of iterations. After finding the minimum and maximum values we can interpolate the height values into any range we want. The number of iterations required to get a good looking terrain depends on the size of the map, larger maps usually require more iterations.
Advantages of this algorithm:
simplicity
works for any map size
scalable (the quality of the terrain can be controlled with the number of iterations)
Disadvantages:
high computational cost ( for an W*H sized map and N lines it is O(W*H*N) )
not "infinite" like perlin noise
An online demo is available here, it is implemented in processing.js. It generates a 100*100 map with 256 iterations. Since it runs in the browser the calculation speed is quite slow, so be patient.
The source code is also available: download.
I plan to make a 2d rpg. I have looked at several different variations of calculating field of view (this used to be a good summary, but seems to be unavailable at the moment), but I did not really like any of them. Somehow they seemed to be too sharp, too "digital" - something is either visible or not.
I wanted a fov calculation that gave more natural results, and I thought that simulating light propagation would be a good candidate. Since the game world would be a 2d grid, the idea of using a cellular automaton to calculate light propagation came to my mind, and I started experimenting with it.
After a few ours of planning and coding, I got the results that satisfied my need:
How does it work? Every cell in the grid has two attributes. The first attribute is transparency: if a cell is transparent, light can propagate through it, otherwise it can only receive light. This value represents wether the cell in the game world is blocking the light, it is not updated by the automaton.
The second attribute is the strength of the light in that cell. In my implementation it is a floating point value between 0.0 and 1.0. This value is updated during every iteration, the new value is the average of the cell and the neighbouring cells. If the cell is blockling the light, it's value is not included in the averaging, so that they do not light other cells, even thought they can receive light.
I have used 4 neighbours in my implementation. The drawback of this is that the corners are in shadow. This could be easily solved by using 8 neighbours, but that increases the computational costs. Another improvement could be using RGB colours instead of the simple light strength, this way more interesting effects could be achieved.
Strictly speaking this might not count as a calculation of field of view, but it achieves a similar effect. I think this method could give a good atmosphere to a game, especially to games with stealth / horror elements. (Imagine walking down a corridor, when suddenly your torch goes out, and everything becomes totally dark... and then you hear a noise...)
I have implemented this method in processing.js, it is available here, you can experiment with it in the browser. The mouse cursor is the source of the light. In the beginning every cell is a wall, blocking the light. You can 'carve' empty cells into the grid by holding the left mouse button, or build back the walls with the right mouse button. The source code is available here.
