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

[sticker]

oho widzę że ktoś sie tu bawi w pisanie AI w PHP (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

[bim2]

~sticker
Nie (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Po prostu potrzebuję tego do gry. :]

[Babcia@Stefa]

Nieźle, klasa bardzo "huda" i zapewne wydajna.

Niezła robota, mówię tak choć nie testowałem - tylko ten przykład graficzny (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Chyba klasa nie była aż tak trudna jak się wydaje (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

Pozdrawiam, WebNuLL

[bim2]

Jeśli znałeś algorytm to nie (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) A jak go nie znałeś, to dla mnie było ciężko. ;P Na szczęście parę osób pomogło i podało poradniki. Nie wiem czy wydajna, nie testowałem jeszcze.

PS. Nie piszę się chuda? ;P

[Wicko]

Hej, Bartku/Michale! (IMG:http://forum.php.pl/style_emoticons/default/czarodziej.gif)
Ciekawa rzecz, ale.. nie jestem pewny czy to poprawne zachowanie?
(IMG:http://img523.imageshack.us/img523/4154/shot00075qf7.jpg)

[phpion]

Ciekawa rzecz, ale.. nie jestem pewny czy to poprawne zachowanie?

Hmmm, a czy przypadkiem nie jest to właśnie najkrótsza droga z punku Start do punktu Cel?

[AxZx]

ale chyba nie powinna iść po skosie. to zależy pewnie od rodzaju gry.

[phpion]

ale chyba nie powinna iść po skosie. to zależy pewnie od rodzaju gry.

Racja, jest to zapewne uzależnione od zasad gry. Jednak gdyby nie było możliwości pójścia po skosie to nie byłaby to prawdziwa "najkrótsza droga".

[bim2]

Jest to najkrótsza droga. Można przydzielić rangę, że po skosie jest dłużej, ale nie miałem już siły przerabiać. :] Niedługo zamieszczę z możliwością ustalenia drogi po skosie, bo jednak u mnie jest to 2 razy dłuższa droga (IMG:http://forum.php.pl/style_emoticons/default/smile.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)

[ShadowD]

Trochę pokombinowałem i znalazłem błąd a bynajmniej ja tak to rozumiem...

Start:
8*8
Cel:
1*4

I droga skręca w prawo gdzie kończy się i ponownie rozpoczyna na celu. (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)

[bim2]

@wookieb
Błąd w rysowaniu mapki, spójrz na kolejne etapy pod mapką.

@ShadowD
Mi działa normalnie nie licząc tego błędu jaki ma wookieb (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Później poprawie bo narazie nie mam sił. Przygotowałem już działającą wersję w JS (IMG:http://forum.php.pl/style_emoticons/default/haha.gif)

[djstrong]

Hej, Bartku/Michale! (IMG:http://forum.php.pl/style_emoticons/default/czarodziej.gif)
Ciekawa rzecz, ale.. nie jestem pewny czy to poprawne zachowanie?
(IMG:http://img523.imageshack.us/img523/4154/shot00075qf7.jpg)

Nie zagłębiałem się w kod ale nie powinien "numerować" wszystkich pól tylko zatrzymać się gdy znajdzie cel. Może jest tak zrobione, tylko na potrzeby mapki puszczone dalej;)

[bim2]

Jest tak zrobione, ale musi numerować wszystkie kroki aż do celu. Więc jeśli cel będzie na 11 kroku, ponumeruje wszystko do 11 kroku. A co do tego co na mapce widać, nie powinien numerować do końca i mi o dziwo na localhoscie nie numeruje. Nie pamiętam jak jest na serwerze, bo zmieniałem parę rzeczy.

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

[bim2]

Miło, pewnie sam wykorzystam twoją klasę (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Jeśli jest szybsza :] Szkoda że wcześniej nie napisałęś, dzień roboty bym zaoszczędził (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)

[-=Peter=-]

A jednak chyba moja klasa jest z dupy (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif) Przy mapce o rozmiarze 8x8 jest znacznie wydajniejsza, ale przy większych wymiarach moja klasa wymięka (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif) Chyba algorytm jest rzędu wykładniczego ;]

[bim2]

Hmm. I by się zgadzało (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Moja tylko ponumeruje sobie mapkę, a później szuka jednej drogi. To o wiele wydajniejsze niż szukać ileś tam dróg, co przy większej mapce rośnie ekspansyjnie. :]

[bartg]

Imho sprawdzanie każdej trasy przy dobrym algorytmie wydaje się trochę głupi (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) . Jak gdziesz jedziesz to szukasz drogi najkrótszej sprawdzając każdą trasę? ;O