Random Path Generation Algorithm

Random path generation algorithm

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

algorithm to generate random path in 2D tilemap

  1. create 2D map

    so create 2D array of the size of your map and clear it by for example 0

  2. add N random obstacles

    for example filled circles in the map

  3. use A* to find shortest path

    you can use mine ... C++ A* example

If you want something more complex then you can create random terrain and use A* to find shortest path (while going up will cost more then going down ...). To create random terrain you can use:

  • Diamond and Square Island generator

which can be use also used for random map generation...

Random path generation algorithm with defined path size

It seems that you want to find the nearest path between two points A and B in a grid with no obstacles. Movement must be in one of the four cardinal directions. You then want to lengthen this path so that it has a certain length.

First, if there are no obstacles, you don't need to probe all directions. For example, if B is 4 steps to the east and two steps to the north of A, just pick steps from {E, E, E, E, N, N} randomly (or shuffle the array) until you arrive.

The shortest distance d* between A and B is the Manhattan diatance:

    d* = |A.x - B.x| + |A.y - B.y|

If you imagine the grid coloured like a checkerboard, the distance between A and B is even if both have the same colour and odd otherwise. This does not only apply to the sorest distance, but to the distance of any valid path between A and B. Hence, you can only get distances of d* + 2·k.

You can make longer paths by adding small "detours" to your ideal path:

        · · · · · · · ·            · · · · · · · ·            · · · · · · · ·
· · · · · · B · · · · · · · B · · · · · · · B ·
· · · · ┌───┘ · · u · · ┌───┘ · · · · · ┌───┘ ·
· · · · │ · · · · ╒═╕ · └─╖ · · · · · ╔═╡ · · ·
· ┌─────┘ · · · · │ └─────╜ v · · ┌───╜ ╧ w · ·
· A · · · · · · · A · · · · · · · A · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · ·

Each of the "dents" u and v add two segments to your path. When you make dents, take care not to make a dent, where there is already a piece of the path: Dent w has a piece of the path folded back on itself, so that there is a dead end. You can remove the dead end, but the path will have the same length as before.

How to implement all this is left as an exercise to the reader. :)

Random Path generation in a game

Simplest solution I can think of is to generate waypoint nodes that know which other nodes they're connected to, and then randomly choose a connection to follow (possibly with some heuristic to head towards your goal)

eg,

using System.Linq;
public class Waypoint : MonoBehaviour{
public Waypoint[] Connections;

public Waypoint Next( Waypoint previous, Waypoint finalDestination) {

if (this == finalDestination) return null; // You have arrived

var possibleNext = Connections.Where(m => m != previous && CheckHeuristic(m, finalDestination)); // Dont go backwards, and apply heuristic

if (possibleNext.Count() == 0) throw new System.ApplicationException("No exitable paths from Waypoint"); // Error if no paths available

possibleNext = possibleNext.OrderBy( m => Random.Range(0f, 1f)); // 'shuffle'

return possibleNext.First(); // Grab first 'random' possible path
}

private bool CheckHeuristic(Waypoint candidate, Waypoint finalDestination) {
// Basic 'is not farther' check
return Vector3.Distance(candidate.transform.position, finalDestination.transform.position) <= Vector3.Distance(this.transform.position, finalDestination.transform.position);
}
}

Also, "there's no such thing as a free lunch" applies here. There's always a cost to building stuff like this. You'll either spend the time learning A*, or you'll spend the time manually creating paths...

Randomly Generating Curved/Wavy Paths

I also use a copy of the previous answers to realize a simplified version of what I hinted at in the comments.

Use a random walk on the unit circle, that is on the angle, to determine a velocity vector that slowly but randomly changes and move forward using cubic Bezier patches.

var c = document.getElementById("c");var ctx = c.getContext("2d");var cw = c.width = 600;var ch = c.height = 400;var cx = cw / 4, cy = ch / 2;
var angVel = v.value;var tension = t.value;ctx.lineWidth = 4;
var npts = 60;var dw = Array();var xs = Array();var ys = Array();var vxs = Array();var vys = Array();
function Randomize() { for (var i = 0; i < npts; i++) { dw[i] = (2*Math.random()-1); }}
function ComputePath() { xs[0]=cx; ys[0]=cy; var angle = 0; for (var i = 0; i < npts; i++) { vxs[i]=10*Math.cos(2*Math.PI*angle); vys[i]=10*Math.sin(2*Math.PI*angle); angle = angle + dw[i]*angVel; } for (var i = 1; i < npts; i++) { xs[i] = xs[i-1]+3*(vxs[i-1]+vxs[i])/2; ys[i] = ys[i-1]+3*(vys[i-1]+vys[i])/2; }}
function Draw() { ctx.clearRect(0, 0, cw, ch); ctx.beginPath(); ctx.moveTo(xs[0],ys[0]); for (var i = 1; i < npts; i++) { var cp1x = xs[i-1]+tension*vxs[i-1]; var cp1y = ys[i-1]+tension*vys[i-1]; var cp2x = xs[i]-tension*vxs[i]; var cp2y = ys[i]-tension*vys[i] ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, xs[i], ys[i]); } ctx.stroke();}Randomize();ComputePath();Draw();
r.addEventListener("click",()=>{ Randomize(); ComputePath(); Draw();})
v.addEventListener("input",()=>{ angVel = v.value; vlabel.innerHTML = ""+angVel; ComputePath(); Draw();})
t.addEventListener("input",()=>{ tension = t.value; tlabel.innerHTML = ""+tension; Draw();})
canvas{border:1px solid}
<canvas id = 'c'></canvas><table>  <tr><td>angular velocity:</td><td> <input type="range" id="v" min ="0" max = "0.5" step = "0.01" value="0.2" /></td><td id="vlabel"></td></tr>  <tr><td>tension</td><td> <input type="range" id="t" min ="0" max = "1" step = "0.1" value="0.8" /></td><td id="tlabel"></td></tr>  <tr><td>remix</td><td> <button id="r"> + </button></td><td></td></tr></table>

C++ How to generate a random Path

The following description and code snippet should give you enough information to solve the problem without providing an exact solution. Note: the following does not satisfy all of your criteria (e.g., preventing a straight line solution) but any missing pieces should be easy to fill in.


  1. Create the grid
  2. Generate random starting cell
  3. Generate random ending cell that is different than the starting cell
  4. Walk from the starting cell to the ending cell
    1. Mark each position as being 'visited'
    2. Determine the valid moves from this position
      1. At least 1 valid move: add this position position to the 'solution path' and update this position to be one of the valid moves
      2. No valid moves: update this position to be the position most recently added to the solution path (i.e., backup) and remove the position most recently
        added to the solution path
        • Note if the 'solution path' is empty restart again at step 4
  5. Reset the grid back to its original state
  6. Traverse the solution path and mark each cell as 'visited'
  7. Print grid

// Step 1
Grid grid(10, 10);

// Step 2
Cell start = grid.generateRandomCell();

// Step 3
Cell end = start;
while (end == start)
{
end = grid.generateRandomCell();
}

std::vector<Cell> solutionPath;

// Step 4
Cell pos = start;
while (pos != end)
{
// Step 4.1
grid.setValue(pos, '#');

// Step 4.2
std::vector<Cell> possibleMoves = getPossibleMoves(grid, pos);
if (!possibleMoves.empty())
{
// Step 4.2.1
solutionPath.push_back(pos);
pos = possibleMoves[rand() % possibleMoves.size()];
}
else
{
// Step 4.2.2
if (!solutionPath.empty())
{
pos = solutionPath.back();
solutionPath.erase(--solutionPath.end());
}
else
{
pos = start;
grid.reset();
}
}
}

// Step 5
grid.reset();

// Step 6
for (size_t i = 1; i < solutionPath.size(); ++i)
{
grid.setValue(solutionPath[i], 'A' + ((i - 1) % 26));
}
grid.setValue(start, '@');
grid.setValue(end, '!');

// Step 7
std::cout << grid << "\n";


Related Topics



Leave a reply



Submit