随机路径生成算法 [英] Random path generation algorithm
问题描述
我想产生从顶部到基体的底部的随机路径。
I would like to generate a random path from the top to bottom of a matrix.
要求：
- 路径可以缭绕，但必须从行1连接到最后一行。
- 最后，我喜欢的颜色是随机为每个路径块，但现在它可以是一致的（我只用红色测试图）
- 是随机生成的连接从上到下路径
- 路径件显然必须连接，而不应叉（又名，给玩家2个选项来选去，如图所示）
- 的路径只能从顶部至底部（不能移动备份），但它可以随风左右
我考虑过什么：
- 在我不能简单地检查上述行的列是路径的一部分，因为那将不断产生路径件时，发现了第一个真正的价值。
- 在我没有兴趣在手动生成路径，这将需要一个新的矩阵指定1和0，我想要去的路径。然后为每一个随机的路径选择，我将不得不建立一个新的矩阵。更重要的是，在矩阵手动生成路径将使缩放矩阵大小更繁琐的...例如，如果我改变了我的6x6矩阵为100×100。
所以是的，简单的方法是只让这一点，并遍历它：
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;
}
}
}
然后，生成随机的第一个路径件行1。然后为每个后续行，检查路径一块它上面连接...然后从一块，开始产生下一组：
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.
推荐答案
有一件事我想指出的是，你应该改变数组的范围从0开始，或固定数量的产生的范围。目前，它正在生产各种无效的指数。由于您的问题没有得到集中在，我离开它，因为它。
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.
这会产生一个蜿蜒的小路，可以下去备份直到它用完了有效移动或到达屏幕的底部。这里是一个JFIDDLE它 http://jsfiddle.net/j6gkzbr5/1/
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屋！
