0
\$\begingroup\$

enter image description here

Hello, I have a question about algorithm A * !

S : Start.

D : Destination.

W : Wall.

My hero goes from S and the destination is D, W is the walls, my hero can't go in there. If I use the algorithm A *, the hero will go from Cell (3,3) then to Cell (2,2) and finally to Cell (1,1).

It would be very logical if my hero is only a point. But my hero is about the same size of a Cell. So if my hero goes from Cell (2,2) to Cell (1,1), he will be hit by two walls. Each cell is 32 * 32 in size, my hero moves pixels by pixel, so he can collide with the edge of a cell. I have a collision test function, and thus the hero cannot move on.

Can someone help me, thank everyone !

\$\endgroup\$
  • 4
    \$\begingroup\$ Why does your graph allow diagonal movement if you don't want diagonal movement? \$\endgroup\$ – Vaillancourt Dec 11 '19 at 18:19
  • \$\begingroup\$ Oh, It's not that I don't want to move diagonally, but I can't move diagonally in this case! \$\endgroup\$ – Traistorm Dec 12 '19 at 0:35
0
\$\begingroup\$

This is not a problem with the A* algorithm. It's a problem with the data you've given it as input.

At some point in the algorithm, A* asks your map to enumerate the neighbouring nodes reachable from the node it's currently examining.

At this point, if the node (1, 1) is not supposed to be reachable from the current node (2, 2), it's the responsibility of your map / neighbour iteration to not offer (1, 1) as an option for the algorithm to consider. If you give it that as an option, you're saying "paths that pass from that node to this node are valid".

So for example, if your neighbour-enumerating function looks like this, visiting all 8 neighbours of a node, including diagonals:

IEnumerator<Node> GetNeighbours(Node source) {
    for(int x = -1; x <= 1; x++) {
        for(int y = -1; y <= 1; y++) {
            if(x== 0 && y == 0)
                continue;
            if(!map.IsInBounds(source.x + x, source.y + y)
                continue;

            var node = map.GetNode(source.x + x, source.y + y);
             yield return node;
        }
    }
}

...then you likely want to restrict it to visit only the four orthogonal neighbours instead:

IEnumerator<Node> GetNeighbours(Node source) {
    if(map.IsInBounds(source.x - 1, source.y);
        yield return map.GetNode(source.x - 1, source.y);

    if(map.IsInBounds(source.x, source.y - 1);
        yield return map.GetNode(source.x, source.y - 1);

    if(map.IsInBounds(source.x + 1, source.y);
        yield return map.GetNode(source.x + 1, source.y);

    if(map.IsInBounds(source.x, source.y + 1);
        yield return map.GetNode(source.x, source.y + 1);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Oh, thanks you ! \$\endgroup\$ – Traistorm Dec 12 '19 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.