如何随机生成窄路径？

Question

我正在编写一个示例游戏，其中一个方块永远掉落，您需要将它从一边转向另一边。如果你撞墙，你就输了。我正在尝试随机并不断地生成关卡，因此总有一条路可以通过，因此路径会逐渐变窄。

#       #
#       #
#      ##
#     ###
#    ####
#   #####
##  #####
##  #####
##   ####
###  ####
###   ###
####  ###
####  ###
###   ###
###   ###
##   ####
##   ####
##  #####
##  #####
## ######
## ######
## ######
## ######

我目前的方法是有一组可能的路径，然后我随机 select 一行。问题是路径不平坦，有时变得不可能：

#       #
#    ####
#   #####
###   ###
##  #####
###  ####
#     ###
##  #####
####  ### <--- can't get through here
##   ####
####  ###
###   ###
#      ##
## ######
##  #####
## ######
##  #####
##  #####
##   ####
##   ####
#       #
###   ###
## ###### <--- or here
#       #
## ######
## ######

哪些 class 算法可以帮助我开始使用它？

Answer 1

这里是一个简单算法的基础，可以对其进行改进以获得更具挑战性和趣味性的游戏。这里没有IA
它只是生成路径，由于旧路径，这些路径总是可能的。

基本思想是坚持使用位于路径中间的索引。
您可以随意停留或将中间索引向右或向左移动。我在我的实现中选择了随机地使路径变窄。一种可能的改进是通过考虑具有连贯路径的宽度来做出更深入和更智能的移动（如果需要可以这样做）。

// path is a vector of booleans
// wideness tells how narrow the path is
// middle represents the middle of the path
while wideness > 0
{
  thicken wideness sometimes
  move middle to the right, left, or do not move it
  print the path
}

你可以看看 Live C++ code and algorithm here.

结果可能如下所示：

|#      #########|
|##      ########|
|##      ########|
|###      #######|
|####      ######|
|###      #######|
|###      #######|
|####      ######|
|#####      #####|
|#####      #####|
|#####      #####|
|####      ######|
|#####      #####|
|######      ####|
|#######      ###|
|#######    #####|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|##########    ##|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|#########    ###|
|#########    ###|
|#########    ###|
|##########    ##|
|##########    ##|
|##########    ##|
|#########    ###|
|########    ####|
|#######    #####|
|######    ######|
|#######    #####|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|##########    ##|
|###########    #|
|##########    ##|
|##########    ##|
|###########    #|
|##########    ##|
|#########    ###|
|##########    ##|
|##########    ##|
|##########    ##|
|##########    ##|
|#########    ###|
|##########    ##|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|##########    ##|
|#########    ###|
|#########    ###|
|##########    ##|
|#########    ###|
|##########    ##|
|##########  ####|
|##########  ####|
|#########  #####|
|########  ######|
|#########  #####|
|#########  #####|
|########  ######|
|#########  #####|
|##########  ####|
|#########  #####|
|########  ######|
|########  ######|
|########  ######|
|#########  #####|
|#########  #####|
|##########  ####|
|#########  #####|
|##########  ####|
|##########  ####|

Answer 2

我不确定 class，但以下原则可能适用。

你可以跟踪一个 "hole center index", i，它将跟踪任何给定级别的孔的中心，以及一个 "current hole width"（会逐渐变小的东西） , w.

At each level:
 i <- i +/- (w / 2)
 w <- widthModify(w) //decreases width sometimes  
 for all "tokens" n on level
     if [n < i - (w / 2)] or [n > i + (w / 2)] print("#")
     else print(" ")

这意味着后续孔之间必须有一些重叠，因为以下孔的中心位于前一层的 "range of the hole" 中。

Answer 3

算法本身很简单，正如其他人所建议的，要注意的重点是路径的连续性，可以通过首先计算每行路径的宽度然后将其定位来保证它与前一行的间隙重叠。

我们定义：

W_f为表示全宽的静态自然数（"level width")
W_i为小于等于[=29的自然数=]W_f 大于0表示第i行的路径宽度
X_i取MAX(0 , X_i-1 - W_i + 1) 和 MIN(W_f - W_i, X_i-1 + W_i-1 - 1)表示路径从第i行开始的行中的位置

接下来，为了生成W_i我们定义：

P 是一个介于 0 和 1 之间的实数，表示进度（随着时间、距离、得分的变化而增长...... . 关卡中适用于您的游戏的任何东西）。
R_w是0（含）到1之间随机生成的实数(独家).
F_{w_i}(W_f, P, R_w) 计算 W_i.您需要一些非线性函数，它允许所有 P 的全宽度范围，但概率随着 P 的增加而下降。
例如，您可以使用：W_f (1 - (P (1 - R_w) )^0.65)。您可以使用幂常数，或定义一个完全不同的函数来控制宽度。请务必记住将结果向上舍入为自然数。

最后，为了生成 X_i 我们定义：

R_x是0（含）到1之间随机生成的实数(独家).
F_{x_i}(W_i, W_i-1, X_i-1, R_x) 计算 X_i.
函数为：R_x MIN(W_f - W_i, X_i-1 + W_i-1 - 1) + (1 - R_x) MAX(0, X_i-1 - W_i + 1)。将结果四舍五入为自然数很重要。

将所有这些放在一起，这是一个实时 JavaScript 实施：

function PathRow(fullWidth, progress, prevRow) {
  var Rw = Math.random();
  var Rx = Math.random();
  this.width = Math.ceil(fullWidth * (1 - Math.pow(progress * (1 - Rw), 0.65)));
  if(prevRow) {
    this.x = Math.round(Rx * Math.min(fullWidth - this.width, prevRow.x + prevRow.width - 1) +
      (1 - Rx) * Math.max(0, prevRow.x - this.width + 1));
  }
  else {
    this.x = Math.round(Rx * (fullWidth - this.width));
  }
}

function Game(width, height, target) {
  this.progress = 0;
  this.width = width;
  this.height = height;
  this.target = target;
  this.path = [];
}
Game.prototype.next = function(progress) {
  this.progress = progress;
  this.path.push(new PathRow(this.width, this.progress, this.path[this.path.length - 1]));
  this.draw();
}
Game.prototype.draw = function() {
  var pathString = '';
  for(var i = Math.max(0, this.path.length - this.height + 1); i < this.path.length; i++) {
    pathString += '|' + new Array(this.path[i].x + 1).join('#') + new Array(this.path[i].width + 1).join(' ') + new Array(this.width - this.path[i].x - this.path[i].width + 1).join('#') + '|\r\n';
  }
  this.target.innerHTML = pathString;
}

var path = document.getElementById('path');
var go = document.getElementById('go');
go.onclick = function() {
  go.disabled = true;

  var game = new Game(20, 20, path);
  var progress = 0;
  var totalSteps = 480;
  var interval = setInterval(function() {
    game.next(progress++ / totalSteps);
    if(progress == totalSteps) {
      clearInterval(interval);
      go.disabled = false;
    }
  }, 125);
}

#path {
  white-space: pre;
  font-family: monospace;
}

<div id="path"></div>
<br/><br/>
<button id="go">Go!</button>

如何随机生成窄路径？

How to randomly generate a narrow path?

algorithm

random

artificial-intelligence

path-finding