PHP A *複雑な迷路ではPathfindingは機能しませんHackerRank

Question

PHPを使用してPacmanの問題で経路探索をしようとしています。

<?php 
$_fp = fopen("php://stdin", "r"); 

// Node 
class Node { 

    var $x; 
    var $y; 
    var $fCost; 
    var $hCost; 
    var $gCost = 0; 
    var $parent; 

    function __construct($x=0,$y=0){ 
     $this->x = $x; 
     $this->y = $y; 
    } 

    function getNeighbours($depth = 1) { 
     $neighbours = array(); 

     $operand = array(
      array ('x' => -1, 'y' => 0), 
      array ('x' => 0, 'y' => -1), 
      array ('x' => 0, 'y' => 1), 
      array ('x' => 1, 'y' => 0) 
      ); 

     foreach ($operand as $key => $value) { 
      $checkX = $this->x + $value['x']; 
      $checkY = $this->y + $value['y']; 

      if($checkX >= 0 && $checkY >= 0) 
       array_push($neighbours, $node = new Node($checkX, $checkY)); 
     } 

     return $neighbours; 
    } 

    function fCost(){ 
     global $food; 
     return $this->gCost() + $this->hCost($food); 
    } 

    function gCost(){ 
     global $pacman; 
     return abs($pacman->x - $this->x) + abs($pacman->y - $this->y); 
    } 

    function hCost($destination){ 
     return abs($destination->x - $this->x) + abs($destination->y - $this->y); 
    } 
} 

function retracePath($start,$end) { 
    $current = $end; 

    while ($current != $start) { 
     echo $current->x . " " . $current->y."<br>"; 
     $current = $current->parent; 
    } 
} 

$pacman = new Node(); 
$food = new Node(); 

// Input data 
fscanf($_fp, "%d %d", $pacman->x, $pacman->y); // Pacman's position 
fscanf($_fp, "%d %d", $food->x, $food->y); // Food's position 
fscanf($_fp, "%d %d", $row_size, $col_size); // For map size row and col 


// Input for map by row 
for($row=0; $row<$row_size; $row++) { 
    $map[$row] = trim(fgets(STDIN)); 
} 

// Astar 
$arr_open = array(); // set of nodes to be evaluated 
$arr_close = array(); // set of nodes already evaluated 

array_push($arr_open, $pacman); // add the start node to $arr_open 

$key_arr_open = 0; 

while(count($arr_open) > 0) { // loop 

    $current = new Node(); 
    $current = $arr_open[$key_arr_open]; 
    unset($arr_open[$key_arr_open]); 
    array_push($arr_close, $current); 

    if($current->x == $food->x && $current->y == $food->y) { 
     retracePath($pacman,$current); 
     echo "sukses<br>" 
     break; 
    } 

    $neighbours = $current->getNeighbours(); 

    foreach ($neighbours as $key => $data) { 

     if($map[$data->x][$data->y] == "%" or in_array($data, $arr_close)) 
     { 
      //echo "not traversable<br>"; 
      continue; 
     } 

     $new_cost_to_neighbour = $current->gCost() + $current->hCost($data); 

     if($new_cost_to_neighbour < $data->gCost() or !in_array($data, $arr_open)) { 
      $data->gCost = $new_cost_to_neighbour; 
      $data->hCost = $data->hCost($food); 
      $data->fCost = $new_cost_to_neighbour + $data->hCost($food); 
      $data->parent = $current; 

      if(!in_array($data, $arr_open) ) 
      { 
       array_push($arr_open, $data); 
      } 
     } 
    } 

    $key_arr_open ++; 
} 

?> 

入力フォーマット：タイルの位置xとyパックマン、位置xおよびy食品、カウント行と列は、グリッド。グリッド形式はpacmanの場合は "P"、 " 「 - 」は横断方向、「％」は壁用です。

%%%%%% 
%-%%-% 
%-%%-% 
%-%%-% 
%.--P% 
%%%%%% 

コードが仕事である：私はこのような6x6のタイルに入力を与えるとき

問題があります。しかし、複雑な迷路を持つ37x37のタイルを入力すると、配列のノードが常にループします。 （HackerRankより）

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    %-------%-%-%-----------%---%-----%-% 
    %-%%%%%%%-%-%%%-%-%%%-%%%-%%%%%%%-%-% 
    %-------%-------%-%-----%-----%-%---% 
    %%%%%-%%%%%-%%%-%-%-%-%%%-%%%%%-%-%%% 
    %---%-%-%-%---%-%-%-%---%-%---%-%---% 
    %-%%%-%-%-%-%%%-%%%%%-%%%-%-%%%-%%%-% 
    %-------%-----%---%---%-----%-%-%---% 
    %%%-%%%%%%%%%-%%%%%%%-%%%-%%%-%-%-%-% 
    %-------------%-------%-%---%-----%-% 
    %-%-%%%%%-%-%%%-%-%-%%%-%-%%%-%%%-%-% 
    %-%-%-----%-%-%-%-%-----%---%-%-%-%-% 
    %-%-%-%%%%%%%-%-%%%%%%%%%-%%%-%-%%%-% 
    %-%-%-%-----%---%-----%-----%---%---% 
    %%%-%%%-%-%%%%%-%%%%%-%%%-%%%-%%%%%-% 
    %-----%-%-%-----%-%-----%-%---%-%-%-% 
    %-%-%-%-%-%%%-%%%-%%%-%%%-%-%-%-%-%-% 
    %-%-%-%-%-----------------%-%-%-----% 
    %%%-%%%%%%%-%-%-%%%%%-%%%-%-%%%-%%%%% 
    %-------%-%-%-%-----%---%-----%-%---% 
    %%%%%-%-%-%%%%%%%%%-%%%%%%%%%%%-%-%%% 
    %---%-%-----------%-%-----%---%-%---% 
    %-%%%-%%%%%-%%%%%%%%%-%%%%%-%-%-%%%-% 
    %-%---%------%--------%-----%-------% 
    %-%-%-%%%%%-%%%-%-%-%-%-%%%%%%%%%%%%% 
    %-%-%---%-----%-%-%-%-------%---%-%-% 
    %-%-%%%-%%%-%-%-%-%%%%%%%%%-%%%-%-%-% 
    %-%---%-%---%-%-%---%-%---%-%-%-----% 
    %-%%%-%%%-%%%%%-%%%-%-%-%%%%%-%-%%%%% 
    %-------%---%-----%-%-----%---%-%---% 
    %%%-%-%%%%%-%%%%%-%%%-%%%-%-%%%-%-%%% 
    %-%-%-%-%-%-%-%-----%-%---%-%---%-%-% 
    %-%-%%%-%-%-%-%-%%%%%%%%%-%-%-%-%-%-% 
    %---%---%---%-----------------%-----% 
    %-%-%-%-%%%-%%%-%%%%%%%-%%%-%%%-%%%-% 
    %.%-%-%-------%---%-------%---%-%--P% 
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

Answer 1

プログラムはほぼ正しいです。 in_array()だけでなく、位置$x、$y、だけでなく、他のNodeメンバーを比較するため、問題は、$arr_closeまたは$arr_openでノードを検索するためin_array()を使用してから生じる$fCost、$hCost、$gCost ...。したがって、すでに評価されているノードのクローズド・セット内にノードがすでに存在していることを認識せず、他のメンバーが異なる場合には、それを繰り返し評価することになります。ポストにそれが動作しないために迷路を

function in($node, $arr) 
{ 
    foreach ($arr as &$member) 
     if ($member->x == $node->x && $member->y == $node->y) return TRUE; 
    return FALSE; 
}