Improving performance of A* search in PHP I need to figure out what can be done to improve the performance of a A* search algorithm in PHP. The idea is to look for the shortest path, in number of hops, between two points in a "map". Actual distance is irrelevant.

This is a minimalistic functional version of what I'm doing:

&lt;?php

    /*

        1 ____ 2 ____ 3 ___ 5
        | \            ____/|
        |  \    ______/     |
        |   4__/            |
        |  /                7
        | /                 
        6                   

    */

    $points = [
        1 =&gt; [2, 4, 6],
        2 =&gt; [1, 3],
        3 =&gt; [2, 5],
        4 =&gt; [1, 5, 6],
        5 =&gt; [3, 4, 7],
        6 =&gt; [1, 4],
        7 =&gt; [5]
    ];

    function points_pathfind($from, $to)
    {
        global $points;

        if (!isset($points[$from]) || !isset($points[$to]))
            return null;

        if ($from == $to)
            return [$from];

        $seen = [$from];  // improves peformance
        $queue = [];
        $step = [$from, null];
        for (;;)
        {
            if ($queue)
            {
                $step = array_shift($queue);
                if ($step[0] == $to)
                {
                    $result = [];
                    while ($step !== null)
                    {
                        $result[] = $step[0];
                        $step = $step[1];
                    }
                    return array_reverse($result);
                }
            }
            foreach ($points[$step[0]] as $point)
            {
                if (!in_array($point, $seen))
                {
                    $seen[]  = $point;
                    $queue[] = [$point, $step];
                }
            }

            if (!$queue)
                return null;
        }
    }

    echo implode(' -=&gt; ', points_pathfind(1, 7));


Output:


  1 -=> 4 -=> 5 -=> 7


The actual code howover will deal with almost 8000 points with a total of over 15000 connections, in which it all become extremely slow to the point that mapping some paths can take a couple seconds. This is unacceptable to my application. I even considered caching all possibilities to a database (which I will have to do anyway) but it is so slow it would take days only to generate this cache. I'm sure its performance can be improved somehow, I just can't figure out how.
I managed to greatly increase performance by avoiding array resizing and memory reallocation. By allocating all array space I need by start and reusing those arrays instead of recreating and resizing them, the performance of the code has dramatically changed from one search every couple seconds to almost a hundred searches per second.

&lt;?php

    /*

        1 ____ 2 ____ 3 ___ 5
        | \            ____/|
        |  \    ______/     |
        |   4__/            |
        |  /                7
        | /                 
        6                   

    */

    $points = [
        1 =&gt; [2, 4, 6],
        2 =&gt; [1, 3],
        3 =&gt; [2, 5],
        4 =&gt; [1, 5, 6],
        5 =&gt; [3, 4, 7],
        6 =&gt; [1, 4],
        7 =&gt; [5]
    ];

    $seen = $queue = [];
    foreach ($points as $key =&gt; $val)
    {
        $seen[$key] = 0;
        $queue[] = [0, -1];
    }

    function points_pathfind($from, $to)
    {
        global $points, $seen, $queue;

        if (!isset($points[$from]) || !isset($points[$to]))
            return null;

        if ($from == $to)
            return [$from];

        $queue[0][0] = $from;

        array_walk($seen, function (&amp;$a) { $a = 0; });
        $seen[$from] = 1;

        for ($cur = $end = 0; $cur &lt;= $end; ++$cur)    
        {
            foreach ($points[$queue[$cur][0]] as $next)
            {
                if (!$seen[$next])
                {
                    if ($next == $to)
                    {
                        $result = [$to];
                        for ($jmp = $cur; $jmp != -1; $jmp = $queue[$jmp][1])
                            $result[] = $queue[$jmp][0];
                        return array_reverse($result);
                    }

                    ++$end;
                    $seen[$next]    = 1;
                    $queue[$end][0] = $next;
                    $queue[$end][1] = $cur;
                }
            }
        }
    }

    echo implode(' -=&gt; ', points_pathfind(1, 7));


The general approach of the algorithm howover is still the same. I wonder if there is a more intelligent way.