Jump to content
  • Advertisement
povilaslt2

2D Sidescroller pathfinding using A*(A star) algorithm

This topic is 427 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

Hello, I'm trying to implement enemy pathfinding algorihtm, but i have problem with empty tile collision when moving enemy to node.

 

For example this image shows how it should move like shown in example:

large.emptyExample.png.7ca087fc95ef0becf2248a02950b9c48.png

But it stucks at last tile:
large.stuckExample.png.7816d520acf3f66d71bab023f6d714eb.png

 

It happens because enemy collides with right side of "air" tile and then it removes from node list because it "collided", but it works with not "air" tiles of course. How do fix this problem?

Code:

void Enemy::generateMoveToNode(AStar::Vec2i lastNode)
	{
		auto lastSave = AStar::Vec2i{ 0.0f, 0.0f };

		while (!target.empty())
		{
			if (target.back().y == lastNode.y)
			{
				lastSave = target.back();
				target.pop_back();
			}
			else
			{
				moveToNodes.push_back(lastSave);
				moveToNodes.push_back(target.back());
				generateMoveToNode(target.back());
				return;
			}
		}

		moveToNodes.push_back(lastSave);
	}

	void Enemy::updateTarget(std::shared_ptr<InputManager> inputManager)
	{
		if (moveToNodes.empty()) return;

		// Calculate half sizes.
		float halfWidthA = getSize(0) / 2.0f;
		float halfHeightA = getSize(1) / 2.0f;
		float halfWidthB = 32.0f / 2.0f;
		float halfHeightB = 32.0f / 2.0f;

		// Calculate centers.
		auto centerA = glm::vec2(getPosition(0) + halfWidthA, getPosition(1) + halfHeightA);
		auto centerB = glm::vec2((moveToNodes.front().x * 32.0f) + halfWidthB, (moveToNodes.front().y * 32.0f) + halfHeightB);

		// Calculate current and minimum-non-intersecting distances between centers.
		float distanceX = centerA.x - centerB.x;
		float distanceY = centerA.y - centerB.y;
		float minDistanceX = halfWidthA + halfWidthB;
		float minDistanceY = halfHeightA + halfHeightB;

		setKey(inputManager->getKeyBinding("Move Left"), false);
		setKey(inputManager->getKeyBinding("Move Right"), false);
		setKey(inputManager->getKeyBinding("Jump"), false);
		setKey(inputManager->getKeyBinding("Duck"), false);

		// If we are not intersecting at all, return (0, 0).
		if (abs(distanceX) >= minDistanceX || abs(distanceY) >= minDistanceY)
		{
			if (moveToNodes.front().y > ceil(getPosition(1) / 32.0f))
				setKey(inputManager->getKeyBinding("Jump"), true);
			else if (moveToNodes.front().y < ceil(getPosition(1) / 32.0f))
			{
				if (getCanClimb())
					setKey(inputManager->getKeyBinding("Duck"), true);
			}
			else
			{
				if (moveToNodes.front().x < ceil(getPosition(0) / 32.0f))
					setKey(inputManager->getKeyBinding("Move Left"), true);
				else if (moveToNodes.front().x > floor(getPosition(0) / 32.0f))
					setKey(inputManager->getKeyBinding("Move Right"), true);
			}

			updateInput(inputManager);
			return;
		}

		// Calculate and return intersection depths.
		float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
		float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;

		updateInput(inputManager);
		moveToNodes.erase(moveToNodes.begin());
	}

generateMoveToNode: recursive function to generate all nodes.

updateTarget: updates enemy every frame to check if it hits node and then removes it from list and checks next till no nodes left.

Edited by povilaslt2

Share this post


Link to post
Share on other sites
Advertisement

  • 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!