I have been trying to implement the Wave Function Collapse(link) Algorithm in Unity using Best first search. For this I use various helper classes,namely:
Wave_Tiles.cs
using UnityEngine;
using UnityEngine.Tilemaps;
using System.Collections.Generic;
[CreateAssetMenu(menuName = "2D/Tiles/WaveFunctionTiles")]
public class Wave_Tiles : ScriptableObject
{
public bool ongroundtilemap;
public TileBase tiletoinstantiate;
public List<Wave_Tiles> up;
public List<Wave_Tiles> down;
public List<Wave_Tiles> left;
public List<Wave_Tiles> right;
}
This class stores the information for the tiles to use.The tiletoinstantiate is the actual tile that is to be put in the place and its valid neighbours are storedd in the respective lists.
Node.cs
using UnityEngine;
using UnityEngine.Tilemaps;
using System.Collections.Generic;
[System.Serializable]
public class Nodes
{
public bool iscollapsed;
public Vector3Int position;
public List<TileBase> ValidTiles;
public Nodes(Vector3Int pos)
{
position = pos;
ValidTiles = new List<TileBase>();
}
public Nodes(int x, int y)
{
position = new Vector3Int(x, y, 0);
ValidTiles = new List<TileBase>();
}
public TileBase coll(Tilemap ground)
{
if (iscollapsed)
return null;
iscollapsed = true;
TileBase tmp = null;
if (ValidTiles.Count > 0)
{
int rand = Random.Range(0, ValidTiles.Count);
ground.SetTile(position, ValidTiles[rand]);
tmp = ValidTiles[rand];
}
return tmp;
}
public override bool Equals(object obj)
{
if (obj == null)
return false;
if (obj is Nodes)
return Equals(obj as Nodes);
return false;
}
public override int GetHashCode()
{
return position.x ^ position.y;
}
public bool Equals(Nodes obj)
{
if (obj == null)
{
return false;
}
return (position.x == obj.position.x) && (position.y == obj.position.y);
}
}
This class is used to traverse the grid and stores the valid tiles for the position.The collapse function collapses on a random tile from the ValidTile List.
Wave_Func.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Tilemaps;
using System.Linq;
public class Wave_Func : MonoBehaviour
{
public bool working;
public float wait_time;
public Tilemap Grid;
public Vector2Int LimitsMin, LimitsMax;
public Nodes startNode;
WaitForSeconds wait;
public List<Wave_Tiles> Game_Tiles;
public List<Nodes> Openlist, ClosedList, openneighbour, closedneighbour;
private void Start()
{
StartCoroutine(wavefunccoll());
}
public IEnumerator wavefunccoll()
{
working = true;
wait = new WaitForSeconds(wait_time);
Openlist.Add(startNode);
yield return wait;
while (Openlist.Count > 0)
{
Nodes current = Openlist[0];
Openlist.Remove(current);
ClosedList.Add(current);
yield return wait;
yield return StartCoroutine(collapse(current));
Openlist = Openlist.OrderBy(a => a.ValidTiles.Count).ToList();
}
working = false;
}
IEnumerator collapse(Nodes current)
{
closedneighbour.Clear();
yield return null;
TileBase parenttofind = current.coll(Grid);
Wave_Tiles parent = null;
foreach (Wave_Tiles wtf in Game_Tiles)
if (wtf.tiletoinstantiate == parenttofind)
{
parent = wtf;
break;
}
if (parent != null)
foreach (Nodes neighbour in getneighbours(current, parent))
{
if (openneighbour.Contains(neighbour))
openneighbour.RemoveAll(item => item == neighbour);
openneighbour.Add(neighbour);
}
yield return null;
while (openneighbour.Count > 0)
{
current = openneighbour[0];
openneighbour.Remove(current);
closedneighbour.Add(current);
foreach (Wave_Tiles wtf in Game_Tiles)
if (wtf.tiletoinstantiate == parenttofind)
{
parent = wtf;
break;
}
yield return null;
foreach (Nodes neighbour in getneighbours(current))
{
if (openneighbour.Contains(neighbour))
openneighbour.RemoveAll(item => item == neighbour);
openneighbour.Add(neighbour);
}
}
foreach (Nodes neighbour in closedneighbour)
{
yield return null;
if (Openlist.Contains(neighbour))
Openlist.RemoveAll(item => item == neighbour);
Openlist.Add(neighbour);
}
}
List<Nodes> getneighbours(Nodes current, Wave_Tiles parent)
{
List<Nodes> neighbours = new List<Nodes>();
Vector3Int curpos;
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if ((i == 0 && j == 0) || (Mathf.Abs(i) + Mathf.Abs(j) == 2))
continue;
curpos = current.position + new Vector3Int(i, j);
if (curpos.x >= LimitsMax.x || curpos.x < LimitsMin.x || curpos.y >= LimitsMax.y || curpos.y < LimitsMin.y)
continue;
Nodes neighbour = new Nodes(curpos);
if (ClosedList.Contains(neighbour))
continue;
if (Openlist.Contains(neighbour))
neighbour = Openlist[Openlist.IndexOf(neighbour)];
List<TileBase> inter = null;
if (i == 1 && j == 0)
{
if (parent.right == null)
continue;
if (neighbour.ValidTiles.Count < 1)
{
foreach (Wave_Tiles wtf in parent.right)
neighbour.ValidTiles.Add(wtf.tiletoinstantiate);
}
else
{
inter = new List<TileBase>();
foreach (Wave_Tiles wtf in parent.right)
if (neighbour.ValidTiles.Contains(wtf.tiletoinstantiate))
inter.Add(wtf.tiletoinstantiate);
}
}
if (i == -1 && j == 0)
{
if (parent.left == null)
continue;
if (neighbour.ValidTiles.Count < 1)
{
foreach (Wave_Tiles wtf in parent.left)
neighbour.ValidTiles.Add(wtf.tiletoinstantiate);
}
else
{
inter = new List<TileBase>();
foreach (Wave_Tiles wtf in parent.left)
if (neighbour.ValidTiles.Contains(wtf.tiletoinstantiate))
inter.Add(wtf.tiletoinstantiate);
}
}
if (i == 0 && j == -1)
{
if (parent.down == null)
continue;
if (neighbour.ValidTiles.Count < 1)
{
foreach (Wave_Tiles wtf in parent.down)
neighbour.ValidTiles.Add(wtf.tiletoinstantiate);
}
else
{
inter = new List<TileBase>();
foreach (Wave_Tiles wtf in parent.down)
if (neighbour.ValidTiles.Contains(wtf.tiletoinstantiate))
inter.Add(wtf.tiletoinstantiate);
}
}
if (i == 0 && j == 1)
{
if (parent.up == null)
continue;
if (neighbour.ValidTiles.Count < 1)
{
foreach (Wave_Tiles wtf in parent.up)
neighbour.ValidTiles.Add(wtf.tiletoinstantiate);
}
else
{
inter = new List<TileBase>();
foreach (Wave_Tiles wtf in parent.up)
if (neighbour.ValidTiles.Contains(wtf.tiletoinstantiate))
inter.Add(wtf.tiletoinstantiate);
}
}
if (inter != null)
neighbour.ValidTiles = inter;
neighbours.Add(neighbour);
}
}
return neighbours;
}
List<Nodes> getneighbours(Nodes current)
{
List<Nodes> neighbours = new List<Nodes>();
Vector3Int curpos;
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if ((i == 0 && j == 0) || (Mathf.Abs(i) + Mathf.Abs(j) == 2))
continue;
curpos = current.position + new Vector3Int(i, j);
if (curpos.x >= LimitsMax.x || curpos.x < LimitsMin.x || curpos.y >= LimitsMax.y || curpos.y < LimitsMin.y)
continue;
Nodes neighbour = new Nodes(curpos);
if (ClosedList.Contains(neighbour) || closedneighbour.Contains(neighbour) || Openlist.Contains(neighbour))
continue;
if (openneighbour.Contains(neighbour))
neighbour = openneighbour[openneighbour.IndexOf(neighbour)];
neighbours.Add(neighbour);
}
}
return neighbours;
}
}
This class implements the main logic of the algorithm. So the startnode is populated with all the tiles from Game_Tiles and is added to the Openlist which runs a Best first Search and collapses the tile that has the least Count of ValidTiles. The collapse Function randomly choses a tile and "Collapses" the current tile after which it finds the rules for this tile and populates its neighbours' validlist and adds it to the openneighbour.
So my question is that Can I achieve the Wave function collapse using the above mentioned technique? If so could you please point out the problems with this script/technique and some ways to fix it.
Thanks in advance.