[Algorytm]A* Algorytm Opcje

[daniel1302]

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

[daniel1302]

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:

2. Sam graf i jego wierzchołki powinny być raczej reprezentowane przez osobne obiekty - uprościłoby to i podniosło czytelność kodu.

Ten post edytował daniel1302 24.12.2011, 16:47:28