# A* (A-star) implementation in AS3

I am putting together a project for a class that requires me to put AI in a top down Tactical Strategy game in Flash AS3.

I decided that I would use a node based path finding approach because the game is based on a circular movement scheme. When a player moves a unit he essentially draws a series of line segments that connect that a player unit will follow along.

I am trying to put together a similar operation for the AI units in our game by creating a list of nodes to traverse to a target node. Hence my use of Astar (the resulting path can be used to create this line).

Here is my Algorithm

function findShortestPath (startN:node, goalN:node) { var openSet:Array = new Array(); var closedSet:Array = new Array(); var pathFound:Boolean = false; startN.g_score = 0; startN.h_score = distFunction(startN,goalN); startN.f_score = startN.h_score; startN.fromNode = null; openSet.push (startN); var i:int = 0 for(i= 0; i< nodeArray.length; i++) { for(var j:int =0; j<nodeArray[0].length; j++) { if(!nodeArray[i][j].isPathable) { closedSet.push(nodeArray[i][j]); } } } while (openSet.length != 0) { var cNode:node = openSet.shift(); if (cNode == goalN) { resolvePath (cNode); return true; } closedSet.push (cNode); for (i= 0; i < cNode.dirArray.length; i++) { var neighborNode:node = cNode.nodeArray[cNode.dirArray[i]]; if (!(closedSet.indexOf(neighborNode) == -1)) { continue; } neighborNode.fromNode = cNode; var tenativeg_score:Number = cNode.gscore + distFunction(neighborNode.fromNode,neighborNode); if (openSet.indexOf(neighborNode) == -1) { neighborNode.g_score = neighborNode.fromNode.g_score + distFunction(neighborNode,cNode); if (cNode.dirArray[i] >= 4) { neighborNode.g_score -= 4; } neighborNode.h_score=distFunction(neighborNode,goalN); neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; insertIntoPQ (neighborNode, openSet); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); } else if (tenativeg_score <= neighborNode.g_score) { neighborNode.fromNode=cNode; neighborNode.g_score=cNode.g_score+distFunction(neighborNode,cNode); if (cNode.dirArray[i]>=4) { neighborNode.g_score-=4; } neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; openSet.splice (openSet.indexOf(neighborNode),1); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); insertIntoPQ (neighborNode, openSet); } } } trace ("fail"); return false; }

Right now this function creates paths that are often not optimal or wholly inaccurate given the target and this generally happens when I have nodes that are not path able, and I am not quite sure what I am doing wrong right now.

If someone could help me correct this I would appreciate it greatly.

Some Notes

My OpenSet is essentially a Priority Queue, so thats how I sort my nodes by cost. Here is that function

function insertIntoPQ (iNode:node, pq:Array) { var inserted:Boolean=true; var iterater:int=0; while (inserted) { if (iterater==pq.length) { pq.push (iNode); inserted=false; } else if (pq[iterater].f_score >= iNode.f_score) { pq.splice (iterater,0,iNode); inserted=false; } ++iterater; } }

Thanks!

## Answers

Could you explain what's the purpose of these lines:

if (cNode.dirArray[i] >= 4) { neighborNode.g_score -= 4; }

A* is for problems where costs are always positive i.e. cost of paths is monotonically increasing.

Another thing to check, regarding optimality, is that distFunction() is returning always a value which is lesser or equal than the actual cost to reach the goal (i.e. the heuristic is required to be admissible so A* can guarantee it will find optimal solutions).

I don't know anything about AS3 at all - so I can't comment on the priority queue usage.

There is a fast implementation here: https://github.com/tomnewton/AS3AStar

Try out http://script3.blogspot.com/2010/04/star-path-finding-algorthim-in.html you can find there powerful a* pathfinding class with smooth pathfinding option.