Jump to content
  • Advertisement
  • entries
    707
  • comments
    1173
  • views
    435845

Pathfinding and a rant

Sign in to follow this  
Programmer16

124 views

Well, I worked all day and finally got some pathfinding working. I still need to code the actual game's pathfinding. I did a new project so that I didn't have to worry about anything; I could just hack it together and figure out how to get it working.

The way I have it set up is far from perfect, but I did managed to fix a few bugs. The first being that it was circling the goal before actually visiting it (making for a longer path.) The second one thing I noticed is that it was going off in the wrong direction at the start of some of the paths.

Anyway, here are some screenshots:














The green arrow is the currently selected entity while red arrows are other available entities. The green node is the starting tile. White nodes are nodes that were checked and nodes with the circle-line are selected waypoints. The circle-line thingy points to the parent node.
Edit: oh, and the red node is the goal.

Here is my actual pathfinding code:

void Entity::MoveTo(int nDestColumn, int nDestRow)
{
static int nMovement = 0;

m_pMap->m_Batch.Clear();
if(!m_pMap)
return;

if(nDestColumn < 0 || nDestColumn >= m_pMap->m_nColumnCount || nDestRow < 0 || nDestRow >= m_pMap->m_nRowCount)
return;

int nStartX = (m_nX + (TILE_WIDTH / 2));
int nStartY = (m_nY + (TILE_HEIGHT - (TILE_HEIGHT / 4)));

for(int nEntity = 0; nEntity < m_pMap->m_Entities.size(); ++nEntity)
{
Entity CurEntity = m_pMap->m_Entities[nEntity];
if(CurEntity.IsAtPoint(nDestColumn * TILE_WIDTH, nDestRow * TILE_HEIGHT))
++nDestRow;
}

RECT Rect = {9 * TILE_WIDTH, 0, 10 * TILE_WIDTH, TILE_HEIGHT};
m_pMap->m_Batch.AddQuad((nStartX / TILE_WIDTH) * TILE_WIDTH, (nStartY / TILE_HEIGHT) * TILE_HEIGHT, 0.0f, TILE_WIDTH, TILE_HEIGHT, 0xffffffff, &Rect);

std::vector Open, Closed;

PathNode* pStart = new PathNode;
pStart->m_nRelativeCost = 0;
pStart->m_nAbsoluteGuessCost = abs((nStartX / TILE_WIDTH) - nDestColumn) * abs((nStartY / TILE_HEIGHT) - nDestRow);
pStart->m_pParent = 0;
pStart->m_nColumn = (nStartX / TILE_WIDTH);
pStart->m_nRow = (nStartY / TILE_HEIGHT);
Open.push_back(pStart);
bool bFound = false;

std::vector::iterator Itor = Open.begin();
while(Open.size() != 0)
{
PathNode* pNode = (*Itor);
Open.erase(Itor);
for(int nDir = 0; nDir < DIR_COUNT; ++nDir)
{
int nCol = pNode->m_nColumn;
int nRow = pNode->m_nRow;

Tile* pTile = m_pMap->GetNeighbor(nCol, nRow, nDir);
if(pTile)
{
if(pTile->m_pOccupier)
{
Closed.push_back(pNode);
continue;
}
}
else
continue;

for(std::vector::iterator ClosedItor = Closed.begin(); ClosedItor != Closed.end(); ++ClosedItor)
{
if((*ClosedItor)->m_nColumn == nCol && (*ClosedItor)->m_nRow == nRow)
break;
}
if(ClosedItor != Closed.end())
continue;

PathNode* pNewNode = new PathNode;
pNewNode->m_nColumn = nCol;
pNewNode->m_nRow = nRow;
pNewNode->m_nRelativeCost = pNode->m_nAbsoluteGuessCost + 10;
if(nDir > 3)
pNewNode->m_nRelativeCost -= 1;
pNewNode->m_nAbsoluteGuessCost = ((abs(nCol - nDestColumn) + 1) * (abs(nRow - nDestRow) + 1)) * 32;
pNewNode->m_pParent = pNode;
pNewNode->m_nDirectionFromParent = nDir;

if(nCol == nDestColumn && nRow == nDestRow)
{
PathNode* pParent = pNewNode->m_pParent;
while(pParent != 0)
{
SetRect(&Rect, pParent->m_nDirectionFromParent * TILE_WIDTH, TILE_HEIGHT, (pParent->m_nDirectionFromParent + 1) * TILE_WIDTH, TILE_HEIGHT * 2);
m_pMap->m_Batch.AddQuad(pParent->m_nColumn * TILE_WIDTH, pParent->m_nRow * TILE_HEIGHT, 0.0f, TILE_WIDTH, TILE_HEIGHT, 0xffffffff, &Rect);
pParent = pParent->m_pParent;
}
bFound = true;
break;
}

if(pNode->m_nColumn == pNewNode->m_nColumn && pNode->m_nRow == pNewNode->m_nRow)
continue;

for(std::vector::iterator OpenItor = Open.begin(); OpenItor != Open.end(); ++OpenItor)
{
if((*OpenItor)->m_nColumn == nCol && (*OpenItor)->m_nRow == nRow)
{
if(pNewNode->m_nRelativeCost < (*OpenItor)->m_nRelativeCost)
{
(*OpenItor)->m_pParent = pNode;
(*OpenItor)->m_nAbsoluteGuessCost = pNewNode->m_nAbsoluteGuessCost;
(*OpenItor)->m_nDirectionFromParent = pNewNode->m_nDirectionFromParent;
}
break;
}
}
Open.push_back(pNewNode);

SetRect(&Rect, 11 * TILE_WIDTH, 0, 12 * TILE_WIDTH, TILE_HEIGHT);
m_pMap->m_Batch.AddQuad(pNewNode->m_nColumn * TILE_WIDTH, pNewNode->m_nRow * TILE_HEIGHT, 0.0f, TILE_WIDTH, TILE_HEIGHT, 0xffffffff, &Rect);
}
Closed.push_back(pNode);

Itor = Open.begin();
if(!bFound)
{
int nLeastIndex = 0;
int nIndex = 0;
int nLeastValue = (*Itor)->m_nAbsoluteGuessCost + (*Itor)->m_nRelativeCost;
for(; Itor != Open.end(); ++Itor)
{
if(((*Itor)->m_nAbsoluteGuessCost + (*Itor)->m_nRelativeCost) < nLeastValue)
{
nLeastValue = (*Itor)->m_nAbsoluteGuessCost + (*Itor)->m_nRelativeCost;
nLeastIndex = nIndex;
}
++nIndex;
}
Itor = Open.begin() + nLeastIndex;
}
else if(bFound)
break;
}

if(bFound)
{
RECT Rect = {10 * TILE_WIDTH, 0, 11 * TILE_WIDTH, TILE_HEIGHT};
m_pMap->m_Batch.AddQuad(nDestColumn * TILE_WIDTH, nDestRow * TILE_HEIGHT, 0.0f, TILE_WIDTH, TILE_HEIGHT, 0xffffffff, &Rect);
}

if(!bFound)
{
Engine::GetSingleton()->LogDebugOutput("OMG, CAN'T FIND PATH!!! DYING!!!", DOT_TEXT);
}

for(std::vector::iterator Itor = Open.begin(); Itor != Open.end(); ++Itor)
{
PathNode* pNode = (*Itor);
delete pNode;
}
}



I know that some of the code is horrible, its just test code. I'm going to totally redo the whole thing when I actually use it in my game.

I know I'm doing something wrong because it searches in the wrong direction a lot. I don't have a screenshot to show it, but some times it'll search totally in the wrong direction first.

I decided not to do the rant because I'd much rather get comments about my pathfinding. But, to keep your imagination going, it included the word 'penis', so you know it had to be good.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

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
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!