How can I use weighting to reduce the probability of an action?

PHP
1

This particular problem is probably going to be a bit hard to explain, but I’ll give it my best shot.

I’m creating a script that builds a maze, using PHP and CSS. The script works fine, except for one problem. I’ll get to the problem in a sec, but first, a link, and some background:

The idea for this script came about in this thread in the CSS forum. I looked at an entry posted by another member, and wondered if I could create a maze programatically, so I started working on it. This is what I have, so far:

http://www.geekcavecreations.com/css_maze.php?rows=30&cols=50

The problem I’m having is fairly evident, if you refresh the screen a few times, but I’ll describe it here, anyways.

Since the script randomly builds a new maze every time, there’s a fair chance that the maze creates a “blockade” near either the entrance, or the exit, within about 1 to 6 spaces in. This is clearly unacceptable.

What I’m trying to figure out is how to come up with a function that applies a “weight” to the location of the square it’s creating the border for, where the probability of placing a border in any direction is reduced, based on the location of the square.

In other words, if the square is within 1 square of either the entrance or exit, the probability of placing a border is very low (e.g. 5%), whereas the probability of placing a border in any direction of a square in the middle is closer to 80% (Which is what it is, on average, over the entire board). The function I have now already takes into account the border property of the square above it (unless there isn’t one there), or the square to it’s left, with the same caveat.

I’m guessing that the best way is to take a total number of squares (maxRows * maxCols), and creating a percentage, based on the position of the square in question {e.g (col * row) / numCells}, and then apply that number, somehow, to the probability of placing a border. The problem I have is that I don’t have the foggiest notion of how to apply this percentage. Thus, I turn to you folks here. What would a script look like, that can accomplish this goal? Any notions?

2

Isn’t probability, well, just a chance/gamble?

Surely that still leaves the possibility of an insolvable maze, and no one likes those!

3

lol, that’s kinda my point. I think I’m on to something, but I’m still working it out in my head. I’ll post what I figure out, if I can get it to work.

4

Using probability won’t solve your problem, it will just make it less likely. To solve it, you need to be able make sure that adding a wall doesn’t make the maze untraversable. A way to do this is to make sure you can programatically traverse the maze after you add each wall.

To start, I would use a graph(a datastructure) and a depth first traversal.

There’s tons of efficiency improvements that can be done, but this is more advanced, and you already have a lot of reading to do :slight_smile:

5

Some sort of pathing is also something I’m trying to figure out, as well. I’m just not certain where to even start with that train of thought, so it’s the next step. So far I’ve run the script a few dozen times as is, and it has so far never been impassable except for within the first/last 5 cells. This is the main reason why I want to weight the placement of borders first. Once I get that working, I’ll address the challenge of the script actually making a path through the thing.

6

Thinking about the problem more, it would be even easier to just start with an empty maze with no walls, and create a random, valid path. Then, as you build walls, all you need to do is make sure you don’t invalidate your path.

But…if you just want some probability algorithm to make it more likely you don’t block near the entry/exit points, you could determine straight line distance between two points using the pythagorean theorem


//a^2 + b^2 = c^2
function distance($cell1, $cell2) {
    return sqrt(
        pow($cell1['x'] - $cell2['x'], 2)
      + pow($cell1['y'] - $cell2['y'], 2)
    );
}

Then multiply the distance by 0.05

I’m not good enough at math to make it so the result doesn’t exceed 80% at larger distances. I can think of just hard capping it by using min(), but this doesn’t seem like it would be very good for smaller maps. And you probably want the probability to grow at a non linear rate as distance increases anyway. Maybe someone else can try, but I still think you should scrap this is your ultimate goal is to make sure the maze is traversable, because using probability is just wrong. It may be useful to make interesting mazes though.

7

I know that using probability is not a good answer for the maze itself. That’s pretty much a foregone conclusion. However, the point of the exercise isn’t as much to make a workable maze factory, since I’m sure that I’d just be reinventing the wheel there. The primary goal is to increase my knowledge and experience with PHP. So once I get the probability function completed, and fully understand how it works, I’ll move on to pathing, and learn what I can from that. :smiley: One benefit of being self-taught is that I get to set my own curriculum, even if it makes no sense to anyone else. :wink:

8

Update!

I’ve gotten the probability portion to work, with a 95% chance that it created a solvable maze, but the areas near the exit and entrance looked unacceptably blank. So I moved on to creating a pathing routine. I used the following guidelines:

1.) The path should not cross itself
2.) The path builder needs to know how far it can travel in a given direction before it hits either another section of the path, or the edge of the maze
3.) The path cannot travel in any one direction more than one third of the available distance, unless that distance is less than three cells
4.) The path cannot “double back” on itself (see rule #1)
5.) The path MUST end at lastRow, lastCol ( maxRows-1, maxCols-1)

This is what I’ve got for the pathing function:


function makePath() {
  global $cardinal, $lastRow, $lastCol, $path;
  $row = $col = 0;
  $that_a_way = array_flip($cardinal);
  $lCount = $cCount = 0;
  $dir = "e";
  while (!(($row === $lastRow) and ($col === $lastCol))) {
    $maxDistance = 0;
    $zeroCount = 0;
    while ($maxDistance === 0) {
      $zeroCount++;
      $dir = newDirection($dir);
      $maxDistance = getMaxDistance($row, $col, $dir);
      if($zeroCount > 100) {
/*
    This section cheats a little, since sometimes the script "paints itself
     into a corner". Nine times out of ten, this violates rule #1
*/
        $x = $col + 5;
        $x = ($x > $lastCol) ? $lastCol : $x;
        $y = $row + 5;
        $y = ($y > $lastRow) ? $lastRow : $y;
        for ($col = $col; $col <= $x; $col++) {
          $path[$row][$col] = 1; // head east
        }
        for ($row = $row; $row <= $y; $row++) {
          $path[$row][$col] = 2; // head south
        }
        break;
      }
    }
    $travel = rand(1, round($maxDistance / 3) + 1);
    for($l = 0; $l < $travel; $l++) {
      $path[$row][$col] = $that_a_way[$dir];
      switch ($dir) {
        case "n":
          $row--;
          break;
        case "s":
          $row++;
          break;
        case "e":
          $col++;
          break;
        case "w":
          $col--;
      }
      $row = ($row > $lastRow) ? $lastRow : $row;
      $col = ($col > $lastCol) ? $lastCol : $col;
    }
    $lCount++;
  }
}

This seems to work as intended, creating a random path that extends from the northeast corner (0,0) to the southwest corner (lastRow, lastCol). Can anyone tell me if there’s perhaps a better way to do this? That section of code is a bit of a mess. :slight_smile:

9

Last time I did anything like that I was at Uni :S A graph will definitely be your best bet to represent a maze. Maybe this helps http://en.wikipedia.org/wiki/Maze_generation_algorithm