基本图形数据结构

本文关键字：数据结构 图形 | 更新日期: 2023-09-27 17:56:01

我正在尝试在Unity中编写一个简单的基于文本的游戏，玩家必须通过移动直接连接的"节点"，从他们的床"比如说"A"导航到出口"G"。以下是我试图优雅地捕获的信息示例：

A 直接连接到 B、C 和 DB 直接连接到 A 和 CC 直接连接到 A 和 BD 直接连接到 A 和 EE 直接连接到 F 和 GF与任何事物直接相关（比方说，游戏结束？G 直接连接到 E

所以我需要能够执行以下操作：1）存储一组节点2） 存储节点之间的连接，可能是单向的3）跟踪当前位置4）（锦上添花）随着游戏中发生的事情改变这些连接

我可以在头顶上创建的任何实现都无法很好地扩展到 1000 个节点。我应该如何解决这个问题？

基本图形数据结构

您可以查看各种图形数据结构。我建议您查看此线程中有关高效图形数据结构的信息性讨论：

https://softwareengineering.stackexchange.com/questions/148313/what-is-the-most-space-efficient-way-to-implement-a-graph-data-structure

它可能适合您的游戏目的的有效图形数据结构之一是使用邻接矩阵 https://en.wikipedia.org/wiki/Adjacency_matrix 因为您可能会发现在两个单元格之间移动角色或对象在游戏中经常发生。因此，邻接矩阵可帮助您非常快速地找到特定单元格的同级单元格。但是，此方法需要一些内存来存储图形中任何两个同级单元格之间的所有可能的邻接关系。

但是，如果您的图绝对是有向图，其中任何两个节点之间的所有连接都是单向的。您可能需要查看邻接列表 https://en.wikipedia.org/wiki/Adjacency_list，其中存储每个单元格中的邻接节点列表。因此，查找特定单元格的同级需要更少的时间。

您的问题与道路网络非常相似：

class Crossroad {
   List<Road> roadList = new List<Road>();
}
class Road {
   Crossroad start;
   Crossroad end;
   bool isOneWay;
}
class RoadNetwork {
   List<Crossroad> crossroadList = new List<Crossroad>();
   List<Road> roadList = new List<Road>();
   Crossroad currentCrossroad;
}

1）存储一组节点：RoadNetwork.crossroadList

2）存储节点之间的连接可能是单向的：类道路

3）跟踪当前位置：RoadNetwork.currentCrossroad

4）（锦上添花）随着游戏中发生的事情改变这些连接：您可以随时更改十字路口列表和道路列表。

相关文章：