Random Path Generation Algorithm

Question

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

Fiddle

Requirements:

• The path can rotate, but it must connect from line 1 to the last line.
• In the end, I would like the colors to be random for each part of the path, but at the moment this can be uniform (I tested below only in red).
• Paths connecting from top to bottom are randomly generated.
• Obviously, the fragments of the path should be connected and should not be fork (aka, give the player 2 choices shown here).
• The path can only go from top to bottom (cannot move backward), but it can rotate left and right

What I thought:

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

So yes, an easy way would be to just do it and go 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 is an empty grid on the right that it should generate

My thought was to first create a grid and add gaps 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 part of the path in random order on line 1. Then, for each next line, make sure that there is a track above it to connect ... then from this part run the following 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"); } } 

While he adds the initial step, then the line below, but then stops.

Answer 1

One thing that I would like to point out is that you have to change the range of the array to start from scratch, or fix the range of the generated number. It is currently producing a range with invalid indices. Since your question was not focused on this, I left it as it is.

This creates a winding path that can be lowered and restored until it ends in actual moves or reaches the bottom of the screen. Here is 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

This is how I would approach this problem.

1) Clearly define your rules for what constitutes a valid path. those. a function matching a matrix with a boolean. From your question, I do not quite understand what the correct path is, and I still have not understood what you are.

2) Repeatedly generates a random arrangement of tiles until an agreement is reached with the rules for an acceptable path. On modern processors, this will work fast for 6x6, but will take longer on large areas, for example. 100x100

An algorithmic solution may be possible, saving processing time, but this is a quick gain in terms of development time and code simplicity. It also has the advantage that you get a uniform distribution, i.e. Each path is as probable as any other path.

An example rule set might be:

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

1) Each tile in the matrix (except for two end plates) must be neighbors with exactly two plates from the four possible directions N, S, E, W

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

3) One end tile should be in the top row and the other in the bottom row

Answer 3

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

After creating the maze on the matrix, you must find the path from the start point to the end point (it can be every point. You just need to keep in mind that every second can be a wall). You can find many different algorithms in the link at the bottom of the post. With the maze created using the recursive backtracer, you are guaranteed to connect the rows / columns as you want (as I said, each point is connected to all the others), but not every position can be expensive (due to the need to place walls)

The path you found from start to finish meets your requirements, so you only need to delete everything that does not belong to the path.

If you create your own stack, you can easily process matrices of size ~ 2Kx2K. Maybe more.

For further reading about everything related to the mazes, I recommend this site http://www.astrolog.org/labyrnth/algrithm.htm

You can make some changes to the maze generator so that you can start / complete any possible tile, not only every second. The easiest solution for this that I can think of is to simply create a maze with an offset of 1 for 50% of cases.

Answer 4

If you go one step at a time, and going up is excluded, it seems to me that all you need to track is the last two movements (except for determining the first step). Then the algorithm could follow a set of rules, arbitrarily choosing the next fragment from the available options.

For example:

 If the last two movements were West then South, East would not be available. If the last two movements were East then East, Southeast would not be available. And so on. 

Answer 5

here jsfiddle

enter row and column of any size

 function yolYap(satir,sutun=0){ //My Create Path Function if(ilk){ //İlk seçim: First selection ilk=false; sutun = Math.floor((Math.random()*6)+1); matrix[satir][sutun].data('p', true); matrix[satir][sutun].addClass("red"); yolYap(satir,sutun); }else{ var xy=[]; var solust=satir>1&&sutun>1?!matrix[satir-1][sutun-1].data("p"):true var sol=sutun>1?!matrix[satir][sutun-1].data("p"):false if(sol && solust)//{ xy.push([satir,sutun-1]);//alert("<-");} var sagust=satir>1&&sutun<matrix[1].length-1?!matrix[satir-1][sutun+1].data("p"):true; var sag=sutun<matrix[1].length-1?!matrix[satir][sutun+1].data("p"):false; if(sag && sagust)//{ xy.push([satir,sutun+1]);//alert("->");} //satir>-1?alert("büyük"):alert("küçük"); xy.push([satir+1,sutun]); var sec = Math.floor((Math.random()*102)+1)%xy.length; matrix[xy[sec][0]][xy[sec][1]].data("p", true); matrix[xy[sec][0]][xy[sec][1]].addClass("red"); //alert(xy.join(" - ")); if(xy[sec][0]<matrix.length-1) yolYap(xy[sec][0],xy[sec][1]); else alert("Finish"); } 

}