javascript - 随机路径生成算法

Question

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

FIDDLE

要求:

• 路径可以蜿蜒曲折，但必须从第一行连接到最后一行。
• 最终，我希望每个路径 block 的颜色都是随机的，但现在它可以是统一的(我在下面只用红色进行了测试)
• 从上到下连接的路径是随机生成的
• 路径 block 显然必须连接，不应 fork (又名，给玩家 2 个选择去的选项，如图所示)
• 路径只能从上到下(不能向上移动)，但可以左右 flex

我的想法:

• 我不能简单地检查上面行的列是否是路径的一部分，因为它会在找到第一个真值时不断生成路径片段。
• 我对手动生成路径不感兴趣，因为这需要一个新的矩阵，用 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);
}