- Home /
How to generate imperfect and random paths?
Hello guys! This morning i made simple a* pathfinding implementation ( from sebastian tutorial ) to create roads, it works perfectly, but they are too strange built too close too walls, some times made in staircase forms.What are solutions to create some random roads from point to point, is there way to apply perlin noise ( but road still has start and end point ) ? Are there any other algorithms to generate path that is not imperfect, some sort of shaping, or this is just need to be coded by myself?
For example that strange staircase should be more straight line and be a bit more random. Better to get shortest path and then modify it or take another algorithm?
Thanks in advance!
public List<Node> FindPath (Node origin, Node destination)
{
List<Node> openSet = new List<Node>();
HashSet<Node> closedSet = new HashSet<Node>();
openSet.Add(origin);
while (openSet.Count > 0)
{
Node currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{
if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost)
if(openSet[i].hCost < currentNode.hCost)
currentNode = openSet[i];
}
openSet.Remove(currentNode);
closedSet.Add(currentNode);
if (currentNode == destination)
{
return RetracePath(origin, destination);
}
List<Node> neighbours = GetNeighbours(currentNode.x, currentNode.y);
for (int i = 0; i < neighbours.Count; i++)
{
if (!GridNodes[neighbours[i].x, neighbours[i].y].walkable || closedSet.Contains(neighbours[i]))
continue;
int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbours[i]);
if (newMovementCostToNeighbour < neighbours[i].gCost || !openSet.Contains(neighbours[i]))
{
neighbours[i].gCost = newMovementCostToNeighbour;
neighbours[i].hCost = GetDistance(neighbours[i], destination);
neighbours[i].parent = currentNode;
if (!openSet.Contains(neighbours[i]))
openSet.Add(neighbours[i]);
}
}
}
return null;
}
Add a random value to the final cost of every node when retrieving cost.