78 lines
3.6 KiB
Markdown
78 lines
3.6 KiB
Markdown
|
# Raport 2
|
||
|
|
|
||
|
|
Algorytm A* znajduje się w pliku:
|
||
|
|
```sh
|
||
|
|
waiter.py
|
||
|
|
```
|
||
|
|
jako funkcja
|
||
|
|
```sh
|
||
|
|
findPath(self, goal)
|
||
|
|
```
|
||
|
|
Rozpoczyna się stworzeniem pustych list i określeniem wierzchołka startowego i końcowego.
|
||
|
|
Dla startowego wierzchołka określany jest rodzic: *None*
|
||
|
|
|
||
|
|
## Pętla główna algorytmu
|
||
|
|
Główna pętla będzie trwać do momentu gdy *openList* będzie pusta.
|
||
|
|
Na początek *openList* jest sortowana, następnie usuwany jest z niej pierwszy wierzchołek i dodawany jest do *closedList*.
|
||
|
|
|
||
|
|
Następnym krokiem jest dodanie do tabeli *children* wierzchołki sąsiednie - sprawdzając czy takie istnieją tj. czy ich pozycja nie wychodzi poza zakres.
|
||
|
|
|
||
|
|
### Wyszukiwanie następnika
|
||
|
|
Wyszukiwanie następnika polega na znalezieniu następnego wierzchołka do jakiego powinien pójść agent. Zawarte jest ono w pętli:
|
||
|
|
```sh
|
||
|
|
for child in children:
|
||
|
|
```
|
||
|
|
Na początku sprawdzamy czy danego "dziecka" nie ma w *closedList* tzn. wykluczamy możliwość cofnięcia się agenta po wierzchołkach, które już przeszliśmy.
|
||
|
|
Potem aktualizowane są parametry wierzchołka:
|
||
|
|
- ustalamy rodzica jako *currentNode*
|
||
|
|
- modyfikujemy *startCost* dodając jedynkę do *startCost* obecnego wierzchołka
|
||
|
|
- ustalamy heurystykę jako suma długości przyprostokątnych
|
||
|
|
- obliczamy *totalCost* dodając do siebie *startCost* i *heuristic*
|
||
|
|
|
||
|
|
Na koniec sprawdzamy jeszcze czy danego dziecka nie ma już w *openList*, a jeśli nie, to dodajemy go do *openList*.
|
||
|
|
|
||
|
|
### Zwracanie ścieżki
|
||
|
|
Zwracanie ścieżki odbywa się gdy *currentNode* jest taki sam jak końcowy wierzchołek.
|
||
|
|
Tworzymy wtedy ścieżkę cofając się od końcowego wierzchołka do wierzchołka, którego rodzic jest równy: *None*
|
||
|
|
|
||
|
|
# Translacja ścieżki
|
||
|
|
Znajduje się w pliku
|
||
|
|
```sh
|
||
|
|
waiter.py
|
||
|
|
```
|
||
|
|
jako funkcja
|
||
|
|
```sh
|
||
|
|
translatePath(self, path):
|
||
|
|
```
|
||
|
|
Przyjmuje jako argument ściężkę zwracaną przez algorytm A*.
|
||
|
|
Funckja ta sprawdza każdy wierzchołek ścieżki i porównując z obecną pozycją kelnera i kierunkiem w jaki jest odwrócony "tłumaczy" go na odpowiedni ciąg znaków, gdzie:
|
||
|
|
- F - oznacza ruch do przodu
|
||
|
|
- R - obrót w prawo
|
||
|
|
- L - obrót w lewo
|
||
|
|
|
||
|
|
Następnie zwraca ciąg *output*
|
||
|
|
|
||
|
|
[//]: # (These are reference links used in the body of this note and get stripped out when the markdown processor does its job. There is no need to format nicely because it shouldn't be seen. Thanks SO - http://stackoverflow.com/questions/4823468/store-comments-in-markdown-syntax)
|
||
|
|
|
||
|
|
|
||
|
|
[dill]: <https://github.com/joemccann/dillinger>
|
||
|
|
[git-repo-url]: <https://github.com/joemccann/dillinger.git>
|
||
|
|
[john gruber]: <http://daringfireball.net>
|
||
|
|
[df1]: <http://daringfireball.net/projects/markdown/>
|
||
|
|
[markdown-it]: <https://github.com/markdown-it/markdown-it>
|
||
|
|
[Ace Editor]: <http://ace.ajax.org>
|
||
|
|
[node.js]: <http://nodejs.org>
|
||
|
|
[Twitter Bootstrap]: <http://twitter.github.com/bootstrap/>
|
||
|
|
[jQuery]: <http://jquery.com>
|
||
|
|
[@tjholowaychuk]: <http://twitter.com/tjholowaychuk>
|
||
|
|
[express]: <http://expressjs.com>
|
||
|
|
[AngularJS]: <http://angularjs.org>
|
||
|
|
[Gulp]: <http://gulpjs.com>
|
||
|
|
|
||
|
|
[PlDb]: <https://github.com/joemccann/dillinger/tree/master/plugins/dropbox/README.md>
|
||
|
|
[PlGh]: <https://github.com/joemccann/dillinger/tree/master/plugins/github/README.md>
|
||
|
|
[PlGd]: <https://github.com/joemccann/dillinger/tree/master/plugins/googledrive/README.md>
|
||
|
|
[PlOd]: <https://github.com/joemccann/dillinger/tree/master/plugins/onedrive/README.md>
|
||
|
|
[PlMe]: <https://github.com/joemccann/dillinger/tree/master/plugins/medium/README.md>
|
||
|
|
[PlGa]: <https://github.com/RahulHP/dillinger/blob/master/plugins/googleanalytics/README.md>
|