1

我需要帮助编写一个有弹性的映射（图形构建）算法。这是问题所在：

想象一下，您有一个面向文本的虚拟现实 (TORG/MUD)，您可以在其中通过 telnet 发送移动命令（n、s、w、e、向上、向下、向内、向外……等）以将角色从房间移动到房间。并且服务器在每个移动步骤之后发回相应的房间描述。你的任务是生成一个表示底层地图结构的图形，这样你就可以在客户端简单地做一个 DFS 来弄清楚如何从一个房间到另一个房间。您还想设计系统，以便需要最少的用户输入

以下是假设：

  • 服务器上的底层图拓扑永远不会改变。

  • 房间描述不是唯一的。大多数房间都有不同的描述，但有些房间的描述完全相同。房间描述偶尔会稍作更改（几天或几周）

  • 你的移动可能会随机失败，概率很小，你会得到一个错误信息而不是新的房间描述，例如“你停下来等马车通过”，“门被锁上了”，你的角色仍然会在当前房间。

  • 您不能假设每次移动的单位空间距离。例如，您可能具有如下所示的拓扑，因此假设每个相邻房间的单位距离并为每个房间分配硬坐标是行不通的。但是，您可以假设相对方向是一致的，即沿 X（西，东）和 Y（南，北）的拓扑排序中不会有环。

  • 目标：给定您之前访问过的目的地，该算法保证最终将您移动到该位置，并且大部分时间会找到最短路径。错误是允许的，但算法应该能够即时检测和纠正错误。

示例图：

A--B---B
|      | <- k
C--D-E-F

我已经实现了一个非常简单的解决方案，可以记录房间描述并构建图表。以下是我的程序在 json 中生成的图形表示的示例。“出口”是映射到节点 ID 的移动方向。-1 表示未映射的房间。如果用户沿着某个方向行走并在图形表示中检测到 -1，则算法将尝试查找图形中已经存在的节点。如果找到具有相同描述的节点，它将提示用户判断新看到的房间是否是旧节点之一。如果没有，它会添加一个新节点并将其连接到图形。

"node": [
        {
            "description": "You are standing in the heart of the Example city. There is a fountain with large marble statue in it...",
            "exits": {
                "east": -1,
                "north": 31,
                "south": 574,
                "west": 42
            },
            "id": 0,
            "name": "cot",
            "tags": [],
            "title": "Center of Town",
            "title_color": "\u001b[1m\u001b[36m Center of Town\u001b[0;37;40m"
        },
        {
        ...

这个简单的解决方案在构建图形时需要人工输入检测循环。例如，在上图中，假设相同的字母代表相同的房间描述。如果您从第一个 B 开始映射，然后向左、向下、向右……直到您执行移动 k，现在您再次看到 B，但映射器无法确定它是否是它之前看到的 B。

简而言之，我希望能够编写一个弹性图构建算法，该算法在隐藏的目标图中行走（可能是无限的）并生成（并不断更新）一个可以（希望）与目标图相似的图。然后，我们使用生成的图来帮助在目标图中导航。是否有针对此类问题的现有算法？

我也想过将一些机器学习技术应用到这个问题上，但我无法写出具体的模型。我正在考虑为我们看到的每个房间（房间描述、出口、相邻节点）定义一个特征列表，每次我们看到一个房间时，我们都会尝试找到最适合特征的图形节点，并基于一些更新规则（如 Winnow 或 Perceptron）根据一些错误检测指标更新我们看到的描述。

任何想法/建议将不胜感激！

4

1 回答 1

0

许多 MU* 将为您提供一种获取房间唯一标识符的方法。（在 MUSH 及其分支上，就是think %L。）其他人可能会设置为以缩写形式描述您已经去过的房间。如果没有，你需要一些方法来确定你以前是否在一个房间里。一种简单的方法是计算每个房间的足够信息的哈希值，以获得唯一的密钥。但是，可能会故意设置一个迷宫来诱使您认为自己在不同的位置。 尤其是巫术，它的设计目的是让老派玩家在地图上绘制地牢时，当他们意识到他们的地图一定是错误的时候，他们会把头发扯掉，而Zork系列有一个谜题，当你在其他地方时，你为了标记你在迷宫中的位置而掉落的物体会四处移动。在实践中，编写工具来解决这些难题不太值得。

您应该能够记住所有对最短路径的表并更新它以匹配您在搜索新出口时探索的子图。这可以实现为N × N表，其中第i行、第j列告诉您从位置i到位置j的最短路径的下一步. 通常，对于有向图。即使每次运行 Dijkstra 算法就足够了，但实际上每次移动都会在地图上添加一个房间，并且不会在许多其他房间之间添加更短的路径。您会希望自动映射您已经去过的房间之间的连接（除非它们应该被隐藏），而不是强迫探索者繁琐地穿过每个单独的出口并返回查看它的去向。

如果您可以设计地图，您还可以布置区域以便在它们之间导航，然后您可以保持表格小：每个只需要包含您故意布置为迷宫的各个区域的地图探索。也就是说，如果你想从一个地牢到另一个地牢，你只需要查找最近的出口，然后在世界地图上查找地牢之间的方向，而不是一张随整个位置数二次增长的大桌子游戏。例如，如果您已将世界布置为嵌套层次结构，其中房间位于街道上的建筑物中，位于某个国家/地区的某个地区的城市附近的街道上，您可以将位置存储为一颗树，

我不确定使用神经网络等的机器学习在这里会有什么帮助；如果您正在寻找的技巧是看起来与您以前见过的房间相同的房间实际上是重复的，那么处理这种情况的方法是同时维护多个可能的地图假设表面上相同的房间是或不是重复的，一个分叉小径的花园。

于 2018-01-04T08:11:18.133 回答