Package lejos.robotics.pathfinding

Class Node

java.lang.Object

lejos.robotics.pathfinding.Node

Direct Known Subclasses:

GridNode, RandomSelfGeneratingNode

public class Node
extends java.lang.Object

This class represents a Node which can be connected to other neighboring nodes. Node sets can be searched using search algorithms. Typically the search algorithm only requires one starting node and one goal node. It assumes these nodes are linked by intermediate nodes.

See Also:

SearchAlgorithm

Field Summary

Fields

Modifier and Type	Field and Description
private Node	cameFrom The predecessor node used by A* search algorithm to mark off the previous node in the search tree.
private float	g_score The cumulative distance from the start node to this node.
private float	h_score
(package private) static int	MULTIPLIER This constant is multiplied with the float coordinate to get an integer for faster internal computations.
private java.util.ArrayList<Node>	neighbors List of neighbors to this node.
float	x The x coordinate of this node.
float	y The y coordinate of this node.

Constructor Summary

Constructors

Constructor and Description
Node(float x, float y) Creates a new instance of a node.

Method Summary

Modifier and Type	Method and Description
boolean	addNeighbor(Node neighbor) Adds a neighboring node to this node, connecting them together.
protected float	calculateG(Node neighbor) Calculates the distance to a neighbor node.
protected float	calculateH(Node goal) Calculates the distance to the goal node.
protected float	getF_Score() Method used by A* to calculate search score.
protected float	getG_Score() Method used by A* to calculate search score.
java.util.Collection<Node>	getNeighbors() Returns all the neighbors which this node is connected to.
protected Node	getPredecessor() Used by A* search.
int	neighbors() Indicates the number of neighbors (nodes connected to this node).
boolean	removeNeighbor(Node neighbor) Removes a node from this node as neighbors, effectively disconnecting them.
protected void	setG_Score(float g) Method used by A* to calculate search score.
protected void	setH_Score(float h) Method used by A* to calculate search score.
protected void	setPredecessor(Node orig) Used by A* search.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MULTIPLIER

static final int MULTIPLIER

This constant is multiplied with the float coordinate to get an integer for faster internal computations. A multiplier of 100 gives the equivalent of 2 decimal places (1.2345 = 123)

See Also:

Constant Field Values

x

public float x

The x coordinate of this node.

y

public float y

The y coordinate of this node.

g_score

private float g_score

The cumulative distance from the start node to this node.

h_score

private float h_score

cameFrom

private Node cameFrom

The predecessor node used by A* search algorithm to mark off the previous node in the search tree.

neighbors

private java.util.ArrayList<Node> neighbors

List of neighbors to this node.

Constructor Detail

Node

public Node(float x,
            float y)

Creates a new instance of a node.

Parameters:

x - The x coordinate of this node.

y - The y coordinate of this node.

Method Detail

getNeighbors

public java.util.Collection<Node> getNeighbors()

Returns all the neighbors which this node is connected to.

Returns:

The collection of all neighboring nodes.

neighbors

public int neighbors()

Indicates the number of neighbors (nodes connected to this node).

Returns:

int Number of neighbors.

addNeighbor

public boolean addNeighbor(Node neighbor)

Adds a neighboring node to this node, connecting them together. Note: You must make sure to add this node to the neighbor, and also add the neighbor to this node. This method doesn't do both.

Parameters:

neighbor - The neighboring node to connect with.

Returns:

Returns false if the neighbor already existed, or if you try to add this node to itself as a neighbor.

removeNeighbor

public boolean removeNeighbor(Node neighbor)

Removes a node from this node as neighbors, effectively disconnecting them. Note: You have to remove this node from the neighbor, and also remove the neighbor from this node. This method doesn't do both.

Parameters:

neighbor - The neighboring node to disconnect from.

Returns:

Returns false if the neighbor did not previously exist as a neighbor.

setH_Score

protected void setH_Score(float h)

Method used by A* to calculate search score. The H score is the estimated distance to the goal node from this node. It can either be distance "as the crow flies" or in the case of a grid navigation mesh, the minimum number of grid spaces to get to the goal node (x squares horizontally + y squares vertically from goal). NOTE: There is no getH_score() because the A* algorithm only needs to set this value, not retrieve it.

Parameters:

h -

calculateG

protected float calculateG(Node neighbor)

Calculates the distance to a neighbor node. This method is used to optimize the algorithm.

Parameters:

neighbor -

Returns:

the distance to neighbor

calculateH

protected float calculateH(Node goal)

Calculates the distance to the goal node. This method is used to optimize the algorithm.

Parameters:

goal -

Returns:

the distance to goal

setG_Score

protected void setG_Score(float g)

Method used by A* to calculate search score. The G score is the cumulative distance from the start node to this node.

Parameters:

g -

getG_Score

protected float getG_Score()

Method used by A* to calculate search score. The G score is the cumulative distance from the start node to this node.

Returns:

the search score

getF_Score

protected float getF_Score()

Method used by A* to calculate search score. You can't set FScore because it is derived internally by adding the gscore and hscore.

getPredecessor

protected Node getPredecessor()

Used by A* search. Stores the node that the search came from prior to this node.

Returns:

the predecessor node

setPredecessor

protected void setPredecessor(Node orig)

Used by A* search. Stores the node that the search came from prior to this node.

Parameters:

orig -