Jump to content

Photo

Escapades with implementing A* into ZScript


  • Please log in to reply
7 replies to this topic

#1 coolgamer012345

coolgamer012345

    🔸

  • Members
  • Location:Indiana, USA

Posted 02 August 2018 - 12:10 AM

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!).


  • Matthew likes this

#2 Timelord

Timelord

    The Timelord

  • Banned
  • Location:Prydon Academy

Posted 02 August 2018 - 03:52 PM

Grayswandir managed to do it, so you might want to ask him.

The critical failing point is how slow the routine runs, when called constantly.

#3 Gleeok

Gleeok

    It's dangerous to dough alone, bake this.

  • Members
  • Real Name:Pillsbury
  • Location:Magical Land of Dough

Posted 02 August 2018 - 06:12 PM

This is something that probably should be part of the ZC engine and exposed via scripts. Pathfinding is something that's on my agenda but there's no telling when I'll get around to it.

#4 Deedee

Deedee

    Bug Frog Dragon Girl

  • Moderators
  • Real Name:Deedee
  • Pronouns:She / Her, They / Them
  • Location:Canada

Posted 02 August 2018 - 06:41 PM

I'd suggest not going this route. My attempts to implement this have resulted in lag-filled messes, and ultimately I just went with my own homebrewed pathfinding solution.



#5 coolgamer012345

coolgamer012345

    🔸

  • Members
  • Location:Indiana, USA

Posted 02 August 2018 - 10:20 PM

Grayswandir managed to do it, so you might want to ask him.

The critical failing point is how slow the routine runs, when called constantly.

This could certainly be an issue, however I don't think this will be too big of an issue when you have very few enemies and/or only run the algorithm every nth steps rather than every single frame.

 

This is something that probably should be part of the ZC engine and exposed via scripts. Pathfinding is something that's on my agenda but there's no telling when I'll get around to it.

That would be pretty nice. I would prefer if the algorithm was implemented in a way that it can be used for things other than the screen directly. For the mean time, we got this.
 

I'd suggest not going this route. My attempts to implement this have resulted in lag-filled messes, and ultimately I just went with my own homebrewed pathfinding solution.

That's why I'm making this thread Xd



#6 grayswandir

grayswandir

    semi-genius

  • ZC Developers

Posted 02 August 2018 - 10:45 PM

I think the problem is here:
if(FScore[OpenSet[i]] < smallest && FScore[OpenSet[i]] >= 0)
{
	smallest = i;
}
I believe you want this instead:
if(FScore[OpenSet[i]] < FScore[smallest] && FScore[OpenSet[i]] >= 0)
{
	smallest = i;
}
Since smallest starts out at 0, the condition there never evaluates to true, since it'd need to be < 0 and >= 0 at the same time. So instead of taking the node with the smallest fscore, you're just taking the first one each time. Then, if you reach a node without any new neighbors, the first slot in OpenSet never gets filled, so it gets stuck.
 
 
 
As for speed, the biggest issue I see is the constant checking if arrays are empty. What I like to do is code up my own arrays where index 0 is the count of elements in the actual array that starts from 1 onwards.
void Put(int arr, int val)
{
	// Increase array size by 1.
	arr[0] += 1;
	// Save val in newly created slot.
	arr[arr[0]] = val;
}

void Remove(int arr, int index)
{
	// Take the last value in the array and put it in the deleted slot.
	arr[index + 1] = arr[arr[0]];
	// Decrease the array size by 1.
	arr[0] -= 1;
}

bool ArrEmpty(int arr)
{
	return arr[0] == 0;
}

bool ArrContainsVal(int arr, int val)
{
	// Start at the end of the array, and move left.
	for (int i = arr[0]; i > 0; i -= 1)
	{
		if (arr[i] == val) return true;
	}

	return false;
}

Also, instead of having ClosedSet be a list of all the closed nodes, I find it easier to just have a bool IsClosed[176] array that you set to true as you close off nodes, since you never actually need to count how many you've closed so far.
  • coolgamer012345 likes this

#7 coolgamer012345

coolgamer012345

    🔸

  • Members
  • Location:Indiana, USA

Posted 03 August 2018 - 03:04 AM

I tried your fix, Grayswandir, and it helps somewhat. I am finding that the algorithm is finding very inefficient paths, though. Here's one example:
unknown.png
(I apologize for the funky resolution, I tried resizing a screenshot in paint and it didn't want to)

Different patterns of obstructions make different paths, all of which are inefficient. Also, really complex paths deadend for no apparent reason, and the algorithm just gives up.



#8 grayswandir

grayswandir

    semi-genius

  • ZC Developers

Posted 21 August 2018 - 12:07 AM

Alright, I got it working.
			smallest = 0;
			for(int i = 0; i < SizeOfArray(OpenSet); i += 1)
			{
				if(OpenSet[i] > 0)
				{
					if(FScore[OpenSet[i]] < FScore[OpenSet[smallest]] && FScore[OpenSet[i]] >= 0)
					{
						smallest = i;
					}
				}
			}
You wanted FScore[OpenSet[smallest]] there instead of just OpenSet[smallest]. I also added in a smallest = 0; before the loop starts since I wasn't sure if it was getting reset or not.

Here's the full script I ended up using for reference, in case I made any other changes I forgot about: https://pastebin.com/cceuRCPH
I made it so pressing Ex1 advanced step-by-step, and holding Ex2 advanced quickly. I also had it change the debug combos to keep track of the comes from direction, and whether it was open/closed/etc.
 
Screenshots:
Spoiler

  • coolgamer012345 likes this


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users