2

I'm writing a sample game where a block falls down forever, and you need to steer it from side to side. If you hit the walls, you lose. I'm trying to randomly and continually generate the level so there's always a way through, and so the path gets progressively narrower.

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

My current approach is to have an array of possible paths, then I randomly select a row. The problem is that the path is not smooth, and at times, it becomes impossible:

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

What class of algorithms would help me get started with this?

rodrigo-silveira
  • 12,607
  • 11
  • 69
  • 123

3 Answers3

2

Here the basis of a simple algorithm which can be improved to get a more challenging and interesting game. There is no IA here.
It just generates paths which can always be possible thanks to the older path.

The basic idea is to stick with an index which will be the middle of the path.
There you randomly stay or move this middle index to the right or left. I have chosen in my implementation to randomly get the path narrower. One possible improvement is to make deeper and smarter moves by taking into account the wideness in such a way to have coherent paths (can do it if needed).

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

You can have a look at the Live C++ code and algorithm here.

Result can look like this :

|#      #########|
|##      ########|
|##      ########|
|###      #######|
|####      ######|
|###      #######|
|###      #######|
|####      ######|
|#####      #####|
|#####      #####|
|#####      #####|
|####      ######|
|#####      #####|
|######      ####|
|#######      ###|
|#######    #####|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|##########    ##|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|#########    ###|
|#########    ###|
|#########    ###|
|##########    ##|
|##########    ##|
|##########    ##|
|#########    ###|
|########    ####|
|#######    #####|
|######    ######|
|#######    #####|
|########    ####|
|#########    ###|
|########    ####|
|#########    ###|
|#########    ###|
|##########    ##|
|###########    #|
|##########    ##|
|##########    ##|
|###########    #|
|##########    ##|
|#########    ###|
|##########    ##|
|##########    ##|
|##########    ##|
|##########    ##|
|#########    ###|
|##########    ##|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|###########    #|
|##########    ##|
|###########    #|
|###########    #|
|##########    ##|
|#########    ###|
|#########    ###|
|##########    ##|
|#########    ###|
|##########    ##|
|##########  ####|
|##########  ####|
|#########  #####|
|########  ######|
|#########  #####|
|#########  #####|
|########  ######|
|#########  #####|
|##########  ####|
|#########  #####|
|########  ######|
|########  ######|
|########  ######|
|#########  #####|
|#########  #####|
|##########  ####|
|#########  #####|
|##########  ####|
|##########  ####|
coincoin
  • 4,595
  • 3
  • 23
  • 47
  • This generates an "ever shrinking path". Looks like the OP wants a path that "breathes" a little. – Amit Aug 30 '15 at 21:37
2

I'm not sure about a class, but the following principle might apply.

You could keep track of a "hole center index", i, which will track the center of a hole at any given level, as well as a "current hole width" (the thing that will become progressively smaller), 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(" ")

This means there must be some overlap between the subsequent holes because the center of the following is in the "range of the hole" of a preceding level.

Danny Skyrme
  • 21
  • 2
1

The algorithm itself is quite simple, and as others suggested, the main point to take care of is the contiguousness of the path which can be guaranteed by first calculating the width of the path at each row and then positioning it so that it overlaps a gap at the previous row.

We define:

  • Wf to be a static natural number representing the full width ("level width")
  • Wi to be a natural number less then or equal to Wf and greater then 0 representing the path width at row i
  • Xi to be natural number between MAX(0, Xi-1 - Wi + 1) and MIN(Wf - Wi, Xi-1 + Wi-1 - 1) representing the position across the row where the path starts at row i

Next, to generate Wi we define:

  • P is a real number between 0 and 1 representing the progress (growing as a function of time, distance, score... whatever works for your game) in the level.
  • Rw is a randomly generated real number between 0 (inclusive) and 1 (exclusive).
  • Fwi(Wf, P, Rw) which calculates Wi. You need some nonlinear function that allows full width range for all P but with probabilities dropping as P advances.
    For example, you could use: Wf (1 - (P (1 - Rw))0.65). You can play around with the power constant, or define an entirely different function to control the width. It's important to remember to round the result up to a natural number.

And finally, to generate Xi we define:

  • Rx is a randomly generated real number between 0 (inclusive) and 1 (exclusive).
  • Fxi(Wi, Wi-1, Xi-1, Rx) which calculates Xi.
    The function is: Rx MIN(Wf - Wi, Xi-1 + Wi-1 - 1) + (1 - Rx) MAX(0, Xi-1 - Wi + 1). It's important to round the result to a natural number.

Putting all of that together, here's a live JavaScript implementation:

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>
Amit
  • 45,440
  • 9
  • 78
  • 110