Smoothing out turns in pathfinding

Started by
2 comments, last by Jon Hellebuyck 13 years, 4 months ago
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:207X:144 Y:209X:146 Y:207X:143 Y:210X:146 Y:208X:143 Y:210X:145 Y:208X:143 Y:210X:145 Y:209X:142 Y:211<<< RepeatedX:144 Y:209X:142 Y:211<<< RepeatedX:144 Y:209X:141 Y:211X:143 Y:210X:141 Y:212X:143 Y:210X:140 Y:212X:143 Y:210X:140 Y:212X:142 Y:211X:139 Y:213X:142 Y:211X:139 Y:213X:141 Y:211X:139 Y:213X:141 Y:212X:138 Y:214


Thanks in advance
Jack

[Edited by - lucky6969b on December 11, 2010 1:08:13 AM]
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...
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
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.
Jon Hellebuyck - Mode13.com

This topic is closed to new replies.

Advertisement