🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Artificial Intelligence

Pathfinding, need feedback

Artificial Intelligence Programming

Started by Calin April 30, 2020 05:52 PM

109 comments, last by Calin 4 years, 1 month ago

Calin

456

Author

April 30, 2020 05:52 PM

I started work on the pathfinding algorithm. I know the stages of the algorithm (how it should look like in the end), bellow is almost pseudocode (it`s real code but I haven`t started building/debugging)

void FindPath(int Startx, int Startz, int Endx, int Endz)
{
	
	
	Surrounding Sectors[8];
	


	for(int i  = 0; i < 8; i++)
	{
		Sectors[i].distance = -1;
		Sectors[i].excluded = false;
	}
	if(NodeCoord(Startx, Startz +1).access)//N
	{
		
		Distancex = NodeCoord(Startx, Startz +1).x - Endx;
		Distancez =  NodeCoord(Startx, Startz +1).z - Endz;
		Sectors[0].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[0].excluded = true;

	}
	if(NodeCoord(Startx+1,Startz+1).access)//NE
	{
		
		Distancex = NodeCoord(Startx+1,Startz+1).x - Endx;
		Distancez =  NodeCoord(Startx+1,Startz+1).z - Endz;
		Sectors[1].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[1].excluded = true;
	}
	if(NodeCoord(Startx+1,Startz).access)//NE
	{
		
		Distancex = NodeCoord(Startx+1,Startz).x - Endx;
		Distancez =  NodeCoord(Startx+1,Startz).z - Endz;
		Sectors[2].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[2].excluded = true;
	}
	if(NodeCoord(Startx+1,Startz-1).access)//SE
	{
		
		Distancex = NodeCoord(Startx+1,Startz-1).x - Endx;
		Distancez =  NodeCoord(Startx+1,Startz-1).z - Endz;
		Sectors[3].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[3].excluded = true;
	}
	if(NodeCoord(Startx,Startz-1).access)//S
	{
		
		Distancex = NodeCoord(Startx,Startz-1).x - Endx;
		Distancez =  NodeCoord(Startx,Startz-1).z - Endz;
		Sectors[4].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[4].excluded = true;
	}
	if(NodeCoord(Startx-1,Startz-1).access)//SW
	{
		
		Distancex = NodeCoord(Startx-1,Startz-1).x - Endx;
		Distancez =  NodeCoord(Startx-1,Startz-1).z - Endz;
		Sectors[5].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[5].excluded = true;
	}
	if(NodeCoord(Startx-1,Startz).access)//W
	{
		
		Distancex = NodeCoord(Startx-1,Startz).x - Endx;
		Distancez =  NodeCoord(Startx-1,Startz).z - Endz;
		Sectors[6].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[6].excluded = true;
	}
	if(NodeCoord(Startx-1,Startz+1).access)//NW
	{
		
		Distancex = NodeCoord(Startx-1,Startz+1).x - Endx;
		Distancez =  NodeCoord(Startx-1,Startz+1).z - Endz;
		Sectors[7].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
		
	}
	else
	{
		Sectors[7].excluded = true;
	}
	

	for (int i =0; i < 8; i++)
	{
		if(!Sectors[i].excluded)
		{
			TrunkListCount++;
			TrunkList[TrunkListCount].x =  Sectors[i].x;
			TrunkList[TrunkListCount].z =  Sectors[i].z;
		}
	}

	int Closest = 1000;
	int j = -1;
	for(int i =0; i< 8; i ++)
	{
		
		if(Sectors[i].distance < Closest)
		{
		   Closest = Sectors[i].distance;
		   j = i;
		}
	}
	

	ChartNode Candidate;
	Candidate.x = TrunkList[TrunkListCount].x;
	Candidate.z = TrunkList[TrunkListCount].z;


	FindNext( Sectors[j].x,  Sectors[j].z, Endx,Endz);

		StringCchPrintfA(IGmessage,1024,"Closest %d",Closest);
		MessageBox(NULL, IGmessage, "Textures.exe", MB_OK);

}

Surrounding FindNext(int Startx, int Startz, int Endx, int Endz)
{
Surrounding Sectors[8];
if(NodeCoord(Startx, Startz +1).access)//N
{
 
 Distancex = NodeCoord(Startx, Startz +1).x - Endx;
 Distancez =  NodeCoord(Startx, Startz +1).z - Endz;
 Sectors[0].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx+1,Startz+1).access)//NE
{
 
 Distancex = NodeCoord(Startx+1,Startz+1).x - Endx;
 Distancez =  NodeCoord(Startx+1,Startz+1).z - Endz;
 Sectors[1].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx+1,Startz).access)//NE
{
 Distancex = NodeCoord(Startx+1,Startz).x - Endx;
 Distancez =  NodeCoord(Startx+1,Startz).z - Endz;
 Sectors[2].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx+1,Startz-1).access)//SE
{
 Distancex = NodeCoord(Startx+1,Startz-1).x - Endx;
 Distancez =  NodeCoord(Startx+1,Startz-1).z - Endz;
 Sectors[3].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx,Startz-1).access)//S
{
 
 Distancex = NodeCoord(Startx,Startz-1).x - Endx;
 Distancez =  NodeCoord(Startx,Startz-1).z - Endz;
 Sectors[4].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx-1,Startz-1).access)//SW
{
 
 Distancex = NodeCoord(Startx-1,Startz-1).x - Endx;
 Distancez =  NodeCoord(Startx-1,Startz-1).z - Endz;
 Sectors[5].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx-1,Startz).access)//W
{
 
 Distancex = NodeCoord(Startx-1,Startz).x - Endx;
 Distancez =  NodeCoord(Startx-1,Startz).z - Endz;
 Sectors[6].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}
if(NodeCoord(Startx-1,Startz+1).access)//NW
{
 
 Distancex = NodeCoord(Startx-1,Startz+1).x - Endx;
 Distancez =  NodeCoord(Startx-1,Startz+1).z - Endz;
 Sectors[7].distance = sqrtf(Distancex * Distancex + Distancez*Distancez);
 
}

int Closest = 1000;
int j = -1;
for(int i =0; i< 8; i ++)
{
 
 if(Sectors[i].distance < Closest)
 {
    Closest = Sectors[i].distance;
    j = i;
 }
}

Surrounding Result;
Result.x = Sectors[j].x;
Result.z = Sectors[j].z;
return Result;
}

My project`s facebook page is “DreamLand Page”

JoeJ

4,260

April 30, 2020 06:55 PM

Feedback requested? Well… what should i say?

It does not really look like you are familiar with graph algorithms, so i propose you look up how A-Star and Dijkstra shortest path algorithms work. You'll learn from others much faster than by reinventing rectangular wheels from scratch.

Or, if your obstacles are small and sparse and you do not really need complex path finding but just a straight line, look up DDA or Bresenham line drawing. Testing the entire neighborhood on each step is not necessary.

NikiTo

245

April 30, 2020 06:58 PM

Put the repeated code inside methods/functions.
When you call the functions/methods give it that “NodeCoord(Startx+-1,Startz+-1.z” as argument. Write the calls right one after the other on one new line each in order for that “+-1+-1” to be exactly one below the other and to not hurt your eyes.

Why is "distance", negative? Try to find better names for your variables.

I did not read it entirely, because it hurts the eyes to read this. Make it more “visually friendly to a stranger”.

Some examples of logic here:
https://qiao.github.io/PathFinding.js/visual/

Calin

456

Author

April 30, 2020 07:04 PM

JoeJ said:
Feedback requested? Well… what should i say?

If at least a forum member gets to see what I`m doing its a win.

Put the repeated code inside methods/functions.

I haven`t started refractoring yet. I`ll do it when I`ll finish the algorithm

My project`s facebook page is “DreamLand Page”

Alberth

10,216

April 30, 2020 08:11 PM

Making distance positive is a waste of time, when you take the square the value becomes non-negative anyway. Taking the square-root of the distances is not needed either, it's perfectly fine to find the smallest squared distance, since square-root is a strictly monotonic increasing function. (Smallest output of square-root comes from the smallest input, thus you can compare inputs and completely omit computing any outputs.)

As for path-finding, this code finds the distance of a neighbouring cell to the end-point. Likely you want to keep the direction as well. For path-finding this is only sufficient if you have only obstacles of size 2 or less I think, or sufficiently convex shaped obstacles.

With other obstacles, your routine may get stuck and jump back and forth between two adjacent tiles.

Calin

456

Author

April 30, 2020 08:22 PM

Alberth said:
when you take the square the value becomes non-negative anyway

awesome, I learn things that aren`t pathfinding related too.

Taking the square-root of the distances is not needed either

I do need to determine the closest square/tile of the surroundings when I`m building the main trunk

My project`s facebook page is “DreamLand Page”

Calin

456

Author

April 30, 2020 09:13 PM

sorry, segmentation of messages is a problem I have, previous message edited.

My project`s facebook page is “DreamLand Page”

NikiTo

245

May 01, 2020 02:23 AM

@alberth I commented about the naming of variables, Maybe he could name it “step" or something else. It is hard to explain to somebody negative distance because such thing does not exist.

Such logical mistakes lead to wrong code. If a class “Bread” has a method “cutASlice()” it reveals bad logic since the very beginning. Breads can not cut themselves in slices.

That was my commenting about. Unrelated to the algorithm at all.

Alberth

10,216

May 01, 2020 05:21 AM

Calin said:
I do need to determine the closest square/tile of the surroundings when I`m building the main trunk

I understand that, but the smallest distance is also the smallest squared distance. So you can compute the squared distance everywhere (by not doing sqrt), and find the tile with the minimum squared distance. That tile is the closest neighbour.

NikiTo said:
It is hard to explain to somebody negative distance because such thing does not exist.

I can quite live with a variable that needs a second statement to fix itself to its true meaning, as it avoids introducing a second intermediate variable. I would have written “distance = abs(…)” and be done with it in one line, but ah well.

At some point it does move into the semantically nonsense category indeed, but that is also something you learn as you go.

I am much more bothered why people use a code style that is so hard to read and wastes so much vertical space, the most precious space you have to read code. I will probably never understand it.

NikiTo said:
That was my commenting about. Unrelated to the algorithm at all.

I read your post, and understood that. I agreed with what you said, and had nothing else useful to say about it (ie you said it all imho), which is why I neither commented on your post, nor said anything else on that matter.

NikiTo

245

May 01, 2020 06:21 AM

@Alberth I agree. Sometimes it is semantics only.

Sometimes is like reading a program written by Yoda. And our brains are soft. If you share a room with Yoda for 6 months, you will start talking like him. Reading bad code or staring to a photo of human feces is like a virus for our minds. It affects us badly. How can we protect our minds from “can't unsee” attacks?… By stopping looking at the bad information as soon as possible.

In my own opinion and practice, if i start to read a chess program and see somewhere a variable or method named “distance”, i will stop reading further that program. Functionally, chess game lacs the concept of distance.

Reading bad code is a torture. Reading good code is easy.

I don't try to reduce the numbers of line of code. But i try hard to minimize the repeats in the code. I try hard to shape the functionality of the code.

pseudocode:

Pos2D[] scanRangeOfNeighbors(int startOffset, int maxReach, TypeOfBreed breedType) {
Pos2D[] obstaclesSquaresPositions;
for (int offset = startOffset; offset ≤ maxReach; offset++) {
obstaclesSquaresPositions.append(scanNeighborsAtOffset(offset, breedType));
}
return obstaclesSquaresPositions;
}

Now it is easy to get the result of that method and feed more methods with it. This is what i define as less lines of code written. Omitting the “{}”s to make the code shorter is a personal taste thing. There are extensions for C# that will fire an alarm if you forget the space in "for(int". This is not indispensable in my own opinion.

🎉 Celebrating 25 Years of GameDev.net! 🎉

Pathfinding, need feedback

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

🎉 Celebrating 25 Years of GameDev.net! 🎉

Pathfinding, need feedback

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines