a* pathfinding - cost of successor

Question

I'm remaking an old warcraft 3 custom game that I used to play way back when and putting it on the iphone. Basically, you have a set amount of time to build a maze out of a set amount of blocks, and the longer it takes the creep to run the maze, the more points you get.

I'm doing this all in airplay with cocos2d, and right now I'm putting in the a* pathfinding algorithm. I'm using Justin Heyes-Jones' implementation and working on the node class right now.

However, a couple things are confusing me. The class looks like this:

class MapSearchNode
{
public:
    unsigned int x;  // the (x,y) positions of the node
    unsigned int y; 


    MapSearchNode() { x = y = 0; }
    MapSearchNode( unsigned int px, unsigned int py ) { x=px; y=py; }

    bool IsGoal( MapSearchNode &nodeGoal ) { return (x == nodeGoal.x && y == nodeGoal.y); }
    bool IsSameState( MapSearchNode &rhs ) { return (x == rhs.x && y == rhs.y); }

    float GoalDistanceEstimate( MapSearchNode &nodeGoal );
    float GetCost( MapSearchNode &successor );
    bool GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node );

    //void PrintNodeInfo();
};

I'm just not sure what GetCost means. In this example maze, where X's are walls and _'s are walkable areas, would the cost of going from (3, 1) to (3, 2) be 0? And then what would the cost of going from (3, 1) to (4, 1), since it's impossible?

X X _ X X
X _ _ X X
X _ X X X
X _ _ _ _
X X X X X

And then I guess I can just implement GoalDistanceEstimate by using the distance formula, correct?

Answer 1

The general A* is based on a weighted graph. In practical maze solving applications, all edges have the same finite weight (usually 1) for passable terrain and infinite (written as a very large number, just use 100000 or something) for impassable terrain.