专门的寻路方法？
我在（很少的）空闲时间里制作一款 Roguelike 游戏。 每个楼层基本上都是一些通过路径连接在一起的矩形房间。 然而，我希望房间之间的路径看起来自然且有风。 例如，我不会考虑以下自然外观：
B
X
X
X
XX
XX
XX
AXX
我真的想要更像这样的东西：
B
X
XXXX
X
X
X
X
AXXXXXXXX
这些路径必须满足一些属性：
- 我必须能够指定它们所包围的区域，
- 我必须能够参数化如何它们又风又长，
- 线路不应该看起来像从一条路径开始并在另一条路径结束。 例如，上面的第一个例子看起来好像是从 A 开始，到 B 结束，因为它基本上反复改变方向，直到与 B 对齐，然后径直走到那里。
我希望使用 A*，但老实说，我不知道我的启发法是什么。 我也考虑过使用遗传算法，但我不知道该方法最终有多实用。
我的问题是，获得我想要的结果的好方法是什么？ 请不要只指定“A*”或“Dijkstra 算法”之类的方法，因为我还需要良好启发式的帮助。
I am working on a roguelike in my (very little) free time. Each level will basically be a few rectangular rooms connected together by paths. I want the paths between rooms to be natural-looking and windy, however. For example, I would not consider the following natural-looking:
B
X
X
X
XX
XX
XX
AXX
I really want something more like this:
B
X
XXXX
X
X
X
X
AXXXXXXXX
These paths must satisfy a few properties:
- I must be able to specify an area inside which they are bounded,
- I must be able to parameterize how windy and lengthy they are,
- The lines should not look like they started at one path and ended at the other. For example, the first example above looks as if it started at A and ended at B, because it basically changed directions repeatedly until it lined up with B and then just went straight there.
I was hoping to use A*, but honestly I have no idea what my heuristic would be. I have also considered using a genetic algorithm, but I don't know how practical that method might end up.
My question is, what is a good way to get the results I want? Please do not just specify a method like "A*" or "Dijkstra's algorithm," because I also need help with a good heuristic.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在弄清楚如何生成路径之前，您必须找出一种更精确的方法来表达您想要的内容。 一种方法是为每条路径分配一个分数，然后搜索高分路径。 以下是一些需要考虑的问题：
您是否更喜欢长直跑而不是短直跑？ 您将如何量化这种偏好？ （为了使搜索算法收敛，如果您的评分函数是非线性的，则会更容易。）
如果您不想直接到达目的地，您可能需要奖励偏离主线的步骤。 例如，在从 A 到 B 的路径上，考虑每个点，然后采取三步并计算点之间的方向。 现在取该方向与从 A 到 B 的直线方向之差的余弦。将其取反。 线上的步数为 -1 对你不利，垂直的步数为中性，远离线的步数为你 +1。
以下是一些不错的后续步骤：
然后您就可以考虑搜索算法了。
Before you can figure out how to produce paths, you have to figure out a more precise way to state what you want. One way to do this is assign each path a score, then search for high-scoring paths. Here are some questions to consider:
Do you prefer long straight runs to short ones? How will you quantify this preference? (To get a search algorithm to converge, it will be easier if your scoring function is nonlinear.)
If you want not to go straight to your destination, you may want to reward steps that are off the main line. For example, on the path from A to B, consider each point, then take three steps and compute the direction between points. Now take the cosine of the difference of that direction and the direction straight from A to B. Negate it. Steps on the line count -1 against you, steps perpendicular are neutral, and steps away from the line count +1 for you.
Here are some good next steps:
Then you'll be ready to think about search algorithms.
我想说寻路在这里是错误的术语：通常涉及找到从 A 到 B 的有效路线，而您的问题不是找到该路线，而是创建适合您目的的路线。 您故意创建次优路径，并且它们的质量将难以量化。 所以我不认为具有任何启发式的搜索算法是解决该问题的最佳方案。 当您有一个强制性标准（工作路径）和一些模糊的、未定义的标准（自然外观和蜿蜒）时，最好从满足强制性要求开始，并尝试将其转变为其他要求。 这样你就总能找到有用的东西。
我建议，考虑到您似乎更喜欢以直角转弯的水平和垂直路径，从从 A 到 B 的直线 2 段路径开始。（带有曼哈顿距离启发式的 A* 可以为您找到这一点，但它就像很容易自己走出去）。 然后沿着两个线段之一和该线段的两个端点之一取一个随机点，并将该线段与其自身平行移动一段随机距离。 然后添加 2 条额外的线段，将线的新位置连接到旧的连接点。 您的第二个示例显示了该算法的一次迭代：如果 A 是 (0,0) 并且 B 是 (5, 7) 那么您随机选择了第二条线段（垂直线段），在 (0,5 ) 和 (5,5) 处的中点，并将该部分向右推 3 个单位，然后再将其重新连接起来。
I would say pathfinding is the wrong term here: usually that involves finding a valid route from A to B, and your problem is not the finding of that route but in creating routes to suit your purpose. You are deliberately creating sub-optimal paths and their quality will be hard to quantify. So I don't think a search algorithm with any heuristic would be the best solution for the problem. When you have one mandatory criterion (a working path) and some fuzzy, undefined criteria (natural-looking and winding), it's best to start out by meeting the mandatory requirements and attempt to mutate it towards the other requirements. That way you always have something that works.
I suggest, given that you seem to prefer horizontal and vertical paths turning at right angles, to start off with a straight, 2 segment path from A to B. (A* with Manhattan distance heuristic can find this for you, but it's just as easy to step it out yourself). Then take a random point along one of the two segments and one of the two end points for that segment, and move that subsection of the line parallel to itself by some random distance. Then add the 2 extra line segments to join the new position of the line to the old connection points. Your second example shows one iteration of this algorithm: if A is (0,0) and B is (5, 7) then you have picked the 2nd line segment (the vertical one) at random, picked the endpoint at (0,5) and a midpoint at (5,5), and pushed that section to the right by 3 units, before joining it back up.
这里有一个想法——
从 A 开始，向随机方向移动——向左、向上或向下。 每次移动后，滚动一个随机数字，看看你是否转身。 假设 75% 的时间您会继续朝同一方向行驶，25% 的时间您会掉头。 当你转弯时，总是朝靠近 B 的方向转弯。这意味着，如果你向左或向右移动，你就必须向上移动，如果你向上移动，请做出向右/向左的选择基于您当前距离目标左侧或右侧有多远。 另外，如果您触及世界边界之一，请转身！
编码应该不会太难。 我有一种感觉，你只是想让事情变得比需要的更复杂......
Here's an idea ---
Start at A and make a move in a random direction -- left, up, or down. After each move, roll a random number to see if you turn. Lets say that 75% of the time you keep traveling in the same direction, and 25% of the time you'll turn. When you turn, always turn in a direction that leads closer to B. That will mean that if you're moving left or right, you'll have to turn up, and if you're moving up, make a right/left choice based on how far you currently are to the right or left of the goal. Also, if you hit one of the world boundaries, turn!
That shouldn't be too difficult to code. I have a feeling you're just trying to make this more complicated than it needs to be...