2
\$\begingroup\$

I'm trying to understand if the A* algorithm is a possible pathfinding solution for my game.

I have a simple grid of nodes that an enemy can move around on, but the nodes represent traversable terrain at different heights in my game world. So although an enemy might be able to "jump down" from Node A to Node B (where Node A is much higher than Node B), it could not do the reverse and "climb up" from Node B to Node A. In other words, whether the A* algorithm can travel from one node to another depends on the direction of travel. It may be possible in one direction but not the other.

Can A* handle a situation like this, or do I need a different pathfinding algorithm?

\$\endgroup\$
  • \$\begingroup\$ You seem to be having a 'undirected graph', meaning that there is an arc between Node A and Node B, without considering direction; you should "direct" it, i.e. have an arc from Node A to Node B, but no arc from Node B to Node A. Or you could add a cost to each arc (taking the direction into consideration) to make going from Node B to Node A too expensive for your AI to consider. \$\endgroup\$ – Vaillancourt Mar 20 '15 at 16:03
  • \$\begingroup\$ If you are using a hexagonal grid, check out my HexgridUtilities library (open source, MIT License) here: hexgridutilities.codeplex.com. It includes an efficient A-star implementation as well as raycasting line-of-sight on terrain hexgrids. \$\endgroup\$ – Pieter Geerkens Mar 20 '15 at 21:21
  • \$\begingroup\$ Yes. A* considers whether you can move from A to B separately from whether you can move from B to A. You can have one or the other or both or neither. It also considers the cost of moving from A to B separately from the cost of moving from B to A, so climbing up could be slower than climbing down. \$\endgroup\$ – amitp Mar 20 '15 at 22:17
2
\$\begingroup\$

AStar is a suitable algorithm and can easily accomplish what you're describing.

It all comes down to either applying a set of rules or costs to the various connections between the nodes in your world(graph).

For example you could just have a bit of logic code in your TryGetNeighbours function call in each step of your pathfinding algorithm [untested code example] :

void Search(Node start, Node goal) {
    // ...
    Node[] neighbours = new Node[];
    if(TryGetNeighbours(currentNode, out neighbours) {
        foreach(var node in neighbours) {
            // do pathfinding calcs i.e. f = g + h. etc
        ...
        }
    }
    // ...
}

bool TryGetNeighbours(Node current, out Node[] neighbours) {
    Node neighbour;
    for(int x = 0; x < 4; x++) {
        // determine neighbouring node by Vector addition etc
        neighbour = current.pos + x
        if(neighbour.CanTraverse(current) {
            neighbours[x] = neighbour;
        }
    }
    if(neighbours[0] != null) return true;
    return false;
}
\$\endgroup\$
2
\$\begingroup\$

Yes it can.

You just have to create a method like "CanIMoveFrom1to2(currentNode, targetNode)". Then in A*, before analyzing that node any further, just check if its walkable from this node, if not, discard it, if yes then add it to open list.

\$\endgroup\$

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.