FireFlight
FireFlight
Embedded Files
This game is inspired by fire helicopters flying over flaming forests.
Role: Developer
Team size: 12
Engine: Unity
Duration: 4 weeks
Languages used: C#
Player is expected to load waters from various water sources, then unleash water from above to put out the fire. There will be initial fires on map, and then it will grow in severity and spread by time. In-game UI elements will indicate player about the location of fire's center.
K-Mean Clustering algorithm
K-Mean Clustering algorithm
An algorithm very commonly used by machine learning. It can recursively group datas into given number of "clusters", and determine the center of each cluster.
This is how the algorithm works:
Acquire initial input of number of clusters, and (optional) center variance as threshold.
Evenly distribute data into clusters, calculate the center of each cluster.
Evaluate all data with centers in step 2, and determine the closest center they belong, which forms new cluster.
Repeat step 3 until the centers' movements are less than the threshold.
Output the centers' locations.
Implementation:
class FireKClustering
{
private int m_clusters;
private List<Tile> m_gameMap;
private List<int> m_fireTiles;
private List<Vector3> m_fireTileWorldPos = new List<Vector3>();
private List<int> m_centroids = new List<int>(); // by tile index
private List<Vector3> m_centroidsWorldPos = new List<Vector3>();
private List<List<Vector3>> m_clusteredTiles = new List<List<Vector3>>();
public FireKClustering(List<Tile> p_gameMap, int k) // k means number of clusters
{
m_gameMap = p_gameMap;
m_clusters = k;
}
public List<Vector3> KClusteringRun()
{
while (true)
{
KClusteringAssign();
if (KClusteringUpdate())
{
break;
}
}
return m_centroidsWorldPos;
}
public bool KClusteringInit(Dictionary<int, int> p_fireTiles)
{
m_centroids.Clear();
m_clusteredTiles.Clear();
m_centroidsWorldPos.Clear();
m_fireTileWorldPos.Clear();
if (p_fireTiles.Count < m_clusters) return false;
m_fireTiles = p_fireTiles.Keys.ToList<int>();
foreach (int i in m_fireTiles)
{
m_fireTileWorldPos.Add(m_gameMap[i].getWorldPosition());
}
// Randomly select m_clusters data points as initial centroids
Random rnd = new Random();
HashSet<int> ints = new HashSet<int>();
while (true)
{
ints.Add(m_fireTiles[rnd.Next(0, m_fireTiles.Count)]);
if (ints.Count == m_clusters)
{
break;
}
}
for (int i = 0; i < ints.Count; i++)
{
m_centroids.Add(ints.ElementAt(i));
m_centroidsWorldPos.Add(m_gameMap[m_centroids[i]].getWorldPosition());
m_clusteredTiles.Add(new List<Vector3>());
}
return true;
}
public void KClusteringAssign()
{
// clear each list in m_clusteredTiles
for (int i = 0; i < m_clusters; i++)
{
m_clusteredTiles[i].Clear();
}
foreach (Vector3 v3 in m_fireTileWorldPos)
{
List<float> distanceToCentriods = new List<float>();
for (int i = 0; i < m_clusters; i++)
{
distanceToCentriods.Add(DistanceBetween(v3, m_centroidsWorldPos[i]));
}
int closest = distanceToCentriods.IndexOf(distanceToCentriods.Min());
m_clusteredTiles[closest].Add(v3);
}
}
public bool KClusteringUpdate()
{
List<Vector3> newCentroids = new List<Vector3>();
foreach (List<Vector3> cluster in m_clusteredTiles)
{
float sumX = 0.0f;
float sumZ = 0.0f;
foreach (Vector3 v3 in cluster)
{
sumX += v3.x;
sumZ += v3.z;
}
sumX /= (float)cluster.Count;
sumZ /= (float)cluster.Count;
newCentroids.Add(new Vector3(sumX, 0, sumZ));
}
for (int i = 0; i < m_clusters; i++)
{
if (DistanceBetween(newCentroids[i], m_centroidsWorldPos[i]) > 1.0f) // that's the threshold
{
// centroid has moved over the threshold, the clustering algorithm will continue
m_centroidsWorldPos = newCentroids;
return false;
}
}
// stabled
m_centroidsWorldPos = newCentroids;
return true;
}
public float DistanceBetween(Vector3 v1, Vector3 v2)
{
return Mathf.Sqrt((v1.x - v2.x) * (v1.x - v2.x) + (v1.z - v2.z) * (v1.z - v2.z));
}
}
}
Discussion and future improvement:
Discussion and future improvement:
The class can be changed to persistent, i.e. the data and centers will be saved between updates. When fire spreads out or is put off, tiles will be added/removed from its data. However, in our test, persistent K-Mean Clustering won't save execution time and will cause unwanted synchoronization issue. We did not apply this design.
It has a potential bug that when number of fire tiles is less than number of clusters. We prevent this bug by checking number of fire tiles before calling this algorithm.
It cannot change number of clusters on-the-fly.
Fire spread
Fire spread
public bool FireSpread()
{
// This function can be called by a timer from state machine.
Dictionary<int, int> fireTilesCopy = new Dictionary<int, int>(m_fireTiles); // copy constructor
HashSet<int> newFireTiles = new HashSet<int>();
foreach (KeyValuePair<int, int> kvp in fireTilesCopy)
{
if (kvp.Value != 3)
{
// fire grows up
m_fireTiles[kvp.Key] += 1;
}
else
{
int fireGroupIndex = -1;
for (int i = 0; i < m_fireGroups.Count; i++)
{
if (m_fireGroups[i].GetHashSet().Contains(kvp.Key))
{
fireGroupIndex = i;
break;
}
}
HashSet<int> result = AddTileToFire(m_tiles[kvp.Key].getWorldPosition(), 3);
newFireTiles.AddRange(result);
}
}
// deal with new tiles
return AddFire(newFireTiles.ToList<int>());
}
Discussion:
Discussion:
Fire has different "severity" and only highest severity will grow to adjacent tiles.
A hash set must be used to store the new fire tiles, otherwise one tile may catch fire twice and the severity will immediately reach maximum, and the game will be impossible to win.
It is not very efficient and can introduce more efficient data structures.
Page updated
Google Sites
Report abuse