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


55

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?


6
Niesamowite pytanie! Jestem bardzo zainteresowany! Mam już kilka pomysłów, ale podzielę się nimi, jak tylko wrócę do domu.
jcora

Tak naprawdę próbuję napisać kopię „jak najbliżej” Minecrafta. Napisałem już wszystkie rzeczy do zarządzania zapasami i recepturami i muszę powiedzieć, że wszystko działa bardzo dobrze. Jestem zadowolony z czystego kodu. Jednak napisanie go nie było łatwe. Napisałem około 10 klas, aby wszystko działało ładnie, przepisy, siatki, ekwipunek itp. Kiedy znajdę trochę czasu, napiszę odpowiedź.
Martijn Courteaux,

Powinieneś przyjrzeć się, jak Minecraft koduje ich przepisy rzemieślnicze.
Bradman175,

Odpowiedzi:


14

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:

Drzewo receptur

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.


Bardzo proste. Lubię to.
David Eyk

Zaakceptuję ten, ponieważ lubię drzewa, hasze i diagramy, które przechodzą do sedna sprawy. Jedno spojrzenie na diagram i prawie natychmiast zrozumiałem twój algorytm.
David Eyk

23

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.


1
Zastanawiałem się, czy niewielka liczba przepisów w Minecraft może nie poddać się liniowemu poszukiwaniu.
David Eyk

1
Robi to i jest zasadniczo tym, co napisałem powyżej (z możliwą optymalizacją wyszukiwania binarnego). Pozostawia to jednak kilka opcji tworzenia pochodni, które można zmieścić praktycznie w dowolnym miejscu. Po uzyskaniu rozmiaru przepisu nie musisz dodawać 6 przepisów na pochodnie i ograniczasz wyszukiwanie tylko do tych o prawidłowym rozmiarze w jednym kroku. - Zasadniczo opcje dla punktu 2 są grupowane według rozmiaru, przenieś przepis do rogu lub dodaj więcej zduplikowanych przepisów.
Elva

15

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
    }
}

3
To jest ... bardzo, bardzo mądre.
Raveline

18
Masz problem i chcesz go rozwiązać za pomocą wyrażeń regularnych? Teraz masz 2 problemy :)
Kromster mówi o wsparciu Moniki

2
@Krom Myślę, że prawdopodobnie żartujesz, ale czy masz jakieś uzasadnienie tego komentarza? Użycie wyrażenia regularnego jest tylko zwięzłym (dopasuj siatkę do przepisu za pomocą pojedynczego wiersza kodu) i elastycznym (spełnia wszystkie wymagania tego problemu) sposobem na wykonanie dopasowania na zestawie danych (zawartość siatki). Nie widzę żadnych znaczących wad w porównaniu z wprowadzaniem własnego algorytmu dopasowywania i upraszcza to cały proces.
David Gouveia,

2
@DavidGouveia, to tylko fraza dla osób, które nie są zbyt wygodne z Regex. Jeśli zdecydują się rozwiązać problem z wyrażeniem regularnym, mają teraz dwa problemy: (1) faktyczny problem, który chcą rozwiązać (2) napisanie wzoru wyrażenia regularnego w celu rozwiązania tego problemu
iamserious

2
Wracając do „teraz masz dwa problemy” - Regex będzie miał problemy, gdy tylko będziesz mieć więcej pozycji niż zakres wydruku ASCII, chyba że procesor regex obsługuje Unicode i możesz zagwarantować, że niektóre kombinacje nie spowodują wyłączenia kompilatora regex NFA w górę. Możesz połączyć swój własny DFA (całkiem łatwo), aby dopasować wzorce; ale regex byłby najlepszym sposobem na wykonanie prototypu.
Jonathan Dickinson

3

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.


Repozytorium Bukkit nie ma żadnego kodu Minecraft, potrzebujesz MCP (i kopii Minecraft)
BlueRaja - Danny Pflughoeft

Czy to nie jest odwrotność twojej drugiej odpowiedzi?
David Eyk

@DavidEyk (to moja pierwsza odpowiedź) nie jest tak naprawdę, jest bardziej zależny od struktury mapy skrótów (niezależnie od tego, czy jest to tabela wielkoformatowa, czy w pamięci). Powodem, dla którego odpowiedziałem ponownie, jest to, że martwiłem się kolizjami mieszania prowadzącymi do słabej wydajności - przynajmniej w przypadku tablicy pamięci w pamięci. Moja inna odpowiedź działałaby lepiej dla większej liczby elementów i struktury w pamięci - gdzie działałoby to lepiej, gdyby było w SQL / etc.
Jonathan Dickinson

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.