- Home /
Generate tiles along a path a certain distance before reaching end position
My end goal is to create a path from start (the circle) to the end position (the square) while making sure that the path is 2-4 tiles long. The length of the path is randomized.
The problem is that since I am working with seed based generation, I want most seeds to look unique from each other, and in order to do so twisting and bending each path differently would help make each seed seem more different from each other (among other factors that haven't been implemented in the current build). If I had an algorithm to just go from start to finish, the program in most instances would just get to the destination in the shortest distance possible, but in my case I want it to purposely take a longer way before reaching the end destination.
The above 4 is an example of how different lengths/variations of lengths can affect how the path looks and how it can occupy different spaces. The square's location is also randomly generated (also made sure the square can only occupy non corner tiles and tiles not directly in the way of the starting circle).
Is there any way I can implement this or any advice that you guys could possibly give me to help achieve this? Thank you!
Answer by Ymrasu · Aug 07, 2020 at 12:50 PM
I would make a flow field using Dijkstra's algorithm. That way I'd know how many steps it would take to get to the end position from anywhere on the grid. Then instead of just following the shortest path, I could set the path up to be a certain amount of steps.
For example: In your grid samples, the starting position would have a value of 3 (since it takes 3 steps to get to the end, which Dijkstra's figured out) but we want a path of 4. We keep the path of 4 in mind when deciding where to go next. So we check the neighbor values of start, and we want to stay at 3 or higher since our desired path is 4. But the neighbor values are both 2, there is nothing we can do about that so we 50/50 to choose one. Then we lower the path desired down to 3 since we took a step. Lets say we went east, the next to neighbors are 1 to the north or 3 to the east. Remember we want the path to be longer still since we still need 3 steps to finish the path, but we want to remain a bit random so we can do 25/75 chance to go to the 1 or 3 value. We lower the desired down again to 2 for that step; say we went east again, the new neighbor values would be 2 and 4, we cant pick 4 since our desired path length is 2 and going 4 would make the path too long. Lets back up one and say we had picked north that had a value of 1. That would put us next to the end, the neighbors would be west, north, and east with values of 2, 0 (the end), and 2. We know we cant go north to end it yet, that would make the path too short. So randomly pick one of the 2 values. Then continue to randomly select neighbors that wont make the path too long or too short while keeping track of the remaining path length required.
I hope my "example" wasn't too wordy to get lost in. If you need a little help with coding it, I can provide some as well. Good luck!
Edit: Here is a script I put together so you can learn from. Just attach it to an empty gameobject. It uses gizmos so you can visualize whats going on.
using System.Collections.Generic;
using UnityEngine;
public class FlowField : MonoBehaviour
{
public int mapSeed = 1234;
public Vector2Int mapSize = new Vector2Int(4,4);
public int minSteps = 2;
public int maxSteps = 4;
public Vector2Int start;
public Vector2Int end = new Vector2Int(1,2);
int[,] flowfield;
int[,] pathGrid;
[SerializeField] int steps; // so we can see how many steps were chosen
List<Vector2Int> offsets;
// call this for each new target
int[,] GenerateField(Vector2Int size, Vector2Int target)
{
// create grid of cells holding int value (steps from target)
var field = new int[size.x, size.y];
// set all cells to -1 to show it has not been assigned a value
for (int x = 0; x < size.x; x++)
for (int y = 0; y < size.y; y++)
field[x,y] = -1;
// offsets to check neighbor locations (I dont like doing this, but it was quick)
offsets = new List<Vector2Int>();
offsets.Add(Vector2Int.up);
offsets.Add(Vector2Int.down);
offsets.Add(Vector2Int.left);
offsets.Add(Vector2Int.right);
// queue to store locations that need to be checked for neighbor cells
Queue<Vector2Int> openCells = new Queue<Vector2Int>();
// since we are starting from target, add it to queue to have it's neighbors checked
openCells.Enqueue(target);
// and set it's value to 0 (since its the end)
field[target.x, target.y] = 0;
// while we still have cells being checked
while (openCells.Count > 0) {
var current = openCells.Dequeue(); // grab next in line
// check north, south, east, and west neighboring cells
foreach (var offset in offsets) {
var neighbor = current + offset;
// check to see if its within bounds of array
if (neighbor.x < 0 || neighbor.x >= size.x || neighbor.y < 0 || neighbor.y >= size.y)
continue; // out of bounds, skip it
// have we already assigned a value this cell? (not -1)
if (field[neighbor.x, neighbor.y] > -1)
continue; // already assigned a value, skip it
// queue the cell so we can check for it's neighbors
openCells.Enqueue(neighbor);
// assign it's value of 1 step greater then the cell we're coming from
field[neighbor.x, neighbor.y] = field[current.x, current.y] + 1;
}
}
// done checking all cells
return field;
}
int[,] CreatePath(int[,] field, int seed, Vector2Int start, Vector2Int end)
{
var size = new Vector2Int(field.GetLength(0), field.GetLength(1));
int[,] path = new int[size.x, size.y]; // 0 - not path, 1 - path
Random.InitState(seed);
int requiredSteps = steps = Random.Range(minSteps, maxSteps + 1); // max is exclusive, so we need to +1
// begin path from start
var current = start;
// make start and end a part of the path
path[start.x, start.y] = 1;
path[end.x, end.y] = 1;
while (requiredSteps > 0 && current != end) {
// get neighbors
var validNeighbors = new List<Vector2Int>();
foreach (var offset in offsets) {
var neighbor = current + offset;
if (neighbor.x < 0 || neighbor.x >= size.x || neighbor.y < 0 || neighbor.y >= size.y)
continue; // out of bounds, skip it
if (path[neighbor.x, neighbor.y] > 0)
continue; // already assigned a value, skip it
if (field[neighbor.x, neighbor.y] > requiredSteps || field[neighbor.x,neighbor.y] == 0)
continue; // not within requiredSteps
// valid neighbor
validNeighbors.Add(neighbor);
}
// other logic or weights can be placed here
if (validNeighbors.Count > 0) {
// randomly pick a remaining neighbor
int i = Random.Range(0, validNeighbors.Count);
current = validNeighbors[i]; // assign to current
path[current.x, current.y] = 1; // add to path
}
// lower requiredSteps and loop again until at end
requiredSteps--;
}
return path;
}
private void OnDrawGizmosSelected()
{
if (flowfield == null) {
// gererate a flowfield with a grid size of 4 by 4 and a target at location (1, 2)
flowfield = GenerateField(mapSize, end);
}
// see flowfield values
//for (int x = 0; x < flowfield.GetLength(0); x++)
// for (int y = 0; y < flowfield.GetLength(1); y++)
// Handles.Label(new Vector3(x + 0.5f, y + 0.5f), flowfield[x, y].ToString());
// Draw grid for testing
Gizmos.color = Color.white;
// draw horzontal lines
for (int y = 0; y <= flowfield.GetLength(1); y++)
Gizmos.DrawLine(new Vector3(0f, y, 0f), new Vector3(flowfield.GetLength(0), y, 0f));
// draw vertical lines
for (int x = 0; x <= flowfield.GetLength(0); x++)
Gizmos.DrawLine(new Vector3(x, 0f, 0f), new Vector3(x, flowfield.GetLength(1), 0f));
// draw target
Gizmos.color = Color.red;
Gizmos.DrawCube(new Vector3(end.x + 0.5f, end.y + 0.5f, 0f), Vector3.one * 0.5f);
// draw start
Gizmos.color = Color.green;
Gizmos.DrawSphere(new Vector3(start.x + 0.5f, start.y + 0.5f, 0f), 0.25f);
if (pathGrid == null) {
pathGrid = CreatePath(flowfield, mapSeed, start, end);
}
// draw path
for (int x = 0; x < pathGrid.GetLength(0); x++)
for (int y = 0; y < pathGrid.GetLength(1); y++)
if (pathGrid[x,y] > 0) {
Gizmos.color = Color.yellow;
Gizmos.DrawSphere(new Vector3(x + 0.5f, y + 0.5f, 0f), 0.1f);
}
}
private void OnValidate()
{
minSteps = Mathf.Min(minSteps, maxSteps);
maxSteps = Mathf.Max(minSteps, maxSteps);
mapSize.x = Mathf.Clamp(mapSize.x, 2, 10);
mapSize.y = Mathf.Clamp(mapSize.y, 2, 10);
start.x = Mathf.Clamp(start.x, 0, mapSize.x-1);
start.y = Mathf.Clamp(start.y, 0, mapSize.y-1);
end.x = Mathf.Clamp(end.x, 0, mapSize.x-1);
end.y = Mathf.Clamp(end.y, 0, mapSize.y-1);
flowfield = GenerateField(mapSize, end);
pathGrid = CreatePath(flowfield, mapSeed, start, end);
}
}
Sounds interesting, I'll see what I can do and I'll let you know here if I need any help. Thanks!
Been working on it for a bit but I've been having some trouble with implementation of the algorithm into code, are you able to point me in the right direction? Thanks!
Added a script to the answer (it wouldn't let me reply it; I think it was too long, oops)
I can't express in words how thankful I am for such a detailed response with even comments on what each element does. Reading through it all right now and I have a good grasp of how I should proceed writing it in my final project.
If you got a PayPal I'm down to give you some coffee money or something man, seriously thanks!