Strona główna Polish Python Coders Group
   Strona główna   Pomoc Zaloguj się Rejestracja  
Witamy, Gość. Zaloguj się lub zarejestruj.
Czy dotarł do Ciebie email aktywacyjny?

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Aktualności: PyStok #42 - wystąpią Łukasz Langa i Dominik Kozaczko
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: Wyznaczenie drogi do bramki  (Przeczytany 341 razy)
« : 02:30 14/06/19 »
venxx Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 5


Witam.
Próbuję stworzyć prostego bota do gry paper soccer, lecz stanąłem na problemie dotyczącym określeniem czy w następnym ruchu będzie opcja strzelenia gola czyli czy będzie dostępna droga do bramki przykładowo:

Nie mam nawet na celu szukania najkrótszej drogi tylko aby potrafił określić jest dostępna droga czy nie.
Szukałem informacji takich jak szukanie w labiryncie, aczkolwiek nie mam pomysłu jakbym mógł to użyć w moim kodzie ponieważ nie opieram się na grafach.
PS. Czy pygame gdy jest uruchomione musi pobierać 100% procesora?
Mój kod:
https://github.com/8371/Paper-soccer/blob/master/paper_soccer.py
Zapisane
« Odpowiedz #1 : 06:35 14/06/19 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 91
Wiadomości: 434


Skoro starczy wiedzieć że droga jest, możesz "zalać" boisko. Generalnie koncepcja jest taka: Spod bramki wydobywa się woda, która rozlewa się w te strony w które można wykonać ruch. Jak dojdzie do piłki, to znaczy że jest droga (a jak nie będzie możliwości jej dalszego rozlania a piłka dalej sucha to niema).
Zapisane
« Odpowiedz #2 : 07:57 14/06/19 »
Guaz Offline
Expert Python User

Zobacz profil
****

Reputacja: 72
Płeć: Mężczyzna
Wiadomości: 542


Jak powiedział wyżej @sig Uśmiech

Dodam tylko jak określa się to bardziej informatycznie:
Tworzysz strukturę drzewa, korzeniem jest bramka. I teraz zależnie od możliwości z danego punktu, przeszukujesz w szerz (nie do najgłębszego wyczerpania) możliwości dojścia do bramki. Czyli sprawdzasz kolejno pierwszy poziom, drugi, trzeci itd. każdy poziom reprezentuje ilość kresek. Reszta jak u kolegi wyżej.

Co do pyGame. Niestety, nie nadaje się on w praktyce do tworzenia gier, ogólnie python i jego 'silniki' jak pygame nie są do tego przeznaczone, przez brak sztywnego typowania między innymi. Przez co ilość pamięci jest kolosalna, a renderowanie grafiki daleko odbiega od wydajności innych języków. Dlatego jeśli chcesz tworzyć gry, niestety python mnie mocno zawiódł, więc polecam skierować spojrzenie w bardziej powszechne narzędzia jak choćby unity Uśmiech
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #3 : 18:29 14/06/19 »
Ameise Offline
Hello World!

Zobacz profil
*

Reputacja: 2
Wiadomości: 7


Zalogowałem się tylko dlatego, że kiedyś uwielbiałem tę grę Chichot Jeszcze nie widziałem dobrego bota do tej gry, zazwyczaj słaby mini-max, którego potrafi ograć gracz 1300 na kurniku Uśmiech Od 2-3 lat niektórzy próbują coś z MCTS, może trochę lepiej, tak powiedzmy wygrywa z graczami 1500, ale to wciąż słabo. mini-max czy mcts są dobre, ale przydałyby się też dodatkowe założenia przy pisaniu bota (np. wybieraj jedne z najdłuższych sekwencji ruchów - im więcej zapełnienia planszy, tym mniej możliwych ruchów w przyszłości - nie potrafię tego dokładnie wytłumaczyć, każdy kto gra w piłkę wie o co mi chodzi) + np. wbudowanie 'schematów' w pamięci bota. Jakieś pół roku temu przeglądałem githuba w poszukiwaniu projektów dot. piłki i moim zwycięzcą jest:

- https://github.com/slunzok/papersoccer (strona internetowa)
- https://github.com/slunzok/papersoccer-scripts (jakieś skrypty w pythonie, jest jeden nawet w pygame, ale tylko przeglądanie partii)

Fajny projekt, szczególnie ta strona internetowa - wydaje mi się, że możesz przejrzeć plik .js dot. 'orlika treningowego' i przerobic na pythona - ten mazak Gmocha wyznacza wszystkie możliwe sekwencje dla kolejnego ruchu, dodałbyś dodatkowego ifa, jeśli piłka jest w bramce i chyba masz o to o co ci chodzi Uśmiech Szkoda tylko, że autor chyba porzucił rozwijanie strony.

Sam ci nie pomogę, bo napisanie **naprawdę dobrego** bota do tej gry wydaje mi się czasochłonne. Tak tylko wrzuciłem tu swoje 3 grosze na temat piłki, przejrzyj może jeszcze inne projekty na githubie i życzę ci powodzenia! Uśmiech
Zapisane
« Odpowiedz #4 : 01:48 15/06/19 »
venxx Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 5


@Sig wydaje mi się, że wiem co masz na myśli tylko w jaki sposób mógłbym to wykonać patrząc na mój kod?
@Guaz Mógłbyś trochę bardziej rozwinąć myśl tego drzewka?
@Ameise Znasz tę grę? Bardzo się ciesze bo jest mało popularna. Co do tych bardziej zaawansowanych opcji narazie się za nie nie porywam bo mam problem z tą prostą sprawą rok temu próbowałem to zrobić ale sam nie dam rady. Te linki które wysłałeś są mi dobrze znane nawet znam gościa który to zrobił. Czemu porzucił ten projekt nie mam pojęcia prawdopodobnie brak czasu i brak zysków z tego.
Jeśli ktoś miałby czas prosiłbym o bardziej szczegółową pomoc ponieważ piszę tutaj już w ostateczności ponieważ sam już mam problem cokolwiek dodać do mojego kodu i obawiam się, aby on miał sens trzeba by go napisać porządnie od nowa.
Zapisane
« Odpowiedz #5 : 21:00 15/06/19 »
Ameise Offline
Hello World!

Zobacz profil
*

Reputacja: 2
Wiadomości: 7


Dwa przykłady ode mnie (opierając się na przeróbce skryptów ze strony papersoccer.pl):

1) Gole - gif --- Gole - download --- Tak jak już pisałem powyżej, wystarczy lekko przerobić kod z orlika treningowego np.:

- dodałem tablicę gmochGoals
- w funkcji prev() i next() zamiast gmochMoves dałem gmochGoals - żeby wyświetlał tylko gole, a nie wszystkie możliwe ruchy
- w funkcji setGmochMode() dodałem gmochGoals = [], żeby wyzerować tablicę - kiedy ktoś odklika mazak Gmocha
- w funkcji marker() dodałem ifa dla ruchów (0,1,3,4,5,7 - bez 2 i 6, bo w tych przypadkach nigdy nie nastąpi taka możliwość), czy piłka w bramce:

Kod
// gorna bramka
if (tmpCursorY-1 == 0) {
   gmochGoals.push(gmochMultiMoves[i] + "0");
}

lub                         

Kod
// dolna bramka
if (tmpCursorY+1 == 12) {
   gmochGoals.push(gmochMultiMoves[i] + "3");
}

- w funkcji drawGameState(), przy ifie, który sprawdza, czy gmochMode == 1, zamieniłem wszystkie gmochMoves na gmochGoals - żeby rysował tylko gole, nie wszystkie możliwe ruchy

I gotowe. Trochę wystarczy pogłówkować i naprawdę mając kod z tej strony można szybko dopisać sobie nowe funkcje (ale przyznaję, mi zajęło 3 dni, zanim zrozumiałem działanie Język)

2) Bot - gif --- Bot - download -  I kolejny przykład, jak zmodyfikować kod z orlika treningowego, żeby zrobić najprostszego bota (tzn. robisz ruch, a bot w odpowiedzi wykonuje najdłuższy możliwy - nie ma tu żadnej głębokości przeszukiwania minimax itp., po prostu okroiłem maksymalnie mazak Gmocha i ze wszystkich możliwych ruchów automatycznie wykonuje tylko jeden, ten o najdłuższej długości, a jeśli jest ich więcej, to losuje jeden z nich)

- dodałem zmienną botMode = 0
- w funkcji buttonPress() dodałem ifa:

Kod
// jesli uzytkownik wlaczyl tryb bota, po kazdym kliknietym, zakonczonym ruchu przeciwnika wywoluj okrojony mazak Gmocha (marker())
if (botMode == 1 && multiMove == 0) {
   marker();
}

- w funkcji marker() wywaliłem ( w "2. Dodanie do tymczasowej tablicy tmpBoard trwają ...") wszystkie tmpCursorList.push([tmpCursorX, tmpCursorY, "0"]); itp. bo nie mają znaczenia; w ("3. Na koniec sprawdzenie 8 ruchów. Jeśli można ...") dla każdego ruchu wywalam wyliczenia boardClicks, boardFingerprint, bo nie mają znaczenia, a dodaję:

Kod
// gmochMoves zawiera wszystkie najdluzsze ruchy, jesli aktualny ruch jest dluzszy, wyczysc tablice gmochMoves i dodaj ruch - to teraz on bedzie najdluzszy - i wszystkie kolejne o takiej samej dlugosci beda dodawane do gmochMoves
 
next_move = gmochMultiMoves[i] + "0";
if (gmochMoves.length != 0 && next_move.length > gmochMoves[0].length) {
   gmochMoves = [];
}
gmochMoves.push(gmochMultiMoves[i] + "0");


- w funkcji marker() przy końcowym ifie gmochMultiMoves.length == 0 dodałem (kod wziąłem z funkcji prevMove(), można powiedzieć, że to tak, jakbym na stronie papersoccer.pl w orliku treningowym uruchomił mazak Gmocha, a następnie kliknął 'zatwierdź ruch' - muszę tak zrobić, żeby teraz zaktulizować pozycję kursora itp.):

Kod
                var random_move = gmochMoves[Math.floor(Math.random()*gmochMoves.length)];
               moves.push(random_move);
 
               for (var m=0;m<random_move.length;m++) {
                   if (random_move[m] == "0") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "0";
                       board[cursorX][cursorY-1] = board[cursorX][cursorY-1] + "4";  
 
                       cursorY = cursorY - 1;
                   } else if (random_move[m] == "1") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "1";
                       board[cursorX+1][cursorY-1] = board[cursorX+1][cursorY-1] + "5";
 
                       cursorX = cursorX + 1;
                       cursorY = cursorY - 1;
                   } else if (random_move[m] == "2") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "2";
                       board[cursorX+1][cursorY] = board[cursorX+1][cursorY] + "6";
 
                       cursorX = cursorX + 1;
                   } else if (random_move[m] == "3") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "3";
                       board[cursorX+1][cursorY+1] = board[cursorX+1][cursorY+1] + "7";
 
                       cursorX = cursorX + 1;
                       cursorY = cursorY + 1;
                   } else if (random_move[m] == "4") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "4";
                       board[cursorX][cursorY+1] = board[cursorX][cursorY+1] + "0";
 
                       cursorY = cursorY + 1;
                   } else if (random_move[m] == "5") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "5";
                       board[cursorX-1][cursorY+1] = board[cursorX-1][cursorY+1] + "1";
 
                       cursorX = cursorX - 1;
                       cursorY = cursorY + 1;
                   } else if (random_move[m] == "6") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "6";
                       board[cursorX-1][cursorY] = board[cursorX-1][cursorY] + "2";
 
                       cursorX = cursorX - 1;
                   } else if (random_move[m] == "7") {
                       board[cursorX][cursorY] = board[cursorX][cursorY] + "7";
                       board[cursorX-1][cursorY-1] = board[cursorX-1][cursorY-1] + "3";
 
                       cursorX = cursorX - 1;
                       cursorY = cursorY - 1;
                   }
               }
 
               xrange = [];
               yrange = [];
               for(var i=cursorX-1;i<cursorX+2;i++){xrange.push(i);}
               for(var i=cursorY-1;i<cursorY+2;i++){yrange.push(i);}
 
               gmochId = 0;
               gmochMoves = [];
               gmochBlocked = [];
               gmochPermutation = [];
 
               //marker();
               next();


Trochę więcej kombinowania, ale też w miarę proste, trzeba tylko dobrze pomyśleć Język To tyle ode mnie, i tak poświęciłem większość część soboty na zrobienie tych dwóch rzeczy (a tylko przerobiłem kod od kogoś i dodałem parę linijek, a co dopiero tłumaczyć wszystko od początku i napisać to w pythonie Chichot a gdzie minimax czy inne rzeczy Chichot) Według mnie olej pygame i spróbuj się wgłębić w ten kod z githuba, praktycznie logikę gry masz już napisaną, teraz tylko dopisać własne funkcje. Ja nie mam czasu nikogo uczyć/tłumaczyć, więc życzę ci wytrwałości w nauce i powodzenia! Uśmiech
Zapisane
« Odpowiedz #6 : 00:47 17/06/19 »
venxx Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 5


@Ameise dziękuję Ci bardzo za poświęcony czas i wyczerpującą odpowiedź.
Dołożę wszelkich starań w celu przeanalizowania tego co napisałeś i wgłębienia się w kod
ze strony papersoccer. Jeśli będę miał z czymś problem postaram się dać znać Uśmiech
Zapisane
« Odpowiedz #7 : 13:08 17/06/19 »
Guaz Offline
Expert Python User

Zobacz profil
****

Reputacja: 72
Płeć: Mężczyzna
Wiadomości: 542


https://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz

Tu masz o przeszukiwaniu drzewa wszerz. Ogólnie idziesz od pierwszego węzła (bramki) i szukasz najbliższego dojścia do piłki lub wyczerpania możliwości. Algorytm możesz stosować dopiero od pewnej odległości od bramki Uśmiech

Chodzi ogólnie o to, by każdy węzeł (gałąź) to była teoretyczna pozycja piłki w której może się odbić (do pierwszego węzła), albo piłka tam się znajduje w tym momencie Uśmiech
Zachowując te zasadę stworzysz strukturę drzewa, wymagana będzie do tego rekurencja. Ogólnie z tego artykułu na wikipedii wyciągniesz wszelkie dane które potrzebne ci są do wygooglowania. 
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #8 : 22:50 17/06/19 »
venxx Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 5


Jak tak patrze w tym kodzie na Wikipedii jest to użyte za pomocą grafu
"funkcja BreadthFirstSearch (Graf G, Wierzchołek s)"
W moim kodzie nie używałem grafu jak patrze to i na papersoccer i w tych kodach wszędzie są grafy czyli jednak trzeba pisać nowy kod i ten mój wyrzucić?
Zapisane
« Odpowiedz #9 : 01:00 18/06/19 »
Guaz Offline
Expert Python User

Zobacz profil
****

Reputacja: 72
Płeć: Mężczyzna
Wiadomości: 542


Na grafach jest to wszystko inspirowane, przyznam się że nie zaglądałem w twój kod. Ale zakładam że posiadając jakikolwiek inny odpowiednik grafu, węzły czy cokolwiek tego typu, jesteś w stanie to zrobić.

Struktura grafu w tym wypadku mogłaby być mocno złożona. Załóż teraz że jeden punkt ma 8 połączeń które musi mieć powiązane. Samo skonstruowanie tego będzie po prostu ciężkie. Chyba że to ja bym do tego podchodził od złej strony.

Już lepiej prezentowałaby się bitowa ( list(bytearray()) )macierz dwuwymiarowa ze względu na pamięć, 9 (3x3) komórek przeznaczonych na punkt/punkt_odbijający i połączenia/ewentualną ścianę.

W każdym razie, dopóki nie bawisz się w optymalizacje. Struktura to rzecz drugorzędna dopóki potrafisz stworzyć metodę, która robi to co chcesz zrobić.
Ja osobiście w pracy mam ostatnio wystarczająco grzebania w cudzym kodzie, więc jakbyś podrzucił konkretny fragment w jaki sposób budujesz, przechowujesz i modyfikujesz swoją planszę, to na pewno będzie łatwiej Uśmiech
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
« Odpowiedz #10 : 05:33 18/06/19 »
venxx Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 5



X informuje ile mam wolnych dróg z danego ruchu
Mniej więcej tak to wygląda
Zapisane
« Odpowiedz #11 : 10:52 18/06/19 »
Guaz Offline
Expert Python User

Zobacz profil
****

Reputacja: 72
Płeć: Mężczyzna
Wiadomości: 542


Okej, rozumiem teraz na jakiej to jest zasadzie.
Hmmm...
Ja bym zrobił to tak: spróbowałbym zrobić to przeszukanie ze środka bramki. Jak np. kreska jest w odległości 4. Wtedy robisz sobie drzewo odbijając od słupków w trzy dozwolone strony (jeden punkt się będzie powtarzał, pozostaje nam 5). Zapamiętujesz sobie to, jak piłka znajdzie się w którymś z tych punktów, to znaczy że może się dalej odbijać, więc dodajesz kolejne potencjalne połączenia które mogą przynieść zwycięstwo. 'pt'. gdzie piłka musi się znaleźć aby komputer wygrał. I stworzysz sobie sieć punktów (polecam 'tuple(x, y)' zamknięte w zbiorze 'set(tuple(x, y))'), jak do jednego z nich dojdzie, to masz rozwiązanie. Zakładając że żadne z odbić po drodze nie zostało wykorzystane.

Możesz też zamiast przechowywać tuple w zbiorze, stworzyć klasę która będzie miała koordynaty (x, y) oraz słownik gdzie kluczem będzie (x, y) a wartością połączenie, które musi być dostępne żeby ta droga była do zrealizowania. Możesz wtedy też w tym zbiorze przechować różne drogi dla jednego punktu które dałyby zwycięstwo.

Co do stworzenia samej 'mapy ruchów'. Skoro twoje AI się porusza, wykorzystaj te funkcję, ale wykonuj to na deepcopy planszy, sprawdzając możliwe drogi od punktu początkowego, a następnie dla kolejnych gałęzi. Jak nie zrobisz deepcopy, pozmieniasz sobie strukturę listy dwuwymiarowej i popsujesz sobie Uśmiech. Sama funkcja badająca to, powinna być rekurencyjna i odwołująca się do kontenera obiektów z możliwymi drogami do zwycięstwa, update tego robisz tylko gdy piłka znajdzie się w jednym z twoich (x,y) Uśmiech

Będzie to przeszukiwanie wgłąb prostsze i efektywniejsze od przeszukiwania wszerz przy tej strukturze, ponieważ nie znajdzie się tu gałąź z infinity loop'em Uśmiech
Zapisane

Python 3.5+ / Mint

Daje wędkę zamiast ryby. Chyba że ktoś się chce czegoś nauczyć, wtedy chętnie pomogę każdemu.
Za rybę niestety trzeba zapłacić Z politowaniem.
Strony: [1]   Do góry
Drukuj
Skocz do:  

© 2007 - 2019 Polish Python Coders Group
Powered by SMF 1.1.21 | SMF © 2006-2009, Simple Machines | Theme by PixelSlot