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

[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".