|
-
Path finding A* so close yet so far
hey ppl,
i've been attempting some pathfinding and i have gotten really close! it works fine untill its surrounded by other nodes that have already been tested which means it cant do complex maps so heres the code:
A*
Code:
package {
import flash.display.*;
import flash.events.*;
import flash.utils.*;
import flash.text.TextField;
public class pf extends MovieClip {
public var map:Array = new Array();
public var floor:int=0;
public var wall:int=1;
public var tileWidth:Number=20;
public var xcoord;
public var ycoord;
public var curX;
public var curY;
public var startX;
public var startY;
public var endX;
public var endY;
public var startNode;
public var endNode;
public var Hx:Number;
public var newGx:Number;
public var nextNode;
public var openSet:Array = new Array();
public var closedSet:Array = new Array();
public var nodeAr:Array = new Array();
public var dontPush:Boolean = false;
public var mLength:Number;
public var fAr:Array = new Array();
public var startDown:Boolean=false;
public var openSetChange:Boolean=false
public var startPos:startBlock=new startBlock;
public var endPos:endBlock=new endBlock;
public var highlighter:squareSelected=new squareSelected;
public function initPF() {
map = [
/*[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]
];*/
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1],
[1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1],
[1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,0,1],
[1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,1,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
];
mLength = map[0].length;
//trace("mlength: "+mLength)
addChild(endPos);
addChild(startPos);
addChild(highlighter);
addEventListener(Event.ENTER_FRAME,calcMousePos);
addEventListener(MouseEvent.CLICK,startFinInit);
for (var k in map[0]) {
for (var i in map[k]) {
var n:node = new node(i,k,map[k][i]);
addChildAt(n,0);
if (nodeAr.length>=1) {
nodeAr.push(n);
} else {
nodeAr.push(n);
}
}
}
var button:path = new path();
addChild(button);
button.addEventListener(MouseEvent.CLICK,nextStep);
}
public function nextStep(event:MouseEvent) {
contAstar(nextNode,nextNode.x,nextNode.y,endNode.x,endNode.y);
}
public function calcMousePos(event:Event) {
xcoord=Math.floor(mouseX/tileWidth);
ycoord=Math.floor(mouseY/tileWidth);
highlighter.x=xcoord*tileWidth;
highlighter.y=ycoord*tileWidth;
//trace(mLength*ycoord+xcoord)
}
public function startFinInit(event:MouseEvent) {
//trace(nodeAr[0]);
if (startDown==false) {
if (map[ycoord][xcoord]!=wall) {
startPos.x=highlighter.x;
startPos.y=highlighter.y;
startNode = nodeAr[mLength*ycoord+xcoord];
trace(startNode.x,nodeAr[mLength*ycoord+xcoord])
startDown=true;
}
} else {
if (map[ycoord][xcoord]!=wall) {
endPos.x=highlighter.x;
endPos.y=highlighter.y;
endNode = nodeAr[mLength*ycoord+xcoord];
firstCalc(startNode,startNode.x,startNode.y,endNode.x,endNode.y);
startDown=false;
trace(startNode.x,startNode.y,endNode.x,endNode.y);
}
}
}
public function contAstar(sNode,cx,cy,ex,ey) {
if (sNode!= endNode) {
if (openSet.length>0) {
SurroundCalc(sNode,cx,cy-tileWidth,ex,ey);
SurroundCalc(sNode,cx,cy+tileWidth,ex,ey);
SurroundCalc(sNode,cx-tileWidth,cy,ex,ey);
SurroundCalc(sNode,cx+tileWidth,cy,ex,ey);
getSmallestF();
getNextNode();
}
} else {
trace("pathFound");
}
}
public function firstCalc(sNode,cx,cy,ex,ey) {
trace(cx,cy,ex,ey);
trace("iName = "+sNode.iName);
sNode.g = 0;
sNode.h = hueristic(cx,cy,ex,ey);
sNode.f = sNode.g+sNode.h;
closedSet.push(sNode);
SurroundCalc(sNode,cx,cy-tileWidth,ex,ey);
SurroundCalc(sNode,cx,cy+tileWidth,ex,ey);
SurroundCalc(sNode,cx-tileWidth,cy,ex,ey);
SurroundCalc(sNode,cx+tileWidth,cy,ex,ey);
getSmallestF();
getNextNode();
}
public function hueristic(x1,y1,x2,y2) {
Hx = Math.sqrt(((x2-x1)*(x2-x1))+((y2-y1)*(y2-y1)));
Hx = Math.round(Hx);
return Hx;
}
public function SurroundCalc(pNode,cx,cy,ex,ey) {
dontPush = false;
openSetChange = false
for (var i:Number = 0; i<=nodeAr.length-1; i++) {
if (nodeAr[i].x == cx && nodeAr[i].y == cy) {
for (var k:Number = 0; k <openSet.length; k++) {
if (openSet[k].iName == nodeAr[i].iName) {
openSetChange = true
trace("in open set");
trace("node: "+nodeAr[i].iName+" , "+"open: "+openSet[k].iName+"\n");
}
}
for (var j:Number = 0; j <closedSet.length; j++) {
if (closedSet[j].iName == nodeAr[i].iName ) {
dontPush = true;
trace("in closed set");
trace("node: "+nodeAr[i].iName+" , "+"closed: "+closedSet[j].iName+"\n");
}
}
if (dontPush == false) {
//trace(nodeAr[i].notWalkable)
if(!openSetChange){
if (nodeAr[i].notWalkable == false) {
pNode = MovieClip(parent).nodeAr[i];
var sNode = nodeAr[i];
sNode.g = pNode.g+10;
sNode.h = hueristic(cx,cy,ex,ey);
sNode.f =sNode.g+ sNode.h;
//trace("F: "+nodeAr[i].f);
openSet.push(sNode);
//trace("openSet.length: "+openSet.length)
for (var l:Number = 0; l < fAr.length; l++) {
fAr.splice(0,1);
}
}
}else{
sNode = nodeAr[i];
newGx = pNode.g+10;
if(newGx<sNode.g){
sNode.g = newGx;
sNode.f =sNode.g+ sNode.h;
}
}
}
}
}
trace("");
}
public function getSmallestF() {
for (var i:Number = 0; i<=openSet.length-1; i++) {
//trace(openSet[i].f)
fAr.push(openSet[i].f);
//trace("pushed")
}
fAr.sort(Array.NUMERIC);
trace("far: "+fAr)
}
public function getNextNode() {
closedSetPush:
for (var i:Number = 0; i<=nodeAr.length; i++) {
for (var k:Number = 0; k<=openSet.length-1; k++) {
//trace(openSet[k].iName+" is in openSet")
if (openSet[k].iName == nodeAr[i].iName) {
if (nodeAr[i].f == fAr[0]) {
trace("moved "+openSet[k].iName+" to closedSet");
closedSet.push(nodeAr[i]);
openSet.splice(k,1);
nextNode = nodeAr[i];
break closedSetPush;
}
}
/*wpx.push(nextNode.x)
wpy.push(nextNode.y)*/
}
}
for (var l:Number = 0; l<=closedSet.length-1; l++) {
trace(closedSet[l].iName+" is in closedSet")
}
}
}
}
node:
Code:
package {
import flash.display.*;
import flash.events.*;
import flash.utils.*;
import flash.text.TextField;
public class node extends MovieClip {
public var f:Number = -1;
public var g:Number = -1;
public var h:Number = -1;
public var notWalkable:Boolean = true;
public var costMultiplier:Number=1.0;
/*this.instanceName = "node"+(i*K)
trace(this.instanceName)*/
public function node(x,y,nw) {
addEventListener(Event.ENTER_FRAME,upDate);
if (nw == false) {
this.h_TXT.text = "";
this.g_TXT.text = "";
this.f_TXT.text = "";
this.gotoAndPlay(1);
} else {
this.gotoAndPlay(2);
}
notWalkable = nw
this.x=x*40;
this.y=y*40;
}
public function upDate(event:Event) {
if (notWalkable == false) {
if (h>=0) {
this.h_TXT.text = h.toString();
}
if (g>=0) {
this.g_TXT.text = g.toString();
}
if (f>=0) {
this.f_TXT.text = f.toString();
}
}
}
}
}
(excuse all the traces)
is there something i have done wrong? cos i'm sure i have got it 99% right just that last bit is wrong cheers to the person that helps me!
-
Palindrome emordnilaP
What would help is not to show us hard core code, you should upload swf examples that shows the behavior of the script. It's hard to visualize harder code concepts like unique path finding scripts (as they can all be completely different).
Also, at least comment the functions, like describe the purpose of the function and may be include some overview detail how it operates.
Just some tips to help you get a worthwhile response.
-
ah k will do
A*:
Code:
package {
import flash.display.*;
import flash.events.*;
import flash.utils.*;
import flash.text.TextField;
public class pf extends MovieClip {
public var map:Array = new Array();
public var floor:int=0;
public var wall:int=1;
public var tileWidth:Number=20;
public var xcoord;
public var ycoord;
public var curX;
public var curY;
public var startX;
public var startY;
public var endX;
public var endY;
public var startNode;
public var endNode;
public var Hx:Number;
public var newGx:Number;
public var nextNode;
public var openSet:Array = new Array();
public var closedSet:Array = new Array();
public var nodeAr:Array = new Array();
public var dontPush:Boolean = false;
public var mLength:Number;
public var fAr:Array = new Array();
public var startDown:Boolean=false;
public var openSetChange:Boolean=false
public var startPos:startBlock=new startBlock;
public var endPos:endBlock=new endBlock;
public var highlighter:squareSelected=new squareSelected;
public function initPF() {
//defines the map
map = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1],
[1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1],
[1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,0,1],
[1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,1,1,0,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1],
[1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
];
//the length of the map along the x axis
mLength = map[0].length;
addChild(endPos);
addChild(startPos);
addChild(highlighter);
addEventListener(Event.ENTER_FRAME,calcMousePos);
addEventListener(MouseEvent.CLICK,startFinInit);
//creates map
for (var k in map[0]) {
for (var i in map[k]) {
var n:node = new node(i,k,map[k][i]);
addChildAt(n,0);
//pushes nodes into a node array for ease of calling them out
if (nodeAr.length>=1) {
nodeAr.push(n);
}
}
}
// adds a button so i can do the path finding in steps instead of it
// happening all at once
var button:path = new path();
addChild(button);
button.addEventListener(MouseEvent.CLICK,nextStep);
}
public function nextStep(event:MouseEvent) {
contAstar(nextNode,nextNode.x,nextNode.y,endNode.x,endNode.y);
}
// calculates the mouse x,y coordinates relative to the map and
//which node it is on
public function calcMousePos(event:Event) {
xcoord=Math.floor(mouseX/tileWidth);
ycoord=Math.floor(mouseY/tileWidth);
highlighter.x=xcoord*tileWidth;
highlighter.y=ycoord*tileWidth;
}
//placing the start and end indicators at the right place and definfing
//the start and end nodes
public function startFinInit(event:MouseEvent) {
// first click places the start indicator and defines the start node
if (startDown==false) {
if (map[ycoord][xcoord]!=wall) {
startPos.x=highlighter.x;
startPos.y=highlighter.y;
startNode = nodeAr[mLength*ycoord+xcoord];
trace(startNode.x,nodeAr[mLength*ycoord+xcoord])
startDown=true;
}
} else {
// 2nd click places the end indicator and defines the end node
if (map[ycoord][xcoord]!=wall) {
endPos.x=highlighter.x;
endPos.y=highlighter.y;
endNode = nodeAr[mLength*ycoord+xcoord];
//start pathfinding with the first calculation
firstCalc(startNode,startNode.x,startNode.y,endNode.x,endNode.y);
startDown=false;
trace(startNode.x,startNode.y,endNode.x,endNode.y);
}
}
}
public function firstCalc(sNode,cx,cy,ex,ey) {
//get start node values and push it into the closed set
sNode.g = 0;
sNode.h = hueristic(cx,cy,ex,ey);
sNode.f = sNode.g+sNode.h;
closedSet.push(sNode);
// test the surrounding nodes
SurroundCalc(sNode,cx,cy-tileWidth,ex,ey);
SurroundCalc(sNode,cx,cy+tileWidth,ex,ey);
SurroundCalc(sNode,cx-tileWidth,cy,ex,ey);
SurroundCalc(sNode,cx+tileWidth,cy,ex,ey);
getSmallestF();
getNextNode();
}
public function contAstar(sNode,cx,cy,ex,ey) {
if (sNode!= endNode) {//if its not on the end node
if (openSet.length>0) {// the openset still has nodes to test
// test the surrounding nodes
SurroundCalc(sNode,cx,cy-tileWidth,ex,ey);
SurroundCalc(sNode,cx,cy+tileWidth,ex,ey);
SurroundCalc(sNode,cx-tileWidth,cy,ex,ey);
SurroundCalc(sNode,cx+tileWidth,cy,ex,ey);
getSmallestF();
getNextNode();
}else{
trace("no path")
}
} else {
trace("pathFound");
}
}
//calculate the h value for a node
public function hueristic(x1,y1,x2,y2) {
Hx = Math.sqrt(((x2-x1)*(x2-x1))+((y2-y1)*(y2-y1)));
Hx = Math.round(Hx);
return Hx;
}
public function SurroundCalc(pNode,cx,cy,ex,ey) {
dontPush = false;
openSetChange = false
for (var i:Number = 0; i<=nodeAr.length-1; i++) {
//test every node in the node array
if (nodeAr[i].x == cx && nodeAr[i].y == cy) {
//test to see wich node in the node array is the current node
for (var k:Number = 0; k <openSet.length; k++) {
if (openSet[k].iName == nodeAr[i].iName) {
openSetChange = true
//test to see if the current node is in the open set
}
}
for (var j:Number = 0; j <closedSet.length; j++) {
//test to see if the current node is the closed set
if (closedSet[j].iName == nodeAr[i].iName ) {
dontPush = true;
}
}
//if not in closed set
if (dontPush == false) {
//if not in open set
if(!openSetChange){
if (nodeAr[i].notWalkable == false) {
//define its parent
pNode = MovieClip(parent).nodeAr[i];
//get the g,h and f values for the node
var sNode = nodeAr[i];
sNode.g = pNode.g+10;
sNode.h = hueristic(cx,cy,ex,ey);
sNode.f =sNode.g+ sNode.h;
//add it to the open set
openSet.push(sNode);
cleant the f array
for (var l:Number = 0; l < fAr.length; l++) {
fAr.splice(0,1);
}
}
}else{
//if the new g value is lower than the old g value re-calc f
sNode = nodeAr[i];
newGx = pNode.g+10;
if(newGx<sNode.g){
sNode.g = newGx;
sNode.f =sNode.g+ sNode.h;
}
}
}
}
}
}
public function getSmallestF() {
//goes through the open set adds all the f values to an F array: fAr
for (var i:Number = 0; i<=openSet.length-1; i++) {
fAr.push(openSet[i].f);
}
//sorts the f array into smallest to largest
fAr.sort(Array.NUMERIC);
}
public function getNextNode() {
closedSetPush:
for (var i:Number = 0; i<=nodeAr.length; i++) {
//goes through every node in the node array
for (var k:Number = 0; k<=openSet.length-1; k++) {
//goes through every node in the open set array
if (openSet[k].iName == nodeAr[i].iName) {
//if a node in the node array is the same as the node in the open set array
if (nodeAr[i].f == fAr[0]) {
//and if that node has an f value the same as the first value in the f array
closedSet.push(nodeAr[i]);
//add it to closed set
openSet.splice(k,1);
//remove it from the open set
nextNode = nodeAr[i];
make it the next node to start from
break closedSetPush;
}
}
}
}
//traces the closed set
for (var l:Number = 0; l<=closedSet.length-1; l++) {
trace(closedSet[l].iName+" is in closedSet")
}
}
}
}
node:
Code:
package {
import flash.display.*;
import flash.events.*;
import flash.utils.*;
import flash.text.TextField;
public class node extends MovieClip {
public var f:Number = -1;
public var g:Number = -1;
public var h:Number = -1;
public var notWalkable:Boolean = true;
public var costMultiplier:Number=1.0;
public function node(x,y,nw) {
//gets the x,y coords from the A* script when it creats the map and if its //walkable or not
addEventListener(Event.ENTER_FRAME,upDate);
//if not walkable == false (lol double negative)
if (nw == false) {
this.h_TXT.text = "";
this.g_TXT.text = "";
this.f_TXT.text = "";
this.gotoAndPlay(1);//floor tile
} else {
this.gotoAndPlay(2);//wall tile
}
notWalkable = nw
this.x=x*40 // x *tile width;
this.y=y*40;//y* tile height
}
public function upDate(event:Event) {
if (notWalkable == false) {
// if walkable aka not a wall upadate the g,h,f values ( if it has one) and //display them
if (h>=0) {
this.h_TXT.text = h.toString();
}
if (g>=0) {
this.g_TXT.text = g.toString();
}
if (f>=0) {
this.f_TXT.text = f.toString();
}
}
}
}
}
there is that better?? ummm i'm not sure how to attatch .swf files so i cant show you where it goes wrong...
acctually i will add it to deviant art
http://buk09.deviantart.com/art/fail...ding-124534991
cheers
-
Hrmm - it sounds like your nodes are getting added to the closed list without being removed from the open one....If I recall correctly, you should still be examining surrounded nodes but since all their neighbors are already closed they would be considered dead ends and that node should get closed so the search continues elsewhere.
-
cheers man, that was exactly the problem lol! but i figured it out my self which is good! then i came back here to see what ppl had said but cheers for the thought XD
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote