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
create 2D map
so create 2D array of the size of your map and clear it by for example
0
add
N
random obstaclesfor example filled circles in the map
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.
- Create the grid
- Generate random starting cell
- Generate random ending cell that is different than the starting cell
- Walk from the starting cell to the ending cell
- Mark each position as being 'visited'
- Determine the valid moves from this position
- At least 1 valid move: add this position position to the 'solution path' and update this position to be one of the valid moves
- 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
- Reset the grid back to its original state
- Traverse the solution path and mark each cell as 'visited'
- 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
Displaying a Div Only on Tumblr Blog Homepage
How to Replay a CSS3 Animation in Reactjs
How to Set Width of <Div> to Fit Constant Number of Letters in Monospace Font
How to Show the Only Part of the Image
Using !Important in Jquery's CSS() Function
How to Query Whole Dom for Elements Matching Some Computed Style ? (In Pure Js)
Isotope Jquery Plugin Doesn't Show Properly on Chrome
After Content Update from Ajax Jquery Not Work Properly
Grunt Plugin for Assets Versioning
Jquery/Js:Detect User's Scroll Attempt Without Any Window Overflow to Scroll To
If HTML, CSS, and JavaScript Are Client-Side, Why Are They Components of a PHP File
Get the Computed Style and Omit Defaults
iOS 11 Getusermedia Not Working
Highlight an Individual Word Within a Text Block on Hover