随机路径生成算法 [英] Random path generation algorithm

问题描述

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

  var colorEn = [RoyalBlue，LawnGreen，red，orange，yellow，black，white ，MediumOrchid]; 
 var $ color =null; 
 var matrix = []; 
 var list = [] 
 
 $（document）.ready（function（）{
 
 createMyGrid（）; 
 createPath 
 $ b}）; 
 
 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）; 
 
 //主循环，运行直到我们到达最后一行。 
 do {
 CreateNewFrontier（row，randomColumn）; 
 // list现在包含所有合法动作的列表
 
 var randomNumber = Math.floor（（Math.random（）*（list.length）））; 
 //随机选择一个
 
 row = list [randomNumber] [0]; 
 randomColumn = list [randomNumber] [1]; 
 
 //标记为
 MarkPath（row，randomColumn）; 
} while（row< 6）//这应该是matrix.length  -  1 
} 
 
 //此函数清除前面的有效移动列表，并生成新的一个。 
 
 function CreateNewFrontier（row，column）{
 list = []; 
 
 //检查每个基数方向是否落在矩阵的边界内。 
 //如果它将该节点传递给addtofrontier函数以供进一步考虑。 
 
 // if（row-1> = 1）AddToFrontier（row-1，column）; 
 //注释掉，因为我们不再考虑引导的路径。 
 if（column + 1  if（row + 1< matrix.length）AddToFrontier（row + 1，column）; 
 if（column-1> = 1）AddToFrontier（row，column  -  1）; 
} 
 
 //此函数检查以确保要添加到边界的节点不违反任何限制
 //主要是，根据问题描述，没有节点在任何基本方向上触摸2个以上的节点
 
函数AddToFrontier（row，column）{
 //首先我们确保这个节点不在路径上。没有回溯，因为它会违反只有一个连续路径的条件。 
 
 if（matrix [row] [column] .data（'partOfPath'）！= true）{
 
 //现在我们需要确保有最多的邻居
 //已经在路径上，否则我们将违反单个路径条件。 
 //所有标记的邻居计数... 
 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 ++; 
} 
 
 //...如果只有1，我们将节点添加到可能的移动列表中。 
 if（markedNeighbors< 2）{
 var index = list.length; 
 list [index] = []; 
 list [index] [0] = row; 
 list [index] [1] = column; 
} 
} 
} 
 
 //帮助函数将节点标记为已访问。 
 function MarkPath（row，column）{
 matrix [row] [column] .data（'partOfPath'，true）; 
 matrix [row] [column] .addClass（red）; 
} 
 
 //帮助函数检查是否标记了路径。 
 //看起来有点奇怪，因为我不熟悉JS，并不知道如何未初始化的//变量将返回，所以我决定返回相反。 
 
 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; 
} 
} 
} 
 
函数log（word）{
 console.log（word）; 
} 
  

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.

解决方案

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

这篇关于随机路径生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！