Improving performance of A* search in PHP
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.