Jump to content
  • Advertisement
povilaslt2

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

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

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!