[class] Znajdź najkrótszą drogę, algorytm A* Opcje

[bim2]

[PHP] pobierz, plaintext 
<?php
/**
 * License
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 **/
/**
 * @author Hernas Service <kontakt@hernass.pl>
 * @copyright 2008 HernasS.pl.
 * @version 2.0
 */
class Way {
    /* Startowy punkt na osi X */
    private $start_x;
    
    /* Startowy punkt na osi Y */
    private $start_y;
    
    /* Mapa podana przez użytkownika */
    private $aMap;
    
    /* Mapa wygenerowana na potrzeby skryptu */
    private $aMap_;
    
    /* Punkt przeznaczenia na osi X */
    private $destination_x;
    
    /* Punkt przeznaczenia na osi Y */
    private $destination_y;
    
    /* Tablica przeszukiwania dróg */
    private $aWay = array();
    
    /* Tablica wyjściowa z wybraną drogą */
    private $aWays = array();
    
    /* Numer kolejnego kroku przeszukiwania */
    private $fillNumber = 0;
    
    /* Konstruktor klasy
     * @param integer $x - Startowy punkt na osi X
     * @param integer $y - Startowy punkt na osi Y
     * @param array $aMap - Mapa podana przez użytkownika
    */
    public function __construct($x, $y, $aMap)
    {
        $this->aMap = $aMap;
        
        $this->aWays[] = array($x, $y);
        $this->start_x = $x;
        $this->start_y = $y;
        
        $this->regenerateMap();
        
    }
    /* Szuka drogi
     * @param integer $x - Punkt przeznaczenia na osi X
     * @param integer $y - Punkt przeznaczenia na osi Y
    */
    public function findWay($x, $y)
    {    
        $this->destination_x = $x;
        $this->destination_y = $y;    
        
        $this->startFinding();
        $this->mirrorFinding($x, $y);
        return $this->aWay;
    }
    /* Znaczy kolejne kroki na mapie */
    private function startFinding()
    {
        foreach($this->aWays AS $v)
        {
            list($x, $y) = $v;
            $this->aMap_[$y][$x] = $this->fillNumber;
            $new_x[] = $x+1;
            $new_y[] = $y;
            
            $new_x[] = $x+1;
            $new_y[] = $y+1;
            
            $new_x[] = $x+1;
            $new_y[] = $y-1;
            
            $new_x[] = $x-1;
            $new_y[] = $y;
            
            $new_x[] = $x-1;
            $new_y[] = $y+1;
            
            $new_x[] = $x-1;
            $new_y[] = $y-1;
                    
            $new_x[] = $x;
            $new_y[] = $y+1;
            
            $new_x[] = $x;
            $new_y[] = $y-1;
            $paths = array();
            foreach($new_x AS $i => $v)
            {
                if(isset($this->aMap_[$new_y[$i]][$v]) AND $this->aMap_[$new_y[$i]][$v]==-1)
                {
                    if($v==$this->destination_y AND $new_y[$i]==$this->destination_x)
                    {
                        $paths[] = array($v, $new_y[$i]);
                        break;
                    }
                    $paths[] = array($v, $new_y[$i]);
                }
            }
        }
        
        $this->fillNumber++;
    if(isset($paths))
    {
        $this->aWays = $paths;
        $this->startFinding();
    }
        
    }
    /* Szuka drogi od końca po kolejnych krokach
     * @param integer $x - Punkt kolejnego kroku na osi X
     * @param integer $y - Punkt kolejnego kroku na osi Y
    */
    private function mirrorFinding($x, $y)
    {
        $new_x[] = $x+1;
        $new_y[] = $y;
        
        $new_x[] = $x+1;
        $new_y[] = $y+1;
        
        $new_x[] = $x+1;
        $new_y[] = $y-1;
        
        $new_x[] = $x-1;
        $new_y[] = $y;
        
        $new_x[] = $x-1;
        $new_y[] = $y+1;
        
        $new_x[] = $x-1;
        $new_y[] = $y-1;
                
        $new_x[] = $x;
        $new_y[] = $y+1;
        
        $new_x[] = $x;
        $new_y[] = $y-1;
        foreach($new_x AS $i => $v)
        {
            if(isset($this->aMap_[$new_y[$i]][$v]) AND $this->aMap_[$new_y[$i]][$v]==($this->aMap_[$y][$x]-1))
            {
                $this->aWay[] = array($new_y[$i], $v);
                $this->mirrorFinding($v, $new_y[$i]);
                break;
            }
        }
    }
    /* Generuję mapę na potrzeby skryptu    */
    private function regenerateMap()
    {
        foreach($this->aMap AS $y => $v_)
        {
            foreach($v_ AS $x => $v)
            {
                if($this->start_x == $x AND $this->start_y == $y)
                {
                    $this->aMap_[$y][$x] = 0;
                } elseif($v==1) {
                    $this->aMap_[$y][$x] = -2;
                } elseif($v==0) {
                    $this->aMap_[$y][$x] = -1;
                } else {
                    $this->aMap_[$y][$x] = -2;
                }
            }            
        }
    }
    
    
}
?>
[PHP] pobierz, plaintext 

Oraz przykład użycia (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

[PHP] pobierz, plaintext 
<?php
$aMap = array(
array(1,0,0,0,1,0,0,0),
array(1,0,1,1,1,1,0,0),
array(1,0,1,0,0,1,0,1),
array(0,0,0,0,0,0,0,1),
array(0,0,0,1,1,1,1,1),
array(0,1,0,0,0,0,0,0),
array(1,1,0,0,0,1,0,0),
array(1,1,0,1,1,1,0,0),
); // 0 -można chodzić
$oWay = new Way(2, 7, $aMap); //X i Y liczone od 0 (jak klucz arraya)
print_r($oWay->findWay(7, 7));
?>
[PHP] pobierz, plaintext 

Oraz przykład graficzny:
http://hernass.pl/searchWay/

PS. Dziękuję wszystkim, którzy pomogli przy skrypcie (IMG:http://forum.php.pl/style_emoticons/default/snitch.gif)

[wookieb]

Sry za offtop ale... Dla startowego elementu 2,1 i koncowego 6,1 zaznacza dodatkowe pole jako "droga" pomimo tego ze do tej drogi nie nalezy. Czy to własciwe zachowanie?
(IMG:http://img229.imageshack.us/img229/9829/clipboard02wt9.th.jpg) (IMG:http://img229.imageshack.us/images/thpix.gif)