Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: Need Help with A*

1. ## Need Help with A*

So I'm using as3 with the World Construction Kit and I made an attempt to implement the A* algorithm, but it doesn't work. This is the error it gives me:
Error: Error #1502: A script has executed for longer than the default timeout period of 15 seconds.
I have 3 classes. A Sensor_Node class which detects if it's being touched, and functions as the nodes that the algorithm evaluates. I also have a Sensor_Start and Sensor_Stop classes that the Sensor_Node detects in order to differentiate between the start and stop positions and obstacles.
Where I run my code I create all the nodes and put them in a 2D array. I then have a heuristic function that evaluates the heuristics and assigns those values to each node. Then some functional methods, then the algorithm.
I attempted to teach myself the algorithm and I understand how it works and the process it goes through, but I can't understand why it's not working here. Maybe WCK is made to cut off after a certain time-out point and the algorithm takes too long, but I think it's likely I made a mistake with it somewhere.
So finally here's the code it runs:

Code:
var nodeArray:Array = [];
var open_List:Array = [];
var closed_List:Array = [];
var start_Node:Sensor_Node;
var target_Node:Sensor_Node;
var checking_Node:Sensor_Node;
var foundTarget:Boolean = false;
var base_MoveCost:int = 10;

var tempNode:Sensor_Node = new Sensor_Node();
for(var i=0;i<23;i++){
nodeArray[i] = [];
for(var j=0;j<40;j++){
nodeArray[i][j]= new node_SensorNode();
nodeArray[i][j].x = (j+0.5)*20;
nodeArray[i][j].y = (i+0.5)*20;
}
}
}
}
function getHeuristic():Boolean{
var touching_Stop_i:int = -1;
var touching_Stop_j:int = -1;
for(var i=0;i<23;i++){
for(var j=0;j<40;j++){
if(nodeArray[i][j].touching_StopNode){
touching_Stop_i = i;
touching_Stop_j = j;
break;
}
}
}
if(touching_Stop_i>-1 && touching_Stop_j>-1){
for(i=0;i<23;i++){
for(j=0;j<40;j++){
var xdiff:int = Math.abs(touching_Stop_j - j);
var ydiff:int = Math.abs(touching_Stop_i - i);
nodeArray[i][j].h_Heuristic = xdiff+ydiff;
}
}
return true;
}else{
return false;
}
}
function arrayContains(v:Sensor_Node,a:Array):Boolean{
for(var i=0;i<a.length;i++){
if(a[i]==v){
return true;
}
}
return false;
}
function arrayRemove(target:Sensor_Node, a:Array):void{
for(var i=0;i<a.length;i++){
if(a[i]==target){
a.splice(i,1);
}
}
}
function getSallestFValue():Sensor_Node{
var s:Sensor_Node = open_List[0];
for(var i=0;i<open_List.length;i++){
if(open_List[i] < s){
s = open_List[i];
}
}
return s;
}
function setStartingNode():void{
for(var i=0;i<23;i++){
for(var j=0;j<40;j++){
if(nodeArray[i][j].touching_StartNode){
start_Node = nodeArray[i][j];
}
}
}
}
function setNodeCompass():void{
for(var i=0;i<23;i++){
for(var j=0;j<40;j++){
try{
nodeArray[i][j].setNorth(nodeArray[i-1][j]);
nodeArray[i][j].setSouth(nodeArray[i+1][j]);
nodeArray[i][j].setEast(nodeArray[i][j-1]);
nodeArray[i][j].setWest(nodeArray[i][j+1]);
}catch(e:Error){}
}
}
}
function startAStar(e:KeyboardEvent):void{
if(e.keyCode==32){
setNodeCompass();
setStartingNode();
if(getHeuristic()){
checking_Node = start_Node;
update();
}else{
trace("Error");
}
}
}
function update():void{
while(!foundTarget){
findPath();
}
traceBackPath();
}
function traceBackPath():void{
var n:Sensor_Node = target_Node;
while(n!=null){
n.gotoAndStop(5);
n=n.node_Parent;
}
}
function findPath():void{
if(!foundTarget){
try{
if(checking_Node.north){
determineNodeValues(checking_Node,checking_Node.north);
}
if(checking_Node.south){
determineNodeValues(checking_Node,checking_Node.south);
}
if(checking_Node.east){
determineNodeValues(checking_Node,checking_Node.east);
}
if(checking_Node.west){
determineNodeValues(checking_Node,checking_Node.west);
}
}catch(e:Error){

}
closed_List.push(checking_Node);
arrayRemove(checking_Node, open_List);
checking_Node = getSallestFValue();
}
}
function determineNodeValues(current:Sensor_Node, testing:Sensor_Node):void{
if(testing==null){return;}
if(testing==target_Node){
target_Node.node_Parent = current;
foundTarget = true;
return;
}
if(testing.touching_Something){
return;
}
if(!arrayContains(testing,closed_List)){
if(arrayContains(testing,open_List)){
var new_MoveCost = current.g_MoveCost + base_MoveCost;
if(new_MoveCost<testing.g_MoveCost){
testing.node_Parent = current;
testing.g_MoveCost = new_MoveCost;
testing.getfValue();
}
}else{
testing.node_Parent = current;
testing.g_MoveCost = current.g_MoveCost + base_MoveCost;
testing.getfValue();
open_List.push(testing);
}
}
}

Any help is appreciated. Please and Thank you.

2. I found the problem.
I forgot to initialize the stop node if anyone was wondering.
Though i'd still like this thread deleted.