PHP A* algorithm runs too slow

[Rokas.Rud]

Hello. So I wrote A-star pathing algorith. It is working fine, however it is to slow, if distance between start and finish is big. This "big" isn't really that big. It may take even 30seconds in 11x11 grid... I am looking for some optimization ideas of proffesionals here. Code:

<?php
function db_bf_check($connect, $x, $y, $owner_id){
    //patikrina ar koks objektas yra siame langelyje
    $query = "SELECT * FROM battlefield WHERE owner_id='".$owner_id."' AND x='".$x."' AND y='".$y."'";
    $result = $connect->query($query);
    $row = $result->fetch_array(MYSQLI_ASSOC);
    if($row['structure'] == 1){
        return $walkable = 0;
    } else {
        return $walkable = 1;
    }

}

function path($connect, $start, $end, $owner_id){
    $open_nodes = array();
    $closed_nodes = array();
    $closed_nodes_coord_only = array();

    $start_node = explode("|", $start);

    if(!function_exists('nodes_around')){
        function nodes_around($connect, $open_nodes, $closed_nodes, $closed_nodes_coord_only, $current_node_x, $current_node_y, $end, $start, $owner_id){

            $north_node = $current_node_x."|".($current_node_y - 1);
            $north_node_ex = explode("|", $north_node);
            $east_node = ($current_node_x + 1)."|".$current_node_y;
            $east_node_ex = explode("|", $east_node);
            $south_node = $current_node_x."|".($current_node_y + 1);
            $south_node_ex = explode("|", $south_node);
            $west_node = ($current_node_x -1)."|".$current_node_y;
            $west_node_ex = explode("|", $west_node);

            //viskas paejo. Skaiciuojama zingsnio verte.
            if(!function_exists('calculate')){
                function calculate($open_nodes, $end, $start, $current_node_x, $current_node_y, $direction_node_x, $direction_node_y, $dir){ //kadangi galima eiti ant sio node - apskaiciuoja jo kaina
                    $end_node = explode("|", $end);
                    $start_node = explode("|", $start);
                    $g = abs($start_node[0] - $direction_node_x) + abs($start_node[1] - $direction_node_y);
                    $h = abs($end_node[0] - $direction_node_x) + abs($end_node[1] - $direction_node_y);
                    $f = $g + $h;
                    $number = count($open_nodes);
                    $open = $number.":".$direction_node_x."|".$direction_node_y.":".$f.":".$dir;

                    return $open;
                }
            }

            if(!function_exists('array_closed_check')){
                function array_closed_check($node, $closed_nodes, $open_nodes){

                    if(in_array($node, $open_nodes) || in_array($node, $closed_nodes)){
                        return 1;
                    }else {
                        return 0;
                    }
                }
            }

            if(db_bf_check($connect, $north_node_ex[0], $north_node_ex[1], $owner_id) == 1 && array_closed_check($north_node, $closed_nodes_coord_only, $open_nodes) < 1){ //tikrina ar galima eiti per aplink esanti node(siuo atveju tikrina ar nera siena)
                $open_nodes[] = calculate($open_nodes, $end, $start, $current_node_x, $current_node_y, $north_node_ex[0], $north_node_ex[1], "south");
            }
            if(db_bf_check($connect, $east_node_ex[0], $east_node_ex[1], $owner_id) == 1 && array_closed_check($east_node, $closed_nodes_coord_only, $open_nodes) < 1){ //tikrina ar galima eiti per aplink esanti node(siuo atveju tikrina ar nera siena)
                $open_nodes[] = calculate($open_nodes, $end, $start, $current_node_x, $current_node_y, $east_node_ex[0], $east_node_ex[1], "west");
            }
            if(db_bf_check($connect, $south_node_ex[0], $south_node_ex[1], $owner_id) == 1 && array_closed_check($south_node, $closed_nodes_coord_only, $open_nodes) <1){ //tikrina ar galima eiti per aplink esanti node(siuo atveju tikrina ar nera siena)
                $open_nodes[] = calculate($open_nodes, $end, $start, $current_node_x, $current_node_y, $south_node_ex[0], $south_node_ex[1], "north");
            }
            if(db_bf_check($connect, $west_node_ex[0], $west_node_ex[1], $owner_id) == 1 && array_closed_check($west_node, $closed_nodes_coord_only, $open_nodes) < 1){ //tikrina ar galima eiti per aplink esanti node(siuo atveju tikrina ar nera siena)
                $open_nodes[] = calculate($open_nodes, $end, $start, $current_node_x, $current_node_y, $west_node_ex[0], $west_node_ex[1], "east");
            }

            return $open_nodes;
        }
    }

    if(!function_exists('get_path')){
        function get_path($closed_nodes, $start, $last){
            $path = array();
            $path[] = $last;
            $done = 0;

            while($done < 1){
                for($c = 0; $c < count($closed_nodes); $c++){ //padaro nauja array tik is koordinaciu
                    $coord = explode(":", $closed_nodes[$c]);
                    $coord_complete[] = $coord[1];
                }
                $key = array_search($last, $coord_complete); //end koordinates key, closed_node arrejuje
                $direction = explode(":", $closed_nodes[$key]);
                $direction_complete = $direction[3];

                if($direction_complete == "north"){
                    $coord_part = explode("|", $direction[1]);
                    $next_node = $coord_part[0]."|".($coord_part[1] - 1);
                }
                if($direction_complete == "east"){
                    $coord_part = explode("|", $direction[1]);
                    $next_node = ($coord_part[0] + 1)."|".$coord_part[1];
                }
                if($direction_complete == "south"){
                    $coord_part = explode("|", $direction[1]);
                    $next_node = $coord_part[0]."|".($coord_part[1] + 1);
                }
                if($direction_complete == "west"){
                    $coord_part = explode("|", $direction[1]);
                    $next_node = ($coord_part[0] - 1)."|".$coord_part[1];
                }
                $last = $next_node;
                $path[] = $next_node;

                if($next_node == $start){
                    $done = 1;
                    return $path;
                }
            }
        }
    }

    $closed_nodes_coord_only[] = $start_node[0]."|".$start_node[1];
    $open_nodes = nodes_around($connect, $open_nodes, $closed_nodes, $closed_nodes_coord_only, $start_node[0], $start_node[1], $end, $start, $owner_id);

    $f_score = array();

    if(!function_exists('choose_node')){
        function choose_node($open_nodes){
            for($c2 = 0; $c2 < count($open_nodes); $c2++){//iistraukia f scora is visu array ir sudeda i kita array tik f scorus, tam kad juos galetu palyginti
                $f = explode(":", $open_nodes[$c2]);
                $f_score[] = $f[2];
            }
            $min_f_score = min($f_score);
            $key = array_search($min_f_score, $f_score);
            $chosen_node = explode(":", $open_nodes[$key]); // su maziausiu f score esantis nodas, kodas tesiasi nuo jo

            $chosen_node_coord = explode("|", $chosen_node[1]);
            $chosen_node_coord[] = $open_nodes[$key];

            $closed_node_construction = $chosen_node_coord[0]."|".$chosen_node_coord[1];
            $closed_nodes[] = $closed_node_construction;

            return $chosen_node_coord;
        }
    }


    $done = 0;

    while($done < 1){
        $chosen_node_coord_x = choose_node($open_nodes)[0];
        $chosen_node_coord_y = choose_node($open_nodes)[1];

        $closed_nodes_coord_only[] = $chosen_node_coord_x."|".$chosen_node_coord_y;
        $closed_nodes[] = choose_node($open_nodes)[2];

        $key = array_search(choose_node($open_nodes)[2], $open_nodes);
        unset($open_nodes[$key]);
        $open_nodes = array_values($open_nodes);

        if($chosen_node_coord_x."|".$chosen_node_coord_y == $end){
            $done = 1;
            $path = get_path($closed_nodes, $start, $end);
            $path_complete = array_reverse($path);
        }else{
            $open_nodes = nodes_around($connect, $open_nodes, $closed_nodes, $closed_nodes_coord_only, $chosen_node_coord_x, $chosen_node_coord_y, $end, $start, $owner_id);    
        }
    }

    return $path_complete;
}
?>

I was checking loading times, and last while is taking all the seconds to load. Hope you will be able to read it... Still believe it is possible to optimize it :) Please help, and Thank You.

[veedeoo]

I am just guessing here and I hope someone can look at your code thoroughly

I suspect while loop is running to infinite cycle.

$done = 0;

while($done < 1){
        for($c2 = 0; $c2 < count($open_nodes); $c2++){

        }

  }

It will continue to run who knows until when. While codes below will immediately terminate when $done evaluates to true or assume the value of <1.

$done = 0;

while($done < 1){

    for($c2 = 0; $c2 < count($open_nodes); $c2++){

    }

    $done++;

}

not tested proofs ( just don't have the time actually run it, but I am assuming example below will demonstrate infinite loop.

Example 1 : This will slow down your server, because while loop will never break and will be forced to run over and over again, until the CTRL + C is hit.

$x = 0;

while($x < 1){

    for($y = 1; $y<=3; $y++){

        echo 'Y: '. $y.'<br/>';

    }

    echo '<b>X:</b> '. $x.'<br/>';


}

Example 2: This will terminate or break right away, as soon as $x evaluates to true or have incremented to 1. What is so cool about example 2 is that the output of $y would appear as if it is on top of $x and not inside of it.

$x = 0;

while($x < 1){

    for($y = 1; $y<=3; $y++){

        echo 'Y: '. $y.'<br/>';

    }

    echo '<b>X:</b> '. $x.'<br/>';

    $x++;

}

Example 2 will only loop 3 times while $x is less than 1 .

Y: 1
Y: 2
Y: 3
X: 0

For the benefits of other readers, this is how the parser prepares the output of example 2. The for loop Y terminates before the X becomes 1. Or we can simply say $x will only increment after $y has incremented less than or equal to 3.

 x0-y1-y2-y3-x1

while example 1 can be represented like this, looking for the break point of x..

x0-y1-y2-y3-y1-y2-y3-y.............?x....?x....?x

[lorenzoDAlipio]

nice proofs veed. You can also spread those proofs upwards and sideways similar to 4 axis, thus making it not leaving any stone unturned.