Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- In a Dijkstra search, this starting node edge is normally not recorded, but now we need to
- store this information. Every node’s data structure needs to contain a new value representing this
- starting node edge. During the Dijkstra search, when the neighbors of a node are explored, the
- starting node edge is passed down to the neighboring nodes as they are placed on the open list.
- This transfers the starting node edge information from node to node during the search.
- Once the Dijkstra floodfill has completed, every node is marked with a starting node edge. In
- the case of Figure 22.4, each node is marked with either an A, B, or C. The final task is to iterate
- through all nodes in the map and build up the bounding boxes that contain each starting node
- edge, as shown in Figure 22.5. Once complete, each bounding box (4 values representing left,
- right, top, and bottom) is stored on the appropriate starting node’s edge. This is the data that are
- used during runtime to prune the search during the goal-bounding check.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement