[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)

[-=Peter=-]

Zainspirowany tym tematem, nie patrząc na kod który bim2 podał, stworzyłem też swoją klasę szukającą najkrótszą drogę (też żadnego książkowego algortmu nie znałem na ten problem). Oto kod, jeśli ktoś by chciał go wykorzystać to brać śmiało (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif) Nie sprawdzałem go dokładnie, ale faktycznie zwraca najkrótszą drogę.

[PHP] pobierz, plaintext 
<?php
 
class Path{
    /**
     * Map
     * 
     * example:
     *  $map = array(
     *         array(0, 1, 0, 0, 0, 0),
     *         array(0, 1, 0, 1, 0, 1),
     *         array(1, 1, 1, 1, 0, 1),
     *         array(1, 1, 1, 1, 1, 1),
     *         array(1, 0, 1, 0, 1, 1),
     *         array(0, 1, 1, 0, 0, 0)
     * );
     *
     *
     * @var array
     */
    private $map = array();
    
    /**
     * Size of map
     * 
     * @var array
     */
    private $mapSize = array();
    
    /**
     * Coordinates of start field ($sx, $sy) and
     * destination field ($dx, $dy)
     * 
     * @var integer
     */
    private $sx, $sy, $dx, $dy;
    
    /**
     * Generated shortest way
     *
     * @var array
     */
    private $path = array();
    
    /**
     * Number of footsteps
     *
     * @var int
     */
    private $minFootsteps = null;
    
    /**
     * Constructor
     *
     * @param array Map
     */
    public function __construct(array $map){
        $this->setMap($map);
    }
    
    /**
     * Setter
     *
     * @param array Map
     * @return boolean
     */
    private function setMap(array $map){
        
        //validation
        if(count($map) > 0){
            $size = null;
            
            foreach($map as $line){
                $size = ($size === null ? count($line) : $size);
                
                if(count($line) != $size){
                    throw new Exception('Wymiary kazdego wiersza maja byc takie same!');
                }
                
                foreach($line as $element){
                    if($element != 0 && $element != 1){
                        throw new Exception('Wartosci pojedynczego pola musza miec wartosc 0 lub 1');
                    }
                }
            }
            
            $this->map = $map;
            $this->mapSize = array($size, count($map));
            return true;
        }
        throw new Exception('Podano pusta mape');
    }
    
    /**
     * Getter
     *
     * @return array
     */
    public function getMapSize(){
        return $this->mapSize;
    }
    
    /**
     * Set start field
     *
     * @param integer $x
     * @param integer $y
     * @return boolean
     */
    public function setStart($x, $y){
        if($this->validatePoint($x, $y)){
            $this->sx = $x;
            $this->sy = $y;
            
            return true;
        }
        
        return false;
    }
    
    /**
     * Set destination field
     *
     * @param integer $x
     * @param integer $y
     * @return boolean
     */
    public function setDestination($x, $y){
        if($this->validatePoint($x, $y)){
            $this->dx = $x;
            $this->dy = $y;
            
            return true;
        }
        
        return false;
    }
    
    /**
     * Get generated the shortest way
     *
     * @return array
     */
    public function getPath(){
        return $this->path;
    }
    
    /**
     * Start searching
     */
    public function search(){
        $this->walk($this->sx, $this->sy);            
    }
    
    public function isWay(){
        return (count($this->path) > 0 ? true : false);
    }
    
    /**
     * Main method
     *
     * @param integer x coordinate of current field
     * @param integer y coordinate of current field
     * @param integer number of footsteps
     * @param array path
     * @param array visited fields
     * @return boolean
     */
    private function walk($x, $y, $footsteps = 0, $path = array(), $visited = array()){
        $path[] = array($x, $y);
        
        if($x == $this->dx && $y == $this->dy){
            if(($this->minFootsteps == null) || ($this->minFootsteps > $footsteps)){
                $this->minFootsteps = $footsteps;
                $this->path = $path;            
            }
            
            return true;
        }
        
        $visited[$x.'x'.$y] = 1;
        $footsteps += 1;
        
        //Próbuj wejść na każde sąsiednie pole (nie na skos)
        //i kontynuuj podróżowanie :]
                
        if(isset($this->map[$y][$x-1])){
            if(($this->map[$y][$x-1] == 1) && !array_key_exists(($x-1).'x'.$y, $visited)){
                $this->walk($x-1, $y, $footsteps, $path, $visited);
            }
        }
        
        if(isset($this->map[$y][$x+1])){
            if(($this->map[$y][$x+1] == 1) && !array_key_exists(($x+1).'x'.$y, $visited)){
                $this->walk($x+1, $y, $footsteps, $path, $visited);
            }
        }
        
        if(isset($this->map[$y-1][$x])){
            if(($this->map[$y-1][$x] == 1) &&  !array_key_exists($x.'x'.($y-1), $visited)){
                $this->walk($x, $y-1, $footsteps, $path, $visited);
            }
        }
        
        if(isset($this->map[$y+1][$x])){
            if(($this->map[$y+1][$x] == 1)  && !array_key_exists($x.'x'.($y+1), $visited)){
                $this->walk($x, $y+1, $footsteps, $path, $visited);
            }
        }
        
        return false;                
    }
    
    private function validatePoint($x, $y){
        if($x > ($this->mapSize[0] - 1) || $y > ($this->mapSize[1] - 1)){
            return false;
        }
        
        
        if($this->map[$y][$x] == 0){
            return false;
        }
        
        return true;
    }    
}
 
//użycie
$map = array(
        array(0, 1, 0),
        array(0,1,0),
        array(0, 1, 1),
);//1 - da się przejść, 0 - nie da się przejść
$o = new Path($map);
$o->setStart(1,1);
$o->setDestination(2,2);
$o->search();
 
$path = $o->getPath();
?>
[PHP] pobierz, plaintext 

Przeprowadziłem też testy porównawcze mojej klasy i klasy bim2. Aby był sens tego porównania (czyli porównanie samego algorytmu porównania) z klasy bim2 wywaliłem możliwość chodzenia na skos (w mojej klasie to nie jest uwzględnione), a z mojej wywaliłem walidację mapy (bo u bim2 nie ma tego, a jest cholernie zasobożerne). Wynik testów wskazał, że moja klasa jest 40 razy wydajniejsza. Pewnie to z tego względu, że (wnioskuję z powieszchownego rzucenia okiem) klasa bim2 ustala ilość koniecznych kroków, które trzeba wykonać dla każdego pola z podanej mapki, a algorytm mojej klasy polega na tym aby wygenerować wszystkie możliwe drogi z punktu do punktu i wybrać najkrótszą.

Może trochę chamsko (wg niektórych?) się podpiąłem pod ten temat, no ale równie dobrze mógłbym nic nie napisać i zostawić to dla siebie, a tak to przynajmniej są podane dwa trochę różne sposoby rozwiązania podobnego/tego samego problemu (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif) (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif) Może komuś się to kiedyś sprzyda.

Ten post edytował -=Peter=- 2.01.2009, 18:51:18