• Advertisement
Sign in to follow this  

Smoothing out turns in pathfinding

This topic is 2686 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

Hello,
You can assume the path is based on points/pixels where it was generated by AStar at the last stage. I used the following code snippet to smooth out the path, but I found some resulting points repeated. Does anyone have a generic algorithm for smoothing out a pixel-based path? Or fixes for my coding?


void CAStar::SmoothPath()
{
std::vector<D3DXVECTOR2> catmull;

if (m_finalArray.size() < 3)
return;

// double up
for (int i = 0; i < m_finalArray.size(); i++)
{
if (i == 0) {
catmull.push_back(m_finalArray);
catmull.push_back(m_finalArray);


}
else if (i == m_finalArray.size()-1)
{
catmull.push_back(m_finalArray);
catmull.push_back(m_finalArray);

} else
{
catmull.push_back(m_finalArray);


}

}
m_finalArray.clear();
//assert (m_finalArray.size() != catmull.size());

// switch size here
if (catmull.size() > 0 && catmull.size() <= 10)
{
for (int j = 0; j < catmull.size()-10;j++) {
D3DXVECTOR2 v;
for (double s = 0; s < 1.0f; s+=0.5){
D3DXVec2CatmullRom(&v, &catmull[j], &catmull[j+1], &catmull[j+5], &catmull[j+10],s);
m_finalArray.push_back(v);
}
}


}
else if (catmull.size() > 10 && catmull.size() <= 20)
{
for (int j = 0; j < catmull.size()-20;j++) {
D3DXVECTOR2 v;
for (double s = 0; s < 1.0f; s+=0.5){
D3DXVec2CatmullRom(&v, &catmull[j], &catmull[j+1], &catmull[j+10], &catmull[j+20],s);
m_finalArray.push_back(v);
}
}

}
if (catmull.size() > 20)
{
for (int j = 0; j < catmull.size()-30;j++) {
D3DXVECTOR2 v;
for (double s = 0; s < 1.0f; s+=0.5){
D3DXVec2CatmullRom(&v, &catmull[j], &catmull[j+1], &catmull[j+15], &catmull[j+30],s);
m_finalArray.push_back(v);
}
}


}

return;
}










This is a bit of hard-coded. Any tips is greatly appreciated!


....
X:147 Y:207
X:144 Y:209
X:146 Y:207
X:143 Y:210
X:146 Y:208
X:143 Y:210
X:145 Y:208
X:143 Y:210
X:145 Y:209
X:142 Y:211<<< Repeated
X:144 Y:209
X:142 Y:211<<< Repeated
X:144 Y:209
X:141 Y:211
X:143 Y:210
X:141 Y:212
X:143 Y:210
X:140 Y:212
X:143 Y:210
X:140 Y:212
X:142 Y:211
X:139 Y:213
X:142 Y:211
X:139 Y:213
X:141 Y:211
X:139 Y:213
X:141 Y:212
X:138 Y:214


Thanks in advance
Jack

[Edited by - lucky6969b on December 11, 2010 1:08:13 AM]

Share this post


Link to post
Share on other sites
Advertisement
I'm planning to do something like this myself soon, but I haven't tried it yet so I don't have a proper answer for you. But my plan was to delete most of the points and only keep every 5th point (for example). Then to use a Bezier curve to interpolate between those points. But like I say, I don't kow how well it works yet...

Share this post


Link to post
Share on other sites
Quote:
Original post by PolyVox
I'm planning to do something like this myself soon, but I haven't tried it yet so I don't have a proper answer for you. But my plan was to delete most of the points and only keep every 5th point (for example). Then to use a Bezier curve to interpolate between those points. But like I say, I don't kow how well it works yet...


I was initially deciding to follow Pinter's source code(found in the resource section of this site), but I couldn't understand some of its key points. So I am using Catmull rom cos i think its easier, actually, I need a quite precise pathfinding algorithm for my simulation...So good luck to you, please share your findings if you have any :)
Thanks
Jack

Share this post


Link to post
Share on other sites
I was having the same problem you are having with repeat visits to the same place using A*, so I created a separate grid to track where I'd already been. Something like:

int aStarCost[gridWidth][gridHeight]; //actual grid values used to find path
bool beenThereAlready[gridWidth][gridHeight]; //true if the square is chosen

I started with all the elements of beenThereAlready set to false, then set each one to true if I chose it as a point along the path. When choosing the next point in the path, I would look both at the total A* cost and also whether the point had already been visited. If it was true, I would ignore it as an option.

Share this post


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

  • Advertisement