The Nodes are points in three dimensional space linked to other Nodes by wires called Connectors. They also have a number of fields concerning the calculation of different algorithms. The Pathfinder object hosts a few methods for creating networks of Nodes for you, but you can also make these networks yourself.
Field Summary | |
float | x The 'x' property of a Node's spatial location. |
float | y The 'y' property of a Node's spatial location. |
float | z The 'z' property of a Node's spatial location. |
Node | parent A Node initially set to null that aquires the target of a neighbour during and after a search algorithm is called. Try to make your projects account for 'parent's frequent null setting to avoid breaking your code. |
float | f |
float | g |
float | h The distance to the goal from this Node, used by aStar() and bfs() methods. |
ArrayList | links An ArrayList of Connectors that are attached to other Nodes. This is initially empty. |
boolean | walkable Determines whether this Node is considered an obstacle in a search. Also used in link stripping methods. Initially set to true. |
Constructor Summary |
Node () Creates a Node object with a spatial location of (0.0, 0.0, 0.0). |
Node (float x, float
y) Creates a Node object with a spatial location defined by the parameters given. The z coordinate is set to 0.0. |
Node (float
x, float y, float z) Creates a Node object with a spatial location defined by the parameters given. |
Node (float x, float
y, ArrayList links) Creates a Node object with a spatial location defined by the parameters given. The z coordinate is set to 0.0. The links parameter assumes an ArrayList of Connectors is being given to it. |
Node (float x, float
y, float z, ArrayList links) Creates a Node object with a spatial location defined by the parameters given. The links parameter assumes an ArrayList of Connectors is being given to it. |
Method Summary | |
void | reset () Sets 'parent' to null and sets 'f', 'g' and 'h' properties to 0.0. |
void | setG () Calculates the cost of reaching this Node based on the Node's 'parent' property. |
void | setH (Node finish) Calculates the distance from this Node to the finish Node. |
void | setF (Node finish) Calculates the A* formula from this Node to the finish Node. |
void | MsetH (Node finish) Calculates the distance from this Node to the finish Node. Uses Manhattan method to calculate distance. |
void | MsetF (Node finish) Calculates A* formula from this Node to the finish Node. Uses Manhattan method to calculate distance. |
Node | copy () Returns a duplicate of this Node with outgoing links and location intact. Fields 'f', 'g' and 'h' will be set to 0.0. |
void | connect (Node n) Generates a Connector and adds it to the 'links' property to create an outgoing connection. The Euclidean distance between the two Nodes is used to calculate the distance property 'd' of the Connector. |
void | connect (Node n, float d) Generates a Connector and adds it to the 'links' property to create an outgoing connection. The parameter 'd' is used to define the Connector's distance property 'd'. |
void | connect (ArrayList links) Assumes an ArrayList of outgoing Connectors is given in the parameter and is added to the 'links' property of the Node. |
void | connectBoth (Node n) Generates a Connector and adds it to the 'links' property of this Node and the target Node to create a two-way link between the Nodes. The Euclidean distance between the two Nodes is used to calculate the distance property 'd' of the Connector. |
void | connectBoth (Node n, float d) Generates two Connectors and adds one to the 'links' property of this Node and the target Node to create a two-way link between the Nodes. The parameter 'd' is used to define the Connector's distance property 'd'. |
int | indexOf (Node n) Returns the index in 'links' of the Connector that is targeted at Node 'n'. |
boolean | connectedTo (Node n) Returns true if the Node has an outgoing connection to Node 'n'. |
boolean | connectedTogether (Node
n) Returns true if both Node 'n' and this Node have a Connector leading to each other. |
void | mulDist (float m) Iterates through 'links' property and multiplies the distance property 'd' of all outgoing Connectors and all incoming Connectors to this Node. |
void | setDist (Node n, float d) Sets the distance property 'd' of the outgoing Connector for Node 'n' to the parameter 'd'. |
void | setDistBoth () Sets the distance property 'd' of the Connector for Node 'n' to the parameter 'd' and does the same for the Connector leading to this Node from Node 'n'. |
void | disconnect () Iterates through 'links' property and removes all incoming links to this Node. |
void | radialDisconnect () Iterates through a sphere of influence around the Node unlinking Nodes. Used for corner linked Nodes to create space around obstacles. |
boolean | straightLink (Node myLink) Returns true if the Node 'myLink' is not connected at the corner to this Node. |
float | dist (Node n) Returns the Euclidean distance from this Node to Node 'n'. |
float | manhattan (Node n) Returns the Manhattan method distance from this Node to Node 'n'. |
Constructor Detail |
public Node ()
Creates a Node at a spatial location of (0.0, 0.0, 0.0). The 'links' ArrayList property is empty and awaits calls to the connect methods to attach it to other Nodes.
public Node (float x, float y)
Creates a Node at a spatial location of (x, y, 0.0). Nodes that share a 'z' property of 0.0 bypass the longer equation needed to measure distances in 3D. This means the user is free to develop 2D searches without concern for the 3D support slowing their code down. The 'links' ArrayList property is empty and awaits calls to the connect methods to attach it to other Nodes.
Parameters:
x - the 'x' property of the Node's spatial location.
y - the 'y' property of the Node's spatial location.
public Node (float x, float y, float z)
Creates a Node at a spatial location of (x, y, z). The 'links' ArrayList property is empty and awaits calls to the connect methods to attach it to other Nodes.
Parameters:
x - the 'x' property of the Node's spatial location.
y - the 'y' property of the Node's spatial location.
z - the 'z' property of the Node's spatial location.
public Node (float x, float y, ArrayList links)
Creates a Node at a spatial location of (x, y, 0.0). Nodes that share a 'z' property of 0.0 bypass the longer equation needed to measure distances in 3D. This means the user is free to develop 2D searches without concern for the 3D support slowing their code down. The 'links' parameter assumes an ArrayList of Connectors leading to other Nodes has been given and the Node will possess those outgoing connections.
Parameters:
x - the 'x' property of the Node's spatial location.
y - the 'y' property of the Node's spatial location.
links - an ArrayList of Connectors leading to other
Nodes.
public Node (float x, float y, float z, ArrayList links)
Creates a Node at a spatial location of (x, y, z). The 'links' parameter assumes an ArrayList of Connectors leading to other Nodes has been given and the Node will possess those outgoing connections.
Parameters:
x - the 'x' property of the Node's spatial location.
y - the 'y' property of the Node's spatial location.
z - the 'z' property of the Node's spatial location.
links - an ArrayList of Connectors leading to
other Nodes.
Method Detail |
public void reset ()
This method resets all of the parameters of the Node and is called on all Nodes at the beginning of each search. The fields 'f', 'g' and 'h' are set to 0.0, the field 'parent' is set to null.
public void setG ()
This method generates a score for the property 'g' by successively adding the 'd' properties of Connectors together. This is used by the dijkstra() and aStar() methods to create efficient paths.
public void setH (Node finish)
This method calculates the Euclidean distance from this Node to the finish Node and applies the result to the field 'h'.
Parameters:
finish - the goal of the search.
public void setF (Node finish)
This method calculates the sum of properties 'g' and 'h' and assigns the result to property 'f'. This forms the A* formula:
f = g+h
Where 'g' is the cost of reaching this Node and 'h' is the distance to the target. This method is used by aStar() to calculate the shortest path without conducting an exhaustive search.
Parameters:
finish - the goal of the search.
public void MsetH (Node finish)
This method calculates the Manhattan method distance from this Node to the finish Node and applies the result to the field 'h'. This method can be faster an encourage straighter paths, but will not guarantee the shortest path because it overestimates the score.
Parameters:
finish - the goal of the search.
public void MsetF (Node finish)
This method calculates the sum of properties 'g' and 'h' and assigns the result to property 'f'. This forms the A* formula:
f = g+h
Where 'g' is the cost of reaching this Node and 'h' is the distance to the target. This method is used by aStar() to calculate the shortest path without conducting an exhaustive search. In calculating 'h' the Manhattan method is used. This method can be faster an encourage straighter paths, but will not guarantee the shortest path because it overestimates the score.
Parameters:
finish - the goal of the search.
public Node copy ()
This returns a copy of the Node with outgoing links and location the same.
public void connect (Node n)
This method generates an outgoing Connector targeted at Node 'n' and adds it to the 'links' property. The 'd' property of the Connector is the Euclidean distance from this Node to Node 'n'. The user should understand that this method generates a one-way link (which may be desirable) and they will have to either call this method on Node 'n' targeting this Node or call connectBoth() to create a two-way connection.
Parameters:
n - a Node for which a Connector will be generated.
public void connect (Node n, float d)
This method generates an outgoing Connector targeted at Node 'n' and adds it to the 'links' property. The parameter 'd' is assigned to distance property 'd' of the Connector. This allows the user to create wormhole like connections which have a low cost for travelling through and will be favourable to the search algorithm. The user should understand that this method generates a one-way link (which may be desirable) and they will have to either call this method on Node 'n' targeting this Node or call connectBoth() to create a two-way connection.
Parameters:
n - a Node for which a Connector will be generated.
d - the distance property of the generated.
public void connectBoth (Node n)
This method generates an outgoing Connector targeted at Node 'n' and adds it to the 'links' property. It also generates an incoming Connector from Node 'n' to create a two-way connection. The 'd' property of both Connectors is the Euclidean distance from this Node to Node 'n'.
Parameters:
n - a Node to which a two-way connection is created.
public void connectBoth (Node n, float d)
This method generates an outgoing Connector targeted at Node 'n' and adds it to the 'links' property. It also generates an incoming Connector from Node 'n' to create a two-way connection. The parameter 'd' is assigned to distance property 'd' of the Connector. This allows the user to create wormhole like connections which have a low cost for travelling through and will be favourable to the search algorithm.
Parameters:
n - a Node to which a two-way connection is created.
d - the distance property of both generated Connectors.
public int indexOf (Node n)
This returns the index value of the Connector in 'links' that is targeted at Node 'n'. If there is more than one Connector targeted at at Node 'n' then it will only return the value of the first Connector that qualifies. If no Connector in 'links' is targeted at 'n' then this method will return the value -1.
Parameters:
n - a Node for which the index of a Connector is to be found.
public boolean connectedTo (Node n)
This returns true if a Connector is found in 'links' that is targeted at Node 'n'.
Parameters:
n - a Node to which a Connector for is to be verified.
public boolean connectedTogether (Node n)
This returns true if a Connector is found in 'links' that is targeted at Node 'n' and if there is a Connector from 'n' targeted to this Node.
Parameters:
n - a Node for which a two-way connection to is to be verified.
public void mulDist (float m)
This method iterates through outgoing Connectors from this Node and multiplies the 'd' property of all those Connectors by the parameter 'm'. This method is useful for maps with terrain modifiers upon them. A square can be set as difficult or easy to travel though.
Parameters:
m - a value by which the 'd' properties of the outgoing Connectors will be multiplied.
public void setDist (Node n, float d)
This method finds the Connector targeted at Node 'n' and sets it's distance property 'd' to the parameter of the same name. It targets only the first Connector it finds and if a Connector for 'n' does not exist then this method silently fails.
Parameters:
n - a Node for which the Connector is to be found
and modified.
d - the new distance property 'd' of the Connector
for Node 'n'.
public void setDistBoth (Node n, float d)
This method finds the Connector targeted at Node 'n' and sets it's distance property 'd' to the parameter of the same name. It then does the same for a Connector targeted at this Node. It targets only the first Connectors it finds and if a Connector for 'n' does not exist then this method silently fails. If an outgoing Connector to 'n' exists but a return Connector does not, then the outgoing Connector is still set but the method will not throw an exception.
Parameters:
n - a Node for which an outgoing and incoming
Connector is to be found and modified.
d - the new distance property 'd' for the modified
Connectors.
public void disconnect ()
This method iterates through all of the outgoing Connectors from this Node and then removes any incoming Connectors targeted at this Node. This effectively removes the Node from a search whilst preserving it's outgoing links. This method will not be effective in cases where one-way connections incoming to this Node exist.
public void radialDisconnect ()
This method uses the shortest Euclidean distance to a connected Node to define a sphere of disconnection. The aim of this is to generate a physical presence and force all paths around. Because a search path has no width it will take impossible routes through unwalkable Nodes next to each other at diagonals. This method removes such links, making search paths respect the physical presence of a disconnected Node. Like disconnect() this method uses the Node's immediate Connectors to calculate the disconnection and may not be effective in cases of one-way links.
public boolean straightLink (Node myLink)
This method returns true if the Node 'myLink' is not Connected at the corners to myLink. This is deduced from the notion that if the Node's coordinates differ only along one dimension (say only 'z' for example), then that link is perpendicular to one of the other 'straight links'.
Parameters:
myLink - a Node to be tested for a link along one dimension only.
public float dist (Node n)
This returns the Euclidean distance from this Node to Node 'n'. This method checks the 'z' properties of both Nodes before calculation. If 'z' in both Nodes is equal to 0.0 it performs the less expensive 2D measurement. In tests this proved to be faster than defaulting to 3D measurement all the time.
Parameters:
n - a Node to measure the distance to.
public float manhattan (Node n)
This returns the Manhattan method distance from this Node to Node 'n'. Manhattan measurement is faster and offers straighter paths but is an overestimate and will not assist in offering the shortest path. This method checks the 'z' properties of both Nodes before calculation. If 'z' in both Nodes is equal to 0.0 it performs the less expensive 2D measurement. In tests this proved to be faster than defaulting to 3D measurement all the time.
Parameters:
b - a Node to measure the distance to.