Как произвольно генерировать узкий путь?

Question

Я пишу пример игры, где блок падает навсегда, и вам нужно направлять его из стороны в сторону. Если вы попадете в стены, вы проиграете. Я пытаюсь случайным образом и постоянно генерировать уровень, поэтому всегда есть путь, и поэтому путь становится все более узким.

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

Мой текущий подход заключается в массив возможных путей, то я случайно выбрать строку. Проблема заключается в том, что путь не является гладким, и время от времени, становится невозможным:

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

Какой класс алгоритмов поможет мне начать работу с этим?

Answer 1

Здесь лежит простой алгоритм, который можно улучшить, чтобы получить более сложную и интересную игру. Здесь нет ИА.
Он просто генерирует пути, которые всегда могут быть возможны благодаря более старому пути.

Основная идея - придерживаться указателя, который будет посередине пути.
Там вы случайно остаетесь или перемещаете этот средний указатель вправо или влево. Я выбрал в своей реализации случайное получение пути уже. Одно из возможных улучшений заключается в том, чтобы сделать более глубокие и умные шаги, принимая во внимание широту таким образом, чтобы иметь согласованные пути (можно сделать это, если необходимо).

// 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

Я не уверен, о классе, но может применяться следующий принцип.

Вы можете отслеживать «индекс центра отверстия», i, который будет отслеживать центр отверстия на любом заданном уровне, а также «текущую ширину отверстия» (вещь, которая будет постепенно уменьшаться) ш.

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(" ") 

Это означает, что должно быть некоторое перекрытие между последующими отверстиями, потому что центр следующего находится в «диапазоне» дыры предшествующего уровня.

Answer 3

Алгоритм сам по себе довольно прост, и, как было предложено другими, основной задачей, о которой стоит заботиться, является смежность пути, которая может быть гарантирована, сначала вычисляя ширину пути в каждой строке, а затем позиционируя ее так, чтобы он перекрывает пробел в предыдущем ряду.

Определим:

• Вт _е, чтобы быть статическим натуральное число, представляющее полную ширину («ширина уровня»)
• Вт _я быть натуральное число, меньшее или меньшее W _f и более, то 0, представляющая путь ширины в строке я
• X _я, чтобы быть натуральное число между MAX (0, X _я-1 - З _я + 1) и MIN (Вт _F - W _я, X _я-1 + W _я-1 - 1) представляющей позицию через ряд, где путь начинается в строке я

Далее, для создания W _я мы определяем:

• P вещественное число между 0 и 1, представляющего прогресс (растет в зависимости от времени, расстояние, оценка ... все, что работает для вашей игры) на уровне.
• R _ж является случайным образом вещественного числа в диапазоне от 0 (включительно) и 1 (исключительного).
• Р _{ш я} (Вт _F, P, R _ж), который вычисляет Вт _я. Вам нужна некоторая нелинейная функция, которая допускает полный диапазон ширины для всех P, но с вероятностью падения как P авансы.
  Например, вы можете использовать: Вт _е (1 - (Р (1 - R _ж)) ^0,65). Вы можете играть с постоянной мощности или определять совершенно другую функцию для управления шириной. Важно не забывать округлять результат до до натурального числа.

И, наконец, для создания X _я мы определяем:

• R _х является случайным образом вещественное число между 0 (включительно) и 1 (эксклюзивные).
• Р _{х я} (Вт _я, Вт _я-1, Х _я-1, R _х), который вычисляет Х _я.
  Функция: R _х MIN (Вт _е - Ш _я, X _я-1 + W _я-1 - 1) + (1 - R _х) 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>