随机路径生成算法

Question

我想从矩阵的顶部到底部生成随机路径.

小提琴

要求:

• 路径可以绕过,但它必须从第1行连接到最后一行.
• 最后,我希望每个路径的颜色都是随机的,但是现在它可以是均匀的(我在下面用红色测试过)
• 从顶部到底部连接的路径是随机生成的
• 路径碎片显然必须连接,并且不应该分叉(也就是说,给玩家2选择选择去,这里显示)
• 路径只能从上到下(不能向上移动),但它可以向左和向右吹

我考虑过的:

• 我不能简单地检查上面的行的列是否是路径的一部分,因为它会在找到第一个真值时连续生成路径段.
• 我对手动生成路径不感兴趣,因为这需要一个新的矩阵,指定我希望路径前进的1和0.然后对于每个"随机"路径选项,我将不得不构建一个新的矩阵.更重要的是,手动生成矩阵中的路径会使矩阵大小缩放更加繁琐...例如,如果我将6x6矩阵更改为100x100.

所以是的,简单的方法就是制作它并迭代它:

        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]
        ];

在左边,空格,在右边,它应该生成什么

我的想法是首先创建网格并在每个矩阵条目中添加跨度:

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

然后,在第1行中随机生成第一个路径段.然后对于每个后续行,检查其上方的路径段以进行连接...然后从该块开始生成下一个集:

        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");   
                }
        }

到目前为止,它正在添加初始步骤,然后是下面的行,但随后停止.

Answer 1

我想指出的一件事是，您应该将数组的范围更改为从零开始，或者修复生成的数字的范围。目前，它正在生成一个包含无效索引的范围。由于您的问题不是集中于此，所以我将其保留。

这会产生一条蜿蜒的路径，可以向下和返回，直到它耗尽有效的移动或到达屏幕的底部。这是一个 JFIDDLE 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);
}