private SearchNode < O , T > joinBothPaths ( SearchNode < O , T > forwardPath , SearchNode < O , T > reversePath ) throws SearchNotExhaustiveException { // Check if an alternative path join algorithm has been set and delegate to it if so if ( pathJoiner != null ) { return pathJoiner . joinBothPaths ( forwardPath , reversePath ) ; } // No alternative path join algorithm has been supplied so use this default one else { // Used to hold the current position along the reverse path of search nodes SearchNode < O , T > currentReverseNode = reversePath ; // Used to hold the current position along the forward path of search nodes SearchNode < O , T > currentForwardNode = forwardPath ; // Loop over all nodes in the reverse path checking if the current reverse node is the // goal state to terminate on. while ( ! goalPredicate . evaluate ( currentReverseNode . getState ( ) ) ) { // Create a new forward node from the parent state of the current reverse node, the current reverse // nodes applied operation and cost, and an increment of one to the path depth SearchNode < O , T > reverseParentNode = currentReverseNode . getParent ( ) ; T state = currentReverseNode . getParent ( ) . getState ( ) ; Operator < O > operation = currentReverseNode . getAppliedOp ( ) ; float cost = currentReverseNode . getPathCost ( ) - reverseParentNode . getPathCost ( ) ; currentForwardNode = currentForwardNode . makeNode ( new Successor < O > ( state , operation , cost ) ) ; // Move one step up the reverse path currentReverseNode = reverseParentNode ; } // Return the last forward search node found return currentForwardNode ; } }
Once a match has been found between the forward and reverse fringes of the search a path is known to exist from the start to the goal . The path is not complete at this stage because it remains to reverse all of the steps in the backward half of the path and add them to the forward half of the path to produce the complete forward path from start to the goal .