Witam, prosze o ocene algorytmu pod wszelkimi punktami.
Narazie jest to wersja testowa. Sam algorytm działa wg. mnie nieźle, jednak muszę ujednolicić system przestrzeni.
Krótka instrukcja:
Żółte pola: Puste
Czerwone: Mur
Niebieskie: Alternatywny wątek poszukiwań
Zielone: Możliwe do przeszukania dla odpowiedniego wątku.
Fioletowe: Wygenerowana ścieżka.


Prezentacja: http://damnedland.pl/astar/class.php

Kody(użycia i algorytmu)
http://damnedland.pl/explorer/index.php?dir=Algorytmy

Super, szczególnie brak opisu do czego ma to służyć ;]

tez sie nad tym zastanawialem do czego to ma słuzyc ale pomyslalem ze jestem za glupi na to wiec nie pytalem;)

kwadraciki ladne:)

Algorytm A* służy do znalezienia drogi, gdy mamy całą mapę. W tym algorytmie klikasz "Select start's field" klikasz na kwadracik klikasz na "Select finish's field" i klikasz na inny kwadracik i pokazuje się ścieżka. Nie patrzyłem na kod, ale działa dobrze

@Fifi209: Skoro do oceny poddaje się implementację algorytmu A*, to o czym innym niż o najkrótszej ścieżce pomiędzy dwoma punktami w grafie może być mowa?

Co do kodu to raczej nie ma co samego algorytmu oceniać bo to nie Twoje dzieło. Implementacja natomiast nie powiedziałbym by była zbyt "cieakwa".
1. W przypadku błędnych danych (np. podawanie nieistniejących współrzędnych) powinny być rzucane wyjątki.
2. Sam graf i jego wierzchołki powinny być raczej reprezentowane przez osobne obiekty - uprościłoby to i podniosło czytelność kodu.
3. Sam mechanizm przeszukujący powinien raczej zwrócić jedynie kolekcję wierzchołków z najkrótszą drogą, a nie modyfikować jakąś mapę.
4. Całość powinna być kompletnie niezależna od sposobu wykorzystania, a w tej chwili z tego co widzę tak nie jest.
5. Fajnie by było jakby sama implementacja A* była jedynie jednym z możliwych sposobów wyszukania najkrótszej ścieżki - w końcu A* to nie jedyny algorytm rozwiązujący ten problem. Innymi słowy by całość umożliwiała wyszukanie również innymi metodami:

[PHP] pobierz, plaintext 
$graph = new Graph().
// dodanie węzłów do grafu
 
$startNode = $graph->getNode(123);
$endNode = $graph->getNode(321);
 
$impl = new AStar();
// jakieś tam przygotowanie obiektu
$path = $graph->findShortestRoute($startNode, $endNode, $impl); // wyszuka przy pomocy A*
 
 
$impl= new DijkstrasAlgorithm();
// jakieś tam przygotowanie obiektu
$path = $graph->findShortestRoute($startNode, $endNode, $impl); // wyszuka przy pomocy algorytmu Dijkstry
[PHP] pobierz, plaintext 

Modyfikacje mapy mogę wyłączyć.

[PHP] pobierz, plaintext 
$astar -> enableAnimations(0); 
[PHP] pobierz, plaintext 

Scieżke też zwraca, lecz tutaj jej nie potrzebuje. Ścieżka zwracana jest w formie tablicy.
możemy to sprawdzić np

[PHP] pobierz, plaintext 
$route = $astar -> getRoute();
print_r($route);
[PHP] pobierz, plaintext 

Algorytm Dikstra rozważałem lecz on przeszukuje większy obszar co jest automatycznie wolniejsze(I wykorzystuje się go gdy nie znamy położenia celu, wtedy np zbieracz może przeszukać mapę żeby zebrać surowiec).

A tutaj potrzebuje wyszukać drogę(tylko 1 postać sięporusza na mapie 2d).

Może to nie ja wymyśliłem algorytm, ale nieźle musiałem się nagłowić aby on działał. Jest to narazie wersja testowa, cały czas go dopracowuje, bo chce go przepisać do JS.
Podczas pisania nie spojżałem na inny kod, korzystałem głównie z: http://en.wikipedia.org/wiki/A*_search_algorithm

Co do tych wyjątkow to się zastanowie bo zawsze zwracałem false w przypadku niepowodzenia, ale wyjątki mogę zastosować.

A co do Przestrzeni to właśnie jestem w trakcie pisania klasy, w ten sposób łatwo mogę zmienić sposób przekazywania mapy do algorytmu.

Crozin, być może, że kod przepiszę(pozmieniam) na nowo, żeby go ujednolicić, ale od czegoś trzeba zacząć. I właśnie dlatego umieściłem go tutaj, żebyście mi pomogli i doradzili.
Crozin możesz mnie nakierować na jakieś informacje dokładniejsze o tym:

Algorytm ten podałem jako jakikolwiek inny pracujący na grafie. A by taka praca była wygodna potrzebna jest odseparowanie struktury grafu od algorytmu i jego konkretnego wykorzystania.
W przypadku niepowodzenia można co najwyżej zwrócić null. Wartość logiczna true/false jest już zarezerwowana dla funkcji mających zwrócić jedną z tych dwóch wartości. Oczywiście przez niepowodzenie nie mamy tutaj na myśli błędu - wtedy jedynym dopuszczalnym rozwiązaniem jest wyjątek.

W chwili obecnej wykorzystujesz tablice jako struktury danych. Jest to złe ponieważ jest to zbyt dynamiczna struktura danych. Nie ma ona określonych konkretnych elementów, a co gorsza powoduje odseparowanie struktury danych od konkretnych metod operacji na nich - co jest głównym założeniem i zaletą OOP. Jedyny ich plus w PHP to to, że jednak w wielu przypadkach szybsze niż rozwiązania obiektowe, ponieważ są wbudowane w samo PHP.

Crozin:
Mam do ciebie jeszcze jedno pytanie.
Z twoich postów wywnioskowałem, że lepiej dla mnie zrobić algorytm odseparowany od grafu. I doszedłem do wniosku, że jest to rozwiązanie dobre, bo w zależności od sytuacji będe mógł wykorzystać odpowiedni algorytm.

Ty w przykładzie podałeś indeksowanie pól/wierzchołków grafu za pomocą jednej zmienne, dla mnie nie jest to wygodne, i trudniejsze do edycji. Ale nie o to chodzi.

Czyli np musze napisać jakiś separator algorytmu od grafu.

I pomyślałem, że może to tak działać:
1)Algorytm korzysta z klasy Space, która z kolei wykonuje wszystkie operacje na klasach poszczególnych grafów.

Klasa Space jest tylko jedna.
Klasy grafów implementują interfejs który narzuca im odpowiednie metody z ktorych będzie korzystała klasa Space jako separator.


2)Algorytm wykonuje operacje bezpośrednio korzystając z dołączonej do klasy algorytmu klasy w taki sposób:

[PHP] pobierz, plaintext 
public function construct(GraphInterface $graph,....)
{
$this -> graph = $graph;
}
[PHP] pobierz, plaintext 

Jednak rozwiązanie pierwsze wydaje się lepsze, bo gdy zmienie algorytm to zmieniam tylko klasę Space, i tak samo gdy zmienię obsługę grafu.

Które rozwiązanie ty byś mi pocił lub ktoś inny, jestem otwarty na propozycje.
Chyba, że macie coś ciekawszego.

Pozdrawiam Daniel

Zacznijmy od tego czym jest graf? Jest zbiorem wierzchołków połączonych ze sobą krawędziami. Każdy z tych elementów może mieć swoje indywidualne właściwości, a więc i każdy z nich powinien być reprezentowany przez osobną klasę, która powinna implementować jakiś podstawowy interfejs.

Tutaj musisz się zastanowić czy chcesz robić kod ogólny do współpracy z grafami jako takimi, czy specyficzny dla Twojego przypadku jakim jest "kratkowa mapa". Taka mapa może co prawda być dosyć łatwo przedstawiona jako graf na dwa sposoby:
1. Każda jedna kratka to wierzchołek połączony z innymi krawędzią długości 1 lub 1.5 dla ukośnych sąsiadów.
2. Za wierzchołki robią dwie skrajne kratki połączone linią prostą krawędzią o odpowiedniej długości (przykładowo punkty 2x49 i 49x49 mogą być połączone krawędzią długości 48).

Żeby zobaczyć jak można reprezentować graf w pamięci i jak brać się za operowanie na nim możesz podejrzeć sobie źródła biblioteki JGraphT.

Czli jak?
1)Każda "kratka" powinna posiadać swój obiekt osobny obiekt dziedziczony pod XXXInterface?

[PHP] pobierz, plaintext 
Class P0_0 implements XXXInterface
Class P0_1 implements XXXInterface
Class P3_0 implements XXXInterface
Class Px_y implements XXXInterface
[PHP] pobierz, plaintext 

2) Czy może powinien być jeden obiekt posiadający jakiś interface

[PHP] pobierz, plaintext 
Class Standard Node Implements NodeInterface
{
//Koordynaty
private $x;
private $y;
//Wysokośc punktu 
private $height
//Typ pola(woda, trawa, itp)
private $type;
//Obrazek reprezentujący(wyświetlany) pole grafu. 
private $image;
 
public function __construct($x, $y, $height, $type, $image)
{
if (is_int($x))
$this -> x = $x;
else
throw new Exception('X Coords isn't int type!');
 
....
}
 
public function getCoords()
{
return array('x'=>$this -> x, 'y'=> $this -> y);
}
[PHP] pobierz, plaintext 

Jeśli to 1 rozwiązanie to zdecydowanie mnie nie przekonuje bo zje to więcej pamięci niż moja aplikacja, chyba, że da się to zoptymalizować. hehehe


Jeśli to drugie rozumowanie to mam kilka pytań
To drugie rozwiązanie wykorzystuje kilka znanych mi aplikacji, modułów obiektowych np: PDO
Dane o polach przechowywać np w pliku z grafem.

Wszystkie obiekty tworzę podczas wywołania obiektu grafu, czy może obiekty tworzę podczas wywołania danego punktu($graph -> getNode(2,3); aby nie zaśmiecać pamięci.

Obiekty tworzył bym na podstawie pliku z grafem np:

[XML] pobierz, plaintext 
<node x="0" y="0">
<height>25</height>
<type>earth</type>
<image>233.jpg</image>
</node>
 
<node x="x" y="y">
<height>...</height>
<type>water</type>
<image>...</image>
</node>
[XML] pobierz, plaintext 

Po pierwsze to krótka powtórka z tego czym jest obiekt, a czym klasa. To pierwsze to konkretna instancja danej klasy, tworzymy ich dziesiątki. To drugie to jedynie szablon do tworzenia tych obiektów - występuje raz. Tak więc nie ten pierwszy potworek jaki pokazałeś, a drugi.
Po drugie musisz wczytać cały* graf do pamięci - jak niby później miałbyś na nim operować nie mając danych w pamięci?

Prawdę powiedziawszy słowa nie rozumiem z tego.

* technicznie dałoby się w ramach potrzeb wczytywać fragmenty grafu, ale to strasznie skomplikowałoby kod, poza tym tutaj na 99,9% nie ma takiej potrzeby.

PS. Od PHP 5.4 wykorzystanie obiektów powinno również znacznie ograniczyć zużycie pamięci, a czas wykonywania powinien zrównać się z wersją z wykorzystaniem tablic.

Dzięki, jak poprawie, dodam komentarze do phpDocumentator to wstawie do oceny ponownie