Advertisement
Guest User

Untitled

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