二维网格可到达目的地
假设我有一个二维网格。寻路是我的问题的第二步。
我的事情是，假设我在网格中间有一个单元。我希望能够告诉用户“这些都是您可用的目的地。”。
根据该单位可以行走的方格数量，我想向用户展示“这些是您可以到达的所有方格”。然后找到用户选择的目的地。
进行首次搜索以显示可到达目的地的最佳方式是什么？
根据地形的不同，地形也可能有限制和奖励。
我不知道这叫什么，所以非常感谢有关在哪里查找或谷歌搜索什么的指示。
干杯! :)
/E
Let's say I have a 2d grid. Pathfinding is a secondary step in my problem.
My thing is, lets say I have a unit in the middle of the grid. I want to be able to tell the user "These are all your available destinations.".
Based on how many squares the unit can walk, I want to show the user, "these are all the squares you can reach." and then pathfind the destination the user picks.
What's the best way to do the first search to show the reachable destinations?
The terrain can also have limits och bonuses depending on terrain.
I don't know what this is called so pointers on where to look or what to google would be greatly appreciated.
Cheers! :)
/E
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
最好的方法可能是深度优先搜索（http://en.wikipedia.org/wiki/Depth_first_search），并限制你可以走多远。
The best way would probably be depth first search (http://en.wikipedia.org/wiki/Depth_first_search) with a limit on how far away you can go.
对于网格中的每个点，存储：
要计算此值，请执行广度优先搜索：
记住要注意，这样你如果有限制，则在正确的步骤数后停止搜索。
如果正确执行此操作，您可以找到所有可到达的点，找到它们的距离有多长，并且还可以获得可用的最短路径（尽管它是“向后”存储的）
不要对最短路径问题进行深度优先搜索！您可能会一遍又一遍地进行许多重复的计算。
（除非您使用更高级的启发式算法，例如 A* - 但无论如何您应该已经知道自己在做什么）
For each point in the grid, store:
To calculate this, do a breadth-first search:
Remember to pay atention so you stop the search after the correct number of steps if you have a limit.
If you do this correctly you can find all the reachable points, find how long their distance is and also have the shortest path available (although it is stored "backwards")
Don't do depth-first search for shortest-path problems! You will likely Do many repeated calculations over and over again.
(Unless you are using more advanced heuristic algorithms, such as A* - but then you should already know what you are doing anyway)
用相同的数字标记连接的单元格，用不同的数字标记未连接的单元格。您可以在 http://en.wikipedia.org/wiki/Connected_Component_Labeling 找到标记单元格的两遍算法。如果单元格数量不同，玩家将无法到达该位置。
Mark connected cells with same numbers and not connected with different. You may find a two pass algorithm for marking the cells at http://en.wikipedia.org/wiki/Connected_Component_Labeling . If the cells are different number, player can't reach that location.