Shannon's Entropy
Entropy itself is considered a measure of disorder, the factor of probabilities of events and states which are uncertain and can change due to unknowable variables. When used in computing, this is more generally akin to the random number generation discussed in my blog post on the subject, however a closer to true random variation using real life objects (like the lava lamps shown here). But the version used in the project is based on information theory, and for most choices within the algorithm that use entropy, the pseudo random number generation is fine, it is almost indifferent to all of the options. However for the collapsing of tiles, some cells have more options and we want to specifically know which tiles have the least options to collapse them. Essentially picking the most likely cells next to try and avoid conflicts.
Shannon's entropy is a way of determining which cells will have the least possible remaining options. But not using just it's own but comparatively to the overall potential options it could've had, including factoring in the individual tiles' "weights". I am using how much they show up in the input model to determine the weights.
This is the article first published in 1948 by C.E. Shannon which is the foundation of the entropy calculations if more information about the specifics is wanted.
This is my current code for programming the Shannon's Entropy per cell, which I only do when possibilities are removed:
//Calculating Shannon's Entropy
public float calculateEntropyValue()
{
//If the tile is selected, there's no chance of it changing in the program, so it's entropy is 0
if(tileUsed)
{
return 0f;
}
float sum_of_weights = 0;
float sum_of_weight_log_weights = 0;
float weightSum = GetSumOfTileWeights(possibleTiles);
//Going through this cells' possible tiles and calculating the possibilities' weight values
for(int i = 0; i < possibleTiles.Count; ++i)
{
float weight = possibleTiles[i].Frequency / weightSum;
sum_of_weights += weight;
sum_of_weight_log_weights += weight * Mathf.Log(weight);
}
return (Mathf.Log(sum_of_weights) - (sum_of_weight_log_weights / sum_of_weights));
}The function to get the sum of the tile weights looks like this:
//Going through and adding up each tiles' weights based on a given list
public static int GetSumOfTileWeights(List<Tile> tilesToWeigh)
{
int totalWeight = 0;
for(int i = 0; i < tilesToWeigh.Count; ++i)
{
totalWeight += tilesToWeigh[i].Frequency;
}
return totalWeight;
}
I added a visualiser to the grid so the entropy values are shown whilst the grid is filling in with tiles. Due to the input models' frequencies of each of the tile types.
This is the input model I've used for the demonstration, an addendum on the previous one used for testing. It is made in such a way wherein there aren't any possibilities (that I know of yet) where the grid can fail to generate. It also produces a lot of the dirt and water tiles because they show up the highest amount of times and can be connected to the most amount of other tiles.
I realised that before this point I hadn't shown the algorithm in effect, this is using seed 7919 like last time. The grid is flipped since I have realised it was wrong when adding a way of combining multiple input models.
Updates To Adjacency Rules
In the last blog post I had described some of the issues I have faced so far, in that I mentioned that currently it's just the simple tiled model. Whilst that's true, I hadn't added the code to have the adjacency rules use any sort of direction vector or enum in the rules. This meant that any roads or river pieces could be placed in any direction from tiles it could be placed next to, which is wrong. Initially I tried to use a tuple in my current code before coming to the conclusion that it's just unnecessarily complicating the code, and just having the rule be a separate struct would make more sense. I then pass through the local translations to neighbours when I get them to check against which making and using the rules.
[Serializable]
public struct AdjacencyRule
{
public AdjacencyRule(Tile newTile, Vector2 newDir)
{
tile = newTile;
direction = newDir;
}
public Tile tile;
public Vector2 direction;
}
Using a variable of this type in the tile, replacing the list of tiles I had before, made it a lot easier and more compact than before. So it's now possible to add rivers and roads correctly, although I'm still making each potential rotation a separate scriptable object / prefab (which could be improved).
Comments