Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> [class] Znajdź najkrótszą drogę, algorytm A*
bim2
post
Post #1





Grupa: Zarejestrowani
Postów: 1 873
Pomógł: 152
Dołączył: 9.04.2006
Skąd: Berlin

Ostrzeżenie: (0%)
-----


  1. <?php
  2. /**
  3.  * License
  4.  *
  5.  * This library is free software; you can redistribute it and/or
  6.  * modify it under the terms of the GNU Lesser General Public
  7.  * License as published by the Free Software Foundation; either
  8.  * version 2.1 of the License, or (at your option) any later version.
  9.  *
  10.  * This library is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  * Lesser General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU Lesser General Public
  16.  * License along with this library; if not, write to the Free Software
  17.  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18.  **/
  19. /**
  20.  * @author Hernas Service <kontakt@hernass.pl>
  21.  * @copyright 2008 HernasS.pl.
  22.  * @version 2.0
  23.  */
  24. class Way {
  25.    /* Startowy punkt na osi X */
  26.    private $start_x;
  27.    
  28.    /* Startowy punkt na osi Y */
  29.    private $start_y;
  30.    
  31.    /* Mapa podana przez użytkownika */
  32.    private $aMap;
  33.    
  34.    /* Mapa wygenerowana na potrzeby skryptu */
  35.    private $aMap_;
  36.    
  37.    /* Punkt przeznaczenia na osi X */
  38.    private $destination_x;
  39.    
  40.    /* Punkt przeznaczenia na osi Y */
  41.    private $destination_y;
  42.    
  43.    /* Tablica przeszukiwania dróg */
  44.    private $aWay = array();
  45.    
  46.    /* Tablica wyjściowa z wybraną drogą */
  47.    private $aWays = array();
  48.    
  49.    /* Numer kolejnego kroku przeszukiwania */
  50.    private $fillNumber = 0;
  51.    
  52.    /* Konstruktor klasy
  53.      * @param integer $x - Startowy punkt na osi X
  54.      * @param integer $y - Startowy punkt na osi Y
  55.      * @param array $aMap - Mapa podana przez użytkownika
  56.     */
  57.    public function __construct($x, $y, $aMap)
  58.    {
  59.        $this->aMap = $aMap;
  60.        
  61.        $this->aWays[] = array($x, $y);
  62.        $this->start_x = $x;
  63.        $this->start_y = $y;
  64.        
  65.        $this->regenerateMap();
  66.        
  67.    }
  68.    /* Szuka drogi
  69.      * @param integer $x - Punkt przeznaczenia na osi X
  70.      * @param integer $y - Punkt przeznaczenia na osi Y
  71.     */
  72.    public function findWay($x, $y)
  73.    {    
  74.        $this->destination_x = $x;
  75.        $this->destination_y = $y;    
  76.        
  77.        $this->startFinding();
  78.        $this->mirrorFinding($x, $y);
  79.        return $this->aWay;
  80.    }
  81.    /* Znaczy kolejne kroki na mapie */
  82.    private function startFinding()
  83.    {
  84.        foreach($this->aWays AS $v)
  85.        {
  86.            list($x, $y) = $v;
  87.            $this->aMap_[$y][$x] = $this->fillNumber;
  88.            $new_x[] = $x+1;
  89.            $new_y[] = $y;
  90.            
  91.            $new_x[] = $x+1;
  92.            $new_y[] = $y+1;
  93.            
  94.            $new_x[] = $x+1;
  95.            $new_y[] = $y-1;
  96.            
  97.            $new_x[] = $x-1;
  98.            $new_y[] = $y;
  99.            
  100.            $new_x[] = $x-1;
  101.            $new_y[] = $y+1;
  102.            
  103.            $new_x[] = $x-1;
  104.            $new_y[] = $y-1;
  105.                    
  106.            $new_x[] = $x;
  107.            $new_y[] = $y+1;
  108.            
  109.            $new_x[] = $x;
  110.            $new_y[] = $y-1;
  111.            $paths = array();
  112.            foreach($new_x AS $i => $v)
  113.            {
  114.                if(isset($this->aMap_[$new_y[$i]][$v]) AND $this->aMap_[$new_y[$i]][$v]==-1)
  115.                {
  116.                    if($v==$this->destination_y AND $new_y[$i]==$this->destination_x)
  117.                    {
  118.                        $paths[] = array($v, $new_y[$i]);
  119.                        break;
  120.                    }
  121.                    $paths[] = array($v, $new_y[$i]);
  122.                }
  123.            }
  124.        }
  125.        
  126.        $this->fillNumber++;
  127.    if(isset($paths))
  128.    {
  129.        $this->aWays = $paths;
  130.        $this->startFinding();
  131.    }
  132.        
  133.    }
  134.    /* Szuka drogi od końca po kolejnych krokach
  135.      * @param integer $x - Punkt kolejnego kroku na osi X
  136.      * @param integer $y - Punkt kolejnego kroku na osi Y
  137.     */
  138.    private function mirrorFinding($x, $y)
  139.    {
  140.        $new_x[] = $x+1;
  141.        $new_y[] = $y;
  142.        
  143.        $new_x[] = $x+1;
  144.        $new_y[] = $y+1;
  145.        
  146.        $new_x[] = $x+1;
  147.        $new_y[] = $y-1;
  148.        
  149.        $new_x[] = $x-1;
  150.        $new_y[] = $y;
  151.        
  152.        $new_x[] = $x-1;
  153.        $new_y[] = $y+1;
  154.        
  155.        $new_x[] = $x-1;
  156.        $new_y[] = $y-1;
  157.                
  158.        $new_x[] = $x;
  159.        $new_y[] = $y+1;
  160.        
  161.        $new_x[] = $x;
  162.        $new_y[] = $y-1;
  163.        foreach($new_x AS $i => $v)
  164.        {
  165.            if(isset($this->aMap_[$new_y[$i]][$v]) AND $this->aMap_[$new_y[$i]][$v]==($this->aMap_[$y][$x]-1))
  166.            {
  167.                $this->aWay[] = array($new_y[$i], $v);
  168.                $this->mirrorFinding($v, $new_y[$i]);
  169.                break;
  170.            }
  171.        }
  172.    }
  173.    /* Generuję mapę na potrzeby skryptu    */
  174.    private function regenerateMap()
  175.    {
  176.        foreach($this->aMap AS $y => $v_)
  177.        {
  178.            foreach($v_ AS $x => $v)
  179.            {
  180.                if($this->start_x == $x AND $this->start_y == $y)
  181.                {
  182.                    $this->aMap_[$y][$x] = 0;
  183.                } elseif($v==1) {
  184.                    $this->aMap_[$y][$x] = -2;
  185.                } elseif($v==0) {
  186.                    $this->aMap_[$y][$x] = -1;
  187.                } else {
  188.                    $this->aMap_[$y][$x] = -2;
  189.                }
  190.            }            
  191.        }
  192.    }
  193.    
  194.    
  195. }
  196. ?>


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

  1. <?php
  2. $aMap = array(
  3. array(1,0,0,0,1,0,0,0),
  4. array(1,0,1,1,1,1,0,0),
  5. array(1,0,1,0,0,1,0,1),
  6. array(0,0,0,0,0,0,0,1),
  7. array(0,0,0,1,1,1,1,1),
  8. array(0,1,0,0,0,0,0,0),
  9. array(1,1,0,0,0,1,0,0),
  10. array(1,1,0,1,1,1,0,0),
  11. ); // 0 -można chodzić
  12. $oWay = new Way(2, 7, $aMap); //X i Y liczone od 0 (jak klucz arraya)
  13. print_r($oWay->findWay(7, 7));
  14. ?>


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)
Go to the top of the page
+Quote Post
 
Start new topic
Odpowiedzi
AxZx
post
Post #2





Grupa: Zarejestrowani
Postów: 1 385
Pomógł: 55
Dołączył: 1.03.2005
Skąd: śląsk

Ostrzeżenie: (0%)
-----


ale chyba nie powinna iść po skosie. to zależy pewnie od rodzaju gry.
Go to the top of the page
+Quote Post
phpion
post
Post #3





Grupa: Moderatorzy
Postów: 6 072
Pomógł: 861
Dołączył: 10.12.2003
Skąd: Dąbrowa Górnicza




Cytat(AxZx @ 19.11.2008, 21:01:19 ) *
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".
Go to the top of the page
+Quote Post

Posty w temacie
- bim2   [class] Znajdź najkrótszą drogę   16.11.2008, 22:28:55
- - sticker   oho widzę że ktoś sie tu bawi w pisanie AI w PHP   17.11.2008, 14:47:59
- - bim2   ~sticker Nie Po prostu potrzebuję tego do gry. :...   17.11.2008, 15:15:00
- - Babcia@Stefa   Nieźle, klasa bardzo "huda" i zapewne wy...   17.11.2008, 20:36:45
- - bim2   Jeśli znałeś algorytm to nie A jak go nie znałeś,...   18.11.2008, 07:44:39
- - Wicko   Hej, Bartku/Michale! Ciekawa rzecz, ale.. ni...   19.11.2008, 18:26:33
|- - phpion   Cytat(Wicko @ 19.11.2008, 20:26:33 ) ...   19.11.2008, 18:53:50
|- - djstrong   Cytat(Wicko @ 19.11.2008, 18:26:33 ) ...   1.01.2009, 12:55:32
- - AxZx   ale chyba nie powinna iść po skosie. to zależy pew...   19.11.2008, 19:01:19
|- - phpion   Cytat(AxZx @ 19.11.2008, 21:01:19 ) a...   19.11.2008, 19:05:58
- - bim2   Jest to najkrótsza droga. Można przydzielić rangę,...   19.11.2008, 20:48:16
- - wookieb   Sry za offtop ale... Dla startowego elementu 2,1 i...   3.12.2008, 16:43:53
- - ShadowD   Trochę pokombinowałem i znalazłem błąd a bynajmnie...   3.12.2008, 20:17:04
- - bim2   @wookieb Błąd w rysowaniu mapki, spójrz na kolejne...   8.12.2008, 17:15:47
- - bim2   Jest tak zrobione, ale musi numerować wszystkie kr...   1.01.2009, 17:54:19
|- - djstrong   Cytat(bim2 @ 1.01.2009, 17:54:19 ) Je...   10.01.2009, 15:21:14
- - -=Peter=-   Zainspirowany tym tematem, nie patrząc na kod któr...   2.01.2009, 18:50:13
- - bim2   Miło, pewnie sam wykorzystam twoją klasę Jeśli je...   2.01.2009, 20:22:07
- - -=Peter=-   A jednak chyba moja klasa jest z dupy Przy mapce ...   3.01.2009, 00:09:02
- - bim2   Hmm. I by się zgadzało Moja tylko ponumeruje sobi...   3.01.2009, 00:33:04
- - bartg   Imho sprawdzanie każdej trasy przy dobrym algorytm...   7.01.2009, 15:16:28
- - bim2   http://hernass.pl/searchWay/ Screen ze starej wers...   4.02.2009, 13:40:42
- - rzymek01   nie łatwiej przerobić z c++ na php Algorytm Dijkst...   4.02.2009, 16:21:53
|- - djstrong   Cytat(rzymek01 @ 4.02.2009, 16:21:53 ...   5.02.2009, 15:13:14
- - bim2   Dla mnie nie jeśli jest Ci prościej to proszę nap...   4.02.2009, 20:03:13
- - ucho   Przydało by się do tego ( jeśli istnieje to niech ...   4.02.2009, 20:31:26
- - rzymek01   @bim2, napisałem o algorytmie Dijkstry, bo jest pr...   5.02.2009, 18:49:56
- - bim2   No nie wiem. http://pl.wikipedia.org/wiki/Przeszuk...   5.02.2009, 19:27:15
- - ShadowD   Nadal chyba jest coś nie tak. Podałem: 88 21 I d...   5.02.2009, 21:36:00
- - bim2   Mówisz o js czy php?   5.02.2009, 23:49:12
- - ShadowD   Php js nie sprawdzałem... ;]   6.02.2009, 02:08:21
- - krriv   Witajcie, planuję napisać aplikacj...   20.06.2009, 09:22:58
- - bim2   Może połącz na początek te 64 pola tak żeby stanow...   21.06.2009, 19:28:18
- - krriv   Jeśli chodzi o połączenia to są nimi wspomniane wc...   22.06.2009, 11:47:42
- - rzymek01   zbudować graf, który będzie odzwierciedlał połaczn...   22.06.2009, 15:17:43


Reply to this topicStart new topic
2 Użytkowników czyta ten temat (2 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Aktualny czas: 15.10.2025 - 18:15