将网格 N*N 存储到邻接图中？位置和邻居
Store Grid N*N into an Adjacency Graph? Position and Neighbors
再次更新此 post。
这次是为了让事情更清楚。
我正在尝试在大小为 9x9 的 Grid 中进行解析，但是这个大小会随着时间的推移而改变，它不是固定的。这是一款名为 Quoridor 的棋盘游戏。我可以使用的是 Board class。这为我提供了以下 horizontal bool[,] 和 vertical bool[,]，我可以遍历每个并打印出 x, y 位置。但是这些不同，取决于它是水平方向，还是垂直方向和位置.
玩家只能向北、向南、向西或向东移动一步。另一个玩家（人类）可以放置一堵墙（障碍物），水平或垂直覆盖两个方块。我的自动播放器必须从棋盘构建一个节点图，并根据棋盘上的变化和它自己的位置刷新图。例如，如果玩家不能从当前位置向左移动，则连接两个节点的边将被删除，只有在障碍物引起的情况下。然后 BFS 将 运行 再次针对图形和 return 这个（自动）玩家使用并执行其移动的新位置 (x, y)。
9x9 网格 上的每个方块将代表Graph 中的一个 Node。这意味着 Graph 中的 顶点或节点数 List 将是 9x9=81。每个 Nodes 持有 size 4 的 list 或 2D array 代表 North, South[=86] =]、West 和 East 可能是 bool 类型。
现在，我提供了我编写的 Graph class 的示例代码以及 Node class。我希望这里的最新信息能说明问题。我已经实现了BFS算法。但这部分是我无法正确理解的。我看了这个视频是为了一些想法：https://www.youtube.com/watch?v=KiCBXu4P-2Y
代码
class Graph<T>
{
private int _V;
private List<T>[] _Nodes;
public Graph(int v)
{
_V = v;
_Nodes = new List<T>[v];
for (int i = 0; i < _Nodes.Length; i++)
_Nodes [i] = new List<T>();
}
public IEnumerable<T> Nodes(int v) { return (IEnumerable<T>)_Nodes[v];}
public int V { get => _V; }
public bool EdgeExists(){}
public void AddEdge(Node n, T u, T w){}
public void RemoveEdge(){}
}
并且，
class Node<T>
{
private int _E;
private List<T>[] _Adj;
public Node(int e)
{
_E = e;
_Adj = new List<T>[e];
for (int i = 0; i < _Adj.Length; i++)
_Adj [e] = new List<T>();
}
public IEnumerable<T> Adj(int e) { return (IEnumerable<T>)_Adj[e];}
public int E { get => _E; }
public void AddEdge(Node n, T u, T w){}
public void RemoveEdge(T value){}
}
我阅读了以下 SO 线程：
- How can you make an adjacency matrix which would emulate a 2d grid
- Implementing 2D Grid Network ( Graph ) and Adjacency Matrix of it in C
- How can I build a graph from a 2D array?
- https://docs.microsoft.com/en-us/previous-versions/ms379574(v=vs.80)?redirectedfrom=MSDN
根据你所说的，我对你的问题的理解是：
如何处理像 (x=0,y=0)、(x=9,y=5) 或 (x=9.y=9) 这样的边缘节点......
你应该处理8个案例
对于左上角的情况，节点只有 2 个邻居，因此将顶部和左侧的邻居设置为 Null
这是构建与二维数组具有相同布局的邻接矩阵的一种方法：
internal record Graph
{
public List<Node> Nodes { get; set; }
public Graph(int numberOfTiles)
{
var matrixSize = (int)Math.Sqrt(numberOfTiles);
var rows = matrixSize;
var columns = matrixSize;
var nodes = new Node[rows, columns];
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
nodes[row, column] = new Node(row, column);
}
}
Nodes = new List<Node>(rows * columns);
foreach (var node in nodes)
{
var row = node.Row;
var column = node.Column;
if (row > 0) node.West = nodes[row - 1, column];
if (column > 0) node.North = nodes[row, column - 1];
if (row < rows - 1) node.East = nodes[row + 1, column];
if (column < columns - 1) node.South = nodes[row, column + 1];
Nodes.Add(node);
}
}
}
internal record Node
{
public int Row { get; }
public int Column { get; }
public Node[] Neighbors { get; } = new Node[4];
public Node North
{
get => Neighbors[0];
set => Neighbors[0] = value;
}
public Node East
{
get => Neighbors[1];
set => Neighbors[1] = value;
}
public Node South
{
get => Neighbors[2];
set => Neighbors[2] = value;
}
public Node West
{
get => Neighbors[3];
set => Neighbors[3] = value;
}
public Node(int row, int column)
{
Row = row;
Column = column;
}
}
这适用于 BFS。 Edges/boundaries 由节点的邻居定义 null.To 创建边，只需将适当的邻居设置为空。例如创建一条水平边，设置西节点的东邻为空，东节点的西邻为空。
如果我们有一个 9x9 方阵，我们可以执行以下操作：第一步，用所有节点填充图形节点列表。第二步，制作一个循环来处理邻居。如果我们说节点在图的中间，那么 currentNode.LeftNode = NodeList[currentNodePosition-1] currentNode.RightNode = NodeList[currentNodePosition+1] currentNode.TopNode = NodeList[currentNodePosition+9] currentNode.BottomNode = NodeList[currentNodePosition-9]。正如我之前所说，您应该处理上图中的空情况。希望你明白我的意思
要将排列在二维网格中的节点（以及关联数据）存储到邻接图中，我更喜欢分三步进行操作。
1 将节点数据读入二维向量
2 向图中添加节点 class
2 扫描向量，在相邻节点之间添加 links 到图形 class
让我们假设输入是一个文本文件，其中节点数据排列在 space 分隔的原醇行中（由 'o' 指示）。对于 3 x 3，它可能看起来像这样
o 1 2 3
o 2 5 2
o 3 2 1
一些 C++ 代码将其读入向量
std::vector<std::vector<float>> grid;
int RowCount = 0;
int ColCount = -1;
int start = -1;
int end = -1;
std::string line;
while (std::getline(myFile, line))
{
std::cout << line << "\n";
auto token = ParseSpaceDelimited(line);
if (!token.size())
continue;
switch (token[0][0])
{
case 'o':
{
if (ColCount == -1)
ColCount = token.size() - 1;
else if (token.size() - 1 != ColCount)
throw std::runtime_error("Bad column count");
std::vector<float> row;
for (int k = 1; k < token.size(); k++)
row.push_back(atof(token[k].c_str()));
grid.push_back(row);
}
... other cases if needed to parse other kinds of input data
现在我们可以将节点添加到图中 class。我有一个方便的方法 ( orthogonalGridNodeName ) 为位于网格
上的节点提供人类可读的名称
cGraph myFinder;
RowCount = grid.size();
// add nodes at each grid cell
for (int row = 0; row < RowCount; row++)
{
for (int col = 0; col < ColCount; col++)
{
int n = myFinder.findoradd(
orthogonalGridNodeName(row, col));
// TODO: add data for this node from grid
}
}
现在我们应该能够在节点之间添加 links。这里我假设每个 link 的成本为 1.
// link cells orthogonally
for (int row = 0; row < RowCount; row++)
for (int col = 0; col < ColCount; col++)
{
int n = row * ColCount + col;
if (fDirected)
{
if (col > 0)
{
int left = row * ColCount + col - 1;
myFinder.addLink(n, left, 1);
}
}
if (col < ColCount - 1)
{
int right = row * ColCount + col + 1;
myFinder.addLink(n, right, 1);
}
if (fDirected)
{
if (row > 0)
{
int up = (row - 1) * ColCount + col;
myFinder.addLink(n, up, 1);
}
}
if (row < RowCount - 1)
{
int down = (row + 1) * ColCount + col;
myFinder.addLink(n, down, 1);
}
}
我认为这应该很容易移植到 C#
再次更新此 post。
这次是为了让事情更清楚。
我正在尝试在大小为 9x9 的 Grid 中进行解析，但是这个大小会随着时间的推移而改变，它不是固定的。这是一款名为 Quoridor 的棋盘游戏。我可以使用的是 Board class。这为我提供了以下 horizontal bool[,] 和 vertical bool[,]，我可以遍历每个并打印出 x, y 位置。但是这些不同，取决于它是水平方向，还是垂直方向和位置.
玩家只能向北、向南、向西或向东移动一步。另一个玩家（人类）可以放置一堵墙（障碍物），水平或垂直覆盖两个方块。我的自动播放器必须从棋盘构建一个节点图，并根据棋盘上的变化和它自己的位置刷新图。例如，如果玩家不能从当前位置向左移动，则连接两个节点的边将被删除，只有在障碍物引起的情况下。然后 BFS 将 运行 再次针对图形和 return 这个（自动）玩家使用并执行其移动的新位置 (x, y)。
9x9 网格 上的每个方块将代表Graph 中的一个 Node。这意味着 Graph 中的 顶点或节点数 List 将是 9x9=81。每个 Nodes 持有 size 4 的 list 或 2D array 代表 North, South[=86] =]、West 和 East 可能是 bool 类型。
现在，我提供了我编写的 Graph class 的示例代码以及 Node class。我希望这里的最新信息能说明问题。我已经实现了BFS算法。但这部分是我无法正确理解的。我看了这个视频是为了一些想法：https://www.youtube.com/watch?v=KiCBXu4P-2Y
代码
class Graph<T>
{
private int _V;
private List<T>[] _Nodes;
public Graph(int v)
{
_V = v;
_Nodes = new List<T>[v];
for (int i = 0; i < _Nodes.Length; i++)
_Nodes [i] = new List<T>();
}
public IEnumerable<T> Nodes(int v) { return (IEnumerable<T>)_Nodes[v];}
public int V { get => _V; }
public bool EdgeExists(){}
public void AddEdge(Node n, T u, T w){}
public void RemoveEdge(){}
}
并且，
class Node<T>
{
private int _E;
private List<T>[] _Adj;
public Node(int e)
{
_E = e;
_Adj = new List<T>[e];
for (int i = 0; i < _Adj.Length; i++)
_Adj [e] = new List<T>();
}
public IEnumerable<T> Adj(int e) { return (IEnumerable<T>)_Adj[e];}
public int E { get => _E; }
public void AddEdge(Node n, T u, T w){}
public void RemoveEdge(T value){}
}
我阅读了以下 SO 线程：
- How can you make an adjacency matrix which would emulate a 2d grid
- Implementing 2D Grid Network ( Graph ) and Adjacency Matrix of it in C
- How can I build a graph from a 2D array?
- https://docs.microsoft.com/en-us/previous-versions/ms379574(v=vs.80)?redirectedfrom=MSDN
根据你所说的，我对你的问题的理解是： 如何处理像 (x=0,y=0)、(x=9,y=5) 或 (x=9.y=9) 这样的边缘节点...... 你应该处理8个案例
对于左上角的情况，节点只有 2 个邻居，因此将顶部和左侧的邻居设置为 Null
这是构建与二维数组具有相同布局的邻接矩阵的一种方法：
internal record Graph
{
public List<Node> Nodes { get; set; }
public Graph(int numberOfTiles)
{
var matrixSize = (int)Math.Sqrt(numberOfTiles);
var rows = matrixSize;
var columns = matrixSize;
var nodes = new Node[rows, columns];
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
nodes[row, column] = new Node(row, column);
}
}
Nodes = new List<Node>(rows * columns);
foreach (var node in nodes)
{
var row = node.Row;
var column = node.Column;
if (row > 0) node.West = nodes[row - 1, column];
if (column > 0) node.North = nodes[row, column - 1];
if (row < rows - 1) node.East = nodes[row + 1, column];
if (column < columns - 1) node.South = nodes[row, column + 1];
Nodes.Add(node);
}
}
}
internal record Node
{
public int Row { get; }
public int Column { get; }
public Node[] Neighbors { get; } = new Node[4];
public Node North
{
get => Neighbors[0];
set => Neighbors[0] = value;
}
public Node East
{
get => Neighbors[1];
set => Neighbors[1] = value;
}
public Node South
{
get => Neighbors[2];
set => Neighbors[2] = value;
}
public Node West
{
get => Neighbors[3];
set => Neighbors[3] = value;
}
public Node(int row, int column)
{
Row = row;
Column = column;
}
}
这适用于 BFS。 Edges/boundaries 由节点的邻居定义 null.To 创建边，只需将适当的邻居设置为空。例如创建一条水平边，设置西节点的东邻为空，东节点的西邻为空。
如果我们有一个 9x9 方阵，我们可以执行以下操作：第一步，用所有节点填充图形节点列表。第二步，制作一个循环来处理邻居。如果我们说节点在图的中间，那么 currentNode.LeftNode = NodeList[currentNodePosition-1] currentNode.RightNode = NodeList[currentNodePosition+1] currentNode.TopNode = NodeList[currentNodePosition+9] currentNode.BottomNode = NodeList[currentNodePosition-9]。正如我之前所说，您应该处理上图中的空情况。希望你明白我的意思
要将排列在二维网格中的节点（以及关联数据）存储到邻接图中，我更喜欢分三步进行操作。
1 将节点数据读入二维向量 2 向图中添加节点 class 2 扫描向量，在相邻节点之间添加 links 到图形 class
让我们假设输入是一个文本文件，其中节点数据排列在 space 分隔的原醇行中（由 'o' 指示）。对于 3 x 3，它可能看起来像这样
o 1 2 3
o 2 5 2
o 3 2 1
一些 C++ 代码将其读入向量
std::vector<std::vector<float>> grid;
int RowCount = 0;
int ColCount = -1;
int start = -1;
int end = -1;
std::string line;
while (std::getline(myFile, line))
{
std::cout << line << "\n";
auto token = ParseSpaceDelimited(line);
if (!token.size())
continue;
switch (token[0][0])
{
case 'o':
{
if (ColCount == -1)
ColCount = token.size() - 1;
else if (token.size() - 1 != ColCount)
throw std::runtime_error("Bad column count");
std::vector<float> row;
for (int k = 1; k < token.size(); k++)
row.push_back(atof(token[k].c_str()));
grid.push_back(row);
}
... other cases if needed to parse other kinds of input data
现在我们可以将节点添加到图中 class。我有一个方便的方法 ( orthogonalGridNodeName ) 为位于网格
上的节点提供人类可读的名称 cGraph myFinder;
RowCount = grid.size();
// add nodes at each grid cell
for (int row = 0; row < RowCount; row++)
{
for (int col = 0; col < ColCount; col++)
{
int n = myFinder.findoradd(
orthogonalGridNodeName(row, col));
// TODO: add data for this node from grid
}
}
现在我们应该能够在节点之间添加 links。这里我假设每个 link 的成本为 1.
// link cells orthogonally
for (int row = 0; row < RowCount; row++)
for (int col = 0; col < ColCount; col++)
{
int n = row * ColCount + col;
if (fDirected)
{
if (col > 0)
{
int left = row * ColCount + col - 1;
myFinder.addLink(n, left, 1);
}
}
if (col < ColCount - 1)
{
int right = row * ColCount + col + 1;
myFinder.addLink(n, right, 1);
}
if (fDirected)
{
if (row > 0)
{
int up = (row - 1) * ColCount + col;
myFinder.addLink(n, up, 1);
}
}
if (row < RowCount - 1)
{
int down = (row + 1) * ColCount + col;
myFinder.addLink(n, down, 1);
}
}
我认为这应该很容易移植到 C#