How can a recursive algorithm be reviewed to find the shortest path?

Question

https://vimeo.com/70999946

I implemented a recursive path search algorithm. This recursive algorithm works on the basis of predefined nodes connected together. Each node has four pointers containing a further direction: top, button, left and right. A recursive algorithm simply goes through each node and looks for each of these four directions one by one to reach its final destination; consider the following 7 nodes: A, B, C, D, E, F, G, H.

A (Button->D, Right->B) B (Right->C, Left->B) C (Left->B) D (Button->G, Right->E, Top->A) E (Right->F, Left->D) F (Left->E) G (Right->H, Top->D) H (Left->G) 

These nodes when presenting a general view will be displayed in the following figure.

 A—B—C | D—E—F | G—H 

In this example, suppose the start path of the node is equal to node A and wants to go to node H as the final destination. node A looks at its own rights, buttons, on the left and top in order; his right pointed to node B; as a result, he decided to switch to node B; node B in the same template chooses to go right, node C. When the walker reaches node C; since its right, top and button keys are locked, node C goes back to node B. Also node B goes back to node A. The walker goes back to the starting point. Then node A goes to its button base node in order; which means that it goes to node D. node D goes to the right node E and then node F. As node F locks; it goes back to node E and node D. Then node D selects its button, node G according to the order of the walker. From there, node G goes to node H. Finally, the walker reaches its final destination.

 Pseudocode: Recursive Path Finding Algorithm ArrayList findPath(GameObject currentPoint , GameObject targetPoint , ArrayList InputArrayList) { 1-Duplicate InputArrayList as tempArrayList 2-If the currentPoint equals to target Point return inputArrayList //*** End Condition found target 3-If the Right side of the currentPoint is empty goto step 4 3.1- Add currentPoint to tempArrayList //*** Call Right 3.2- tempArrayList = findPath(currentpoint.Right, targetPoint, tempArrayList); 3.3- If tempArrayList is not null return tempArrayList 4-If the Button side of the currentPoint is empty goto step 5 4.1- Add currentPoint to tempArrayList //*** Call Button 4.2- tempArrayList = findPath(currentpoint.Button, targetPoint, tempArrayList); 4.3- If tempArrayList is not null return tempArrayList 5-If the Left side of the currentPoint is empty goto step 6 5.1- Add currentPoint to tempArrayList //*** Call Left 5.2- tempArrayList = findPath(currentpoint.Left, targetPoint, tempArrayList); 5.3- If tempArrayList is not null return tempArrayList 6-If the Top side of the currentPoint is empty goto step 7 6.1- Add currentPoint to tempArrayList //*** Call Top 6.2- tempArrayList = findPath(currentpoint.Top, targetPoint, tempArrayList); 6.3- If tempArrayList is not null return tempArrayList 7-Return null; //*** End Condition does not found target } 

Note: the actual code is in C #, you can download it from.

Occurrence of a problem in a case study: How do you understand this code; he has a weakness to illustrate this; given the following general overview of nodes, with the assumption that the start of node is equal to node A and the final destination is node H.

 A—B—C | D—E—F—I | | | G—H—J—K 

Although the best path solution is (A, D, G, H), the recursive path search algorithm explained finds (A, D, E, F, I, K, J, H) as its solution; it really seems like a robot is a stupid robot: D!

Figure 1: Recursive Path Search Algorithm

Figure 2: Learning recursive path learning algorithm

I solved the problem by adding learning ability for nodes. You can see the problem details from this link . But, I would have thought if anyone could reconsider the recursive algorithm to find the shortest path.

Thanks,

Answer 1

You do a depth search at the beginning when what you want to do is a breadth-first search . The latter will require a queue , not a recursion. The wiki page explains well how to implement it, so I won’t repeat it here.

There will not be much work to implement A * , which should speed up your results. This will require a priority queue, not a queue; C # does not have a priority queue in the base library, but, as luck would have it, I am the author of an optimized implementation of the C # priority queue , specifically designed for use in finding paths.

Also, since you mentioned Unity, I will point out that there are several path-finding libraries created specifically for Unity. This is probably the safest route, since effective search for paths in video games is non-trivial.

Answer 2

Why not just compare it with Dijkstra and A * search ?

Note that using recursion instead of a loop, you will most likely get StackOverflow with 1025 recursions.

Answer 3

Below is information about what you need first (write faster). I do not recommend this answer to finding paths. The answers of BlueRaja and Geoffrey are much more generalized, stable and all around improve path finding algorithms. But I wanted to answer the direct question OP.

To simplify my example, borders have a cost / weight of 1. The shortest path == path with the least number of nodes to achieve the goal (technically length == |path| - 1 , since I count the nodes, not the edges, but whatever , the idea is the same). This code will not process loops, so it’s better to use other algorithms.

 public class PathNode { public string Id; public PathNode[] Children = new PathNode[4]; } public class PathFinder : MonoBehaviour { public List<PathNode> shortestPath = null; /// <summary> /// Sets shortest path to `candidatePath` if `candidatePath` is shorter /// or no shortest path yet. /// </summary> public void SetShortestPath(List<PathNode> path){ if(shortestPath == null){ shortestPath = new List<PathNode>(path); return; } if(path.Count < shortestPath.Count) shortestPath = new List<PathNode>(path); } /// <summary> /// depth-first shortest path /// </summary> public void FindShortestPath(PathNode target, List<PathNode> path){ PathNode next = path[path.Count-1]; //get next node from path if(target == next){ SetShortestPath(path); return; } // dfs - iterate children foreach (PathNode node in next.Children){ if(node!=null){ path.Add(node); FindShortestPath(target,path); path.Remove(node); } } } public PathNode ExampleEdgeCreation(){ PathNode a = new PathNode{Id="A"}; a.Children[(int)Direction.Left] = new PathNode{Id="B"}; return a; } } 

Suppose PathNode.Children[0] == PathNode.Children[Left] , etc. I have listed them in the code, but I wanted this example to be small for SO.