===== Szukanie ścieżek =====

==== 1. Algorytmy poszukiwania ścieżek ====

  * **Ślepe** (Uninformed) - wiedzą tylko o rozwiązaniu (gdy trafi to wie, że trafił)
    * Wszerz (BFS)
    * Strategia jednolitego kosztu (Uniform cost search) = BFS jeśli identyczne wagi
    * W głąb (DFS)
    * Algorytm Dijkstry
    * Iteracyjne pogłębianie (Iterative deepening)
    * Dwukierunkowy (Bidirectional search)
  * **Heurystyczne** (Informed) - dodatkowo specyficzna wiedza o konkretnym problemie
    * Zachłanny (Greedy Best-First search)
    * A∗
    * RBFS (Recursive Best-First search)
    * SMA∗ (Simplified Memory-bounded A∗)

//Dla chcących wiedzieć więcej:// [[https://artint.info/2e/html/ArtInt2e.Ch3.html|Chapter 3: Searching for Solutions]]

==== 2. Mapa a graf przeszukiwania ====

**Mapa** obszaru i **graf** przeszukiwania są **niezależne**!
  * Algorytmy poszukiwania najkrótszej ścieżki bazują na grafie, który jest tylko zbiorem wierzchołków i krawędzi (z ew. wagami) -- samodzielnie musimy to przetłumaczyć na rzeczywisty ruch (pokonanie drzwi, przejście na sąsiedni kafelek, cokolwiek innego)
  * Graf zbudowany jak mapa jest łatwiejszy w obsłudze, ale ... \\ ... bardziej złożony dla algorytmów przeszukiwania. \\ Porównaj różne grafy (dla tej samej mapy) przedstawione poniżej: \\ {{path_graph_01.jpg?direct&400|}} \\ {{path_graph_02.jpg?direct&400|}} \\ {{path_graph_03.jpg?direct&400|}}
  * __Ważna decyzja projektowa__ specyficzna dla konkretnego problemu!

//Dla chcących wiedzieć więcej:// [[http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html|Zestawienie podstawowych reprezentacji wykorzystywanych przy tworzeniu map]]

==== 3. A* ====

Narzędzie webowe: [[https://krzysztof.kutt.pl/didactics/psi/pathfinder/]] \\ //(bazuje na [[https://github.com/qiao/PathFinding.js]])//

  - Na początek warto **pobawić się różnymi algorytmami** i sprawdzić jak działają.
    * Można przesuwać początek (zielony) i koniec (czerwony) ścieżki
    * Można rysować krawędzie
  - Później chcemy **przetestować różne heurystyki** dla A*. W pole ''My heuristic'' można wpisać np.:
    * ''dx''
    * ''dy''
    * ''dx + dy''
    * ''Math.sqrt(dx*dx + dy*dy)''
    * ''-dx - dy''
    * ''10 * Math.random()''
  - __Zadanie A:__
    * Przygotuj pierwszy test klikając najpierw ''Clear Walls'' (wyczyści wszystkie ściany), a później ''Build 1st test'': \\ {{path_astar_test1.jpg?direct&450|}}
    * **Jaką heurystykę należy wpisać dla A*, aby najkrótszą ścieżką była ta "nad" ścianą?**
    * Dlaczego?
  - __Zadanie B:__
    * Przygotuj drugi test klikając ''Clear Walls'' i ''Build 2nd test'': \\ {{path_astar_test2.jpg?direct&450|}} 
    * Jaką heurystykę przyjąć dla A*, aby **znaleźć ścieżkę poniżej 300 operacji** (''operations'' w lewym dolnym rogu po zakończeniu wyszukiwania)
    * Warto porównać z włączoną opcją Bi-directional //(ale zejść poniżej 300 operacji należy bez tej opcji!)//

//Dla chcących wiedzieć więcej:// [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps|Artykuł opisujący heurystyki dla grid map]]

==== 4. CodinGame. Pierwsze wyzwanie: Death First Search ====

[[https://www.codingame.com/|CodinGame]] to platforma do nauki/doskonalenia umiejętności programistycznych wykorzystująca gry. Co ważne, większość gry została już przygotowana, a naszym zadaniem jest tylko dopisanie odpowiedniej logiki, co idealnie wpasowuje się w nasze zajęcia!
  * Platforma umożliwia programowanie w __różnych językach__ programowania (C/C++/C#, Java, Python 3, Scala, ...)
  * Każde zadanie na platformie posiada szczegółowy __opis problemu oraz opis reprezentacji__ (jakie konkretnie wartości są używane, zakresy wartości, ...)
  * Tworzony przez nas kod __komunikuje się z silnikiem gry poprzez standardowe wejście/wyjście__ = w każdej iteracji pętli wczytuje stan planszy / mapę / cokolwiek ze standardowego wyjścia, przetwarza to i generuje akcję, którą wypisuje na standardowe wyjście
  * W każdym języku programowania jest już __przygotowany szablon rozwiązania__ obsługujący wejście/wyjście - wartości z wejścia są zapisywane do przykładowych zmiennych, a na końcu printowane są przykładowe wartości wyjściowe
  * Zadania można programować __bez zakładania konta__ (ale: //konto będzie potrzebne do kliknięcia "submit" i zdobycia maksymalnej liczby punktów//)

**__Zadanie__** jest dostępne pod adresem: **__[[https://www.codingame.com/training/medium/skynet-revolution-episode-1|Death First Search - Episode 1]]__**
  * Twój wirus dostał się do sieci Bobnet (wszelkie skojarzenia z siecią Skynet //nie// są przypadkowe)
  * Znajdujesz się w jednej z podsieci. Znajduje się tutaj również agent Bobnet, który wykrył Twoją obecność i próbuje przemieścić się do bramy, aby przekazać informację o Twoim wirusie do pozostałych części sieci.
  * Twoje zadanie: nie dopuścić do tego poprzez uszkadzanie kolejnych połączeń w sieci (aby finalnie nie było możliwości dotarcia przez agenta Bobnet do żadnej z bram)

  - Na początek zapoznaj się ze szczegółowym opisem zadania dostępnym w IDE (po kliknięciu ''Solve'' na stronie problemu albo po przejściu bezpośrednio pod [[https://www.codingame.com/ide/puzzle/skynet-revolution-episode-1|link]])
  - [3 EXP] Zapoznaj się z interfejsem i przygotuj kod, który rozwiązuje pierwsze dwa test cases (''01. Simple test'' i ''02. Several paths''; aby sprawdzić dany test case należy kliknąć odpowiedni przycisk ''Play testcase'')
  - [3 EXP] Przygotuj rozwiązanie dla test case ''03. Star''
  - [3 EXP] Przygotuj kod, który poprawnie rozwiązuje wszystkie test cases + rozwiązuje dodatkowe test cases wykonywane po kliknięciu ''Submit''; możesz wykorzystać dowolny algorytm (ale wystarczy zwykły BFS)
  - Jeżeli to było zbyt proste, spróbuj zmierzyć się z [[https://www.codingame.com/training/hard/skynet-revolution-episode-2|Death First Search - Episode 2]] //(już bez punktów, dla własnej satysfakcji)//