astarlibrary - do not use.h

A Star 算法 的C++实现, 有很好的类实现

		}
		else if (b == parentYval+1)
		{
			if (walkability[parentXval+1][parentYval] == unwalkable 
				|| walkability[parentXval][parentYval+1] == unwalkable)
				corner = unwalkable; 
		}
	}	
	if (corner == walkable) {
	
//	If not already on the open list, add it to the open list.			
	if (whichList[a][b] != onOpenList) 
	{	

		//Create a new open list item in the binary heap.
		newOpenListItemID = newOpenListItemID + 1; //each new item has a unique ID #
		m = numberOfOpenListItems+1;
		openList[m] = newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap
		openX[newOpenListItemID] = a;
		openY[newOpenListItemID] = b;//record the x and y coordinates of the new item

		//Figure out its G cost
		if (abs(a-parentXval) == 1 && abs(b-parentYval) == 1)
			addedGCost = 14;//cost of going to diagonal squares	
		else	
			addedGCost = 10;//cost of going to non-diagonal squares				
		Gcost[a][b] = Gcost[parentXval][parentYval] + addedGCost;

		//Figure out its H and F costs and parent
		Hcost[openList[m]] = 10*(abs(a - targetX) + abs(b - targetY));
		Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]];
		parentX[a][b] = parentXval ; parentY[a][b] = parentYval;	

		//Move the new open list item to the proper place in the binary heap.
		//Starting at the bottom, successively compare to parent items,
		//swapping as needed until the item finds its place in the heap
		//or bubbles all the way to the top (if it has the lowest F cost).
		while (m != 1) //While item hasn't bubbled to the top (m=1)	
		{
			//Check if child's F cost is < parent's F cost. If so, swap them.	
			if (Fcost[openList[m]] <= Fcost[openList[m/2]])
			{
				temp = openList[m/2];
				openList[m/2] = openList[m];
				openList[m] = temp;
				m = m/2;
			}
			else
				break;
		}
		numberOfOpenListItems = numberOfOpenListItems+1;//add one to the number of items in the heap

		//Change whichList to show that the new item is on the open list.
		whichList[a][b] = onOpenList;
	}

//8.If adjacent cell is already on the open list, check to see if this 
//	path to that cell from the starting location is a better one. 
//	If so, change the parent of the cell and its G and F costs.	
	else //If whichList(a,b) = onOpenList
	{
	
		//Figure out the G cost of this possible new path
		if (abs(a-parentXval) == 1 && abs(b-parentYval) == 1)
			addedGCost = 14;//cost of going to diagonal tiles	
		else	
			addedGCost = 10;//cost of going to non-diagonal tiles				
		tempGcost = Gcost[parentXval][parentYval] + addedGCost;
		
		//If this path is shorter (G cost is lower) then change
		//the parent cell, G cost and F cost. 		
		if (tempGcost < Gcost[a][b]) //if G cost is less,
		{
			parentX[a][b] = parentXval; //change the square's parent
			parentY[a][b] = parentYval;
			Gcost[a][b] = tempGcost;//change the G cost			

			//Because changing the G cost also changes the F cost, if
			//the item is on the open list we need to change the item's
			//recorded F cost and its position on the open list to make
			//sure that we maintain a properly ordered open list.
			for (int x = 1; x <= numberOfOpenListItems; x++) //look for the item in the heap
			{
			if (openX[openList[x]] == a && openY[openList[x]] == b) //item found
			{
				Fcost[openList[x]] = Gcost[a][b] + Hcost[openList[x]];//change the F cost
				
				//See if changing the F score bubbles the item up from it's current location in the heap
				m = x;
				while (m != 1) //While item hasn't bubbled to the top (m=1)	
				{
					//Check if child is < parent. If so, swap them.	
					if (Fcost[openList[m]] < Fcost[openList[m/2]])
					{
						temp = openList[m/2];
						openList[m/2] = openList[m];
						openList[m] = temp;
						m = m/2;
					}
					else
						break;
				} 
				break; //exit for x = loop
			} //If openX(openList(x)) = a
			} //For x = 1 To numberOfOpenListItems
		}//If tempGcost < Gcost(a,b)

	}//else If whichList(a,b) = onOpenList	
	}//If not cutting a corner
	}//If not a wall/obstacle square.
	}//If not already on the closed list 
	}//If not off the map
	}//for (a = parentXval-1; a <= parentXval+1; a++){
	}//for (b = parentYval-1; b <= parentYval+1; b++){

	}//if (numberOfOpenListItems != 0)

//9.If open list is empty then there is no path.	
	else
	{
		path = nonexistent; break;
	}  

	//If target is added to open list then path has been found.
	if (whichList[targetX][targetY] == onOpenList)
	{
		path = found; break;
	}

	//If in step-by-step mode draw the screen step by step, waiting
	//for a keypress before the next step is taken.
	if (path == notfinished && stepByStep == true)
	{
		RenderScreen(stepByStep);
		while (1) //while "1" or "enter" or "escape" key not hit
		{
			if (KeyHit(13) || KeyDown(27)) //if enter or escape hit
			{
				stepByStep = false; break;
			}
			if (KeyHit(49)) break; //if "1" key hit
			CheckWinMessages();
		}
	}

	}
	while (!(KeyDown(27)));//Do until path is found or deemed nonexistent

//10.Save the path if it exists.
	if (path == found)
	{

//a.Working backwards from the target to the starting location by checking
//	each cell's parent, figure out the length of the path.
	pathX = targetX; pathY = targetY;
	do
	{
		//Look up the parent of the current cell.	
		tempx = parentX[pathX][pathY];		
		pathY = parentY[pathX][pathY];
		pathX = tempx;

		//Figure out the path length
		pathLength[pathfinderID] = pathLength[pathfinderID] + 1;
	}
	while (pathX != startX || pathY != startY);

//b.Resize the data bank to the right size in bytes
	pathBank[pathfinderID] = (int*) realloc (pathBank[pathfinderID],
		pathLength[pathfinderID]*8);

//c. Now copy the path information over to the databank. Since we are
//	working backwards from the target to the start location, we copy
//	the information to the data bank in reverse order. The result is
//	a properly ordered set of path data, from the first step to the
//	last.
	pathX = targetX ; pathY = targetY;
	cellPosition = pathLength[pathfinderID]*2;//start at the end	
	do
	{
	cellPosition = cellPosition - 2;//work backwards 2 integers
	pathBank[pathfinderID] [cellPosition] = pathX;
	pathBank[pathfinderID] [cellPosition+1] = pathY;

//d.Look up the parent of the current cell.	
	tempx = parentX[pathX][pathY];		
	pathY = parentY[pathX][pathY];
	pathX = tempx;

//e.If we have reached the starting square, exit the loop.	
	}
	while (pathX != startX || pathY != startY);	

	}
	return path;


//13.If there is no path to the selected target, set the pathfinder's
//	xPath and yPath equal to its current location and return that the
//	path is nonexistent.
noPath:
	xPath[pathfinderID] = startingX;
	yPath[pathfinderID] = startingY;
	return nonexistent;
}



//-----------------------------------------------------------------------------
// Name: ReadPath
// Desc: Reads path data created by FindPath()
//-----------------------------------------------------------------------------
void ReadPath(int pathfinderID) //If a path exists, read the path data
//	from the pathbank.
{
	pathLocation[pathfinderID] = 1; //set pathLocation to 1st step
	while (pathLocation[pathfinderID] < pathLength[pathfinderID])
	{
		int a = pathBank[pathfinderID] [pathLocation[pathfinderID]*2-2];
		int b = pathBank[pathfinderID] [pathLocation[pathfinderID]*2-1];
		pathLocation[pathfinderID] = pathLocation[pathfinderID] + 1;
		whichList[a][b] = 3;//draw dotted path
	} 
}