Я пытаюсь найти путь с проблемой Pacman, используя PHP.
<?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 pacman, положение x и y food, счетная строка и столбец плитки, затем сетка. Формат сетки «P» для pacman, «.» для еды, «-» для пройденного пути и «%» для стены.
Проблема в том, что я даю входные данные с плиткой 6×6 следующим образом:
%%%%%%
%-%%-%
%-%%-%
%-%%-%
%.--P%
%%%%%%
Код работает. Но, если я даю ввод с плиткой 37×37 со сложным лабиринтом, узел в массиве open всегда зацикливается. (Из HackerRank)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-------%-%-%-----------%---%-----%-%
%-%%%%%%%-%-%%%-%-%%%-%%%-%%%%%%%-%-%
%-------%-------%-%-----%-----%-%---%
%%%%%-%%%%%-%%%-%-%-%-%%%-%%%%%-%-%%%
%---%-%-%-%---%-%-%-%---%-%---%-%---%
%-%%%-%-%-%-%%%-%%%%%-%%%-%-%%%-%%%-%
%-------%-----%---%---%-----%-%-%---%
%%%-%%%%%%%%%-%%%%%%%-%%%-%%%-%-%-%-%
%-------------%-------%-%---%-----%-%
%-%-%%%%%-%-%%%-%-%-%%%-%-%%%-%%%-%-%
%-%-%-----%-%-%-%-%-----%---%-%-%-%-%
%-%-%-%%%%%%%-%-%%%%%%%%%-%%%-%-%%%-%
%-%-%-%-----%---%-----%-----%---%---%
%%%-%%%-%-%%%%%-%%%%%-%%%-%%%-%%%%%-%
%-----%-%-%-----%-%-----%-%---%-%-%-%
%-%-%-%-%-%%%-%%%-%%%-%%%-%-%-%-%-%-%
%-%-%-%-%-----------------%-%-%-----%
%%%-%%%%%%%-%-%-%%%%%-%%%-%-%%%-%%%%%
%-------%-%-%-%-----%---%-----%-%---%
%%%%%-%-%-%%%%%%%%%-%%%%%%%%%%%-%-%%%
%---%-%-----------%-%-----%---%-%---%
%-%%%-%%%%%-%%%%%%%%%-%%%%%-%-%-%%%-%
%-%---%------%--------%-----%-------%
%-%-%-%%%%%-%%%-%-%-%-%-%%%%%%%%%%%%%
%-%-%---%-----%-%-%-%-------%---%-%-%
%-%-%%%-%%%-%-%-%-%%%%%%%%%-%%%-%-%-%
%-%---%-%---%-%-%---%-%---%-%-%-----%
%-%%%-%%%-%%%%%-%%%-%-%-%%%%%-%-%%%%%
%-------%---%-----%-%-----%---%-%---%
%%%-%-%%%%%-%%%%%-%%%-%%%-%-%%%-%-%%%
%-%-%-%-%-%-%-%-----%-%---%-%---%-%-%
%-%-%%%-%-%-%-%-%%%%%%%%%-%-%-%-%-%-%
%---%---%---%-----------------%-----%
%-%-%-%-%%%-%%%-%%%%%%%-%%%-%%%-%%%-%
%.%-%-%-------%---%-------%---%-%--P%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Ваша программа почти правильная. Проблема возникает из-за использования in_array()
для поиска узла в $arr_close
или же $arr_open
, так как in_array()
сравнивает не только позицию $x
, $y
но и другой Node
члены $fCost
, $hCost
, $gCost
…; таким образом, он не распознает, что узел уже находится в закрытом наборе узлов, уже оцененных, если эти другие члены различаются, и получает возможность оценивать его повторно.
Быстрое решение заключается в использовании вместо in_array()
самостоятельная функция, которая при необходимости сравнивает только $x
, $y
Участники:
function in($node, $arr)
{
foreach ($arr as &$member)
if ($member->x == $node->x && $member->y == $node->y) return TRUE;
return FALSE;
}
Других решений пока нет …