Jump to content
  • Advertisement
Sign in to follow this  
????? ?????

Pathfinding with virtual fields

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

If you intended to correct an error in the post then please contact us.

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.
 
Help please with this issue.

Share this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!