Random path generation algorithm

Question

I would like to generate a random path from the top to bottom of a matrix.

FIDDLE

Requirements:

• The path can wind around, but it must connect from row 1 to the last row.
• Eventually, I'd like the colors to be random for each path piece, but for now it can be uniform (I've tested below with just red)
• Paths connecting from top to bottom are randomly generated
• The path pieces obviously must connect, and shouldn't fork (aka, give player 2 options to choose to go, shown here)
• The path can only go from top to bottom (cannot move back up), but it can wind left and right

What I've considered:

• I can't simply check if the above row's column is part of the path, because then it will continuously generate path pieces when it finds the first true value.
• I'm not interested in generating paths manually, as that would require a new matrix specifying 1's and 0's where I want the path to go. And then for each "random" path option, I would have to build a new matrix. More importantly, manually generating path in matrices would make scaling the matrix size far more tedious... For example If I changed my 6x6 matrix to a 100x100.

So yeah, the easy way would be to just make this and iterate through it:

        var matrixPaths = [
            [0,1,0,0,0,0],
            [0,1,1,1,0,0],
            [0,0,0,1,0,0],
            [0,0,0,1,1,1],
            [0,0,0,0,0,1],
            [0,0,0,0,0,1]
        ];

On the left, empty grid, on the right, what it should generate

My thought was to first create the grid and add the spans in each matrix entry:

        function createMyGrid() {
            //create 6x6 matrix
            for(var i=1; i<=6; i++) {
                matrix[i] = [];
                for(var j=1; j<=6; j++) {
                    var colorIndex = Math.floor(Math.random() * (color.length - 0) + 0);
                    var $span = $('<span />').attr('class', 'colorSquare').html("[" + i + "][" + j + "]");
                    $("#grid").append($span);
                    matrix[i][j] = $span;
                }
            }
        }

Then, generate the first path piece at random in row 1. Then for each subsequent row, check for a path piece above it to connect... then from that piece, start generated the next set:

        function createPath() {
            var randomColumn = Math.floor(Math.random() * (matrix[1].length - 0) + 0);
            matrix[1][randomColumn].data('partOfPath', true);
            matrix[1][randomColumn].addClass("red");
            for (var row = 2; row <= 6; row++) {
                for (var col = 1; col <= 6; col++) {
                    if (matrix[row-1][col].data('partOfPath')) { //if block above is partOfPath... add a set of items of random # of columns across
                        addRowPath(row, col);
                    }
                }           
            }
        }

        function addRowPath (row, pathCol) { //need to start offset from that row/col position, 
            var randRowPathLength = Math.floor(Math.random() * (matrix[row].length - 0) + 0);
                for (var col = pathCol; col <= randRowPathLength; col++) {          
                    matrix[row][col].addClass("red");   
                }
        }

So far it's adding the initial step, then the row below, but then stopping.

Answer 1

One thing i'd like to point out is that you should change the range of the array to start at zero, or fix the range of number generated. Currently, it is producing a range with invalid indices. Since your question wasn't focused on that, i left it as it.

This produces a winding path that can go down and back up until it either runs out of valid moves or reaches the bottom of the screen. Here is a JFIDDLE for it http://jsfiddle.net/j6gkzbr5/1/

var colorEn = ["RoyalBlue", "LawnGreen", "red", "orange", "yellow", "black", "white", "MediumOrchid"];
var $color = "null";
var matrix = [];
var list = []

$(document).ready(function () {

    createMyGrid();
    createPath();

});

function createPath() {
    var row = 1;
    var randomColumn = Math.floor(Math.random() * (matrix[1].length - 0) + 0);

    matrix[1][randomColumn].data('partOfPath', true);
    matrix[1][randomColumn].addClass("red");

   //Main loop, runs until we reach the final row.
    do {
        CreateNewFrontier(row, randomColumn);
        //list now contains a list of all legal moves to make

        var randomNumber = Math.floor((Math.random() * (list.length)));
        //Select one at random

        row = list[randomNumber][0];
        randomColumn = list[randomNumber][1];

        //And mark it
        MarkPath(row, randomColumn);
    } while (row < 6)//This should be matrix.length - 1
}

//This function clears out the previous list of valid moves and generates a new one.

function CreateNewFrontier(row, column) {
    list = [];

    //Check if each cardinal direction falls within the bounds of the matrix.
    //If it does pass that node to the addtofrontier function for further consideration.

    //if (row - 1 >= 1) AddToFrontier(row - 1, column);
    //Commented out, as we are no longer considering paths that lead up.
    if (column + 1 < matrix[row].length) AddToFrontier(row, column + 1);
    if (row + 1 < matrix.length) AddToFrontier(row + 1, column);
    if (column - 1 >= 1) AddToFrontier(row, column - 1);
}

//This function checks to make sure nodes to be added to the frontier don't violate any restrictions
//Mainly, per the question description, no node can touch more than 2 nodes on any cardinal direction

function AddToFrontier(row, column) {
    //First we make sure this node is not already on the path. No backtracking, as it would violate the condition that there be only one continuous path.

    if (matrix[row][column].data('partOfPath') != true) {

        //Now we need to make sure that this node currently only has 1 neighbor at the most that
       //is already on a path, otherwise we will violate the single path condition.
       //So count up all marked neighbors...
        var markedNeighbors = 0;
        if (row - 1 >= 1 && !IsNotMarked(row - 1, column)) {
            markedNeighbors++;
        }
        if (column + 1 < matrix[row].length && !IsNotMarked(row, column + 1)) {
            markedNeighbors++;
        }
        if (row + 1 < matrix.length && !IsNotMarked(row + 1, column)) {
            markedNeighbors++;
        }
        if (column - 1 >= 1 && !IsNotMarked(row, column - 1)) {
            markedNeighbors++;
        }

        //...and if there is only 1, we add the node to the list of possible moves.
        if (markedNeighbors < 2) {
            var index = list.length;
            list[index] = [];
            list[index][0] = row;
            list[index][1] = column;
        }
    }
}

//Helper function to mark a node as visited.
function MarkPath(row, column) {
    matrix[row][column].data('partOfPath', true);
    matrix[row][column].addClass("red");
}

//Helper function to check if a path is marked. 
//It looks a little odd because i'm not that familiar with JS and wasn't sure how an uninitialized     //variable would return, so i decided to return the opposite.

function IsNotMarked(row, column) {
    if (row < 1 || row >= matrix.length) return true;
    if (column < 1 || column >= matrix[row].length) return true;
    return matrix[row][column].data('partOfPath') != true;
}

function createMyGrid() {
    //create 6x6 matrix
    for (var i = 1; i <= 6; i++) {
        matrix[i] = [];
        for (var j = 1; j <= 6; j++) {
            var colorIndex = Math.floor(Math.random() * (colorEn.length - 0) + 0);
            var $span = $('<span />').attr('class', 'colorSquare').html("[" + i + "][" + j + "]");
            $("#grid").append($span);
            matrix[i][j] = $span;
        }
    }
}

function log(word) {
    console.log(word);
}

Answer 2

I would generate a maze using a method that gives a maze where from every point you can get to every other. Recursive backtracer is good enough for this and easy to implement.

After you generate a maze on the matrix you have to find a way from the starting point to the end point (It can be every point. You just have to keep in mind that every second one can be a wall). You can find many different algorithms in the link in the bottom of the post. With maze generated using recursive backtracer you are guaranteed to have connected rows/columns as you want (like I said, every point is connected to every other), but not every position can be a path (due to need of putting walls)

Your found path from begin to end meets your requirments so you only have to delete everything that does not belong to the path.

If you create your own stack you can easly handle matrices of size ~2Kx2K. Maybe bigger.

For further reading on everything related with mazes I recommend this site http://www.astrolog.org/labyrnth/algrithm.htm

You can make some changes to the maze generator so it is possible to have start/end on any possible tile not just every second one. The easiest solution for this I can think of would be just generating maze with an offset of 1 for 50% of cases.

Answer 3

Here's how I would approach this problem.

1) Precisely define your rules for what constitutes a valid path. i.e. a function mapping the matrix to a boolean. From your question I'm not clear what a valid path is, and I'm not clear you are yet, either.

2) Repeatedly generate a random arrangement of tiles until the arrangement produced meets the rules for a valid path. On current processors this will work quickly for 6x6 but will take longer on larger squares e.g. 100x100.

An algorithmic solution may be possible, saving processing time, but this is the quick win in terms of development time and code simplicity. Also has the advantage of giving you a uniform distribution i.e. each path is just as likely to be produced as any other path.

Example ruleset might be:

A path is valid if and only if the matrix satisfies all these criteria:

1) Every tile in the matrix (except for two end tiles) must be neighbors with exactly two tiles out of the four possible directions N,S,E,W

2) Two tiles in the matrix (end tiles) must be neighbors with exactly one tile out of the four possible directions N,S,E,W

3) One end tile must be on the top row, and the other on the bottom row