The Nodes are points in an n-dimensional space with links to other Nodes. They also have a number of fields concerning the calculation of the AStar algorithm. The AStar object hosts a few methods for creating networks of Nodes for you, but you can also make these networks yourself. Be certain that all the Nodes have the same number of dimensions, otherwise the AStar object managing them will throw an exception.
| Field Summary | |
| float [] | p An array serving as a location in space. Nodes measure their distances from each other using this array. p[0] corresponds to x, p[1] to y, etc. Methods x(), y(), etc. are supplied to make the user feel more at home. |
| Node | parent A Node initially set to null that aquires a setting during the course of the AStar algorithm. |
| float | f |
| float | g |
| float | h The distance to the goal from this Node. |
| Vector | links A Vector of Nodes referring to other Nodes, this defines the outgoing links from this Node. |
| boolean | walkable Determines whether this Node is considered an obstacle in a search. Also used in link stripping methods. Initially set to true. |
| float | x () Returns the value of p[0]. |
| float | y () Returns the value of p[1] or 0.0 if the Node has less than two dimensions. |
| float | z () Returns the value of p[2] or 0.0 if the Node has less than three dimensions. |
| float | w () Returns the value of p[3] or 0.0 if the Node has less than four dimensions. |
| Constructor Summary |
| Node (float
[] p) Creates a Node object with a spatial location defined by the parameter given. |
| Node (float []
p, Vector links) Creates a Node object with a spatial location defined by the parameter given. The Node is linked to all of the Nodes specified in the links parameter. |
| Method Summary | |
| void | reset () Sets parent to null and sets f, g and h fields to . |
| void | setF (Node finish, boolean bfs) Calculates AStar formula for this Node to the finish Node unless bfs is true, where instead the BFS formula will be used. |
| void | setG () Calculates the cost of reaching this Node. |
| void | setH (Node finish) Calculates the distance from this Node to the finish Node. |
| void | MsetF (Node finish, boolean bfs) Calculates AStar formula for this Node to the finish Node unless bfs is true, where instead the BFS formula will be used. Uses Manhattan formula to calculate distance. |
| void | MsetG () Calculates the cost of reaching this Node. Uses Manhattan formula to calculate distance. |
| void | MsetH (Node finish) Calculates the distance from this Node to the finish Node. Uses Manhattan formula to calculate distance. |
| Node | copy () Returns a duplicate of this Node with outgoing links and location intact. |
| void | connect (Node n) Adds the Node given in the parameters to the links field. |
| void | connect (Vector links) Adds all Nodes given in the parameters to the links field. |
| void | disconnect () Iterates through links field 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 given has a position that differs along one dimension only. |
| float [] | copyP () Returns a copy of the field p. |
| float [] | addP (float [] b) Adds the elements of the array given to the elements of the field p. |
| float [] | subP (float [] b) Subtracts the elements of the array given to the elements of the field p. |
| void | dimSize (int dim) Trims or expands the number of dimensions the field p uses. |
| float | dist (float [] b) Returns the Euclidean distance from this Node to the location defined in the parameters. |
| float | manhattan (float [] b) Returns the Manhattan distance from this Node to the location defined in the parameters. |
| Constructor Detail |
public Node (float [] p)
Creates a Node at a location defined in the parameters. The links Vector field is empty and awaits the input of links to other Nodes. Locations are stored in arrays because the AStar object has been created to deal with lines, planes, cubes and other constructs, so a flexible location method was required.
Parameters:
p - an array defining a spatial location.
public Node (float [] p, Vector links)
Creates a Node at a location defined in the parameters. The links Vector field is populated with the Nodes supplied in the parameters. Locations are stored in arrays because the AStar object has been created to deal with lines, planes, cubes and other constructs, so a flexible location method was required.
Parameters:
p - an array defining a spatial location.
links -
a Vector of Nodes that this Node is linked to.
| Method Detail |
public void reset ()
This method resets all of the parameters pertaining to the AStar algorithm. The fields f, g and h are set to 0.0, the field parent is set to null. This method is called on all Nodes in an AStar object at the beginning of each new call to getPath().
public void setF (Node finish, boolean bfs)
This method calculates the formula determined by f = g + h, the AStar formula for calculating the shortest route, then applies the result to the field f. If the boolean bfs is set to true it ignores the value g, causing a massive speed increase at a cost of accuracy. This latter method is called Best First Search.
Parameters:
finish - the goal of the search.
bfs - whether BFS is implemented. Set to false
implements standard AStar.
public void setG ()
This method calculates the cost of reaching this Node and applies it to the field g. This function is ignored in BFS (Best First Search).
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 MsetF (Node finish, boolean bfs)
This method calculates the formula determined by f = g + h, the AStar formula for calculating the shortest route, then applies the result to the field f. This method uses Manhattan distance measuring which adds the difference between dimensions together. This yields straighter paths and is faster but can be inaccurate as it is an overestimate. If the boolean bfs is set to true it ignores the value g, causing a massive speed increase at a cost of accuracy. This latter method is called Best First Search.
Parameters:
finish - the goal of the search.
bfs - whether BFS is implemented. Set to false
implements standard AStar.
public void MsetG ()
This method calculates the cost of reaching this Node and applies it to the field g. This method uses Manhattan distance measuring which adds the difference between dimensions together. This yields straighter paths and is faster but can be inaccurate as it is an overestimate. This function is ignored in BFS (Best First Search).
public void MsetH (Node finish)
This method calculates the Manhattan distance from this Node to the finish Node and applies the result to the field h. Manhattan distancing adds the difference between dimensions together. This yields straighter paths and is faster but can be inaccurate as it is an overestimate.
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 adds the given Node to the links field. This method is used in generating webs of Nodes and can be used to create wormholes and gateways.
Parameters:
n - a new outgoing link from this Node.
public void connect (Vector links)
This method adds the given Nodes to the links field. This method is used in generating webs of Nodes and can be used to add new rooms and environments to an existing web of Nodes.
Parameters:
links - new outgoing links from this Node.
public void disconnect ()
This method iterates through all of the Nodes in this Node's links field and disconnects those Nodes links to this Node. The outgoing links from this Node will be unaffected unless this command is called on many Nodes, whereby the links from this Node to a Node calling disconnect() will be severed.
public void radialDisconnect ()
This method defines a search radius defined by the shortest link to another Node. If the mid point of any link surrounding this Node falls in this search area then that link is severed. This serves to prevent corner linked Nodes from generating paths that ignore physical boundaries. This method uses straightLink() to determine the shortest link and will not work if extra dimensions have been added to the Nodes.
public boolean straightLink (Node myLink)
This method returns true if the Node given in the parameters has a location that differs along one dimension only. This is useful indetermining if a linking Node is connected by its corner or its face. This method becomes useless when the dimensions of the Node have been altered to infer terrain.
Parameters:
myLink - a Node to be tested for a link along one dimension only.
public float [] copyP ()
This method returns a copy of the field p, performing a deep copy for the user.
public float [] addP (float [] b)
This method iterates through the elements in the field p and adds to those elements the ones in the parameters given. The new p field will adopt the size of the greater array, p or b. This method is useful in generating unfavourable ground for a path to travel through. On a plane it would be comparable to scaling a mountain and in 3D it would be like moving through water. Ground on the same level is easiest to move through. To create difficult terrain, oscilate the height of the Nodes to be moved through, increasing the cost of passing them.
Parameters:
b - a modification to the field p.
public float [] subP (float [] b)
This method iterates through the elements in the field p and subtracts from those elements the ones in the parameters given. The new p field will adopt the size of the greater array, p or b. This method is useful in generating unfavourable ground for a path to travel through. On a plane it would be comparable to scaling a mountain and in 3D it would be like moving through water. Ground on the same level is easiest to move through. To create difficult terrain, oscilate the height of the Nodes to be moved through, increasing the cost of passing them.
Parameters:
b - a modification to the field p.
public void dimSize (int dim)
This method resizes the field p, trimming it or expanding it. This can be used to standardise modifications to Nodes or set scope for terrain modifiers.
Parameters:
dim - the new size of the field p.
public float dist (float [] b)
This returns the Euclidean distance from this Node's p field to the location in the parameters given. It assumes that both p and b are arrays of equal length, otherwise an exception will be thrown.
Parameters:
b - a location to measure the distance to.
public float manhattan (float [] b)
This returns the Manhattan distance from this Node's p field to the location in the parameters given. The Manhattan distance is the difference between the dimensions given added together. Like measuring how many blocks away a building is. It is very fast and offers straighter search paths but can overestimate costs. This method assumes that both p and b are arrays of equal length, otherwise an exception will be thrown.
Parameters:
b - a location to measure the distance to.