Jak mogę wdrożyć coś takiego jak siatka rzemieślnicza Minecraft?

System rzemieślniczy w Minecraft wykorzystuje siatkę 2x2 lub 3x3. Umieszczasz składniki na siatce, a jeśli umieścisz odpowiednie składniki we właściwym wzorze, aktywuje to przepis.

Kilka interesujących punktów na temat projektu:

• Niektóre przepisy mogą wymieniać niektóre składniki na inne. Na przykład kilof korzysta z patyków do haftowania i może używać drewnianych desek, bruku, wlewków żelaza, złotych wlewków lub diamentowych klejnotów do głowy.
• Liczy się pozycja względna w strukturze, a nie pozycja absolutna na siatce. Oznacza to, że możesz wytworzyć pochodnię , umieszczając kij i węgiel (lub węgiel) we właściwym wzorze w dowolnej z sześciu pozycji na siatce 3x3.
• Wzory mogą być odwracane w poziomie.

Być może zastanawiam się nad tym, ale wydaje się, że to interesujący problem z wyszukiwaniem / redukcją zbiorów. Jak więc działa (lub może) to algorytmicznie?

Innym rozwiązaniem jest użycie nieco skomplikowanego drzewa. Węzły gałęzi w twoim drzewie zostałyby utworzone przez iterację po przepisie (ponownie używając for (y) { for (x) }); jest to twoja standardowa drzewiasta struktura drzewa według księgi. Twój ostatni węzeł zawierałby dodatkową strukturę ( Dictionary/ HashMap), która mapuje wymiary do przepisów.

Zasadniczo to, czego szukasz:

Czarne węzły to twoje gałęzie, które wskazują typ przedmiotu - czerwone to twoje liście (terminatory), które pozwalają ci rozróżnić rozmiar / orientację.

Aby przeszukać to drzewo, najpierw znajdź obwiednię (zgodnie z moją pierwszą odpowiedzią ), a następnie iteruj po węzłach w tej samej kolejności, przemierzając drzewo, gdy idziesz. W końcu po prostu spojrzysz na wymiar w swoim Dictionarylub HashMapi uzyskasz wynik przepisu.

Właśnie dla kopnięć poszedłem i wdrożyłem to - co prawdopodobnie wyjaśni moją odpowiedź. Ponadto : zdaję sobie sprawę, że to inna odpowiedź - i słusznie: to inne rozwiązanie.

Musisz pamiętać, że Minecraft używa tylko bardzo małego zestawu możliwych przepisów, więc nie ma potrzeby, aby wszystko było tak inteligentne.

Powiedziałbym, że powinienem znaleźć najmniejszą pasującą siatkę (tj. Zignoruj ​​puste wiersze i kolumny, aby dowiedzieć się, czy jest to 2x2, 3x3, czy 2x3 (drzwi)). Następnie przeglądaj listę przepisów o tym rozmiarze, po prostu sprawdzając, czy typ przedmiotu jest taki sam (tj. W najgorszym porównaniu 9 liczb całkowitych w Minecraft, ponieważ używa identyfikatora typu liczby całkowitej dla przedmiotów i bloków) i zatrzymaj się, gdy znajdziesz dopasowanie.

W ten sposób względne położenie przedmiotów nie ma znaczenia (możesz umieścić pochodnię w dowolnym miejscu na siatce rzemieślniczej i zadziała, ponieważ widzi ją jako pudełko 1x2, a nie pudełko 3x3, które jest w większości puste).

Jeśli masz ogromną liczbę przepisów, więc przeszukiwanie liniowe możliwych dopasowań zajmuje dużo czasu, możliwe byłoby sortowanie listy i wyszukiwanie binarne (O (log (N)) vs O (N)). Spowodowałoby to dodatkowe prace przy tworzeniu listy, ale można to zrobić przy pierwszym uruchomieniu, a następnie zachować w pamięci.

I ostatnią rzeczą, aby umożliwić przerzucenie przepisu w poziomie najprostsze byłoby po prostu dodanie wersji lustrzanej do listy.

Jeśli chcesz to zrobić bez dodawania drugiego przepisu, możesz sprawdzić, czy przepis wejściowy zawiera element w [0,0] o wyższym identyfikatorze niż w [0,2] (lub [0,1] dla 2x2, kontrola nie jest wymagana dla 1x2, a jeśli tak, wykonaj kopię lustrzaną, jeśli nie, kontynuuj sprawdzanie następnego wiersza, aż dojdziesz do końca. Korzystając z tego, musisz również upewnić się, że przepisy zostały dodane we właściwej rotacji.

Sprawdzenie, czy określona konfiguracja siatki pasuje do określonej receptury, jest proste, jeśli zakodujesz siatkę 3x3 jako ciąg znaków i użyjesz dopasowania wyrażenia regularnego . Przyspieszenie wyszukiwania to inna sprawa, o której w końcu porozmawiam. Czytaj dalej, aby dowiedzieć się więcej.

Krok 1) Zakoduj siatkę jako Ciąg

Wystarczy podać identyfikator każdego typu komórki i połączyć wszystko obok siebie w tej kolejności:

123
456 => 123456789
789

I bardziej konkretny przykład, rozważ przepis na kij, w którym W oznacza drewno, a E jest pustą komórką (możesz po prostu użyć pustego znaku ''):

EEE
WEE => EEEWEEWEE
WEE

Krok 2) Dopasuj przepis przy użyciu wyrażenia regularnego (lub String.Contains z odrobiną przetwarzania danych)

Kontynuując powyższy przykład, nawet jeśli przesuniemy formację, nadal istnieje wzór w sznurku (WEEW wyściełany przez E po obu stronach):

EEW
EEW => EEWEEWEEE
EEE

Niezależnie od tego, gdzie przesuniesz drążek, nadal będzie pasował do następującego wyrażenia regularnego: /^E*WEEWE*$/

Wyrażenia regularne pozwalają również wykonać wspomniane zachowanie warunkowe. Na przykład (wymyślony przepis), jeśli chcesz, aby kilof wykonany z żelaza lub kamienia dawał taki sam efekt, tj .:

III    SSS
EWE or EWE
EWE    EWE

Możesz połączyć oba w wyrażenie regularne: /^(III)|(SSS)EWEEWE$/

Równie łatwo można dodawać przerzucenia w poziomie (również za pomocą operatora |).

Edycja: W każdym razie część wyrażenia regularnego nie jest absolutnie konieczna. Jest to tylko jeden sposób na zawarcie problemu w jednym wyrażeniu. Jednak w przypadku problemu ze zmienną lokalizacją równie dobrze możesz przyciąć ciąg siatki dowolnych spacji (lub liter E w tym przykładzie) i wykonać String.Contains (). W przypadku problemu z wieloma składnikami lub dublowanych przepisów możesz po prostu obsłużyć je wszystkie jako wiele (tj. Osobne) przepisy o tej samej wydajności.

Krok 3) Przyspieszenie wyszukiwania

Jeśli chodzi o ograniczenie wyszukiwania, musisz utworzyć strukturę danych, aby pogrupować przepisy i pomóc w wyszukiwaniu. Traktowanie siatki jako łańcucha również ma tutaj pewne zalety :

1. Można zdefiniować „długość” przepisu jako odległość między pierwszym niepustym znakiem a ostatnim niepustym znakiem. Prosty Trim().Length()podałby ci te informacje. Przepisy można pogrupować według długości i przechowywać w słowniku.

   lub

   Alternatywną definicją „długości” może być liczba niepustych znaków. Nic innego się nie zmienia. Możesz pogrupować przepisy według tych kryteriów.

2. Jeśli punkt 1 nie wystarczy, przepisy można również pogrupować według rodzaju pierwszego składnika, który pojawia się w przepisie. Byłoby to tak proste, jak robienie Trim().CharAt(0)(i ochrona przed przycinaniem skutkującym pustym ciągiem).

Na przykład przechowujesz przepisy w:

Dictionary<int, Dictionary<char, List<string>>> _recipes;

I wykonaj wyszukiwanie jako coś takiego:

// A string encode of your current grid configuration 
string grid;

// Get length and first char in our grid
string trim = grid.Trim();
int length = trim.Length();
char firstChar = length==0 ? ' ' : trim[0];

foreach(string recipe in _recipes[length][firstChar])
{
    // Check for a match with the recipe
    if(Regex.Match(grid, recipe))
    {
        // We found a matching recipe, do something with it
    }
}

Nie mogę powiedzieć ci, jak działa Minecraft One - chociaż jestem pewien, że jeśli spojrzałeś na MCP (jeśli masz legalną kopię Minecraft), możesz się dowiedzieć.

Zaimplementowałbym to w następujący sposób:

1. Mają słownik dyskowy / mapę skrótów ( B + Tree / SQL-Light ) - wartością będzie identyfikator pozycji wyniku receptury.
2. Kiedy użytkownik coś tworzy, po prostu znajdź pierwszy wiersz / kolumnę z przedmiotem NIEZALEŻNIE ; połącz je w przesunięcie.
3. Znajdź ostatni wiersz / kolumnę z elementem, ponownie, niezależnie.
4. Oblicz szerokość i wysokość elementów i dodaj do klucza.
5. Zapętlić zakres właśnie wyliczonego obwiedni i dołączyć identyfikator każdego elementu (używając zwykłego for (y) { for (x) }).
6. Wyszukaj klucz w bazie danych.

Powiedzmy na przykład, że mamy dwa składniki; X i Y oraz puste są *. Weź następujący przepis:

**X
**Y
**Y

Najpierw opracowujemy obwiednię, poddając się (2,0)-(2,2). Dlatego nasz klucz wyglądałby tak [1][3](1 szerokość, 3 wysokość). Następnie zapętlamy każdy element w obwiedni i dołączamy identyfikator, w ten sposób staje się klucz [1][3][X][Y][Y]- następnie przejrzyj to w słowniku / DB i uzyskasz wynik tego przepisu.

Aby dokładniej wyjaśnić niezależność w kroku 2, rozważ następujący przepis:

*XX
XXX
XX*

Górna / lewa strona ma wyraźnie wartość 0,0 - jednak pierwszym przedmiotem, który zazwyczaj napotkasz, będzie 0,1 lub 1,0 (w zależności od pętli). Jeśli jednak znajdziesz pierwszą niepustą kolumnę, a także pierwszy niepusty wiersz i połączysz te współrzędne, otrzymasz 0,0 - ta sama zasada dotyczy dolnej / prawej krawędzi ramki granicznej.

Oto jak to zrobiłem w Block Story: