如何随机生成一条狭窄的路径

我正在编写一款示例游戏，其中一个方块会永远落下，你需要将它从一边转向另一边。如果你碰壁，你就输了。我试着随机地、持续地生成关卡，这样总有一条路可以通过，所以路径会逐渐变窄。

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

我目前的方法是有一个可能路径的数组，然后我随机选择一行。问题是这条路并不平坦，有时会变得不可能:

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

哪一类算法能帮我开始呢?

这里的基础是一个简单的算法，可以通过改进得到一个更具挑战性和趣味性的游戏。这里没有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
}

你可以看看实时c++代码和算法。

结果如下所示:

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

我不确定是一个类，但下面的原则可能适用。

你可以跟踪"孔中心索引"i，它将跟踪任何给定水平孔的中心，以及"当前孔宽度"(将逐渐变小的东西)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(" ")

这意味着后面的洞之间一定有一些重叠，因为下面的中心在前一个关卡的"洞的范围"内。

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

我们定义

W_f为代表全宽度("关卡宽度")的静态自然数
W_i是小于或等于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 <子>我我们定义:

P是一个介于0到1之间的实数，表示进度(以时间、距离、分数…
R_w是0(含)到1(不含)之间随机生成的实数。
F <子> w <子> (w <子> F子> w )计算 w <子>我。你需要一些非线性函数，它允许所有P的全宽度范围，但概率随着P的推进而下降。例如,您可以使用: W f <子> (1 - (P (1 - R <子> W ))<一口> 0.65> 。您可以使用功率常数，或者定义一个完全不同的函数来控制宽度。重要的是要记住将结果向上舍入到一个自然数。

最后,生成 X <子>我们定义:

R_x是0(含)到1(不含)之间随机生成的实数。
F <子> x <子> (W <子>,张W <子> ,张x <子> , R <子> x ), 计算x <子>。
函数是: R <子> x MIN (W <子> f - W <子>,张x <子>张+ W <子> - 1)+ (1 - x R <子> )马克斯·张(0,x <子> - W <子> + 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('#') + '|rn';
  }
  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>

相关内容

最新更新

热门标签：