The Gold Release of Fixin’ To Fight. Fixin’ To Fight is a 3rd person shooter, turret defense game. But, unlike normal turret defense games, where the enemies come down lanes, our game has the enemies attacking you from every possible direction. In order to stay alive and ultimately win the game, you must resist the impending onslaught, and then kill the giant boss bug.
I was the AI Lead on the project, which meant I was in charge of creating the path finding system we used, as well as creating the enemies’ ‘brains.’
I used a Navigation mesh with A* path-finding, which was computed outside of the game running, and loaded into the game via a pre-planning lookup table.
Below is a code snippet from an assistive program that ran A* on an imported navigation mesh file, and output a file containing the lookup table.
Here is the code snippet in word format.
bool CNavMesh::FindSolutionPath( std::vector& solutionList, CMeshCell const* StartCell, CMeshCell const* GoalCell )
{
bool doFullPath = true;
// Time to run A*
// If neither the start nor the goal is a non-NULL value, return.
if(!StartCell)
return false;
if(!GoalCell)
return false;
XMVECTOR goalPos = XMLoadFloat3(&GoalCell->m_vcCentroid);
XMVECTOR currPos = XMLoadFloat3(&StartCell->m_vcCentroid);
// Clear out the map
// clean up the nodes
for(map::iterator iter = m_mCreated.begin(); iter != m_mCreated.end(); ++iter)
{
(*iter).second->Reset();
}
m_mCreated.clear();
// Make a temp guy to say which cell is being looked at now.
CMeshCell const* currentCell = StartCell;
m_mCreated[StartCell] = m_vCreatedNodes[StartCell->m_nID];
tNode * currentNode = m_mCreated[StartCell];
currentNode->pParent = NULL;
// First, clear the OpenHeap to make searching easier
open.clear();
// Add to the OpenHeap the StartCell, so we start... where we start
open.push(currentNode);
// Loop while we have somewhere to go
bool found = false;
float TempFinal = 0.0f;
float GivenFound = 0.0f;
while(!open.empty())
{
// Get the first node in open
currentNode = open.front();
currentCell = currentNode->pCell;
// and get rid of it
open.pop();
// Build the solution list if we found it, or we are close
// enough to it
if(found)
{
if(currentNode->fGiven > GivenFound)
return found;
}
if(currentNode->pCell == GoalCell)
{
tNode const* tempCurrent = currentNode;
if(found)
{
if(currentNode->fFinal < TempFinal)
{
solutionList.clear();
TempFinal = currentNode->fFinal;
GivenFound = currentNode->fGiven;
// Build the list
while(tempCurrent != NULL)
{
solutionList.push_back(tempCurrent->pCell);
tempCurrent = tempCurrent->pParent;
}
}
}
found = true;
TempFinal = currentNode->fFinal;
GivenFound = currentNode->fGiven;
// Build the list
while(tempCurrent != NULL)
{
solutionList.push_back(tempCurrent->pCell);
tempCurrent = tempCurrent->pParent;
}
}
else
{
currPos = XMLoadFloat3(¤tCell->m_vcCentroid);
float distToTarget = XMVectorGetX(XMVector3LengthSq(goalPos - currPos));
float nextDistance = 0.0f, tempDist = 0.0f;
// We couldn't stop
// so for each successor of current....
// all of the edges
for(int i = 0; i < 3; ++i)
{
CMeshCell const* neighbor;
neighbor = currentCell->m_Edges[i]->pNextCell;
if(!neighbor)
continue;
int check = -1;
XMFLOAT3 closestPt = XMFLOAT3(neighbor->m_vcCentroid);
XMVECTOR edgeMidpoints[3];
edgeMidpoints[0] = neighbor->GetMidpoint(0);
edgeMidpoints[1] = neighbor->GetMidpoint(1);
edgeMidpoints[2] = neighbor->GetMidpoint(2);
XMVECTOR testPt = XMLoadFloat3(&closestPt);
nextDistance = XMVectorGetX(XMVector3LengthSq(goalPos - testPt));
float newGivenCost = 0.0f;
float hueristicCost = 0.0f;
newGivenCost = currentNode->fGiven + 1.0f * computeDistance(&currPos, &XMLoadFloat3(&neighbor->m_vcCentroid));
hueristicCost = m_fHeuristicWeight * computeHeuristic(StartCell, &XMLoadFloat3(&neighbor->m_vcCentroid), GoalCell);
// If we haven't used this one before
if((m_mCreated[neighbor] == NULL)
{
tNode* newNode = m_vCreatedNodes[neighbor->m_nID];
if(currentNode->pParent == newNode)
continue;
m_mCreated[neighbor] = newNode;
// It is now used
newNode->pParent = currentNode;
newNode->fGiven = newGivenCost;
newNode->fHeuristic = computeDistance(&XMLoadFloat3(&neighbor->m_vcCentroid),&goalPos)+ hueristicCost;
newNode->fFinal = newGivenCost + newNode->fHeuristic;
open.push(newNode);
}
else if( m_mCreated[neighbor]->fGiven > newGivenCost)
{
tNode* pNode = m_mCreated[neighbor];
if(currentNode->pParent == pNode)
continue;
pNode->pParent = currentNode;
pNode->fGiven = newGivenCost;
pNode->fHeuristic = computeDistance(&XMLoadFloat3(&neighbor->m_vcCentroid),&goalPos)+ hueristicCost;
pNode->fFinal = newGivenCost + pNode->fHeuristic;
// Maintain order in the heap
open.remove(pNode);
open.push(pNode);
}
}
}
}
// Couldn't do anything..... hrm
// Shouldn't happen, but better safe than sorry
return found;
}
{
unsigned int cellNum = m_vMeshCells.size();
m_vEdgeGraph.resize(cellNum);
for(unsigned int r = 0; r < cellNum; ++r)
{
m_vEdgeGraph[r].resize(cellNum);
}
std::cout << "Searching for Solution Path for every cell\n\n\n";
vector solutionList;
char edgeID = -1;
for(unsigned int i = 0; i < cellNum; ++i)
{
edgeID = 3;
std::cout << "Next Cell to search for i:\t" << i << "\n\n";
m_vEdgeGraph[i].setData(i, edgeID);
//m_vEdgeGraph[i][i] = 3;
for(unsigned int b = i + 1; b < cellNum; ++b)
{
solutionList.clear();
edgeID = -1;
if(FindSolutionPath(solutionList, m_vMeshCells[i], m_vMeshCells[b]))
{
CMeshCell const* nextCell = solutionList[solutionList.size()-2];
CMeshCell const* testPos = solutionList[1];
for(int e = 0; e < 3; ++e)
{
if(m_vMeshCells[i]->m_Edges[e]->pNextCell == nextCell)
{
edgeID = e;
break;
}
}
m_vEdgeGraph[i].setData(b, edgeID);
edgeID = (char)12;
for(int e = 0; e < 3; ++e)
{
if(m_vMeshCells[b]->m_Edges[e]->pNextCell == testPos )
{
edgeID = e;
break;
}
}
m_vEdgeGraph[b].setData(i, edgeID);
}
else
{
std::cout << "No edge, we are an island?!?! @ i: " << i << " b: " << b;
system("pause");
}
}
}
}
