- Home /
How can i take the right path in this pathfind algorithm?
I'm trying to make a pathfinding algorithm (A*) by myself to add it to my proyect, and i'm actualy making all the calculation sucessfully to meet the target tile BUT i can't find a way to actualy trim the route of the unused tiles to get the actual path to use.
The failing part seem to be the assignation of the parent node, the one who actualy make the route, i'm not exactly getting right the asignation of this and, as such, when you recalculate the cost so to obtain the optimal path doesn't actualy make a conected line back to the starting tile.
Let me show you an image of how is searching the tiles and then the code, so you can have a better idea of the problem, this is what i have so far:
Picture of the exploration algorithm after finish the search to find the ending tile:
Picture of the backtracking problem:
private void Start()
{
CreateGrid();
foreach (Node item in PathFinding_GetClosedListReady()/*PathFinder_SetStream()*/)
{
WorldController.Instance.world.Tiles[item.x, item.y].ChangeSprite();
}
//TileChangeForUpdate();
//PathFinding_GetClosedListReady();
}
public List<Node> PathFinder_SetStream()
{
List<Node> posiblePath = PathFinding_GetClosedListReady();
Node currentNode = posiblePath.Where(i => i.prefab.name == this.NodeWhereStanding(Seeked).prefab.name).Select(i => i).FirstOrDefault();
Node endingNode = posiblePath.Where(i => i.prefab.name == this.NodeWhereStanding(Seeker).prefab.name).Select(i => i).FirstOrDefault();
Node SelectedNode = new Node (999999999,999999999);
List<Node> newList = new List<Node>();
List<Node> suplementaryList = new List<Node>();
int LowestAmmount;
do
{
LowestAmmount = 999999999;
suplementaryList = Path_Controller.Instance.NodesOfArround(currentNode).Intersect(posiblePath).ToList(); //
newList.Add(currentNode);
foreach (Node node in suplementaryList)
{
//node.UpdateValues(currentNode, endingNode);
if(node.FGcostHCost < LowestAmmount)
{
SelectedNode = node;
SelectedNode.parentNode = currentNode;
}
}
//newList.Add(currentNode);
//currentNode = currentNode.parentNode;
currentNode = SelectedNode;
Debug.Log(SelectedNode.prefab.name);
}
while (currentNode.x != endingNode.x && currentNode.y != endingNode.y);
return newList;
}
private List<Node> PathFinding_GetClosedListReady()
{
Tile firstTile = WorldController.Instance.world.Tiles[this.TileWhereStanding(Seeker).X, this.TileWhereStanding(Seeker).Y];
Tile endingTile = WorldController.Instance.world.Tiles[this.TileWhereStanding(Seeked).X, this.TileWhereStanding(Seeked).Y];
Node currentNode = NodesPositions[firstTile.X, firstTile.Y];
currentNode.UpdateValues(firstTile, endingTile);
List<Node> OpenList = new List<Node>();
List<Node> ClosedList = new List<Node>();
OpenList.Add(currentNode);
float LowestF;
Node selectedNode = currentNode;
ClosedList.Add(currentNode);
do
{
OpenList.AddRange(Path_Controller.Instance.NodesOfArround(currentNode));
LowestF = 999999999;
foreach (Node node in OpenList)
{
if (node.x == endingTile.X && node.y == endingTile.Y)
{
node.parentNode = currentNode;
selectedNode = node;
OpenList.Remove(selectedNode);
ClosedList.Add(selectedNode);
return ClosedList; //Aquí returnaré la ClosedList listo para hacer el algoritmo final O un objeto que retorne y posea la closed y open list
}
node.UpdateValues(firstTile, endingTile);
if (node.FGcostHCost < LowestF && !ClosedList.Any(i => i.prefab.name == node.prefab.name))
{
LowestF = node.FGcostHCost;
node.parentNode = currentNode;
selectedNode = node;
}
}
OpenList.Remove(selectedNode);
ClosedList.Add(selectedNode);
currentNode = selectedNode;
//Debug.Log(currentNode.prefab.name);
}
while (OpenList.Count > 0);
return ClosedList;
}
Here is the methods than i use to get the Heurisitcs of my nodes, is a node method, i suspect the problem can be there too:
public void UpdateValues(Tile StartingTile, Tile EndingTile)
{
try
{
GstartingNode = (StartingTile.X - this.x) + (StartingTile.Y - this.y);//(StartingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (StartingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
HendNode = (EndingTile.X - this.y) + (EndingTile.Y - this.y);//(EndingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (EndingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
GstartingNode = GstartingNode < 0 ? GstartingNode * -1 : GstartingNode;
HendNode = HendNode < 0 ? HendNode * -1 : HendNode;
FGcostHCost = GstartingNode + HendNode;
}
catch (Exception ex)
{
Debug.Log("UpdateValues(Tile StartingTile, Tile EndingTile) Error: " + ex.ToString());
Debug.Log("G: " + GstartingNode + "\nH: " + HendNode + "\nF: " + FGcostHCost);
Debug.Log(Path_Controller.Instance.worldToPathfind.Tiles[this.x, this.y].ToString());
Debug.Log(StartingTile.ToString());
Debug.Log(EndingTile.ToString());
}
}
public void UpdateValues(Node StartingNode, Node EndingNode)
{
try
{
GstartingNode = (StartingNode.x - this.x) + (StartingNode.y - this.y);//(StartingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (StartingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
HendNode = (EndingNode.x - this.y) + (EndingNode.y - this.y);//(EndingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (EndingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
GstartingNode = GstartingNode < 0 ? GstartingNode * -1 : GstartingNode;
HendNode = HendNode < 0 ? HendNode * -1 : HendNode;
FGcostHCost = GstartingNode + HendNode;
}
catch (Exception ex)
{
Debug.Log("UpdateValues(Node StartingTile, Node EndingTile) Error: " + ex.ToString());
}
}
If you need more details, information or have suggestions to improve the question, please let me know.
Thanks a lot
Your answer
Follow this Question
Related Questions
A* Pathfinding Turn Off Rotation 2 Answers
A* endless loop 0 Answers
A* pathfinding generating new path when created new obstacle 0 Answers
A* Pathfinding AB Path usage without Seeker 1 Answer
Multiple Cars not working 1 Answer