source updated, FindNext() will have the same content as the first half of FindPath();
🎉 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!
Pathfinding, need feedback
It's usually better to post new versions in a new post rather than modifying existing posts.
That simplifies reading the discussion afterwards by others much much simpler.
Author
I`m designing the while loop. I have a question after I decide which node has the best weight (the smallest weight) do I add all it`s valid neighbours into the trunk?
void FindPath(int Startx, int Startz, int Endx, int Endz)
{
Surrounding Sectors[8];
for(int i = 0; i < 8; i++)
{
Sectors[i].distance = -1;
}
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;
}
}
TrunkListCount++;
TrunkList[TrunkListCount].x = Sectors[j].x;
TrunkList[TrunkListCount].z = Sectors[j].z;
Surrounding BestNode;
BestNode.distance = 1000;
for(int i =0; i < TrunkListCount; i ++)
{
if(TrunkList[i].weight < BestNode.distance)
{
BestNode.distance = TrunkList[i].weight;
BestNode.x = TrunkList[i].x;
BestNode.z = TrunkList[i].z;
}
}
bool exit = false;
while(!exit)
{
if((BestNode.x != Endx)||(BestNode.z != Endz))
{
FindNext(BestNode.x, BestNode.z, Endx,Endz);
}
else
{
exit = true;
}
}
StringCchPrintfA(IGmessage,1024,"Closest %d",Closest);
MessageBox(NULL, IGmessage, "Textures.exe", MB_OK);
}Calin said:
I`m designing the while loop. I have a question after I decide which node has the best weight (the smallest weight) do I add all it`s valid neighbours into the trunk?
That depends on the algorithm you are implementing, what does it mean if an entry is “in trunk”?
You should protect the loop against overflowing, there may not exist a path at all or your algorithm may start hopping back and forth between a few positions, and you don't want a crash due to such things.
// N NE E SE S SW W NW
static const int dx = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dz = {1, 1, 0, -1, -1, -1, 0, 1};
void FindPath(int Startx, int Startz, int Endx, int Endz)
{
Surrounding Sectors[8];
for(int i = 0; i < 8; i++)
{
Sectors[i].distance = -1;
}
// Compute distance of all neighbours.
for(int i = 0; i < 8; i++)
{
Distancex = NodeCoord(Startx + dx[i], Startz + dz[i]).x - Endx;
Distancez = NodeCoord(Startx + dx[i], Startz + dz[i]).z - Endz;
Sectors[i].distance = sqrtf(Distancex * Distancex + Distancez * Distancez);
}
// Compute closest.
int Closest = 1000;
int j = -1;
for(int i =0; i< 8; i ++)
{
if(Sectors[i].distance < Closest)
{
Closest = Sectors[i].distance;
j = i;
}
}
assert(j >= 0); // Check that a valid index was found.
// Add best to trunk.
TrunkListCount++;
TrunkList[TrunkListCount].x = Sectors[j].x;
TrunkList[TrunkListCount].z = Sectors[j].z;
// ??
Surrounding BestNode;
BestNode.distance = 1000;
for(int i =0; i < TrunkListCount; i ++)
{
if(TrunkList[i].weight < BestNode.distance)
{
BestNode.distance = TrunkList[i].weight;
BestNode.x = TrunkList[i].x;
BestNode.z = TrunkList[i].z;
}
}
// Compute path.
bool exit = false;
while(!exit)
{
if((BestNode.x != Endx)||(BestNode.z != Endz))
{
FindNext(BestNode.x, BestNode.z, Endx,Endz);
}
else
{
exit = true;
}
}
StringCchPrintfA(IGmessage,1024,"Closest %d",Closest);
MessageBox(NULL, IGmessage, "Textures.exe", MB_OK);
}I folded a loop around the first part of your code and reformatted it a bit.
As you can see, I use empty lines to separate different steps in the computation, and keep lines together that implement one step. In that way you get blocks of code that represent steps in the computation. I also added a line of comment above it, so when looking for some specific code, you can just read the comment line, and skip the entire block if it's not the step you are looking for.
Author
I will need to go through all vertices in the trunk and see which has the best weight. once I found the tile with the best weight, I need to check its neighbours, and add them to the trunk again?
You seem to be doing two things at the same time, first thing is figuring out how to actually organize the algorithm to get a sequence of tiles that form a shortest path, second thing is programming that. Problem is, the latter fully depends on the former, as long as you don't quite know how to do the former, doing the latter is mostly a waste of time. Any change in the algorithm makes some upto all of your code obsolete.
Perhaps you should do some reading how others have solved this problem? That should give a more solid foundation of how to do the computation. For example:
https://theory.stanford.edu/~amitp/GameProgramming/
Author
while loop updated
while(!exit)
{
bool exists = false;
bool exit = false;
Surrounding BestNode;
BestNode.weight = 1000;
for(int i =0; i < TrunkListCount; i ++)
{
if(TrunkList[i].weight < BestNode.weight)
{
BestNode.weight = TrunkList[i].weight;
BestNode.x = TrunkList[i].x;
BestNode.z = TrunkList[i].z;
}
}
if((BestNode.x != Endx)||(BestNode.z != Endz))
{
int x = BestNode.x;
int z = BestNode.z;
if(NodeCoord(x,z+1).access)//n
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x,z+1).x)&&(TrunkList[i].z == NodeCoord(x,z+1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x,z+1).x;
TrunkList[TrunkListCount].z = NodeCoord(x,z+1).z;
}
}
if(NodeCoord(x+1,z+1).access)//ne
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x+1,z+1).x)&&(TrunkList[i].z == NodeCoord(x+1,z+1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x+1,z+1).x;
TrunkList[TrunkListCount].z = NodeCoord(x+1,z+1).z;
}
}
if(NodeCoord(x+1,z).access)//e
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x+1,z).x)&&(TrunkList[i].z == NodeCoord(x+1,z).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x+1,z).x;
TrunkList[TrunkListCount].z = NodeCoord(x+1,z).z;
}
}
if(NodeCoord(x+1,z-1).access)//se
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x+1,z-1).x)&&(TrunkList[i].z == NodeCoord(x+1,z-1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x+1,z-1).x;
TrunkList[TrunkListCount].z = NodeCoord(x+1,z-1).z;
} }
if(NodeCoord(x,z-1).access)//s
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x,z-1).x)&&(TrunkList[i].z == NodeCoord(x,z-1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x,z-1).x;
TrunkList[TrunkListCount].z = NodeCoord(x,z-1).z;
}
}
if(NodeCoord(x-1,z-1).access)//sw
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x-1,z-1).x)&&(TrunkList[i].z == NodeCoord(x-1,z-1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x-1,z-1).x;
TrunkList[TrunkListCount].z = NodeCoord(x-1,z-1).z;
} }
if(NodeCoord(x-1,z).access)//w
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x+1,z-1).x)&&(TrunkList[i].z == NodeCoord(x+1,z-1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x+1,z-1).x;
TrunkList[TrunkListCount].z = NodeCoord(x+1,z-1).z;
}}
if(NodeCoord(x-1,z+1).access)//nw
{
exists = false;
for(int i =0; i < TrunkListCount; i++)
{
if((TrunkList[i].x == NodeCoord(x+1,z-1).x)&&(TrunkList[i].z == NodeCoord(x+1,z-1).z))
{
exists = true;
}
}
if(!exists)
{
TrunkListCount++;
TrunkList[TrunkListCount].x = NodeCoord(x+1,z-1).x;
TrunkList[TrunkListCount].z = NodeCoord(x+1,z-1).z;
} }
}
else
{
exit = true;
}
}
A comment about @nikito and code quality:
It is is very important that you do refactor this code. Not just to make it easy for @nikito to read it. But also for you to fix it.
If I find a bug in your code, and you like my fix, and you want to fix it: You will need to fix it in 8 repeating places. The changes of making a typo are multiplied ( by 800% !).
The 2 things you absolutley need to refactor before writing another line of code:
1. Make a distance() function (One that includes x and z inside of it).
2. Put all of these “if” an “else” in a "for loop.
Even if you end up keeping this code, it would make it easier for you to maintain it.
Author
It is is very important that you do refactor this code
I know, being brief is important, but let me finish the algorithm first, then I`ll see how I can reduce the amount the code. I know it can be refractored
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
