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>The biggest issue with your code is that you don't do anything to avoid the same coordinates being visited multiple times. This means that the number of nodes you visit is <em>guaranteed</em> to grow exponentially, since it can keep going back and forth over the first few nodes many times.</p>

<p>The best way to avoid duplication is to maintain a <code>set</code> of the coordinates we've added to the queue (though if your <code>node</code> values are hashable, you might be able to add them directly to the set instead of coordinate tuples). Since we're doing a breadth-first search, we'll always reach a given coordinate by (one of) the shortest path(s), so we never need to worry about finding a better route later on.</p>

<p>Try something like this:</p>

<pre><code>def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    nodes = [(square_pos[x1,y1],0)]
    seen = set([(x1, y1)])
    for node, path_length in nodes:
        if path_length == 50:
            break
        if node.x == x2 and node.y == y2:
            return path_length
        for nx, ny in neighbors:
            try:
                square = square_pos[node.x + nx, node.y + ny]
                if square.lightcycle == None and (square.x, square.y) not in seen:
                    nodes.append((square, path_length + 1))
                    seen.add((square.x, square.y))
            except KeyError:
                pass
    return 50
</code></pre>

<p>I've also simplified the loop a bit. Rather than switching out the list after each depth, you can just use one loop and add to its end as you're iterating over the earlier values. I still abort if a path hasn't been found with fewer than 50 steps (using the distance stored in the 2-tuple, rather than the number of passes of the outer loop). A further improvement might be to use a <code>collections.dequeue</code> for the queue, since you could efficiently <code>pop</code> from one end while <code>append</code>ing to the other end. It probably won't make a huge difference, but might avoid a little bit of memory usage.</p>

<p>I also avoided most of the indexing by one and zero in favor of unpacking into separate variable names in the <code>for</code> loops. I think this is much easier to read, and it avoids confusion since the two different kinds of 2-tuples had had different meanings (one is a <code>node, distance</code> tuple, the other is <code>x, y</code>).</p>

python path-finding