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.

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:

But it stucks at last tile:

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

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 9
• 11
• 11
• Forum Statistics

• Total Topics
633679
• Total Posts
3013299
×