根据 X 范围查找网格中的有效节点
我在根据中心点和最大范围查找网格中的 N 个位置时遇到问题。
我有这个网格，网格中的每个坐标都可以是闭合的或开放的，我绑定到，使用开放坐标，找到第一个周围有效的所有开放坐标，并且它们之间的行走范围等于或小于最大行走范围。
起初，我尝试了使用 A* 的解决方案，其中我将选择范围内的每个坐标，检查它们是否有效，如果有效，我会从它们调用 A* 到中心位置并计算步数（如果它们更高）超过我的最大范围，我只会从列表中删除坐标。当然，对于高于 3 的范围或具有多个坐标的网格来说，这确实很慢。 然后我尝试递归搜索坐标，从中心坐标开始，扩展并递归检查坐标有效性。该解决方案被证明是最有效的，除了在我的代码中，每个函数调用都重新检查已经检查过的坐标并返回重复的值。我以为我可以在函数调用之间共享“已检查”列表，但这只是破坏了我的代码，因为调用正在检查坐标并关闭它，即使它仍然有子节点但技术上不在它们的中心范围内（但在第一个中心的范围内）它会关闭它们并给出一些奇怪的结果。
最后，我的问题是，我该怎么做？我的做法有错吗？有更好的方法吗？
谢谢。
I'm having a problem with finding N positions in a grid based on a central point and a max range.
I have this grid, each coordinate in the grid can be either closed or open, I'm tying to, using an open coordinate, find all the open coordinates around the first that are valid and the walk range between then is equal or lower than the max walk range.
At first I tried a solution using A*, where I would select every coordinate in range, check if they were valid, if they were I would call A* from them to the center position and count the number of steps, if they were higher than my max range I would just remove the coordinate from my list. Of course, this is really is slow for ranges higher than 3, or grids with more than just a few coordinates.
Then I tried recursively searching for the coordinates, starting with the central one, expanding and recursively checking for the coordinates validness. That solution proved to be the most effective, except that in my code, each function call was rechecking coordinates that were already checked and returning repeated values. I thought I could just share the 'checked' list between the functions calls, but that just broke my code, since a call was checking a coordinate and closing it even if it still had child nodes but were technically not in range of their center (but were in range of the first center) it would close them and give some weird results.
Finally, my question is, how do I do that? Is my approach wrong? Is there a better way of doing it?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我曾经实施过类似的事情。您提出的简单递归解决方案对于较小的步行范围效果很好，但对于较大的值，执行时间会失控......
我通过实现 Dijkstra 算法的变体改进了这一点，该算法保留了您所说的访问节点的列表。但是，不要像对 A* 那样对到达的每个坐标运行完整路径搜索，而是如果 N 是您的行走范围，则执行算法的前 N 次迭代（维基百科上的 gif 可能会帮助您理解我的意思）。您访问的节点列表将是您正在寻找的可到达的图块。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
I've implemented something similar once. The simple recursive solution you proposed worked fine for small walk ranges, but execution time spun out of control for larger values ...
I improved this by implementing a variant of Dijkstra's algorithm, which keeps a list of visited nodes as you said. But instead of running a full path search for every coordinate in reach like you did with A*, do the first N iterations of the algorithm if N is your walk range (the gif on Wikipedia might help you understand what I mean). Your list of visited nodes will then be the reachable tiles you're looking for.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm