# Pathfinding with virtual fields

This topic is 1853 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi! I have problems with implementing pathfinding using virtual potentional fields. I have square-tiled 2D world, where we can put start, finish and wall (not walkable) blocks. I've read about "potentional fields" method, but I couldn't find any example, how to realize it and decide to do it myself.

Here is my code:
Point* currentPlayer = start; //current player position
Point* currentBlock;  //current blocked point
XMFLOAT2 blockedForce;
XMFLOAT2 lastsResultative = XMFLOAT2(0, 0);
XMFLOAT2 finishForce;
float squaredDist;
int i = 0;

while (*currentPlayer != *end)
{
finishForce = XMFLOAT2(
end->getX() - currentPlayer->getX(),
end->getY() - currentPlayer->getY() );
finishForce = Calculations::VecNormalize2D(finishForce);
/*finishForce.x *= 10;
finishForce.y *= 10;*/

i = 0;
while (i < blockedPoints.size())
{
currentBlock = blockedPoints[i];

squaredDist = pow( (currentPlayer->getX() - currentBlock->getX()),2 )
+ pow( (currentPlayer->getY() - currentBlock->getY()),2 );

blockedForce = XMFLOAT2(
(currentPlayer->getX() - currentBlock->getX()) / squaredDist,
(currentPlayer->getY() - currentBlock->getY()) / squaredDist);

lastsResultative = XMFLOAT2(
lastsResultative.x + blockedForce.x,
lastsResultative.y + blockedForce.y);
i++;
}

lastsResultative = XMFLOAT2(
lastsResultative.x + finishForce.x,
lastsResultative.y + finishForce.y);

lastsResultative = Calculations::VecNormalize2D(lastsResultative);

// ++++++++++++++ Make decision to what cell we have to walk, ++++++++++++++
// ++++++++++++++ based on the resultant vector ++++++++++++++++++++++++++++
float factor, prevFactor = 1000;
Point *cell = nullptr, *tempCell;
for (int j=-1; j<2; j++)
{
for (int k=-1; k<2; k++)
{
tempCell = GetCell(XMUSHORT2((USHORT)(currentPlayer->getX() + j),
(USHORT)(currentPlayer->getY() + k)));
if ((j==0 && k==0) || tempCell==nullptr) continue;

XMFLOAT2 cellVec = XMFLOAT2((tempCell->getX() - currentPlayer->getX()),
(tempCell->getY() - currentPlayer->getY()));
factor = abs(cellVec.x - lastsResultative.x) + abs(cellVec.y - lastsResultative.y);
if (factor < prevFactor)
{
cell = tempCell;
} else factor = prevFactor;

prevFactor = factor;
}
}
if (cell != nullptr)
{
currentPlayer = cell;
path.push_back(currentPlayer);
}
// ----------------------------------------------------------------------------
}

I've attached screens. In most cases, algorithm steps into eternal loop.

##### Share on other sites

Here is my screenshots.

##### Share on other sites

First thing is to render the vector directions at each node. Whether those look correct or not will narrow down where the problem is.

##### Share on other sites

DrEvil, thanks, it's realy good idea. I've done it and I saw on the vector field, that there are eternal loops, but I can't handle it. On the attached igms I've isolated with black areas wrong vectors. Direction defines as from cell center to periphery.

Don't know how to correct that.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 9
• 15
• 14
• ### Forum Statistics

• Total Topics
634070
• Total Posts
3015333
×