Current Framework Version: 0.5.0
ETPKLDiv Algrorithm was introduced by Lucas and Volz in GECCO 2019. The name stands for Evolutionary Tile Pattern KL-Divergence algorithm. The authors showed amazing results and compared it to GAN and to WFC and it had very competitive results. The algorithm was able to work on small or big inputs which neither GANs nor WFC are able to do. In addition, ETPKLDiv is always able to return a generated map and doesn't get stuck like WFC. The following table is pulled from the paper and shows the comparison between all the algorithms.
Method | Training Time | Generation | Tiny Input |
---|---|---|---|
ETPKLDiv | Fast | Fast to Medium, Never Fails | Yes |
WFC | Fast | Fast to Slow, May Fail | Yes |
GAN | Slow | Always Fast, Never Fails | No |
ELSGAN | Slow | Slow, Never Fails | No |
Here are some actual numbers from running the algorithm to generate new samples using pop_size
equal to 1
and tp_size
equal to 2
on the red and black
picture from the Wave Function Collapse demo. We show the effect of the number of iterations
with respect to the size of the generated sample (width
xheight
). About the effect of pop_size
, it doesn't need to be tested because it will always increase the time by that much unless we parallelize them. Also using higher pop_size
find the solution faster (almost around 1/pop_size
). The tp_size
effect on speed is pretty small where increasing it will increase the number of unique pattern that can be found in any of the images. But since the image size is fixed this means there is a limited amount of unique tiles can appear which is equal to the size of the sample. Because of that the effect of increasing tp_size
is almost negligible.
The following table show the results using the JavaScript implementation running on an old mac book pro from 2015. These values are averaged over multiple runs to get an accurate estimate.
Iterations | 30x30 | 60x60 | 120x120 |
---|---|---|---|
1000 | 0.438 sec | 1.768 sec | 9.598 sec |
5000 | 2.002 sec | 8.023 sec | 46.839 sec |
10000 | 3.985 sec | 16.080 sec | 91.976 sec |
That following table reports the results from the C# implementation on the same machine. These values are averaged over multiple runs to get an accurate estimate.
Iterations | 30x30 | 60x60 | 120x120 |
---|---|---|---|
1000 | 0.972 sec | 4.381 sec | 24.490 sec |
5000 | 4.778 sec | 21.560 sec | 125.510 sec |
10000 | 10.204 sec | 20.340 sec | 112.943 sec |
As you can see that the C# implementation is slower than JavaScript (Sorry I am not great in C# as I didn't use it for awhile). Please help improve it if you are good with C# optimization.
Here are some generate images at different iterations using several different input images and map of size 30x30. All these results are using inter_weight
equal to 0.5. Results quality differ based on that value, for some applications having low inter_weight
might cause producing a more appealing images at fewer iterations than others and vice versa. Just remember the time for 10000 iterations is less than 4 seconds (in the JS implementation as it is more optimized) which will generate on the fly while your game is loading.
Iterations | Example 1 | Example 2 | Example 3 |
---|---|---|---|
1000 | |||
5000 | |||
10000 |
As you can see the algorithm is pretty fast with amazing results in very short time (similar to WFC). But it is very noticeable that the speed drops a lot down when the output image increases. One of the solution is to divide the big image into a grid and generate every part of the grid separately. To blend these independent part you can generate a small image for the in between by fixing the stuff on the left and right and allow the algorithm to just update the middle.
Here are some examples of the generated inputs using the online interactive demo:
As you can see from the picture that the ETPKLDiv is not as strict as WFC in generation which sometimes in harder problems (like Mario and Flowers) will get stuck in local optima. We think by some parameter tuning you might be able to get better results than shown above. Also, we would like to experiment with some quality diversity techniques and having crossover and see its effect. Also, locking some tiles to certain values will make the algorithm generate better results as it is guiding it towards a more desirable output.
The algorithm is pretty simple with no complication. You can read more about it in Lucas and Volz paper. It uses an optimization algorithm (EvolutionStrategy
) to minimize the KL-Divergence value between the new generated map and the original data. KL-Divergence is a method that measures how close two distributions (in our case: the generated sample and the input sample) are to each other. The distributions in our case are just a simple count of the difference in the tile pattern configurations of a certain size (tp_size
) where tile pattern configurations are just a group of tiles beside each other. The algorithm at each step generate a new sample (pop_size
) from the current one (pop_size
) by copying one or more (mut_times
) tile pattern configuration from the input sample to the new one. The algorithm picks the best ones (pop_size
) but allowing some bad ones if the user wants (noise
).
Here is a step by step algorithm if you are trying to replicate it:
- Create
pop_size
number of new samples with dimensionswidth
xheight
. These samples values are randomly chosen from all the possible tile values (tile values is just an integer that could be a color or an index to a tile). - Compute the fitness for each sample by computing the KL-Divergence between that sample and the
input_samples
.- Count the frequency of each tile pattern configuration of size
tp_size
xtp_size
in the tested sample. - Count the frequency of each tile pattern configuration of size
tp_size
xtp_size
in theinput_samples
. - Calculate the KL-Divergence for the tested sample with respect to
input_samples
. This value shows that every tile pattern configuration in the tested sample exists in theinput_samples
. - Calculate the KL-Divergence for
input_samples
with respect to the tested sample. This value shows that every tile pattern configuration in theinput_samples
exists in the tested sample. - Calculate the fitness as negated average weighted sum of the first and second KL-Divergence using
inter_weight
.
- Count the frequency of each tile pattern configuration of size
- Generate a new mutated sample of size
pop_size
from the current samples based on their fitness value. Higher fitness individuals have higher chance to generate new samples than lower ones (noise
can affect that value by giving low fitness individual higher chance to be selected).- Use Rank Selection to select a sample from the current population.
- Clone that selected sample.
- Copy a
tp_size
xtp_size
tile pattern configuration from theinput_samples
to a random location in the cloned sample. Repeat that as many times between1
andmut_times
. - Repeat the previous steps till we have
pop_size
new mutated samples.
- Merge the new mutated samples with the original samples and kill the lowest
pop_size
samples with respect to their fitness value (noise
can affect that order by giving a higher chance to low fitness individual to survive). - Repeat from the second step again till the number of
iterations
has been reached.
Here is a some pictures of the algorithm in action (Don't worry the algorithm is a lot faster than that, it is just slowed down for rendering):
The API for the ETPKLDiv
class is the same between all the implementation. The following table shows all the functions that are provided by the ETPKLDiv
class.
Function Name | Parameters | Functionality |
---|---|---|
constructor |
No parameters are needed for now but in future we should include the optimizer name | Creates the optimization algorithm object. In the current implementation it creates Evolutionary Strategy optimizer |
initializePatternDictionary |
input_samples : a 2D integer matrix of the input data (it can accept 3D matrix if you have multiple inputs) tp_size : the size of the patterns that the algorithm is optimizing towards (minimum is 2) warp = null : is an optional parameter that allows the system to warp the input_samples edges borders = null : is an optional parameter that forces the system to make the edge tiles change based on the input_samples edges |
This function initialize the system for generation based. you don't need to call it if you are using generate function as it will call it automatically |
initializeGeneration |
width : the width of the generated map height : the height of the generated map pop_size=1 : an optional parameter to increase the number of competing maps to enhance the generation |
This function initializes the generation process by specifying the size of the generated map and how many maps to compete for generation. |
step |
inter_weight=0.5 : the weight variable from ETPKLDiv algorithm which balances between having every tile pattern in the generated image exist at least once in the input or vice versa mut_times=1 : maximum number of changes the algorithm is allowed to change in the generated map at once (can be used to push the algorithm from any stuck locations by allowing more changing power) noise=0 : add noise to the fitness computations to push the algorithm from being stuck with a certain map by allowing the algorithm to takes sub optimal moves |
Advance the algorithm by one step forward toward enhancing the generated maps |
generate |
input_samples : a 2D integer matrix of the input data (it can accept 3D matrix if you have multiple inputs) tp_size : the size of the patterns that the algorithm is optimizing towards (minimum is 2) width : the width of the generated map height : the height of the generated map iterations=10000 : an optional parameter to define the number of iterations needed to generate a map warp = null : is an optional parameter that allow the system to warp the input_samples edges borders = null : is an optional parameter that force the system to make the edge tiles changes based on the input_samples edges pop_size=1 : an optional parameter to increase the number of competing maps to enhance the generation inter_weight=0.5 : the weight variable from ETPKLDiv algorithm which balance between having every tile pattern in the generated image exists at least once in the input or vice versa mut_times=1 : maximum number of changes the algorithm is allowed to change in the generated map at once (can be used to push the algorithm from any stuck locations by allowing more changing power) noise=0 : add noise to the fitness computations to push the algorithm from being stuck with a certain map by making the algorithm takes sub optimal moves |
Run the algorithm directly for a fixed amount of iterations (Recommended to use for beginners). |
lockTile |
x : the x location y : the y location value : the value used to lock the tile with |
This function locks a single tile specified by the input to a certain value |
unlockTile |
x : the x location y : the y location |
This function frees a single locked tile specified by the input |
unlockAll |
No parameters are needed | This function frees all the locked tiles |
getIteration |
No parameters are needed | This function returns the number of iterations the optimization algorithm applied |
getFitness |
No parameters are needed | This function returns the fitness of the best generated map |
getMap |
No parameters are needed | This function returns the best generated map |
- Allow multiple tile pattern sizes to be used in generation (needs a way to do the inter_weights and a way to do intra_weights)
- Adding Convolutional Crossover
- Adding Different Optimization Algorithms beside ES
- Adding more exceptions to handle all corner cases
- Adding parallelization when the population size is greater than 1
- Add 3D generation
- Proper Documentation
- Lua Implementation
- C++ Implementation
- Python Implementation
- Java Implementation
- Make more elaborate Unity demo
- Phaser Demo
- Defold Demo
- Jupyter Notebook Demo
- LibGDX Demo
Contributing in this repo is very welcome. You can contribute in many facets explained in the following subsections:
Create a new folder with the name of the language or interface. Add your code inside and make sure that there is an ETPKLDiv
class that can be created and have the same functions provided in Common API section. In the end add a README.md
file to explain how to use it in that language with a small example.
Create a folder for the Demo. The name has to be the engine/languages name followed by "Demo" similar to the "HTMLDemo". Get the latest build of the language needed from the corresponding language folder. Write your demo and make sure it is working fine. Make a pull request to the main repo.
Bug reports and pull requests are welcome on GitHub at https://github.com/amidos2006/etpkldiv.
This code is available as open source under the terms of the MIT License.