GODPAPER | All Packages | All Classes | Index | Frames No Frames |
AStar

Package | com.lookbackon.ds.aStar
Class | public class AStar
Inheritance | AStar AbstractProcess Object

In computer science, A(pronounced "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. Peter Hart, Nils Nilsson and Bertram Raphael first described the algorithm in 1968.[1] It is an extension of Edsger Dijkstra's 1959 algorithm. Aachieves better performance (with respect to time) by using heuristics.

See also

http://www.policyalmanac.org/games/aStarTutorial.htm
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Public Properties
Hide Inherited Public Properties
Show Inherited Public Properties

| Property | Defined By
--- | --- | ---
|  | grid : AStarNodeBoard | AStar
|  | heuristic : Function | AStar
|  | isSelfManaging : Boolean | AbstractProcess
|  | path : Array [read-only] | AStar
|  | percentage : Number [override] [read-only] inheritDoc | AStar
|  | processDone : Boolean | AStar
|  | visited : Array [read-only] | AStar

Protected Properties
Hide Inherited Protected Properties
Show Inherited Protected Properties

| Property | Defined By
--- | --- | ---
|  | _isSelfManaging : Boolean | AbstractProcess

Public Methods
Hide Inherited Public Methods
Show Inherited Public Methods

| Method | Defined By
--- | --- | ---
|  | AStar(isSelfManaging:Boolean = false) | AStar
|  | diagonal(node:AStarNode):Number The standard heuristic for a square grid is the Diagonal distance. | AStar
|  | euclidian(node:AStarNode):Number The standard heuristic for a square grid is the Euclidean distance. | AStar
|  | manhattan(node:AStarNode):Number The standard heuristic for a square grid is the Manhattan distance. | AStar
|  | run():void [override] Like all informed search algorithms, it first searches the routes that appear to be most likely to lead towards the goal. | AStar
|  | runAndManage(allocation:int):void | AbstractProcess
|  | terminate():void | AbstractProcess
|  | yield():void | AbstractProcess

Property Detail

grid | property

`grid:AStarNodeBoard`

Implementation
`public function get grid():AStarNodeBoard`
`public function set grid(value:AStarNodeBoard):void`

heuristic | property |

`heuristic:Function`

Implementation
`public function get heuristic():Function`
`public function set heuristic(value:Function):void`

path | property |

`path:Array` [read-only]

Implementation
`public function get path():Array`

percentage | property |

`percentage:Number` [read-only] [override]

inheritDoc

Implementation
`public function get percentage():Number`

processDone | property |

`processDone:Boolean`

Implementation
`public function get processDone():Boolean`
`public function set processDone(value:Boolean):void`

visited | property |

`visited:Array` [read-only]

Implementation
`public function get visited():Array`
Constructor Detail

AStar | () | Constructor

`public function AStar(isSelfManaging:Boolean = false)`

Parameters

| `isSelfManaging:Boolean` (default = `false`)``

Method Detail

diagonal | () | method

`public function diagonal(node:AStarNode):Number`

The standard heuristic for a square grid is the Diagonal distance. On a square grid that allows 8 directions of movement, use Diagonal distance (L∞).

Parameters

| `node:AStarNode` — AStarNode carried some node info.

Returns

| `Number` — Diagonal distance

See also

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

euclidian | () | method |

`public function euclidian(node:AStarNode):Number`

The standard heuristic for a square grid is the Euclidean distance. On a square grid that allows any direction of movement, you might or might not want Euclidean distance (L2). If Ais finding paths on the grid but you are allowing movement not on the grid, you may want to consider other representations of the map.

Parameters

| `node:AStarNode` — AStarNode carried some node info.

Returns

| `Number` — Euclidean distance

See also

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

manhattan | () | method |

`public function manhattan(node:AStarNode):Number`

The standard heuristic for a square grid is the Manhattan distance. On a square grid that allows 4 directions of movement, use Manhattan distance (L1).

Parameters

| `node:AStarNode` — AStarNode carried some node info.

Returns

| `Number` — Manhattan distance

See also

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

run | () | method |

`override public function run():void`

Like all informed search algorithms, it first searches the routes that appear to be most likely to lead towards the goal.

Thu Jan 16 2014, 01:11 PM +08:00