Autor Wątek: Sprawdzanie czy obiekty są obok siebie w 1 rzedzie(gra logiczna)  (Przeczytany 2667 razy)

Offline Bartolini

  • Użytkownik

# Lipiec 16, 2008, 02:41:02
Chyba każdy zna grę w kulki. W jaki sposób się tam czy kulki są w 1 rzędzie? Bo przychodzi mi do głowy tylko coś takiego:
1.Najpierw sprawdzamy czy na danym polu jest kulka(odczytujemy z tablicy 1).
2.Potem wykrywamy wokół czy jest jakaś tego samego koloru.
3.Jeśli jest to staramy się przedłużyć tą linię(z 2 kulek narazie) w obie strony.
4.Jak się już przedłuży maksymalnie to zapisujemy wszystkie pola(na których są kulki) w 2 tablicy.
5.Jeśli osiągnie linia odpowiednią długość to zapisujemy pola na których są kulki w 3 tablicy.
6.Nie zaczynamy na zapisanych w 2 tablicy robić pkt 1, reszte sprawdzamy.
7.Po sprawdzeniu wszystkich pól to usuwamy z planszy te z tablicy 3
Ale co jeśli mamy trochę skomplikowaną planszę? Na przykład w Ancient Quest of Saqqarah(na victorygames można demo ściągnąć). Trzeba do każdego pola pisać pola z którymi się łączy?
Co do tego rozwiązania to 1 plansza zajmuje 3 tablice(wersja podstawowa), 1 na każde pole i opcjonalnie przy dziwnych planszach dochodzi 8 na każde pole(ilość maksymalnych łączeń), czyli 11 zmiennych na każde pole. Ale czy jest jakieś lepsze rozwiązanie?
« Ostatnia zmiana: Lipiec 16, 2008, 13:17:38 wysłana przez Bartolini »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

swiru

  • Gość
# Lipiec 16, 2008, 02:58:18
Jeśli sprawdzasz tylko po 3 kulki to jedziesz po całej planszy i spr czy niema kulki-kumpla po bokach.
Lub możesz stworzyć mrówki interesuje cie to ? Mogę rozpisać oco looto
« Ostatnia zmiana: Lipiec 16, 2008, 03:31:57 wysłana przez swiru »

Offline revo

  • Użytkownik

# Lipiec 16, 2008, 03:11:44
Rozwiązanie które ja stosowałem wygląda dość prosto. Od każdego pola będącego na krawędzi planszy ruszamy w kierunku przeciwnym do krawędzi. Przy każdym kroku dodajemy na stos pionki - jeśli typ się nie zgodzi, to opróżniamy stos i idziemy dalej (sprawdzamy jeszcze ilość pionków na stosie, żeby policzyć punkty). Oczywiście pionki uniwersalne trochę bardziej komplikują sprawę i trzeba odpowiednio zmieniać zawartość stosu.

Na szczęście nie trzeba sprawdzać wszystkiego, wystarczy zrobić tak, że jeśli na którymś polu pojawia się nowy pionek, to szukamy najbliższej krawędzi w górę i w lewo - sprawdzamy tylko od tych pionków.

W grze podobnej do AQoS robiłbym to pewnie którymś z klasycznych algorytmów grafowych, np. przeszukiwaniem wgłąb i rozważał aktualną ścieżkę. Analizowany podgraf można skutecznie ograniczyć poprzez ostatnio wykonane ruchy. Każde pole powinno mieć też listę pól z którymi się łączy.
« Ostatnia zmiana: Lipiec 16, 2008, 03:13:24 wysłana przez revo »

Offline SiMet

  • Użytkownik

# Lipiec 16, 2008, 09:45:18
Ja w swojej grze (Flood it!) algorytmu przeszukiwania w glab (DFS), co do gry kulki zapewne zrobilbym jakiegos brute force.
Co do tej gry AQoS potraktowac plansze jako graf ew tablice tyle ze wiedziec gdzie sa pola na ktorych nie moze byc naszego pionka.

Offline Bartolini

  • Użytkownik

# Lipiec 16, 2008, 13:06:00
Tyle, że jest z DFS mały problem. Znalazłem kilka rzeczy w sieci. Ale ja niezbyt to rozumiem. Może w teorii trochę(ale i tak mało), ale w praktyce już nic. Nie licząc, że nie wiem jak zapisać połączenia między dwoma. Tylko jak chcecie pisać, że grafem to napiszcie jak go zrobić(w kursie cpp nic nie było o nich, ale kurs był słaby i uprostrzony, może dlatego). Revo, chyba twój algorytm nie sprawdza lini która nie dotyka ściany(o ile do dobrze zrozumiałem). Swiru, 1 sposób to mój(przy planszy złożenej z kwadratów i prostokątów), zajmuje 3 tablice(1 - kulki, 2 - do wykasowania, 3 - jeśli chcemy zaoszczędzić pamięci to nie zaczynamy od nich sprawdzać lini), przy AQoS to w moim pomyśle trzeba jeszcze 8xilość pól zmiennych(w tablicach zapisanych).
EDIT: 1 post pisany pod wpływem snu, niezbyt napisałem to zrozumiale.
« Ostatnia zmiana: Lipiec 16, 2008, 13:56:25 wysłana przez Bartolini »

Offline revo

  • Użytkownik

# Lipiec 16, 2008, 13:56:23
Revo, chyba twój algorytm nie sprawdza lini która nie dotyka ściany(o ile do dobrze zrozumiałem).

Źle zrozumiałeś - przechodzisz całą linię planszy od krawędzi, nie jest ważne w którym miejscu na niej znajduje się linia ułożona z pionków.

Offline SiMet

  • Użytkownik

# Lipiec 16, 2008, 14:53:11
Tzn jezeli chodzi o sprawdzanie czy obiekty sa w jednem rzedzie to chyba najlepszy jest brute force (tak jak pisali sprawdzac kazda linie po kolei i np odkladac elementy na stos). Bo DFS i BFS przydaja sie jesli chcemy sprawdzic czy elementy ze soba sasiaduja. Ew chcemy sprawdzic czy z jednego miejsca da sie dojsc w drugie (tutaj dijkstra). W przypadku sprawdzania linii chyba nie trzeba az tak bardz kombinowac.

Offline Bartolini

  • Użytkownik

# Lipiec 17, 2008, 02:07:31
Zauważyłem że mój sposób może mieć bez problemu zmieścić się w 10 bool na każde pole + 1 mająca co najmniej 3 bity. Czyli  13 bitów na każde pole to nie dużo. Lecz jeśli mamy zwykłą mapę to oszczędzamy 1 bit na pole i sporo(jeśli chodzi o procenty, w ilościach to mało) szybkości. Thx za lepszy sposób.
« Ostatnia zmiana: Lipiec 17, 2008, 02:10:18 wysłana przez Bartolini »

swiru

  • Gość
# Lipiec 17, 2008, 02:25:40
Zauważyłem że mój sposób może mieć bez problemu zmieścić się w 10 bool na każde pole + 1 mająca co najmniej 3 bity. Czyli  13 bitów na każde pole to nie dużo. Lecz jeśli mamy zwykłą mapę to oszczędzamy 1 bit na pole i sporo(jeśli chodzi o procenty, w ilościach to mało) szybkości. Thx za lepszy sposób.
Bool ma 1 bajt.... niby jak komputer miałby zadresowac 1 bit? :o
Noo wyjechałeś z optymalizacja po takiej gafie ze chej  :D

chcesz oszczędzić to użyj pól bitowych :) Lecz wtedy dochodzi mnożenie przez maski....

hmm żeby użyć 1MB to trzeba pole ~~ 280 x 280 (liczylem z glowy XD )
« Ostatnia zmiana: Lipiec 17, 2008, 02:37:32 wysłana przez swiru »

Offline revo

  • Użytkownik

# Lipiec 17, 2008, 02:28:16
Zauważyłem że mój sposób może mieć bez problemu zmieścić się w 10 bool na każde pole + 1 mająca co najmniej 3 bity. Czyli  13 bitów na każde pole to nie dużo. Lecz jeśli mamy zwykłą mapę to oszczędzamy 1 bit na pole i sporo(jeśli chodzi o procenty, w ilościach to mało) szybkości. Thx za lepszy sposób.

Na co Ty chcesz to implementować? Na kalkulator?  ;)

Offline Bartolini

  • Użytkownik

# Lipiec 17, 2008, 15:24:23
Swiru, racja. Choć jeśli miejsce miało by ogromne znaczenie(a nie ma) to można to 8 booli zmienić w 1 bajt. Wystarczy tylko założyć, że kolejne boole to cyfry w kodzie binarnym i przerobić to na dziesiętny (boole ustawione w taki sposób 11001011 można zapisać jako 203) to można potem dostać znowu w binarnym(nie wiem czy trzeba samemu algorytm pisać, czy nie).  Do tego wystarczy 1 bajt z kolorem(126 kolorów  i jeden pusty wystarczy chyba na rodzaje/kolory kulek) i kulkami ktore się skasują po przejrzeniu wszystkiego(jesli kulka jest ustawiona do skasowania to dodajemy 128, jeśli pole z kulka ma liczbę większą od 127 to wywalamy ją, ale to ostatnie to pod koniec sprawdzania), 2 bajty na pole. Na jeden mega wystarczy na 512 (16 x 32 pol). Ale chyba to trochę procesor by bardziej zajęło.  Choć wogle my tu myślimy o mapach w stylu AQoS. Ale jeśli ktoś ma cel by zajmować jak najmniej pamięci to można ewentualnie się pomęczyć.
Na zwykłej mapie zajmuje to 2 bajty, w wersji oszczędzającej 1(126 możliwych rodzajów kulek).
« Ostatnia zmiana: Lipiec 17, 2008, 15:26:24 wysłana przez Bartolini »

Offline revo

  • Użytkownik

# Lipiec 17, 2008, 15:33:34
Chyba coś Ci się obliczenia pomyliły - jeśli w jednym MB chciałbyś zapamiętać 512 obiektów, to na każdy masz 2kB a nie 2 B ;)

Nie masz się co przejmować takimi optymalizacjami - tylko pogorszysz czytelność kodu i pewnie wydajność też na tym ucierpi.

Offline ajur

  • Użytkownik

# Lipiec 17, 2008, 16:35:35
Myślę że w przypadku kulek (jak i wielu innych podobnych gier planszowych), można się ograniczyć do sprawdzania tylko otoczenia ostatnio dodanej kulki, nie całej planszy.
Oczywiście nadal przydało by się wiedzieć jakie są połączenia między polami. W przypadku prostokątnej planszy z takimi samymi polami nie ma raczej problemu (mamy tylko 8 zawsze dobrze zdefiniowanych połączeń) i spokojnie reprezentujemy to jako tablicę.
Gorzej jeżeli plansza jest bardziej złożona, coś jak w tych grach planszowych ze ścieżką, drabinami i linami, albo po prostu takich gdzie nie jest takie oczywiste kto jest czyim sąsiadem. Wtedy najlepiej taką planszę reprezentować jako graf.
Graf jest to bardzo ciekawa struktura danych o której wiele można poczytać na necie albo w podręcznikach ("wprowadzenie do algorytmów i struktur danych" - klasyka w tej dziedzinie). Ale zazwyczaj są dwa sposoby implementacji połączeń w grafie:
1. tablica dwuwymiarowa booli w której oba wymiary indeksuje się numerami wierzchołków, a powiązanie oznacza się wartością true na przecięciu wiersza i kolumny odpowiadającym pewnym wierzchołkom.
2. każdy wierzchołek reprezentujesz jako jeden obiekt który ma wskaźniki do "sąsiadujących" wierzchołków.
To które z tych rozwiązań jest najlepsze, zależy od konkretnej aplikacji.

swiru

  • Gość
# Lipiec 17, 2008, 17:32:06
Cytat: JA
chcesz oszczędzić to użyj pól bitowych :) Lecz wtedy dochodzi mnożenie przez maski....

Swiru, racja. Choć jeśli miejsce miało by ogromne znaczenie(a nie ma) to można to 8 booli zmienić w 1 bajt. Wystarczy tylko założyć, że kolejne boole to cyfry w kodzie binarnym i przerobić to na dziesiętny (boole ustawione w taki sposób 11001011 można zapisać jako 203) to można potem dostać znowu w binarnym(nie wiem czy trzeba samemu algorytm pisać, czy nie). 

.......................................

Offline Bartolini

  • Użytkownik

# Lipiec 18, 2008, 00:11:00
Ja myślałem w sensie:
Bool ma 1 bajt.... niby jak komputer miałby zadresowac 1 bit?

Swiru, racja. Choć jeśli miejsce miało by ogromne znaczenie(a nie ma) to można to 8 booli zmienić w 1 bajt.

A co do przeliczeń to jeszcze myle się(jakoś niezbyt mnie to interesuje, jak i tak w moim przypadku to są niezauważalne wielkości)