Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Oct 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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 loadBoolean:Boolean = true;
    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();
    stage.addEventListener(Event.ENTER_FRAME, frameLoaded);
    stage.addEventListener(KeyboardEvent.KEY_DOWN, startAStar);
    function frameLoaded(e:Event){
    	if(loadBoolean){
    		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;
    				this.addChildAt(nodeArray[i][j],((i*23)+j));
    			}
    		}
    		loadBoolean = false;
    	}
    }
    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
    New to the CF scene
    Join Date
    Oct 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I found the problem.
    I forgot to initialize the stop node if anyone was wondering.
    Though i'd still like this thread deleted.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •