Differences

This shows you the differences between two versions of the page.

--- t1_maze_branching [2024/06/07 12:17] – [Methodology] fpalustre
+++ t1_maze_branching [2024/06/07 12:31] (current) – fpalustre
@@ Line 129: / Line 129: @@
 END FUNCTION
 </code>
-==== Path Accumulator ====
+==== Path Accumulator (C++) ====
 <code c++>
 FUNCTION pathAccumulation(change, startingNode, desiredNode) //change is a struct
@@ Line 217: / Line 217: @@
      RETURN fullPath
+END FUNCTION
+</code>
+==== Path Accumulator (Python) ====
+<code python>
+FUNCTION pathAccumulation(graph, startingNode, removedNodes)
+     furthestNode <- int
+     primaryPath <- List
+     SET furthestNode TO farthestNode(graph, startingNode, removedNodes)
+     SET primaryPath TO BFS(graph, startingNode, furthestNode, removedNodes)
+     finalPath <- List
+     stack <- deque #best to use the deque module from collections
+     FOR EACH node IN primaryPath
+          ADD node TO finalPath
+          ADD node TO stack
+          WHILE stack IS NOT EMPTY
+               currNode <- int
+               SET currNode TO last index of stack
+               added <- bool
+               SET added TO FALSE
+               FOR EACH adjNode IN graph[currNode]
+                    IF adjNode NOT IN primaryPath AND removedNodes AND finalPath AND stack
+                    ADD neighbor TO stack
+                    SET added TO TRUE
+               IF added IS FALSE
+                   REMOVE LAST ELEMENT
+               IF stack IS NOT EMPTY
+                    branchPath <- List
+                    SET branchPath to BFS(graph, currNode, stack[-1], removedNodes)
+                    SET AND ADD branchPath TO finalPath
+          IF finalPath[-1] DOES NOT EQUAL TO node
+               branchPath <- List
+               SET branchPath to BFS(graph, finalPath[-1], node, removedNodes)
+                    SET AND ADD branchPath TO finalPath
+     return finalPath
 END FUNCTION
 </code>
 ===== MATLAB Result =====
-Once the code has been made, the output would be the desired path of your maze. To visually see it, the following is a MATLAB implementation of this maze-branching algorithm.
+Once the code has been made, the output would be the desired path of your maze. To visually see it, the following is a MATLAB implementation of the queue version of the maze-branching algorithm.
   * Green: Start Node
   * Red: End Node