StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>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*.</p> <p>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.</p> <p>Here's some pseudo code to get you started:</p> <pre><code>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 </code></pre> <p>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.</p> <p>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.</p> <p>You can even use this for the ghosts to know the fastest way to get back to pacman when they're in "attack" mode!</p> <p>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.</p> <p>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.</p> <p>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:</p> <pre><code>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 </code></pre> <p>And then you just increment FRAME_NUMBER every frame.</p> <p>Good luck!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload