Advertisement Jump to content
Sign in to follow this  
devmane144

Angelscript A* implementation

This topic is 1787 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been hard at work creating a pathfinding script using the A* algorithm. And it seems to work up until I do collisions. I have the simple pathfinding down. But it seems that when I tell it to ignore certain nodes as kind of a test of collisions, the f score of a point created a while back is smaller. So it jumps back. Obviously this isn't really going to look good, if the entity jumps back in time to go past the obstacle, plus it's bound to lead to problems down the line. I ran the function with coords 0,0 to 10,10. It returned this list of points.

(0,0) (0,1) (0,2) (0,3) (1,3-10) (2-4,10) I told it to block 5,10, and here it jumps back to (2,9) which is 3 blocks manhattan distance away. I also told it to block (0,4), but that part worked out. Anybody have any ideas as to why it doesn't work?


class pathNode{
	int x = 0;
	int y = 0;
	float g = 0;
	float h = 0;
	float f = 0;
	bool blocked = false;
	int parent;
	bool onClosedList = false;
}
class followMe{
	vector2 xy;
	int entityID;
}

array<followMe> pathNodesXY;
array<pathNode> pathNodeReturn;

void pathFind(int x1, int y1, int x2, int y2, int speed, array<pathNode> &out pointList, int entIDSize){
	array<pathNode> openList(1);
	array<pathNode> closedList;
	int gCardinal = 10;
	openList[0].x = x1;
	openList[0].y = y1;
	int debug = 0;
	while(openList.length() > 0){
		pathNode currentNode;
		int f = openList[0].f;
		
		uint openLength = openList.length();
		int lowestFIndex;
		for(uint lowestFOpenListCheck = 0; lowestFOpenListCheck < openLength; lowestFOpenListCheck++){
			if(openList[lowestFOpenListCheck].f <= f){
				f = openList[lowestFOpenListCheck].f;
				currentNode = openList[lowestFOpenListCheck];
				lowestFIndex = lowestFOpenListCheck;
			}
			print(openList[lowestFOpenListCheck].f + " " + lowestFOpenListCheck + " " + openList[lowestFOpenListCheck].x + " " + openList[lowestFOpenListCheck].y);
		}
		print("Selected Point: " + openList[lowestFIndex].x + " " + openList[lowestFIndex].y + " " + openList[lowestFIndex].f);
		closedList.insertLast(openList[lowestFIndex]);
		
		if(closedList[closedList.length() - 1].x == x2 and closedList[closedList.length() - 1].y == y2) break;
		print(closedList[closedList.length() - 1].g);
		openList.removeAt(lowestFIndex);
		
		array<pathNode> successors(8);
		
		int i = -1;
		for(int y = -1; y < 2; y++){
			for(int x = -1; x < 2; x++){
				
				i++;
				
				if(i % 2 == 0) continue;
				
				successors[i].x = closedList[closedList.length() - 1].x + x * speed;
				successors[i].y = closedList[closedList.length() - 1].y + y * speed;
				//print("Current Node: " + closedList[closedList.length() - 1].x + " " + closedList[closedList.length() - 1].y + " " + lowestFIndex);
				//print(i + " " + successors[i].x + " " + successors[i].y);
				
				
				bool ignore = false;
				
				
				/*
				ETHEntityArray collisions;
				
				GetContactEntities(vector2(openList[currentNode].x, openList[currentNode].y), vector2(newNode.x,newNode.y), collisions);
				
				for(uint ii = 0; ii < collisions.Size(); ii++){
					
					if(collisions[ii].HasCustomData() and collisions[ii].GetInt("blocker") == 1){
						ignore = true;
					}
					
				}
				
				if(ignore){
					print("ignored because collisions");
					continue;
					
				}
				*/
				if(successors[i].x == 0 and successors[i].y == 4) ignore = true;
				if(successors[i].x == 5 and successors[i].y == 10) ignore = true;
				for(uint closedCheck = 0; closedCheck < closedList.length(); closedCheck++){
					if(closedList[closedCheck].x == successors[i].x and closedList[closedCheck].y == successors[i].y){
						ignore = true;
					}
				}
				if(ignore) continue;
				
				bool inOpenList = false;
				int openIndex;
				for(uint openCheck = 0; openCheck < openList.length(); openCheck++){
					if(openList[openCheck].x == successors[i].x and openList[openCheck].y == successors[i].y){						
						inOpenList = true;
						openIndex = openCheck;
					}
				}
				
				
				if(inOpenList){
					int g = closedList[closedList.length() - 1].g + gCardinal;
					if(g < openList[openIndex].g){
						openList[openIndex].parent = closedList.length() - 1;
						openList[openIndex].g = g;
						openList[openIndex].f = openList[openIndex].g + openList[openIndex].h;
					}
				}
				
				if(!inOpenList){
					
					successors[i].g = closedList[closedList.length() - 1].g + gCardinal;
					successors[i].h = 12 * (abs(successors[i].x - x2) + abs(successors[i].y - y2));
					successors[i].f = successors[i].g + successors[i].h;
					successors[i].parent = closedList.length() - 1;
					print(successors[i].x + " " + successors[i].y + " " + successors[i].f);
					openList.insertLast(successors[i]);
					
				}
				//print(successors[i].g + " " + successors[i].h + " " + successors[i].f);
				
			}
		}
		debug++;
		//if(debug == 15) break;
		
	}
}

/*

*/

Share this post


Link to post
Share on other sites
Advertisement

Your code could use some cleaning =)  Why post it with commented out code?

 

 

Anyway, from what I can deduce, you're only looking at the F score to find the next open node to check.  You should be looking at the node with the lowest combined H+F score.

Share this post


Link to post
Share on other sites

I thought that if you were doing A* you just wanted to use the F values to find the lowest node point. Where would I put in the H+F score? At the beginning?

Edited by devmane144

Share this post


Link to post
Share on other sites

Okay, so I discovered my problem. I wasn't even bothering to trace the function using parents, I was just hoping it'd find a path through the mess. I finally realized this when I looked at a youtube video. Thank you anyways!

Share this post


Link to post
Share on other sites

I thought that if you were doing A* you just wanted to use the F values to find the lowest node point. Where would I put in the H+F score? At the beginning?

 

If you only use the F score, you just take the node that is the cheapest to get to.  If you just take the H score, you just take the node that is the closest to the goal.  By looking at both, you take the node that is the cheapest to get to and takes you the closest to the goal.

 

Visualize a turn based game with a grid or hexes and various squares that cost different amounts, like a swamp that costs 5 movement.  If you just take F, your AI will never attempt to go into the swamp, even if it's actually the best way to go (like perhaps the goal is surrounded by swamp, the AI would never go in there until ALL other nodes were exhausted)   Also, if all the squares around it just cost the same, it will naively just check the first square that it iterated over.  If all you did was take H, your path will take you through a swamp, even if it would've been faster to go around it.

Edited by ferrous

Share this post


Link to post
Share on other sites

Just a side issue, but if Angelcode supports 'goto' this is a good case (see perennial threads on 'iuse of goto') where a goto statement simplifies the code AND optimizes it.

 

The various places where you set 'ignore = True' if changed to a goto 'label' (point at botton of the candidate checking loop) your code will run alot faster and you can remove a number of statements (ones that test value of 'ignore' to continue)

 

Possibly if Angelcode supports  a continue with variable name designating which loop then you might avoid using the use of goto and use 'continue ii;'

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!