Method for determining exits and entrances for a region in a network
First Claim
1. A computer implemented method for constructing a set of nodes to be employed in paths extending between nodes in a processor readable representation of a network and nodes in a first region in the processor readable representation of a network, wherein the set of nodes is also in the processor readable representation of the network, said method comprising the steps of:
- (a) identifying a set of boundary nodes in the first region; and
(b) identifying a set of target nodes in the processor readable representation of the network in response to at least one boundary node in said set of boundary nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first region.
2 Assignments
0 Petitions
Accused Products
Abstract
A system is employed for finding a path in a network between an origin in a first region and a destination in a second region. In finding this path, the system finds three paths: a path between the origin and an exit node for the first region, a path between an entrance node for the second region and the destination, and a path between the exit node and the entrance node. These three paths are combined to construct the path between the origin and the destination. A set of nodes for use as exit nodes or entrance nodes for a region may be identified by identifying a set of boundary nodes for the region and identifying a set of target nodes. The target nodes are each separated from the region by a sufficient cost. The set of target nodes may serve as a set of exit nodes or entrance nodes. The set of target nodes may also be modified to improve its operation as a set of exit nodes or entrance nodes.
79 Citations
57 Claims
-
1. A computer implemented method for constructing a set of nodes to be employed in paths extending between nodes in a processor readable representation of a network and nodes in a first region in the processor readable representation of a network, wherein the set of nodes is also in the processor readable representation of the network, said method comprising the steps of:
-
(a) identifying a set of boundary nodes in the first region; and (b) identifying a set of target nodes in the processor readable representation of the network in response to at least one boundary node in said set of boundary nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first region. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
-
-
39. A computer implemented method for constructing a set of nodes to be used in pathfinding, wherein the set of nodes is associated with a first region in a processor readable representation of a network, which is stored on a processor readable medium, and wherein the set of nodes is also in the processor readable representation of the network, said method comprising the steps of:
-
(a) identifying a set of boundary nodes in the first region; (b) identifying a set of target nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first region; (c) determining a path between a node in said set of boundary nodes and a node in said set of target nodes; (d) marking a node in said set of target nodes with a set of nodes in said set of boundary nodes; (e) pushing back a node in said set of target nodes to identify a fork node; (f) marking said fork node with a set of nodes in said set of boundary nodes that also mark said node being pushed back in said step (e); (g) adding said fork node to said set of target nodes; and (h) deleting said node being pushed back in step (e) from said set of target nodes. - View Dependent Claims (40)
-
-
41. A computer implemented method of identifying a path between an origin node in a first region and a destination node in a second region, wherein the origin node and the destination node are located on a processor readable representation of a network stored on a computer readable medium, wherein said method includes:
-
(a) identifying a first node, wherein said step of identifying the first node includes the steps of; identifying a first set of boundary nodes in the first region, and identifying a first set of target nodes in the processor readable representation of the network in response to at least one boundary node in said first set of boundary nodes, wherein each node in said first set of target nodes is separated by a sufficient cost from the first region; (b) identifying a second node, wherein said step of identifying the second node includes the steps of; identifying a second set of boundary nodes in the second region, and identifying a second set of target nodes in the processor readable representation of the network in response to at least one of the boundary nodes in said second set of boundary nodes, wherein each node in said second set of target nodes is separated by a sufficient cost from the second region; (c) commencing pathfinding to determine a path between said origin node and said first node; (d) commencing pathfinding to determine a path between said destination node and said second node; and (e) commencing pathfinding to determine a path between said first node and said second node. - View Dependent Claims (42)
-
-
43. A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for constructing a set of nodes to be employed in paths extending between nodes in a processor readable representation of a network and nodes in a first tile in the processor readable representation of the network, wherein the set of nodes is also in the processor readable representation of the network, said processor readable program code including:
-
a first program code, said first program code instructing a processor to identify a set of boundary nodes in the first tile; and a second program code, said second program code instructing a processor to identify a set of target nodes in the processor readable representation of the network in response to at least one boundary node in said set of boundary nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first tile. - View Dependent Claims (44, 45, 46, 47, 48, 49)
-
-
50. A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for identifying a path between an origin node in a first region and a destination node in a second region, wherein the origin node and the destination node are located on a processor readable representation of a network, said processor readable program code including:
-
a first program code, said first program code instructing a processor to identify a first node, wherein said first program code includes; a second program code, said second program code instructing a processor to identify a first set of boundary nodes in the first region, and a third program code, said third program code instructing a processor to identify a first set of target nodes in the processor readable representation of the network in response to at least one boundary node in said first set of boundary nodes, wherein each node in said first set of target nodes is separated by a sufficient cost from the first region; a fourth program code, said fourth program code instructing a processor to identify a second node, wherein said fourth program code includes; a fifth program code, said fifth program code instructing a processor to identify a second set of boundary nodes in the second region, and a sixth program code, said sixth program code instructing a processor to identify a second set of target nodes in the processor readable representation of the network in response to at least one boundary node in said second set of boundary nodes, wherein each node in said second set of target nodes is separated by a sufficient cost from the second region; a seventh program code, said seventh program code instructing a processor to commence pathfinding to determine a path between said origin node and said first node; an eighth program code, said eighth program code instructing a processor to commence pathfinding to determine a path between said destination node and said second node; and a ninth program code, said ninth program code instructing said processor to commence pathfinding to determine a path between said first node and said second node.
-
-
51. An apparatus for constructing a set of nodes to be used in paths extending between nodes in a processor readable representation of a network and nodes in a first tile in a processor readable representation of a network, said apparatus comprising:
-
means for identifying a set of boundary nodes in the first tile; and means for identifying a set of target nodes in the processor readable representation of the network in response to at least one boundary node in said set of boundary nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first tile. - View Dependent Claims (52, 53)
-
-
54. An apparatus for identifying a set of nodes associated with a first tile in a processor readable representation of a network, said apparatus comprising:
-
a processor; a memory, in communication with said processor; and a processor readable storage medium, in communication with said processor and said memory, wherein said processor is programmed to; identify a set of boundary nodes in the first tile, identify a set of target nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first tile, determine a path between a node in said set of boundary nodes and a node in said set of target nodes, mark a node in said set of target nodes with a set of nodes in said set of boundary nodes, push back a node in said set of target nodes to identify a fork node, mark said fork node with a set of nodes in said set of boundary nodes that also mark said node being pushed back, add said fork node to said set of target nodes, and delete said node being pushed back from said set of target nodes.
-
-
55. An apparatus for identifying a path between an origin node in a first tile and a destination node in a second tile, wherein the origin node and the destination node are located on a processor readable representation of a network, said apparatus comprising:
-
a processor; a memory, in communication with said processor; and a processor readable storage medium, in communication with said processor and said memory, wherein said processor is programmed to; identify a first node, wherein said processor is programmed to perform the following operations in identifying the first node; identify a first set of boundary nodes in the first region, and identify a first set of target nodes in the processor readable representation of the network in response to at least one boundary node in said first set of boundary nodes, wherein each node in said first set of target nodes is separated by a sufficient cost from the first region, identify a second node, wherein said processor is programmed to perform the following operations in identifying the second node; identify a second set of boundary nodes in the second region, and identify a second set of target nodes in the processor readable representation of the network in response to at least one node in said second set of boundary nodes, wherein each node in said second set of target nodes is separated by a sufficient cost from the second region, commence pathfinding to determine a path between said origin node and said first node, commence pathfinding to determine a path between said destination node and said second node, and commence pathfinding to determine a path between said first node and said second node.
-
-
56. A machine including a processor readable storage medium, said processor readable storage medium containing data representing a set of nodes in a processor readable representation of a network, wherein said set of nodes is generated by a computer implemented method for constructing the set of nodes to be employed in paths extending between nodes in said processor readable representation of the network and nodes in a first region in the processor readable representation of the network, said method comprising the steps of:
-
(a) identifying a set of boundary nodes in the first region; and (b) identifying a set of target nodes in the processor readable representation of the network in response to a least one boundary node in said set of boundary nodes, wherein each node in said set of target nodes is separated by a sufficient cost from the first region. - View Dependent Claims (57)
-
Specification