提问人：bit_n 提问时间：11/7/2023 最后编辑：ravenspointbit_n 更新时间：11/10/2023 访问量：29
在关于组合元素的游戏中将图形数据结构应用于配方
Applying graph data structure to recipes in a game about combining elements
问：
我正在设计一款游戏，玩家将两种成分组合在一起，创造出一个新元素，然后可以将其用作成分来创造更多的成分。图结构似乎是与配方交互和分析的好方法，但是我想不出编码所有信息的结构。
关于我设计的食谱的一些说明： 它们总是涉及两种成分来创造产品。 两种基本成分可能是相同的成分，两次，一种产品可以有很多配方，一些配方可以有多种产品
一些示例配方来说明规则：
bird + bird = egg
metal + bird = airplane
metal + air = airplane
metal + sky = airplane
bird + engine = airplane
**but** sky + bird =/= airplane
我的第一个想法是，给定成分的产品将定向连接到父节点，但是这省略了其他父节点中的哪一个是组合在一起创建产品的特定父节点。
答：
0赞
ravenspoint
11/7/2023
#1
由于每种产品只需要两种成分，因此明显的数据结构是矩阵。
由于成分的顺序无关紧要，因此您只需要上三角形，包括前导对角线。
您将需要添加一个名为“nothing”的产品。
沿着列头和行头排列所有成分。
用列成分和行成分的乘积填充单元格，根据需要包括“无”。
| X | 金属 | 鸟 | 空气 | 天空 | 发动机 |
|---|---|---|---|---|---|
| 金属 | N | 飞机 | 飞机 | 飞机 | N |
| 鸟 | 蛋 | N | N | 飞机 | |
| 空气 | N | N | N | ||
| 天空 | N | N | |||
| 发动机 | N |
问题仍然是这是否是“最佳”数据结构。您的问题没有足够的细节来回答。这取决于您要对数据结构提出哪些查询。
该矩阵可以解释为无向图的邻接矩阵。这只有在你想问以下问题时才有用：从鸡蛋到飞机的最短路径是什么。我发现很难想象这样的问题意味着什么，所以我不认为图数据结构是要走的路。
0赞
Dillon Davis
11/10/2023
#2
这是您的食谱的另一种更一般的表示形式。考虑一个加权有向二分图，它由两种不同类型的顶点组成：配方顶点和产品顶点。从配方到产品的边缘表示该配方生产该产品。从产品到配方的边缘表示该特定配方需要该产品作为成分。边缘的重量表示产品在配方中消耗/生产的数量。
这当然是非常笼统的;您可以将任意数量的产品（甚至零）作为某些配方的成分，并且一个配方可以生产任意数量的产品。
此图表将使您能够回答以下问题：生产产品的最短链（最短路径搜索）、生产产品的总成分最少、您可以从某些起始成分生产哪些产品等。
评论