问使用PHP创建A*搜索

EN

//$start = array(28, 19), $end = array(14, 19)
//$this->map->map is a multidimensional array, everything has a cost of 1, except for 
//blocking squares that cost 99
//$this->map->map == $this->radar
//blocking square at 23-17, 22-18, 22-19, 22-20, 23-21, 19-17, 20-18,20-19,20-20,19-21
//they are like 2 specular mustache :P
function createPath($start, $end)
{
    $found = false;
    $temp  = $this->cost($start, $end);

    foreach($temp as $t){
        if($t['cost'] == $this->map->map[$end[0]][$end[1]]) $found = true;
        $this->costStack[$t['cost']][] = array('grid' => $t['grid'], 'dir' => $t['dir']);
    }

    ksort($this->costStack);

    if(!$found) {
        foreach($this->costStack as $k => $stack){
            foreach($stack as $kn => $node){
                $curNode = $node['grid'];
                unset($this->costStack[$k][$kn]);
                break;
            }

            if(!count($this->costStack[$k])) unset($this->costStack[$k]);
            break;
        }
        $this->createPath($curNode, $end);
    }
}

function cost($current, $target)
{
    $return = array();

    //$AIM  = array('n' => array(-1,  0),'e' => array( 0,  1),'s' => array( 1,  0),'w' => array( 0, -1));
    foreach($this->AIM as $direction => $offset){
        $position[0] = $current[0] + $offset[0];
        $position[1] = $current[1] + $offset[1];

        //radar is a copy of the map
        if ( $this->radar[$position[0]][$position[1]] == 'V') continue;
        else $this->radar[$position[0]][$position[1]] =  'V';

        $h = (int) $this->distance($position, $target);
        $g = $this->map->map[$position[0]][$position[1]];

        $return[] = array('grid' => $position,
                          'dir'  => $direction,
                          'cost' => $h + $g);
    }

    return $return;
}