iPhone pathfinding implementation

I am trying to create a Pacman AI for the iPhone, not the Ghost AI, but Pacman himself. I am using A* for pathfinding and I have a very simple开发者_开发技巧 app up and running which calculates the shortest path between 2 tiles on the game board avoiding walls.

So running 1 function to calculate a path between 2 points is easy. Once the function reaches the goalNode I can traverse the path backwards via each tiles 'parentNode' property and create the animations needed. But in the actual game, the state is constantly changing and thus the path and animations will have to too. I am new to game programming so I'm not really sure the best way to implement this.

Should I create a NSOperation that runs in the background and constantly calculates a goalNode and the best path to it given the current state of the game? This thread will also have to notify the main thread at certain points and give it information. The question is what?

At what points should I notify the main thread?

What data should I notify the main thread with?

...or am I way off all together?

Any guidance is much appreciated.

What I would suggest for a pacman AI is that you use a flood fill algorithm to calculate the shortest path and total distance to EVERY tile on the grid. This is a much simpler algorithm than A*, and actually has a better worst case than A* anyway, meaning that if you can afford A* every frame, you can afford a flood fill.

To explain the performance comparison in a in a little bit more detail, imagine the worst case in A*: due to dead ends you end up having to explore every tile on the grid before you reach your final destination. This theoretical case is possible if you have a lot of dead ends on the board, but unlikely in most real world pacman boards. The worst case for a flood fill is the same as the best case, you visit every tile on the map exactly once. The difference is that the iterative step is simpler for a flood fill than it is for an A* iteration (no heuristic, no node heap, etc), so visiting every node is faster with flood fill than with A*.

The implementation is pretty simple. If you imagine the grid as a graph, with each tile being a node and each edge with no wall between neighboring tiles as being an edge in the graph, you simply do a breadth first traversal of the graph, keeping track of which node you came from and how many nodes you've explored to get there. You mark a node as visited when you visit it, and never visit a node twice.

Here's some pseudo code to get you started:

openlist = [ start_node ]
do
    node = openlist.remove_first()
    for each edge in node.edges
        child = node.follow_edge(edge)
        if not child.has_been_visited
            child.has_been_visited = true
            child.cost = node.cost + 1
            child.previous = node
            openlist.add(child)
while openlist is not empty

To figure out how to get pacman to move somewhere, you start with the node you want and follow the .previous pointers all the way back to the start, and then reverse the list.

The nice thing about this is that you can make constant time queries about the cost to reach any tile on the map. For example, you can loop over each of the power pellets and calculate which one is closest, and how to get there.

You can even use this for the ghosts to know the fastest way to get back to pacman when they're in "attack" mode!

You might also consider flood fills from each of the ghosts, storing in each tile how far away the nearest ghost is. You could limit the maximum distance you explore, not adding nodes to the open list if they are greater than some maximum cost (8 squares?). Then, if you DID do A* later, you could bias the costs for each tile based on how close the ghosts are. But that's getting a little beyond what you were asking in the question.

It should be fast enough that you can do it inline every frame, or multithread it if you wish. I would recommend just doing it in your main game simulation thread (note, not the UI thread) for simplicity's sake, since it really should be pretty fast when all is said and done.

One performance tip: Rather than going through and clearing the "has_been_visited" flag every frame, you can simply have a search counter that you increment each frame. Something like so:

openlist = [ start_node ]
do
    node = openlist.remove_first()
    for each edge in node.edges
        child = node.follow_edge(edge)
        if child.last_search_visit != FRAME_NUMBER
            child.last_search_visit = FRAME_NUMBER
            child.cost = node.cost + 1
            child.previous = node
            openlist.add(child)
while openlist is not empty

And then you just increment FRAME_NUMBER every frame.

Good luck!

Slightly unrelated, but have you seen the ASIPathFinder framework? Might help if you have more advanced pathfinding needs.

I would recommend just pre-computing the distance between all pairs of points in the map. This takes n^2/2 space where there are n traversable points in the map. According to this link there are 240 pellets on the board which means there are about 57k combinations of points that you could query distances between. This is pretty small, and can be compressed (see here) to take less space.

Then, at run time you don't have to do any real computation except look at your possible moves and the distance to reach that location.