Below is my take on the problem, pretty much starting from scratch. Not thoroughly tested or optimized, but the overall logic should check out.
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public class GridTest : MonoBehaviour
{
private Dictionary<int, Edge> walkedEdges;
private Dictionary<int, Edge> pendingEdges;
private List<Polygon> polygons;
private Node currentNode;
private Edge currentEdge;
private Polygon currentPolygon;
private void Start()
{
walkedEdges = new Dictionary<int, Edge>();
pendingEdges = new Dictionary<int, Edge>();
polygons = new List<Polygon>();
CreateGrid();
FindPolygons();
}
private void FindPolygons()
{
do
{
currentEdge = DequeuePendingEdge();
currentPolygon = new Polygon(currentEdge);
AddWalkedEdge(currentEdge);
MoveToNextNode();
if (WalkEdges())
{
polygons.Add(currentPolygon);
currentPolygon.Draw(Color.red, 100);
}
}
while (pendingEdges.Count > 0);
}
private bool WalkEdges()
{
do
{
currentEdge = FindNextEdge();
if (currentEdge != null)
{
AddWalkedEdge(currentEdge);
currentPolygon.AddEdge(currentEdge);
MoveToNextNode();
}
}
while (currentEdge != null && !currentPolygon.IsClosed() && !currentPolygon.IsConcave());
return currentPolygon.IsClosed();
}
private Edge FindNextEdge()
{
Edge nextEdge = null;
int flippedID = currentEdge.Flip().ID;
List<Edge> candidates = new List<Edge>();
foreach (Node node in currentNode.Connected)
{
Edge edge = new Edge(currentNode, node);
bool isCurrent = edge.ID == flippedID;
if (!walkedEdges.ContainsKey(edge.ID) && !isCurrent)
{
candidates.Add(edge);
}
}
if (candidates.Count > 0)
{
float maxAngle = -180;
foreach (Edge edge in candidates)
{
float angle = currentEdge.GetAngle(edge);
if (angle >= maxAngle)
{
nextEdge = edge;
maxAngle = angle;
}
}
}
return nextEdge;
}
private void MoveToNextNode()
{
currentNode = currentEdge.EndNode;
}
private void AddWalkedEdge(Edge edge)
{
if (!walkedEdges.ContainsKey(edge.ID))
{
walkedEdges.Add(edge.ID, edge);
pendingEdges.Remove(edge.ID);
}
}
private Edge DequeuePendingEdge()
{
List<Edge> list = Enumerable.ToList(pendingEdges.Values);
Edge edge = list[0];
pendingEdges.Remove(edge.ID);
return edge;
}
private void CreateGrid(int xSize = 10, int zSize = 10)
{
Node[,] nodes = new Node[xSize, zSize];
for (int x = 0; x < xSize; x++)
{
for (int z = 0; z < zSize; z++)
{
Vector3 vertex = new Vector3(Displace(x), 0, Displace(z));
nodes[x, z] = new Node(vertex);
}
}
for (int x = 0; x < xSize; x++)
{
for (int z = 0; z < zSize; z++)
{
Node node = nodes[x, z];
do
{
if (RandomFlip() && x > 0)
{
node.ConnectNode(nodes[x - 1, z]);
}
if (RandomFlip() && x < xSize - 2)
{
node.ConnectNode(nodes[x + 1, z]);
}
if (RandomFlip() && z > 0)
{
node.ConnectNode(nodes[x, z - 1]);
}
if (RandomFlip() && z < zSize - 2)
{
node.ConnectNode(nodes[x, z + 1]);
}
}
while (node.Connected.Count == 0);
node.DrawConnections(Color.gray, 100);
}
}
for (int x = 0; x < xSize; x++)
{
for (int z = 0; z < zSize; z++)
{
Node node = nodes[x, z];
foreach (Node connected in node.Connected)
{
Edge edge = new Edge(node, connected);
pendingEdges.Add(edge.ID, edge);
}
}
}
}
private float Displace(int val, float randomness = 0.5f)
{
return val + Random.value * randomness - randomness * 0.5f;
}
private bool RandomFlip(float probability = 0.35f)
{
return probability > 0 && Random.value <= probability;
}
}
public class Node
{
public static int Count;
public int ID;
public Vector3 Vertex;
public List<Node> Connected;
public Node(Vector3 vertex)
{
ID = Count++;
Vertex = vertex;
Connected = new List<Node>();
}
public bool ConnectNode(Node node)
{
if (!Connected.Contains(node))
{
Connected.Add(node);
node.ConnectNode(this); // connections are always both ways
return true;
}
return false;
}
public void DrawConnections(Color color, float duration)
{
foreach (Node node in Connected)
{
Debug.DrawLine(Vertex, node.Vertex, color, duration);
}
}
}
public class Edge
{
public int ID;
public Node StartNode;
public Node EndNode;
public Vector3 Vector;
public Edge(Node start, Node end)
{
ID = GetID(start, end);
StartNode = start;
EndNode = end;
Vector = end.Vertex - start.Vertex;
}
public Edge Flip()
{
return new Edge(EndNode, StartNode);
}
public int GetID(Node start, Node end)
{
return start.ID * Node.Count + end.ID;
}
public float GetAngle(Edge edge)
{
return Vector3.SignedAngle(Vector, edge.Vector, Vector3.up);
}
public void Draw(Color color, float duration)
{
Debug.DrawLine(StartNode.Vertex, EndNode.Vertex, color, duration);
}
}
public class Polygon
{
private static int count;
public int ID;
public List<Edge> Edges;
public List<Node> Nodes;
private float windingAngle;
public Polygon(Edge startEdge)
{
ID = count++;
Edges = new List<Edge>() { startEdge };
Nodes = new List<Node>() { startEdge.StartNode };
}
public void AddEdge(Edge edge)
{
windingAngle += Vector3.SignedAngle(Edges[Edges.Count - 1].Vector, edge.Vector, Vector3.up);
Edges.Add(edge);
Nodes.Add(edge.StartNode);
}
public bool IsConcave(float threshold = -90)
{
return windingAngle <= threshold;
}
public bool IsClosed()
{
return Nodes[0].ID == Edges[Edges.Count - 1].EndNode.ID;
}
public Vector3 GetCentroid()
{
Vector3 vertex = Vector3.zero;
foreach (Node node in Nodes)
{
vertex += node.Vertex;
}
return vertex / (float)Nodes.Count;
}
public void Draw(Color color, float duration)
{
float offset = 0.05f;
List<Vector3> offsetVertices = new List<Vector3>();
Vector3 centroid = GetCentroid();
foreach (Node node in Nodes)
{
Vector3 dir = (centroid - node.Vertex).normalized;
offsetVertices.Add(node.Vertex + dir * offset);
}
int n = offsetVertices.Count - 1;
Debug.DrawLine(offsetVertices[n], offsetVertices[0], color, duration);
for (int i = 1; i <= n; i++)
{
Debug.DrawLine(offsetVertices[i - 1], offsetVertices[i], color, duration);
}
}
}
