Sign in to follow this  
lucky6969b

Smoothing out turns in pathfinding

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[i]);
catmull.push_back(m_finalArray[i]);


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

} else
{
catmull.push_back(m_finalArray[i]);


}

}
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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this