我正在开展一个项目，我将在一个随机迷宫中有一个代理人，而这个迷宫没有退出 . 目标是让代理人探索迷宫并“记住”它的外观 . 一段时间后，我将在一个随机位置生成一个项目，只有在已经绘制出该给定区域时才会通知代理 . 代理将使用它生成的 Map 来确定项目的最短路径 .
我知道像A *这样的迷宫算法，但是这些算法需要一个开始和结束位置来停止遍历 . 这些算法不会“记住”迷宫看起来如何确定两点之间的最短路径 . 由于迷宫关闭，因此没有终点位置 . 我最初的想法是让代理人随机旅行并填写 Map 外观的二维数组，这对我来说似乎效率低下 . 任何想法都会很棒 .
1 回答
所以你将有两个步骤，探索和遍历 .
假设您已完全探索迷宫，那么当项目出现时，您可以使用目标为项目的A * .
要浏览 Map 并存储它，您可以创建适合 Map 的数据结构 . 例如，如果连接路径无关紧要且只有连接，则只需创建一个Node类，其中每个节点都有一个连接节点列表 . 最后，您可以开始广度优先搜索或深度优先搜索以探索整个 Map ，同时将信息存储在上述数据结构中 .
根据实际 Map ，探索算法可能更有效 . 我从深度优先开始，因为这听起来类似于我们人类对迷宫的方法 - 总是在十字路口转向同一方向！ （好的，dfs负责循环路径！）