Hi,

So I am trying to get A* pathfinding working in my project. I know there are some solutions out there but I am trying to go for a Javascript solution that I kinda know a little of whats going on behind the scenes. I found this script partially on here (ported a bit to Unity) and a site that had this script for flash. Most implementations ive seen for flash usually return a solution within 8ms. Well when I use this on Update or Awake depending on the size of my grid that Im using it can cause Unity to hang (little color circle thingy) before it comes to the solution. I would hope I could solve a 64x64 grid rather quickly(honesty id like to solve up to 1024x1024) but thats not the case. Anyone have any pointers for profiling this? Or can anyone see anything in my code that I can do better? Im sorry its a bit of a mess. (oh and I do have another function that sets some of the grid to unpassable (-1)… I just left it out.

```
class MapPathFinder
{
private var finalPosition : Vector2;
private var startPosition : Vector2;
// Storing Arrays That Handle All Nodes
private var openList : Array;
private var closedList : Array;
// 2D Array For Grid Of Environment
private var _array : Array;
// If To Use Euclidean Instead Of Manhattan
private var allowDiagonal : boolean = false;
private var _gridSize : int;
// Constructor
function MapPathFinder(ar : Array, gr : int){
this.instantiate(ar , gr);
}
// Reset / Instantiate Arrays
// Expects: Array of Map points
// Returns: NULL
function instantiate(ar : Array, gr : int){
this._array = ar;
this._gridSize = gr;
this.openList = new Array();
this.closedList = new Array();
}
function init(startPos : Vector2, finalPos : Vector2){
var startX : int = startPos.x;
var startY : int = startPos.y;
var finalX : int = finalPos.x;
var finalY : int = finalPos.y;
// CHECK IF START END POINTS ARE VALID
if (this._array[startX][startY] >= 0 this._array[finalX][finalY] >= 0){
// Store for reference
this.startPosition = startPos;
this.finalPosition = finalPos;
// Create Node And Add to OpenList
var startingNode : StructNode = new StructNode(startPosition, 0, 0, 0);
this.openList.Push(startingNode);
//Debug.Log(finalPosition);
}
}
// ** Find the successors ** //
function getSuccessorsFlash(pos : Vector2){
var r : int = pos.x;
var c : int = pos.y;
// put all the successors in this array...
var ret = new Array ();
if (this._array[r - 1][c] == 0) {
ret.push ([r - 1, c]);
}
if (this._array[r][c + 1] == 0) {
ret.push ([r, c + 1]);
}
if (this._array[r + 1][c] == 0) {
ret.push ([r + 1, c]);
}
if (this._array[r][c - 1] == 0) {
ret.push ([r, c - 1]);
}
// ** disabling the diagonal movement ** //
/*
if (this._array[r + 1][c + 1] == 0 this._array[r][c + 1] == 0 this._array[r + 1][c] == 0) {
ret.push([r + 1, c + 1]);
}
if (this._array[r + 1][c - 1] == 0 this._array[r][c - 1] == 0 this._array[r + 1][c] == 0) {
ret.push([r + 1, c - 1]);
}
if (this._array[r - 1][c - 1] == 0 this._array[r][c - 1] == 0 this._array[r - 1][c] == 0) {
ret.push([r - 1, c - 1]);
}
if (this._array[r - 1][c + 1] == 0 this._array[r][c + 1] == 0 this._array[r - 1][c] == 0) {
ret.push([r - 1, c + 1]);
}
*/
return ret;
};
// Looks Up All Directions From Current Node
// Expects: Vector2
// Returns: List of Vector2 items
function getSuccessors(pos : Vector2){
// Split X and Y into Int based R and C
var r : int = pos.x;
var c : int = pos.y;
//Debug.Log(r);
// Build Base Direction List
var ret : Array = new Array();
if (r-1 > -1)
{
if (this._array[r - 1][c] >= 0) {
ret.Push (new Array(Vector2(r - 1, c), this._array[r - 1][c]));
}
}
if (c+1 < _gridSize)
{
if (this._array[r][c + 1] >= 0) {
ret.Push (new Array(Vector2(r, c + 1), this._array[r][c + 1]));
}
}
if (r + 1 < _gridSize){
if (this._array[r + 1][c] >= 0) {
ret.Push (new Array(Vector2(r + 1, c), this._array[r + 1][c]));
}
}
if (c-1 > -1)
{
if (this._array[r][c - 1] >= 0) {
ret.Push (new Array(Vector2(r, c - 1), this._array[r][c - 1]));
}
}
return (ret);
}
// Gets Distsance between points specified
// Expects: Vector2 for each of the two points
// Returns: Integer distance between points
function getDistance(pos1 : Vector2, pos2 : Vector2){
var d1 : int = Mathf.Abs(pos2.x - pos1.x);
var d2 : int = Mathf.Abs(pos2.y - pos1.y);
return (d1 + d2);
}
function findPath(startPos : Vector2, finalPos : Vector2){
init(startPos, finalPos);
// Iterate OpenList And Find Lowest Cost
while (this.openList.length > 0){
var _max : int = 5000;
var _selected : int = -1;
for (var o=0;o<this.openList.length;o++){
if (this.openList[o].f < _max){
_max = this.openList[o].f;
_selected = o;
}
}
// Remove Node From List And Check If Final Node Required
var node : StructNode = this.openList[_selected];
this.openList.RemoveAt(_selected);
if (node.pos == this.finalPosition){
this.closedList.Push(node);
// Get Last Node And Work Backwards
var cur : StructNode = this.closedList[this.closedList.length - 1];
var ret : Array = new Array();
if(cur.parent != "") {
}
// Build Path
while (cur.parent !== null){
ret.Push(cur);
cur = cur.parent;
}
// Return To Initial Caller
return (ret);
}
//Debug.LogError("foo");
// Get Other Directions And Iterate To Find Best Path
//var successors : Array = this.getSuccessors(node.pos);
var successors : Array = this.getSuccessors(node.pos);
for (var a=0;a<successors.length;a++) {
// Set Skip Default
var _skip : boolean = false;
// Build Struct Properties
var g : int = node.g + this.getDistance(successors[a][0], node.pos);
//var h : int = this.getHeuristic(successors[a][0], this.finalPosition) + successors[a][1];
var h : int = this.getDistance(successors[a][0], this.finalPosition);
var f : int = g + h;
// Create New Node, Apply Parent And Iterate On
var struct : StructNode = new StructNode(successors[a][0], g, h, f);
struct.parent = node;
// Check Lowest Cost In Open List
for (var bo in openList) {
if (bo.pos == struct.pos bo.f < struct.f) {
_skip = true;
break;
}
}
// Check Lowest Cost In Closed List
for (var bc in this.closedList) {
if (bc.pos == struct.pos bc.f < struct.f) {
_skip = true;
break;
}
}
// If Not Found
if (_skip == false) {
// Check Same Position And Remove If Exists
var coCount : int = -1;
for (var co in this.openList) {
coCount++;
if (co.pos == struct.pos) {
this.openList.RemoveAt(coCount);
}
}
// Check Same Position And Remove If Exists
var ccCount : int = -1;
for (var cc in this.closedList) {
ccCount++;
if (cc.pos == struct.pos) {
this.closedList.RemoveAt(ccCount);
}
}
// Add Node To Open List
this.openList.Push(struct);
}
}
// Add Node To Closed List
this.closedList.Push(node);
} // end while
Debug.Log("IMPOSSIBLE TO FIND A PATH");
return (new Array());
}
function Update () {
}
}
```

here is how im calling it. If you need a project please let me know too. And sorry if my math is off on the world to grid conversions .

```
var gridSize = 10;
var castHeight = 10;
var floorGeo : Transform;
var startGeo : Transform;
var endGeo : Transform;
private var grid : Object[];
//private var mypath : Object[];
private var layerMask = 1 << 8;
private var cellSize;
private var mapMoveXToMap;
private var mapMoveYToMap;
private var mapMoveXToWorld;
private var mapMoveYToWorld;
function Array2D(rows : int, columns : int)
{
var array = new Object[rows];
for (i = 0; i < array.length; i++)
{
array[i] = new int[columns];
}
return array;
}
function buildMap (grid : Object[])
{
for (x = 0; x < grid.length; x++)
{
for (z = 0; z < grid.length; z++)
{
grid[x][z] = hasWorldGeo(x,z);
}
}
}
function convertToMapSystem(point : Vector2){
//DIVIDE BY S AND FLOOR RESULT
var movedX = (point.x + mapMoveXToMap);
var movedY = (point.y + mapMoveYToMap);
var xInt : int = Mathf.Floor(Mathf.Abs(movedX/cellSize));
var yInt : int = Mathf.Floor(Mathf.Abs(movedY/cellSize));
return (Vector2(xInt, yInt));
}
function convertToWorldSystem(point : Vector2){
//MULT BY S
//var bounds = floorGeo.renderer.bounds;
//var cellSize = bounds.size.x/gridSize;
var xInt : float = (point.x * cellSize) + (cellSize/2) + mapMoveXToWorld;
var zInt : float = (point.y * -cellSize) - (cellSize/2) - mapMoveYToWorld;
return (Vector3(xInt, 0, zInt));
}
function searchPath(start : Vector2, end : Vector2){
//Debug.Log("ST: " + start + " EN: " + end);
//Debug.Log("ST2: " + convertToMapSystem(start) + " EN2: " + convertToMapSystem(end));
//testLoc(convertToMapSystem(start), convertToMapSystem(end));
var pf = new MapPathFinder(grid,gridSize);
var path = pf.findPath(convertToMapSystem(start), convertToMapSystem(end));
if (path.length > 0){
var userPath : Array = new Array();
for (i=0;i<path.length;i++){
userPath.Push(convertToWorldSystem(path[i].pos));
}
return (userPath);
}
return (path);
}
function Awake () {
grid = new Array2D(gridSize, gridSize);
buildMap(grid);
var bounds = floorGeo.renderer.bounds;
cellSize = bounds.size.x/gridSize;
mapMoveXToMap = -((bounds.center.x)-(bounds.size.x*0.5));
mapMoveYToMap = -((bounds.center.z)+(bounds.size.z*0.5));
mapMoveXToWorld = bounds.center.x-(bounds.size.x*0.5);
mapMoveYToWorld = bounds.center.z-(bounds.size.z*0.5);
}
//then finally somewhere call this
var start = Vector2(startGeo.position.x,startGeo.position.z);
var end = Vector2(endGeo.position.x,endGeo.position.z);
mypath = searchPath(start, end);
```

[/code]