基本的连续2D地图探索(有障碍)算法
这里有一个问题:有一个大小从200*200像素到1000*1000像素的地图。每个像素的长度/宽度都是三分之一英寸。
地图有来自它的墙(可以是任何大小)，并且可以通过任何方式进行预处理。然而，当问题开始时，一个机器人(像素大小为18*18)被放置在一个未知位置，以及几个障碍物和一个目标，所有这些都位于未知位置。
如果机器人撞到任何墙/物体/目标，它会立即死亡。因此，它有一个简单的激光扫描仪，可以完美地看到它前面的一个80*80像素的正方形，以机器人为中心。
我已经解决了定位机器人并确定其在网格上的位置(在一个小误差内)的问题。我在制定一个好的算法来遍历整个地图直到找到目标时遇到了一些麻烦。
我的想法是让机器人移动到右下角，然后以某种方式从左向右扫射，避开障碍物和墙壁，直到找到目标，但我不确定有什么好方法可以做到这一点。
对于这样的事情，有没有合适的算法，或者有没有更好的算法来做我想做的事情？
回答 2
Stack Overflow用户
发布于 2016-02-05 06:44:31
您正在寻找寻路算法
一些建议包括"Flood Fill“算法或”Dijkstra‘s algorithm“与李的算法非常相似(我甚至可以说它们是相同的)，但这只是另一个可以搜索的术语
这可能是最流行的简单路径查找算法："A*search“(星形搜索)此链接还展示了其他一些路径查找算法。(另一个有用的link)。
*星级搜索的关键是你必须知道你在哪里(本地化)和目标在哪里。Dijkstra类型的算法能够在不事先知道目标位置的情况下找到目标。
Stack Overflow用户
发布于 2014-04-22 08:03:33
我脑海中浮现的唯一算法是一个简单的Lee算法。Here's是一个关于它做什么以及它是如何工作的相当不错的教程。
使用这个算法，你应该能够找到所有的障碍物，最终找到目标，你也会找到通向目标的最短路径。
唯一大的区别是你必须移动一个80x80的对象而不是1x1的对象，但我会让你处理你将实现这一点的方式。
https://stackoverflow.com/questions/23207910
复制相似问题
腾讯云开发者
