我试图从2D节点阵列创建一个邻接矩阵 . 邻接矩阵将被传递给将通过节点聚类的程序
-
光谱聚类算法
-
Kmeans聚类算法
节点类
public class Node{
public int _id;
public bool _isWalkable;
public int _positionX;
public int _positionY;
public Vector3 _worldPosition;
}
Grid Class
public class Grid : MonoBehaviour
{
void CreateGrid()
{
grid = new Node[_gridSizeX, _gridSizeY];
Vector3 worldBottomLeft = transform.position -
Vector3.right * worldSize.x / 2 - Vector3.forward * worldSize.y / 2;
//set the grid
int id = 0;
for (int x = 0; x < _gridSizeX; x++)
{
for (int y = 0; y < _gridSizeY; y++)
{
Vector3 worldPosition = worldBottomLeft + Vector3.right *
(x * _nodeDiameter + _nodeRadius) +
Vector3.forward * (y * _nodeDiameter + _nodeRadius);
//check to see if current position is walkable
bool isWalkable =
!Physics.CheckSphere(worldPosition, _nodeRadius, UnwalkableMask);
grid[x, y] = new Node(isWalkable, worldPosition, x, y);
grid[x, y].Id = id ++;
}
}
totalNodes = id;
}
}
节点存储在称为网格的2D数组中，表示要移动的角色的可行走路径 . 我已成功实现了具有欧氏距离启发式的A *算法 . 我想要做的是使用上述聚类算法聚类这些节点，但首先我需要为它们创建一个邻接算法 . 这是我能想到的最好的伪代码
int[][] _adjacencyMatrix = new int[gridSizeX*gridSizeY][gridSizeX*gridSizeY];
for(int x = 0; x < gridSize;x< XgridSize; i++)
{
for(int y = 0; y < gridSize;y< YgridSize; i++)
{
if( !Grid[x][y]._isWalkable)
continue;
Node n = Grid[x][y];
List<Node> neighbors = GetNeighbors(n);
for(int k; k<neighbors.Count(); k++)
{
_adjacencyMatrix[n._id][neighbors[k]._id]=1;
}
}
}
public List<Node> GetNeighbours(Node n)
{
//where is this node in the grid?
List<Node> neighbours = new List<Node>();
//this will search in a 3X3 block
for (int x = -1; x <= 1; x++)
{
for (int y = -1; y <= 1; y++)
{
if (x == 0 && y == 0)
continue; //we're at the current node
int checkX = n._positionX + x;
int checkY = n._positionY + y;
if (checkX >= 0 && checkX < _gridSizeX && checkY >= 0
&& checkY < _gridSizeY)
{
if(grid[checkX, checkY]._isWalkable)
neighbours.Add(grid[checkX, checkY]);
else
continue;
}
}
}
return neighbours;
}
My main concern
我主要担心的是上述算法的总体复杂性 . 感觉它会很重，我在邻接矩阵中总共有（75 ^ 2 = 5625）个节点，大小为5625X5625！找到邻居必须有比这更好的方法吗？
2 回答
矩阵是对称的，因此您只需要保存一半，请参阅（How to store a symmetric matrix?）作为示例 . 矩阵值是二进制的，因此将它们保存为布尔值或位向量将分别将内存减少4或32倍 .
或者，由于对两个相邻节点的检查需要一个恒定的时间（
abs(n1.x - n2.x) <= 1 && abs(n1.y - n1.y) <= 1 && grid[n1.x, n2.x].isWalkable() && grid[n2.x, n2.y]），因此您可以通过聚类算法传递一个在运行中检查邻接的函数 .5k乘5k并不是很大 . 100 MB是你可以留在内存中的东西 . 如果您想避免这种成本，请不要使用基于距离矩阵的算法！
但是，因为你的相似性似乎是
d（x，y）= 1如果相邻且两个节点都可以步行0
你的结果会退化 . 如果你很幸运，你会得到类似连接组件的东西（你可以更容易） . 成对最短路径将更有用，但构建起来也更昂贵 . 不过可能考虑先解决这个问题 . 我猜有一个完整的邻接矩阵是一个很好的起点 .
k-means根本无法使用成对距离 . 对于任意方式，它只需要点到均值的距离 .
在尝试将数据压缩到可能解决不同问题的聚类算法之前，我建议先查看图算法，并花更多时间了解您的目标 .