AStar

AStar class

The AStar class has been set up for a range of uses. After instantiation the user will need to set the flags that will determine how AStar will build a Node-web for them. These flags include linking to squares at the corners of a square as well as distance functions, etc. Then the aStar.makeCuboidNodes() method can be used followed by setting unwalkable squares, disconnecting nodes and lastly adding terrain modifiers.

The following is an example of how you might set up AStar:

// This is our AStar setup
  // A bit long but we want to get it right.
  
  aStar = new AStar();
  
  // Set operation flags
  
  aStar.corners = true;
  aStar.manhattan = false;
  
  // Center it on screen and make a search web
  
  aStar.offset = new float [] {
    nodeWidth/2, nodeHeight/2, 0.0  };
  aStar.makeCuboidNodes(new int [] {
    numCols, numRows  }
  , nodeWidth);
  
  // Make some unwalkable nodes and then disconnect
  
  for(int i = 0; i < 30; i++){
    Node n = (Node)aStar.nodes.get((int)random(aStar.nodes.size()));
    if(n.walkable){
      n.walkable = false;
    }
  }
  aStar.radialDisconnectUnwalkables();
  
  // Let's make the terrain a little lumpy by adding a third dimension
  // We have to modify all of the nodes or the pathfinder will crash.
  // What's interesting is that a high node is hard to get to but the other
  // high node next to it is easy to get to. Use your imagination and have fun.
  
  for(int i = 0; i < aStar.nodes.size(); i++){
    Node n = (Node)aStar.nodes.get(i);
    n.p = n.addP(new float [] {
      0.0, 0.0, random(nodeWidth * 10)    }
    );
  }

This example can be seen in use here

Field Summary
Vector	nodes A storage array for the Nodes used in the AStar algorithm.
Vector	open An array used to collect information on possible routes.
Vector	closed An array of nodes forming possible routes.
boolean	wrap Setting for makeCuboidWeb() and makeCuboidNodes() as to whether a web of Nodes wraps around at its edges. Initially set to false.
boolean	corners Setting for makeCuboidWeb() and makeCuboidNodes() as to whether a web of Nodes links at the corners of nodes. Initially set to false.
boolean	manhattan Sets the AStar to measure distances by adding width, height, depth, etc. Set to false uses Euclidean distances, slower but more accurate. A false setting produces jagged paths on a node-web without corner links. Initially set to true.
boolean	bfs When set to true, ignores the cost of getting to the target. Paths run into alleys and then walk out instead of avoiding them. Although stupid, setting this to true offers a lot of speed. Initially set to false.
float []	offset Setting applied to all Nodes generated with makeCuboidWeb() and makeCuboidNodes(). Refers to the top left most point in generating the web.

Constructor Summary

AStar ()
Creates an AStar pathfinding class without nodes and set to initial state.

AStar (Vector nodes)
Creates an AStar pathfinding class using the nodes given in the parameters.

AStar (int [] dim, float scale)
Creates an AStar pathfinding class and sends a call to the makeNodes method with the given parameters.

Method Summary
Vector	getPath (Node start, Node finish) Returns a Vector containing a route through all of the AStar's array of nodes from start to finish. The objects in the Vector are all Nodes.
void	makeCuboidNodes (int [] dim, float scale) Creates a web of connected Nodes of cuboid dimensions to the scale and dimensions offered and adds them to the nodes field.
void	addNodes (Vector nodes) Adds the Nodes given in the parameters.
Vector	makeCuboidWeb (int dim, float scale) Returns a Vector containing a web of connected Nodes of cuboid dimensions to the scale and dimensions offered.
void	disconnectUnwalkables () Disconnects the links to all of the nodes whose walkable field is set to false.
void	radialDisconnectUnwalkables () Disconnects the links to all of the nodes whose walkable field is set to false and surrounding links that are too near the unwalkable Node.
void	dimSize (int dim) Modifies the number of dimensions all the Nodes use.
int []	getFolded (int n, int [] d) Returns an n-dimensional vector in the form of an array assuming that n is a unit in a list folded into a cuboid of the dimensions given.
int	getUnfolded (int [] p, int [] d) Returns a point in a list from a point in a list folded into a cuboid of the dimensions given.

Constructor Detail

AStar

public AStar ()

Creates an object that can be used to find routes through Nodes. Nodes are objects that contain a Vector linking them by reference to other Nodes and a spatial coordinate. This constructor is advised in generating custom searches, allowing one to set flags and generate a web of nodes offering the fastest search.

AStar

public AStar (Vector Nodes)

Creates an object that can be used to find routes through the Vector of Nodes given to it. Nodes are objects that contain a Vector linking them by reference to other Nodes and a spacial coordinate. This constructor assumes either the presence of another AStar object from which a web of Nodes has been generated or a user made world of Nodes has been generated.

Parameters:

Nodes - a Vector of Nodes to be used in a search.

AStar

public AStar (int [] dim, float scale)

Creates an object that can be used to find routes through a cuboid of Nodes. Nodes are objects that contain a Vector linking them by reference to other Nodes and a spacial coordinate. The parameters given refer to a cuboid of Nodes of dimensions given in the array "dim". These Nodes will be spaced out from the top left most corner at a distance specified by "scale". The Nodes will be automatically created according to the initial flags. This method is a shortcut to a cuboid of Nodes not connected at the corners using the normal AStar search.

Parameters:

dim - an array describing a cuboid of unit Nodes.
scale - the spacing of Nodes in the cuboid.

Method Detail

getPath

public Vector getPath (Node start, Node finish)

AStar searches from the start Node to every connecting Node evaluating a score for each Node and developing the search based on the best score. The formula for this score is:

f = g + h

f is the score applied to the Node, g is the cost of reaching the goal and h is the heuristic distance to the goal. This creates the shortest route to the finish Node. For a much faster search the "bfs" flag can be set to true and the search will ignore the cost to reach the goal. This results in running into alley ways and out in the search, but is computationally faster and should be considered in the presence of few obstacles. If the getPath() method cannot complete its route to the finish node a compromise path is offered that leads to the closest available Node from the finish Node. Note that the compromise is not always efficacious.

Parameters:

start - the starting Node for the search.
finish - the goal to reach in the search.

makeCuboidNodes

public void makeCuboidNodes (int [] dim, scale)

This method resets the nodes field and fills it with a cuboid web of Nodes whose dimensions measured in Nodes reflect the dimensions given. The Nodes are spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the AStar object.

Parameters:

dim - an array defining a line, plane, cuboid or hypercuboid.
scale - the distance between the Nodes excluding diagonal distances.

addNodes

public void addNodes (Vector nodes)

Adds the Vector given to the nodes field. This method can be used after generating custom node environments to add said environments to an AStar object.

Parameters:

nodes - a Vector of Nodes.

makeCuboidWeb

public Vector makeCuboidWeb (int [] dim, scale)

This method returns a cuboid web of Nodes whose dimensions measured in Nodes reflect the dimensions given. The Nodes are spaced apart according to the scale parameter. The Nodes are automatically linked according to the flag settings of the AStar object.

Parameters:

dim - an array defining a line, plane, cuboid or hypercuboid.
scale - the distance between the Nodes excluding diagonal distances.

disconnectUnwalkables

public void disconnectUnwalkables ()

This method iterates through the whole nodes field and disconnects the incoming links to all Nodes whose walkable field is set to false.

radialDisconnectUnwalkables

public void radialDisconnectUnwalkables ()

This method iterates through the whole nodes field and disconnects all links in a sphere around all Nodes whose walkable field is set to false. The range of effect is determined by the shortest link. This method relies on the number of dimensions each Node has. If this has been altered then this method may not work properly. Alter dimensions of Nodes after using this function. This method has been supplied to solve the problem of allowing corner links to nodes without paths passing halfway into the object.

dimSize

public void dimSize (int dim)

This method trims or expands the number of dimensions used by all Nodes in the nodes field. Take note that the maximum number of dimensions AStar will recognise is four, and that numerous methods rely on the number of dimensions Nodes use for altering them. As far as distance measuring is concerned, Nodes with dimensions greater than four will only have their first four dimensions used in distance calculations.

Parameters:

dimSize - the new number of dimensions all Nodes in the nodes field will use.

getFolded

public int [] getFolded (int n, int [] d)

This method returns a point in a cuboid. The point will have as many dimensions as the cuboid. The cuboid is defined by the array given and the point is a unit on a line folded into the cuboid given. This method is supplied because the nodes field is a linear array. Getting the index of individual nodes may prove troublesome for those who do not know the equations for turning lines into planes, cubes or hypercubes. This method should not replace those equations in practise because it is slow. It is supplied for dealing with an arbitrary number of dimensions and is used in Node-web generation.

Parameters:

n - a unit in list or an array of a singular dimension.
d - the dimensions of a cuboid that it is assumed the aforementioned list has been folded into.

getUnfolded

public int getUnfolded (int [] p, int [] d)

This method returns a point on a line or list that has a length equal to the dimensions of a cuboid given in the parameters multiplied together. This method is supplied because the nodes field is a linear array. Getting the index of individual nodes may prove troublesome for those who do not know the equations for turning lines into planes, cubes or hypercubes. This method should not replace those equations in practise because it is slow. It is supplied for dealing with an arbitrary number of dimensions and is used in Node-web generation.

Parameters:

p - a location in a cuboid to be turned into a unit on a list.
d - the dimensions of said cuboid which is actually a list assuming the shape of a cuboid.