从具有连接要求的预定义元素生成有向无环图
Generating a directed acyclic graph from predefined elements with connection requirements
我正在研究一个系统，当给定一组不同类型的元素时，将创建一个连接部分或所有元素的有向无环图。每个元素都有一些输入 A 和输出 B。在构建图形时，系统需要确保前一个节点的输出与当前节点的输入相匹配。
节点的输入和输出是为了确保只连接某些类型的元素
元素看起来像这样
ElementName : Input -> Output
可能有多个 inputs/output，或者没有输出（见下文）。
One : X -> Y
Two : Y -> Z,F
Three : Y, Z -> W
Four : Z -> F
Five : F -> NULL
注：
我们正在谈论很多不同的元素，现在大约有 30 个，但计划随着时间的推移添加更多。
这是程序生成叙事项目的一部分。节点是个人任务。输入是您开始任务所需要的。输出是如何影响故事状态的。
问题：
我见过几种不同的生成随机 DAG 的方法，而不是根据一些预设连接要求（具有连接它们的规则）制作 DAG 的方法。
我还想要一些限制图形复杂性的方法。即限制他们可以拥有的分支数量。
我想要的想法：
你的垃圾箱里有一堆不同类型的乐高积木，比如 30 个。你有连接乐高积木的规则。
Blue -> Red
Blue -> White
Red -> Yellow
Yellow -> Green/Brown
Brown -> Blue
众所周知，每个乐高除了一个颜色外还有一个shape.So 2个蓝色乐高可能不是同一种乐高。所以我们的目标是建立一个符合我们规则的大型结构。即使有我们的规则，我们仍然可以将乐高积木连接成一堆不同的结构。
P.S. 我希望这不是一个笼统的问题。如果是，请记下，我会尽量使其更具体。
听起来 L-system（又名 Lindenmayer 系统）方法可行：
- 您的 collection 乐高积木类似于符号字母表
- 您的连接规则对应于 collection 产生式规则，将每个符号扩展为更大的符号串
- 您的起始乐高代表开始构建的初始 "axiom" 字符串
- 生成的几何结构就是您的 DAG
最简单的方法类似于：给定一个乐高积木，随机 select 一个有效的连接规则并将一个新的乐高积木添加到 DAG。从那里您可以根据需要添加更多的复杂性。如果您需要调整随机 selection 以支持某些规则，您实际上是在构建 stochastic grammar. If the selection of a rule depends on previously generated parts of the DAG it's a type of context sensitive grammar.
Graph rewriting，通过算法从基础图创建一个新图，可能是一个更直白的解决方案，但我个人发现 L-systems 更容易内化并且研究它们会产生并非如此的结果过于自然 academic/theoretical。
L-systems本身就是formal grammars的一个类别。可能值得研究其中的一些相关想法，但很容易（至少对我而言）以牺牲核心开发为代价而被理论内容所牵制。[=14=]
我正在研究一个系统，当给定一组不同类型的元素时，将创建一个连接部分或所有元素的有向无环图。每个元素都有一些输入 A 和输出 B。在构建图形时，系统需要确保前一个节点的输出与当前节点的输入相匹配。
节点的输入和输出是为了确保只连接某些类型的元素
元素看起来像这样
ElementName : Input -> Output
可能有多个 inputs/output，或者没有输出（见下文）。
One : X -> Y
Two : Y -> Z,F
Three : Y, Z -> W
Four : Z -> F
Five : F -> NULL
注：
我们正在谈论很多不同的元素，现在大约有 30 个，但计划随着时间的推移添加更多。
这是程序生成叙事项目的一部分。节点是个人任务。输入是您开始任务所需要的。输出是如何影响故事状态的。
问题：
我见过几种不同的生成随机 DAG 的方法，而不是根据一些预设连接要求（具有连接它们的规则）制作 DAG 的方法。 我还想要一些限制图形复杂性的方法。即限制他们可以拥有的分支数量。
我想要的想法：
你的垃圾箱里有一堆不同类型的乐高积木，比如 30 个。你有连接乐高积木的规则。
Blue -> Red
Blue -> White
Red -> Yellow
Yellow -> Green/Brown
Brown -> Blue
众所周知，每个乐高除了一个颜色外还有一个shape.So 2个蓝色乐高可能不是同一种乐高。所以我们的目标是建立一个符合我们规则的大型结构。即使有我们的规则，我们仍然可以将乐高积木连接成一堆不同的结构。
P.S. 我希望这不是一个笼统的问题。如果是，请记下，我会尽量使其更具体。
听起来 L-system（又名 Lindenmayer 系统）方法可行：
- 您的 collection 乐高积木类似于符号字母表
- 您的连接规则对应于 collection 产生式规则，将每个符号扩展为更大的符号串
- 您的起始乐高代表开始构建的初始 "axiom" 字符串
- 生成的几何结构就是您的 DAG
最简单的方法类似于：给定一个乐高积木，随机 select 一个有效的连接规则并将一个新的乐高积木添加到 DAG。从那里您可以根据需要添加更多的复杂性。如果您需要调整随机 selection 以支持某些规则，您实际上是在构建 stochastic grammar. If the selection of a rule depends on previously generated parts of the DAG it's a type of context sensitive grammar.
Graph rewriting，通过算法从基础图创建一个新图，可能是一个更直白的解决方案，但我个人发现 L-systems 更容易内化并且研究它们会产生并非如此的结果过于自然 academic/theoretical。
L-systems本身就是formal grammars的一个类别。可能值得研究其中的一些相关想法，但很容易（至少对我而言）以牺牲核心开发为代价而被理论内容所牵制。[=14=]