Fast any-angle pathfinding

Question

I'm developing a game for mobile devices and have some trouble in deciding what pathfinding algorithm to use for my AI. My game is played on a static grid map of size up to 200x200. Players are able to move in any direction. Since the game is targeted for mobile devices, the algorithm needs to be very fast and can sacrifice optimality.

I've looked at several algorithms so far:

• A* with JPS optimization - it's supposedly fast, but finds discrete grid paths
• HPA* - from what I expect, it can be faster that A* + JPS, but is not optimal and finds discrete paths as well
• Theta* - this one finds nice continuous paths, but is too slow for distant points
• Anya (http://www.grastien.net/ban/articles/hg-icaps13.pdf) - optimal and any-angle, but relatively unknown and I suspect it would be too slow (I didn't find any benchmarks)

What technique would suit my needs best? Perhaps there are some good and efficient smoothing techniques that can be used to post process paths found by JPS/HPA*? Or is there some fast hierarchical algorithm that operates on continuous paths?

Answer 1

As noted in the comments, appropriate pre-calculation, navigation meshes (or probabilistic roadmaps) and other reductions of the state space should be the first thing to try, with standard heuristic search algorithms, before you start on anything more complex.

However, even if your grid was changing every frame, a 200 by 200 grid isn't so big that running a search at 24 frames a second is unthinkable. Assuming all you were doing in your game was pathfinding, you'd have about 40ms a frame. Provided your planner runs in less (and ideally a lot less) than this, you've got a reasonable chance of just using brute force.

A good measure for how well or badly any search algorithm is performing is the number of states it needs to expand in order to find a solution. A (well-written) A* algorithm with a good heuristic should explore a minimum number of states and should outperform any search that needs to visit every state. With that in mind, Dijkstra search is should be slower than A* (because it expands all states). This means Dikstra search is an approximate upper bound on the time required for planning with A*, even in the worst case, which can be difficult to construct).

To demonstrate that this isn't unreasonable, here is a small piece of Python code to populate an eight-connected grid (a reasonable first-order approximation to any-angle planning) and some related performance results.

import networkx as nx
import itertools
import numpy
import matplotlib.pyplot as plt

def grid_2d_8_connected(n, m):
    G = nx.Graph()
    xs = range(n)
    ys = range(m)
    dxs = [-1, 0, 1]
    dys = [-1, 0, 1]
    ds = [(dx, dy) for dx, dy in itertools.product(dxs, dys)]
    ds = [ d for d in ds if d != (0,0) ]
    for x, y in itertools.product(xs, ys):
        G.add_node( (x, y) )
    nodes = set(G.nodes())
    for x, y in itertools.product(xs, ys):
        for dx, dy in ds:
            sprime = (x+dx, y+dy)
            if sprime in nodes:
                G.add_edge((x, y), sprime)
    return G    

Running a quick performance test:

G = grid_2d_8_connected(200, 200)
%timeit nx.single_source_dijkstra_path_length(G, (0, 0))
1 loops, best of 3: 270 ms per loop

And on a slightly smaller grid:

G = grid_2d_8_connected(75, 75)
%timeit nx.single_source_dijkstra_path_length(G, (0, 0))
10 loops, best of 3: 35.6 ms per loop

Which shows that even a 200 by 200 grid, with a general purpose graph data structure, Dijkstra search (rather than A*) and using an interpreted language, planning on this size grid is only a factor of about 10 too slow (on my laptop).

The rule of thumb for moving to an interpreted language like Python to compiled code is that you typically improve performance (for sufficiently large problems) by a factor of about 10. Using interpreted code should make this fast enough.

My experiments show that reducing the sampling of each dimension of the state space by (a bit more than) a factor of two, is almost enough to achieve the desired performance on it's own. This will give you a representative (upper-bound) on the number of states you want in any simplified graph.