Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
Nowa wersja
Both sides next revision
|
pl:prolog:prolog_lab:listy1 [2014/03/17 15:24] msl [Listy różnicowe] |
pl:prolog:prolog_lab:listy1 [2017/07/17 10:08] 127.0.0.1 edycja zewnętrzna |
| |
===== Dla Zainteresowanych ===== | ===== Dla Zainteresowanych ===== |
| |
| ==== Minecraft ==== |
| Zastanówmy się nad próbą implementacji prostej gry typu [[http://pl.wikipedia.org/wiki/Minecraft|Minecraft]]. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych [[http://pl.wikipedia.org/wiki/Woksel|wokselami]]. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program {{:pl:prolog:prolog_lab:cuboid.pl|}} (wymagane XPCE) i przeanalizować jego działanie. |
| |
| <code prolog> |
| ?- cuboid(2,2,2). |
| </code> |
| |
| Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}: |
| |
| <code prolog> |
| ?- sm. |
| </code> |
| |
| Zadania: |
| - Przerobić predykat ''cuboid'' tak, żeby można było sprecyzować jego pozycję w przestrzeni |
| - Napisać predykat ''cuboids'', który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku |
| - Przy pomocy predykatu ''cuboids'' należy zamodelować [[http://i.ytimg.com/vi/u1bX8kEy0pg/maxresdefault.jpg?|złożony obiekt ze świata Minecraft]] |
| - Bazując na kodzie z ''animation.pl'' należy wprawić krowę w ruch sinusoidalny, imitujący [[https://www.youtube.com/watch?v=QH2-TGUlwu4|kota z filmu]] |
| - [Dla odważnych] dodać do animacji [[https://archive.org/details/nyannyannyan|dźwięk]] podobny do tego z [[https://www.youtube.com/watch?v=QH2-TGUlwu4|filmu]] |
| |
| Pytania: |
| - Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się [[http://et1337.com/2015/02/18/the-poor-mans-voxel-engine/#|link]] |
| - Czy możliwe jest zrobienie w podobny sposób imitacji poniższego [[http://goo.gl/YroZm|filmu]]? |
| |
| |
==== Efektywność odwracania list ==== | ==== Efektywność odwracania list ==== |
[a,b,c|End],End. | [a,b,c|End],End. |
</code> | </code> |
Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Kążdą listę ''[L]'' można przedstawić jako parę ''[L|End]'',''End''. Kiedy ''End'' jest zmienną bez przypisanej wartości, listę o takiej postaci nazywam otwartą (ang. //open list//). Z proceduralnego punktu widzenia zmienna ''End'' jest "wskaźnikiem" na koniec listy ''L''; unifikując z ''End'' inną listę, wstawiamy jej elementy na koniec listy ''L''. Poniżej przedstawiony jest predykat ''sklej_roznicowo/3'', który wykonuje tę operację (uwaga: operator '-' służy tutaj jedynie grupowaniu argumentów; parę ''[L|End]'', ''End'' zapiszemy jako ''[L|End] - End.'') | Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Każdą listę ''[L]'' można przedstawić jako parę ''[L|End]'',''End''. Kiedy ''End'' jest zmienną bez przypisanej wartości, listę o takiej postaci nazywamy otwartą (ang. //open list//). Z proceduralnego punktu widzenia zmienna ''End'' jest "wskaźnikiem" na koniec listy ''L''; unifikując z ''End'' inną listę, wstawiamy jej elementy na koniec listy ''L''. Poniżej przedstawiony jest predykat ''sklej_roznicowo/3'', który wykonuje tę operację (uwaga: operator '''-''' służy tutaj jedynie grupowaniu argumentów; parę ''[L|End]'', ''End'' zapiszemy jako ''[L|End] - End''). |
<code prolog> | <code prolog> |
sklej_roznicowo(L - End, L2, L) :- | sklej_roznicowo(L - End, End, L). |
End = L2. | |
</code> | </code> |
Poniżej przykład wywołania predykatu: | Poniżej przykład wywołania predykatu: |
<code prolog> | <code prolog> |
?:- sklej_roznicowo([a,b,c|End]-End, [d,e,f|End2]-End2, Wynik). | ?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f],Wynik). |
End = [d, e, f|End2], | End = [d, e, f], |
Wynik = [a, b, c, d, e, f|End2]-End2. | Wynik = [a, b, c, d, e, f]. |
</code> | </code> |
| |
Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; ''sklej_roznicowe'' nigdy nie wchodzi w rekurencję, wykonuje jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. | Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; ''sklej_roznicowo'' nigdy nie wchodzi w rekurencję, wykonuje jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. |
| |
Idąc dalej, jeżeli ustalimy, że argumentami ''sklej_roznicowo'' mogą być jedynie listy różnicowe w postaci par ''L - End'', możemy go przepisać do poniższej, interesującej postaci: | Idąc dalej, jeżeli ustalimy, że argumentami ''sklej_roznicowo'' mogą być jedynie listy różnicowe w postaci par ''L - End'', możemy go przepisać do poniższej, interesującej postaci: |
| |
Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy --- dzięki temu lista wynikowa ''Wynik'' w parze z ''End2'' stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy. | Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy --- dzięki temu lista wynikowa ''Wynik'' w parze z ''End2'' stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy. |
| |
| == Do przećwiczenia: == |
| |
| * przetestować predykat ''sklej_roznicowo/3''; |
| * spróbować zastąpić predykat ''sklej/3'' predykatem ''sklej_roznicowo/3'' w predykatach zaimplementowanych na zajęciach; |
| * zastanowić się, jakie przewagi ma ''sklej/3'' nad ''sklej_roznicowo/3''; |
| * przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych. |
| |
== Do poczytania: == | == Do poczytania: == |
* [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]]. | * [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]]. |
| |
==Do przećwiczenia: == | |
| |
* przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych; | |
* zastanowić się, jakie przewagi ma ''sklej/3'' nad ''sklej_roznicowo/3''. | |
| |
--- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58// | --- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58// |