Python - speed up pathfinding
<p>This is my pathfinding function:</p>

<pre><code>def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    old_nodes = [(square_pos[x1,y1],0)]
    new_nodes = []
    for i in range(50):
        for node in old_nodes:
            if node[0].x == x2 and node[0].y == y2:
                return node[1]
            for neighbor in neighbors:
                try:
                    square = square_pos[node[0].x+neighbor[0],node[0].y+neighbor[1]]
                    if square.lightcycle == None:
                        new_nodes.append((square,node[1]))
                except KeyError:
                    pass
        old_nodes = []
        old_nodes = list(new_nodes)
        new_nodes = []
        nodes = []
    return 50
</code></pre>

<p>The problem is that the AI takes to long to respond( <em>response time &lt;= 100ms</em>)
This is just a python way of doing <a href="https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm</a></p>

<p>One reasonably fast solution is to implement the Dijkstra algorithm (that I have already implemented in <a href="http://stackoverflow.com/q/39244636/1679629">that question</a>):</p>

<p>Build the original map. It's a masked array where the walker cannot walk on masked element:</p>

<pre><code>%pylab inline
map_size = (20,20)
MAP = np.ma.masked_array(np.zeros(map_size), np.random.choice([0,1], size=map_size))
matshow(MAP)
</code></pre>

<p><a href="http://i.stack.imgur.com/o0BFs.png" rel="nofollow"><img src="http://i.stack.imgur.com/o0BFs.png" alt="MAP"></a></p>

<p>Below is the Dijkstra algorithm:</p>

<pre><code>def dijkstra(V):
    mask = V.mask
    visit_mask = mask.copy() # mask visited cells
    m = numpy.ones_like(V) * numpy.inf
    connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
    cc = unravel_index(V.argmin(), m.shape) # current_cell
    m[cc] = 0
    P = {}  # dictionary of predecessors 
    #while (~visit_mask).sum() &gt; 0:
    for _ in range(V.size):
        #print cc
        neighbors = [tuple(e) for e in asarray(cc) - connectivity 
                     if e[0] &gt; 0 and e[1] &gt; 0 and e[0] &lt; V.shape[0] and e[1] &lt; V.shape[1]]
        neighbors = [ e for e in neighbors if not visit_mask[e] ]
        tentative_distance = [(V[e]-V[cc])**2 for e in neighbors]
        for i,e in enumerate(neighbors):
            d = tentative_distance[i] + m[cc]
            if d &lt; m[e]:
                m[e] = d
                P[e] = cc
        visit_mask[cc] = True
        m_mask = ma.masked_array(m, visit_mask)
        cc = unravel_index(m_mask.argmin(), m.shape)
    return m, P

def shortestPath(start, end, P):
    Path = []
    step = end
    while 1:
        Path.append(step)
        if step == start: break
        if P.has_key(step):
            step = P[step]
        else:
            break
    Path.reverse()
    return asarray(Path)
</code></pre>

<p>And the result:</p>

<pre><code>start = (2,8)
stop = (17,19)
D, P = dijkstra(MAP)
path = shortestPath(start, stop, P)
imshow(MAP, interpolation='nearest')
plot(path[:,1], path[:,0], 'ro-', linewidth=2.5)
</code></pre>

<p><a href="http://i.stack.imgur.com/EWeXl.png" rel="nofollow"><img src="http://i.stack.imgur.com/EWeXl.png" alt="enter image description here"></a></p>

<p>Below some timing statistics:</p>

<pre><code>%timeit dijkstra(MAP)
#10 loops, best of 3: 32.6 ms per loop
</code></pre>

python path-finding