I agree with @fortran, you might want to take a look at other path-finding like Breath-First, Depth-First, Minimax, Negmax etc and weigh the positives and negatives for your scenario.
As you may know, boost has a a-star implementation. You can try following these instructions to build boost on iPhone, but I'm not sure if it will work or not for you as it's not a "full port" of boost and it may error out on that stuff.
And... for what it's worth... the following is from Algorithms in a Nutshell (Java, not C++ but maybe you'd like to port it)
public Solution search(INode initial, INode goal) {
// Start from the initial state
INodeSet open = StateStorageFactory. create(StateStorageFactory. TREE) ;
INode copy = initial. copy( );
scoringFunction. score(copy) ;
open. insert(copy) ;
// Use Hashtable to store states we have already visited.
INodeSet closed = StateStorageFactory. create(StateStorageFactory. HASH) ;
while (! open. isEmpty( )) {
// Remove node with smallest evaluation function and mark closed.
INode n = open. remove( );
closed. insert(n) ;
// Return if goal state reached.
if (n. equals(goal) ) { return new Solution (initial, n) ; }
// Compute successor moves and update OPEN/CLOSED lists.
DepthTransition trans = (DepthTransition) n. storedData( );
int depth = 1;
if (trans ! = null) { depth = trans. depth+1; }
DoubleLinkedList<IMove> moves = n. validMoves( );
for (Iterator<IMove> it = moves. iterator( ); it. hasNext( ); ) {
IMove move = it. next( );
// Make move and score the new board state.
INode successor = n. copy( );
move. execute(successor) ;
// Record previous move for solution trace and compute
// evaluation function to see if we have improved upon
// a state already closed
successor. storedData(new DepthTransition(move, n, depth) ) ;
scoringFunction. score(successor) ;
// If already visited, see if we are revisiting with lower
// cost. If not, just continue; otherwise, pull out of closed
// and process
INode past = closed. contains(successor) ;
if (past ! = null) {
if (successor. score( ) >= past. score( )) {
continue;
}
// we revisit with our lower cost.
closed. remove(past) ;
}
// place into open.
open. insert (successor) ;
}
}
// No solution.
return new Solution (initial, goal, false) ;
}