[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

[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

oho widzę że ktoś sie tu bawi w pisanie AI w PHP

~sticker
Nie Po prostu potrzebuję tego do gry. :]

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

Niezła robota, mówię tak choć nie testowałem - tylko ten przykład graficzny

Chyba klasa nie była aż tak trudna jak się wydaje

Pozdrawiam, WebNuLL

Jeśli znałeś algorytm to nie 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

Hej, Bartku/Michale!
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?

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

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

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?

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.

@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 Później poprawie bo narazie nie mam sił. Przygotowałem już działającą wersję w JS

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

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.

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 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 Może komuś się to kiedyś sprzyda.

Miło, pewnie sam wykorzystam twoją klasę Jeśli jest szybsza :] Szkoda że wcześniej nie napisałęś, dzień roboty bym zaoszczędził

A jednak chyba moja klasa jest z dupy Przy mapce o rozmiarze 8x8 jest znacznie wydajniejsza, ale przy większych wymiarach moja klasa wymięka Chyba algorytm jest rzędu wykładniczego ;]

Hmm. I by się zgadzało 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. :]

Imho sprawdzanie każdej trasy przy dobrym algorytmie wydaje się trochę głupi . Jak gdziesz jedziesz to szukasz drogi najkrótszej sprawdzając każdą trasę? ;O

Jeśli ten screen jest z Twojego algorytmu to numeracja jest niepoprawna. Np. nad niebieskim polem z '5' powinna być szóstka, a jest 7.

http://hernass.pl/searchWay/
Screen ze starej wersji skrypciku Już ładnie działa, i rogi wykrywa :]

Drugi post, dlatego żeby każdy widział i w dużym odstępie czasowym.

Przepisałem kod pod javaScript Dałem znacznik php, żeby było kolorowanie. Niestety przykłady nie mam, ale będzie to coś na zasadzie
Mapa jak tablica w PHP oczywiście :]

[PHP] pobierz, plaintext 
<?php
Map = generateMap();
var oSearchWay = new SearchWay();
oSearchWay.find(1,1,12,15,Map);
 
 
/**
/* A* Algorithm - SearchWay by Hernass.pl 
**/
/**
* 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
*/
function SearchWay() {
    var obj = new Object();
    
    obj.number = 0;
    obj.dest = new Array();
    obj.startPos = new Array();
    obj.Map = new Array();
    obj.Way = new Array();
    obj.find = function(start_x, start_y, dest_x, dest_y, map)
    {
        obj.Map = map;
        obj.Way = new Array();
        obj.number = 0;
 
        obj.dest = new Array();
        obj.dest[0] = dest_x; //x
        obj.dest[1] = dest_y; //y
 
        obj.startPos = new Array();
        obj.startPos[0] = new Array();
        obj.startPos[0][0] = start_x; //x
        obj.startPos[0][1] = start_y; //y
        obj.mark(obj.startPos);
        obj.searchReverse(obj.dest);
        return obj.Way;
    };
    obj.searchReverse = function(pos) {
        x = pos[0];
        y = pos[1];
        new_x = new Array();
        new_y = new Array();
        
        new_x[0] = x+1;
        new_y[0] = y;
        
        new_x[1] = x-1;
        new_y[1] = y;
        
        new_x[2] = x;
        new_y[2] = y+1;
        
        new_x[3] = x+1;
        new_y[3] = y+1;
        
        new_x[4] = x-1;
        new_y[4] = y+1;
        
        new_x[5] = x;
        new_y[5] = y-1;
        
        new_x[6] = x+1;
        new_y[6] = y-1;
        
        new_x[7] = x-1;
        new_y[7] = y-1;
        
        for(ii in new_x)
        {
            nx = new_x[ii];
            ny = new_y[ii];
            if(obj.Map[ny]!=undefined && obj.Map[ny][nx]!=undefined && obj.Map[ny][nx]==(obj.Map[y][x]-1) && obj.Map[ny][nx]>-1)
            {
                obj.Way[(obj.Map[y][x]-1)] = new Array();
                obj.Way[(obj.Map[y][x]-1)][0] = nx-x;
                obj.Way[(obj.Map[y][x]-1)][1] = ny-y;
                obj.searchReverse(new Array(nx, ny));
            }
        }
    };
    obj.mark = function(searching)
    {
        
        for(i in searching)
        {
            x = searching[i][0];
            y = searching[i][1];
            if(obj.Map[y]!=undefined && obj.Map[y][x]!=undefined)
            {
                obj.Map[y][x] = obj.number;
            }
            if(obj.dest[0]==x && obj.dest[1]==y)
            {
                return;
            }
        }
        
        nextMark = false;
        new_map = new Array();
        ii_ = 0;
        for(i in searching)
        {
        nextMark = true;
            x = searching[i][0];
            y = searching[i][1];
                        
            new_x = new Array();
            new_y = new Array();
            
            new_x[0] = x+1;
            new_y[0] = y;
            
            new_x[1] = x+1;
            new_y[1] = y+1;
            
            new_x[2] = x+1;
            new_y[2] = y-1;
            
            new_x[3] = x-1;
            new_y[3] = y;
            
            new_x[4] = x-1;
            new_y[4] = y+1;
            
            new_x[5] = x-1;
            new_y[5] = y-1;
                    
            new_x[6] = x;
            new_y[6] = y+1;
            
            new_x[7] = x;
            new_y[7] = y-1;
            for(ii in new_x)
            {
                nx = new_x[ii];
                ny = new_y[ii];
                if((obj.Map[ny]!=undefined && obj.Map[ny][nx]!=undefined) && obj.Map[ny][nx]==-1)
                {
                    new_map[ii_] = new Array();
                    new_map[ii_][0] = nx;
                    new_map[ii_][1] = ny;
                    ii_++;
                }
            }
        }
        obj.number++;
        if(nextMark)
        {
        obj.mark(new_map);
        }
    };
    return obj;
}
/* ********************** */
?>
[PHP] pobierz, plaintext 

nie łatwiej przerobić z c++ na php Algorytm Dijkstry w implementacji kopca?

Dla mnie nie jeśli jest Ci prościej to proszę napisz i zaprezentuj swój kod. Nie lubie ludzi którzy piszą "nie łatwiej by było to i to" żeby pochwalić się swoją wiedzą i nic w tym kierunku nie robić.

Przydało by się do tego ( jeśli istnieje to niech ktoś się podzieli) natywne rozszerzenie do php dodające jakąś kolejkę priorytetową, np kopiec. Dijkstra to jeden z tych nielicznych przypadków kiedy bogactwo struktur danych PHP (np. tablica, tablica czy tablica) nie wystarcza
Przy okazji próby implementacji dowiedziałem się w nieprzyjemny sposób, że likwidowanie, do testów, limitu na czas wykonywania skryptu PHP jest złe. Np. byle literówka może dać tyle komunikatów notice, że syslogd kompletnie zamuli system, a po resecie okaże się, że plik /var/log/user.log ma 5GB

ja bym zrobił A* na kolejce priorytetowej z odpowiednią funkcją przewidującą najkrótszą drogą (min(x,y) w tym przypadku).

@bim2, napisałem o algorytmie Dijkstry, bo jest prostszy w użyciu i w necie masz pełno przykładów, a A* to heura, czyli trochę wyższa szkoła jazdy

No nie wiem.
http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz
lub
tutaj ladnie wytłumaczone i z tego korzystałem:
http://www.gamedev.pl/articles.php?x=view&id=254

Nadal chyba jest coś nie tak.

Podałem:
88
21

I dróżka się podzieliła na dwie .;]

Mówisz o js czy php?

Php js nie sprawdzałem... ;]

Witajcie,

planuję napisać aplikację w PHP służącą do wyszukiwania najkrótszej drogi między dwiema lokacjami. Zastanawia mnie fakt, czy mogę do tego wykorzystać algorytmy typu A* lub Dijkstry. Muszę przyznać, że na tym polu jestem nowicjuszem - być może problem da się rozwiązać zupełnie łatwo i prosto? Proszę o waszą pomoc i ocenę.

Zadanie polega na wyszukaniu drogi, możliwie najkrótszej między START-em a wybraną lokacją (3, 54, 32 itd itd). Ilość lokacji to 64, z czego każda jest oddzielnym polem - nie stanowi 'jednej pełnej mapy', ma po 4 połączenia ("portale") z innymi (na rysunku: zielonkawe kwadraty na obrzeżu pola). Ważne aby algorytm mógł wyszczególnić położenie (w obrębie danego pola), z którego połączenia skorzystał (o ile znalazł drogę do punktu docelowego) np: droga ze startu do lokacji '24'

[Start]->38(Prawy)->[38]->24(Dolny)->[24]



Dziękuję za ewentualną pomoc

Może połącz na początek te 64 pola tak żeby stanowiło to mapkę jednolitą. Połącz je portalami, powiązaniami.

Jeśli chodzi o połączenia to są nimi wspomniane wcześniej 'portale' (jasno zielone). Samej mapy nie da się fizycznie połączyć - miedzy polami można się przenosić jedynie wybierając jeden z portali. Czy możliwe jest opracowanie takiego algorytmu? Jeśli możesz daj mi wskazówkę na jakiej zasadzie 'połączyć' te lokacje?

zbudować graf, który będzie odzwierciedlał połacznia, np.:
[miasto] = połaczenia wychodzące (,)
[1] = 18,38,41
[2] = 51
[3] = 20,38 etc.

i potem zapuścić algorytm dijkstry i po sprawie