0

我在（非常少的）空闲时间制作了一个 roguelike。每个级别基本上都是几个由路径连接在一起的矩形房间。然而，我希望房间之间的路径看起来自然且多风。例如，我不会考虑以下自然外观：

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX

我真的想要更像这样的东西：

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX

这些路径必须满足一些属性：

  1. 我必须能够指定它们的边界区域，
  2. 我必须能够参数化它们的风和长度，
  3. 线条不应看起来像是从一条路径开始并在另一条路径结束。例如，上面的第一个例子看起来好像从 A 开始，在 B 结束，因为它基本上反复改变方向，直到它与 B 对齐，然后就直奔那里。

我希望使用 A*，但老实说，我不知道我的启发式方法是什么。我也考虑过使用遗传算法，但我不知道这种方法最终会有多实用。

我的问题是，什么是获得我想要的结果的好方法？请不要只指定“A*”或“Dijkstra 算法”之类的方法，因为我还需要一个好的启发式帮助。

4

3 回答 3

4

在你弄清楚如何产生路径之前，你必须找出一种更精确的方式来表达你想要的东西。一种方法是为每条路径分配一个分数，然后搜索高分路径。以下是一些需要考虑的问题：

  1. 你更喜欢长直跑还是短跑？您将如何量化这种偏好？（要使搜索算法收敛，如果您的评分函数是非线性的，则会更容易。）

  2. 如果您不想直接前往目的地，您可能需要奖励偏离主线的步骤。例如，在从 A 到 B 的路径上，考虑每个点，然后分三步计算点之间的方向。现在取那个方向和从 A 到 B 的直线方向的差的余弦。取反。对着你的行数为 -1，垂直的步数是中性的，离行数为 +1 的步数。

以下是一些很好的后续步骤：

  • 再想几个得分点子。
  • 用手画出十几条路径，并按照你喜欢它们的程度对它们进行排序。
  • 对于每条路径，手动创建几个小的变化。
  • 在所有路径上运行您的评分功能。继续摆弄，直到你得到一个喜欢你喜欢的评分功能。

然后，您将准备好考虑搜索算法。

于 2009-04-25T23:18:29.333 回答
1

我想说寻路在这里是错误的术语：通常涉及找到从 A 到 B 的有效路线，而您的问题不在于找到该路线，而在于创建适合您目的的路线。您正在故意创建次优路径，并且它们的质量将难以量化。所以我不认为具有任何启发式的搜索算法将是该问题的最佳解决方案。当您有一个强制性标准（一条工作路径）和一些模糊、未定义的标准（自然外观和曲折）时，最好从满足强制性要求开始，然后尝试将其转变为其他要求。这样你总有一些有用的东西。

我建议，鉴于您似乎更喜欢以直角转弯的水平和垂直路径，从 A 到 B 的直线 2 段路径开始。（带有曼哈顿距离启发式的 A* 可以为您找到这个，但它就像很容易自己一步出来）。然后沿两条线段之一和该线段的两个端点之一取一个随机点，并将线的该子段平行于自身移动一段随机距离。然后添加 2 个额外的线段，将线的新位置连接到旧连接点。您的第二个示例显示了该算法的一次迭代：如果 A 是 (0,0) 并且 B 是 (5, 7) 那么您随机选择了第二条线段（垂直线段），在 (0,5 ) 和 (5,5) 处的中点，然后将该部分向右推 3 个单位，然后将其重新连接起来。

于 2009-05-01T13:08:05.583 回答
0

这是一个想法——

从 A 开始，向随机方向移动——向左、向上或向下。每次移动后，滚动一个随机数以查看您是否转身。假设 75% 的时间你会继续朝同一个方向行驶，而 25% 的时间你会转向。转弯时，请始终朝靠近 B 的方向转弯。这意味着如果您向左或向右移动，则必须向上转，如果向上移动，请做出向右/向左选择根据您目前在目标的右侧或左侧的距离。此外，如果您到达世界边界之一，请转身！

这不应该太难编码。我有一种感觉，你只是想让这变得比它需要的更复杂......

于 2009-05-07T21:31:39.520 回答