I've been trying to implement this for ages now (2 years I reckon?) on and off, and I'm having a hell of a time getting it to work. In case you don't know, A* is a pathfinding algorithm. As far as I can tell, it's one of the best, which is why I want to implement it as opposed to others. I based my script on the "Pseudocode" section of this. I hardcoded the start and end goal nodes, and some combos to use for visualizing what's going on (combos 14, 40, and 41, for various things but it basically has to do with drawing the path). I'm hoping I can get some help actually getting this to work. I could provide the quest I'm using, but that might not be necessary considering how little setup the script requires. It seems to work just fine if the path to the end node is completely unobstructed, but if there's anything in the way it starts veering off, and then just gives up instead of going back and finding a new path. You start the pathfinding by pressing Ex1. The script is meant to be generalized, so it could pathfind in any sort of array depending on the array sizes and ARR_W/ARR_H values. Only requires std.zh.
Here's the code itself:
const int ARR_EMPTY = -1; const int ARR_INFINITY = -2; // used in the algorithm. const int ARR_W = 16; const int ARR_H = 11; ffc script Astar { void run() { ClearTrace(); while(true) { // catalyzing the script to run if(Link->InputEx1) { break; } Waitframe(); } int START = 72; int GOAL = 148; int CURRENT = START; int ClosedSet[176]; // Unsorted array ClearArrToVal(ClosedSet, ARR_EMPTY); for(int i = 0; i < SizeOfArray(ClosedSet); i += 1) { if(Screen->ComboS[i] != 0 && i != GOAL) { Put(ClosedSet, i); } } int OpenSet[176]; // Unsorted array ClearArrToVal(OpenSet, ARR_EMPTY); Put(OpenSet, START); int CameFrom[176]; // Sorted array ClearArrToVal(CameFrom, ARR_EMPTY); int GScore[176]; // Sorted array ClearArrToVal(GScore, ARR_INFINITY); GScore[START] = 0; int FScore[176]; // Sorted array ClearArrToVal(FScore, 9999); FScore[START] = heuristic(START, GOAL); int NEIGHBOR = 0; bool VALID_NEIGHBOR = false; int Tentative_GScore = 0; int Iterations = 0; // Custom stuff int Space[] = " "; // Debug stuff int smallest = 0; while(ArrEmpty(OpenSet, ARR_EMPTY) == false) { Iterations += 1; for(int i = 0; i < SizeOfArray(OpenSet); i += 1) { if(OpenSet[i] > 0) { if(FScore[OpenSet[i]] < smallest && FScore[OpenSet[i]] >= 0) { smallest = i; } } } if(smallest < 0) { continue; } CURRENT = OpenSet[smallest]; int currentval[] = "Current node: "; TraceS(currentval); Trace(CURRENT); TraceNL(); if(CURRENT == GOAL) { int SUCCESS[] = "SUCCESS! The script works!"; TraceS(SUCCESS); TraceNL(); int cur = GOAL; Trace(CameFrom[GOAL]); Trace(GOAL); while(cur != START) { cur = CameFrom[cur]; Screen->ComboD[cur] = 14; Trace(cur); Waitframe(); } TraceNL(); Trace(Iterations); break; } if(CURRENT < 0) { Waitframe(); continue; } int msg4[] = "IndiceOfVal(OpenSet, Current) = "; TraceS(msg4); Trace(IndiceOfVal(OpenSet, CURRENT)); TraceNL(); int msg5[] = "OpenSet(IndiceOfVal...) = "; TraceS(msg5); Trace(OpenSet[IndiceOfVal(OpenSet, CURRENT)]); TraceNL(); OpenSet[IndiceOfVal(OpenSet, CURRENT)] = ARR_EMPTY; // ShiftArr(OpenSet, ARR_EMPTY, ARR_EMPTY); // Trace(8888); Put(ClosedSet, CURRENT); for(int i = 0; i < 4; i += 1) // Going through each neighbor of current { VALID_NEIGHBOR = false; if(i == 0) // Up { NEIGHBOR = (CURRENT - ARR_W); if(NEIGHBOR >= 0 && ArrContainsVal(ClosedSet, NEIGHBOR) == false) { VALID_NEIGHBOR = true; } } if(i == 1) // Down { NEIGHBOR = (CURRENT + ARR_W); if(NEIGHBOR < SizeOfArray(OpenSet) && ArrContainsVal(ClosedSet, NEIGHBOR) == false) { VALID_NEIGHBOR = true; } } // // NOTE: LOOK INTO LEFT DIRECTION NODE // It seems like there's an error with FloorToMultiple, which allows it to return a combo on the far right of the screen as being // On the same row as one combo down and on the far left. if(i == 2) // Left { NEIGHBOR = (CURRENT - 1); if(NEIGHBOR >= FloorToMultiple(CURRENT, ARR_W) && ArrContainsVal(ClosedSet, NEIGHBOR) == false) { VALID_NEIGHBOR = true; } } if(i == 3) // Right { NEIGHBOR = (CURRENT + 1); if(NEIGHBOR < FloorToMultiple(CURRENT + ARR_W, ARR_W) && ArrContainsVal(ClosedSet, NEIGHBOR) == false) { VALID_NEIGHBOR = true; } } if(VALID_NEIGHBOR == true) { Tentative_GScore = GScore[CURRENT] + heuristic(CURRENT, NEIGHBOR); int msg2[] = "Tentative GScore: "; TraceS(msg2); Trace(Tentative_GScore); TraceNL(); int msg6[] = "Neighbor node: "; TraceS(msg6); Trace(NEIGHBOR); TraceNL(); Screen->ComboD[NEIGHBOR] = 40; if(ArrContainsVal(OpenSet, NEIGHBOR) == false) { Put(OpenSet, NEIGHBOR); } else if(Tentative_GScore >= GScore[NEIGHBOR]) { continue; // Worse path } CameFrom[NEIGHBOR] = CURRENT; Screen->ComboD[NEIGHBOR] = 41; // Debug GScore[NEIGHBOR] = Tentative_GScore; FScore[NEIGHBOR] = GScore[NEIGHBOR] + heuristic(NEIGHBOR, GOAL); int msg3[] = "End of subloop #"; TraceS(msg3); Trace(i); TraceNL(); } } int msg[] = "End of algorithm loop ~~~~~~~~~~~~~~~~~~~~ Iteration #"; TraceS(msg); Trace(Iterations); TraceNL(); Waitframe(); } while(true) { Waitframe(); } } } void ClearArrToVal(int arr, int val) { for(int i = 0; i < SizeOfArray(arr); i += 1) { arr[i] = val; } } void Put(int arr, int val, int pos) { arr[pos] = val; } void Put(int arr, int val) { for(int i = 0; i < SizeOfArray(arr); i += 1) { if(arr[i] == ARR_EMPTY) { arr[i] = val; break; } } } bool ArrEmpty(int arr, int exception) { bool empty = true; for(int i = 0; i < SizeOfArray(arr); i += 1) { if(arr[i] != exception) { empty = false; break; } } return empty; } int Get(int arr, int arrP, bool remove) { int smallest = arrP[0]; int node = 0; int indice = 0; for(int i = 1; i < SizeOfArray(arrP); i += 1) { if(smallest < arrP[i] && smallest > ARR_EMPTY) { smallest = arrP[i]; node = arr[i]; indice = i; } } if(remove == true) { arr[indice] = ARR_EMPTY; arrP[indice] = ARR_EMPTY; //ShiftArr(arr, ARR_EMPTY, indice); //ShiftArr(arrP, ARR_EMPTY, indice); } //Trace(indice); return node; } // startPos is the indice to shift into/away from void ShiftArr(int arr, int emptyVal, int startPos) { for(int i = startPos; i < SizeOfArray(arr); i += 1) { if(i + 1 >= SizeOfArray(arr)) { // arr[i] = emptyVal; break; } else { arr[i] = arr[i + 1]; } } } // Floors a value to a multiple. int FloorToMultiple(int input, int multiple) { if(multiple == 0) {return 0;} int mul = Abs(multiple); return Floor(input/mul)*mul; } bool ArrContainsVal(int arr, int val) { bool contains = false; for(int i = 0; i < SizeOfArray(arr); i += 1) { if(arr[i] == val) { contains = true; break; } } return contains; } int heuristic(int nodeA, int nodeB) { int a_x = nodeA % ARR_W; int a_y = FloorToMultiple(nodeA, ARR_W) / ARR_W; int b_x = nodeB % ARR_W; int b_y = FloorToMultiple(nodeB, ARR_W) / ARR_W; return Abs(a_x - b_x) + Abs(a_y - b_y); } int IndiceOfLowestVal(int arr) { int smallest = arr[0]; int indice = 0; for(int i = 0; i < SizeOfArray(arr); i += 1) { if(smallest < arr[i] && smallest != ARR_EMPTY && smallest != ARR_INFINITY && smallest >= 0) { smallest = arr[i]; indice = i; } } return indice; } int IndiceOfVal(int arr, int val) { int indice = -1; for(int i = 0; i < SizeOfArray(arr); i += 1) { if(arr[i] == val) { indice = i; break; } } return indice; }
I figured I should post it here, so further developments can easily be published. I'm mainly concerned about just getting the script running properly, so debug stuff or extra stuff in the script that's not detrimental isn't something I want to worry about (yet!).