Как я могу реализовать что-то вроде сетки крафта Minecraft?

55

В крафт-системе Minecraft используется сетка 2x2 или 3x3. Вы помещаете ингредиенты в сетку, и если вы поместите правильные ингредиенты в правильный шаблон, он активирует рецепт.

Несколько интересных моментов о дизайне:

  • Некоторые рецепты могут обменивать определенные ингредиенты на другие. Например, кирка использует палки для рукояти и может использовать деревянные доски, булыжник, железные слитки, золотые слитки или алмазные камни для головы.
  • Важное значение имеет относительная позиция в пределах шаблона, а не абсолютная позиция в сетке. То есть вы можете создать факел , поместив палку и уголь (или древесный уголь) по правильному шаблону в любую из шести позиций на сетке 3х3.
  • Шаблоны могут быть перевернуты горизонтально.

Я, может быть, обдумываю это, но это кажется интересной проблемой поиска / сокращения множеств. Итак, как (или может) это работает, если говорить алгоритмически?

Дэвид Эйк
источник
6
Отличный вопрос! Я очень заинтересован! У меня уже есть некоторые идеи, но я поделюсь ими, как только вернусь домой.
jcora
Я на самом деле пытаюсь написать "как можно ближе" копию Minecraft. Я уже написал все материалы для менеджера инвентаря и рецептов, и должен сказать, что он работает очень аккуратно. Я доволен чистым кодом. Однако это было нелегко написать. Я написал около 10 уроков, чтобы все работало хорошо - рецепты, сетки, инвентарь и т. Д. Когда я найду время, я напишу ответ.
Мартин Курто
Вы должны посмотреть, как майнкрафт кодирует свои рецепты крафта.
Bradman175

Ответы:

14

Другое решение - использовать несколько сложное дерево. Узлы ветвления в вашем дереве будут созданы путем итерации по рецепту (еще раз с использованием for (y) { for (x) }); это ваша стандартная древовидная структура. Ваш последний узел будет содержать дополнительную структуру ( Dictionary/ HashMap), которая сопоставляет измерения с рецептами.

По сути, вы собираетесь это:

Дерево рецептов

Черные узлы - это ваши ветви, которые указывают тип элемента, а красные - ваши листья (терминаторы), которые позволяют вам различать размер / ориентацию.

Для поиска по этому дереву вы сначала найдете ограничивающую рамку (как обрисовано в общих чертах в моем первом ответе ), а затем перебираете узлы в том же порядке, проходя по дереву, как вы идете. Наконец, вы просто посмотрите на размерность в вашем Dictionaryили, HashMapи вы получите результат рецепта.

Я просто пошёл и реализовал это - что, вероятно, прояснит мой ответ. Кроме того : я понимаю, что это другой ответ - и по праву так: это другое решение.

Джонатан Дикинсон
источник
Очень просто. Мне это нравится.
Дэвид Эйк
Я приму это, потому что мне нравятся деревья, хэши и диаграммы, которые касаются сути вопроса. Один взгляд на диаграмму, и я понял ваш алгоритм почти сразу.
Дэвид Эйк
23

Вы должны помнить, что Minecraft использует только очень маленький набор возможных рецептов, так что не нужно ничего такого умного.

Тем не менее, я хотел бы найти наименьшую подходящую сетку (т.е. игнорировать пустые строки и столбцы, чтобы выяснить, 2x2, 3x3 или 2x3 (дверь)). Затем циклически просматривайте список рецептов с таким размером, просто проверяя, является ли тип элемента одинаковым (т. Е. В худшем случае 9 целочисленных сравнений в minecraft, поскольку он использует идентификатор целочисленного типа для элементов и блоков) и прекращайте работу, когда вы находите совпадение.

Таким образом, относительное положение предметов также не имеет значения (вы можете поместить факел в любом месте на сетке крафта, и он будет работать, потому что он видит его как ящик 1х2, а не как ящик 3х3, который в основном пуст).

Если у вас есть огромное количество рецептов, так что выполнение линейного поиска возможных совпадений занимает много времени, можно было бы отсортировать список и выполнить бинарный поиск (O (log (N)) против O (N)). Это может привести к некоторой дополнительной работе по созданию списка, но это можно сделать один раз при запуске и впоследствии сохранить в памяти.

Кроме того, последнее, что позволило бы перевернуть рецепт по горизонтали, было бы просто добавить зеркальную версию в список.

Если вы хотите сделать это без добавления второго рецепта, вы можете проверить, имеет ли входной рецепт элемент в [0,0] с более высоким идентификатором, чем в [0,2] (или [0,1] для 2x2, проверка не требуется) для 1x2 и, если это так, отражайте его, если нет, продолжайте проверять следующую строку, пока не дойдете до конца. Используя это, вы также должны убедиться, что рецепты добавлены в правильном порядке.

Эльва
источник
1
Я задавался вопросом, не может ли небольшое количество рецептов в Майнкрафте подойти для линейного поиска.
Дэвид Эйк
1
Это так, и в основном то, что я написал выше (с возможной оптимизацией бинарного поиска). Однако это оставляет несколько вариантов для изготовления факелов, которые вы можете разместить практически в любом месте. Получив сначала размер рецепта, вам не нужно добавлять 6 рецептов для факелов, и вы ограничиваете поиск только теми, которые имеют правильный размер за один шаг. - Таким образом, в основном варианты для вашей точки 2 сгруппированы по размеру, переместите рецепт в угол или добавьте больше повторяющихся рецептов.
Эльва
15

Узнать, соответствует ли определенная конфигурация сетки определенному рецепту, просто, если вы кодируете сетку 3x3 как строку и используете совпадение регулярного выражения . Ускорение поиска - это другой вопрос, о котором я расскажу в конце. Читайте дальше для получения дополнительной информации.

Шаг 1) Кодировать сетку как строку

Просто укажите идентификатор каждого типа ячейки и объедините все рядом в следующем порядке:

123
456 => 123456789
789

И в качестве более конкретного примера рассмотрим рецепт палки, где W обозначает древесину, а E - пустую ячейку (вы можете просто использовать пустой символ ''):

EEE
WEE => EEEWEEWEE
WEE

Шаг 2) Сопоставьте рецепт с помощью регулярного выражения (или String.Contains с небольшим количеством обработки данных)

Продолжая приведенный выше пример, даже если мы переместим формацию вокруг, в строке все равно будет шаблон (WEEW, дополненный E с обеих сторон):

EEW
EEW => EEWEEWEEE
EEE

Поэтому независимо от того, куда вы перемещаете флешку, она все равно будет соответствовать следующему регулярному выражению: /^E*WEEWE*$/

Регулярные выражения также позволяют вам выполнять условное поведение, которое вы упомянули. Например (составленный рецепт), если вы хотели, чтобы кирка из железа или камня дала такой же результат, то есть:

III    SSS
EWE or EWE
EWE    EWE

Вы можете объединить оба в регулярное выражение: /^(III)|(SSS)EWEEWE$/

Горизонтальные смещения также могут быть добавлены так же легко (с помощью оператора | тоже).

Изменить: Во всяком случае, часть регулярных выражений не является строго необходимым. Это всего лишь один способ инкапсулировать проблему в одном выражении. Но для проблемы с переменным местоположением вы также можете обрезать строку сетки любых пробельных полей (или E в этом примере) и выполнить String.Contains (). А для задачи с несколькими ингредиентами или зеркальных рецептов вы можете просто обрабатывать их как несколько (то есть отдельных) рецептов с одинаковым выходом.

Шаг 3) Ускорение поиска

Что касается сокращения поиска, вам нужно создать некоторую структуру данных, чтобы сгруппировать рецепты и помочь с поиском. Обработка сетки как строки также имеет некоторые преимущества :

  1. Вы можете определить «длину» рецепта как расстояние между первым непустым символом и последним непустым символом. Простое Trim().Length()дало бы вам эту информацию. Рецепты могут быть сгруппированы по длине и сохранены в словаре.

    или же

    Альтернативным определением «длины» может быть количество непустых символов. Больше ничего не меняется. Вы также можете сгруппировать рецепты по этим критериям.

  2. Если точки номер 1 недостаточно, рецепты также могут быть сгруппированы по типу первого ингредиента, который появляется в рецепте. Это было бы так же просто, как делать Trim().CharAt(0)(и защищать от Trim, получая пустую строку).

Так, например, вы должны хранить рецепты в:

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

И выполнить поиск как что-то вроде:

// 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
Это ... очень очень умно.
Raveline
18
У вас есть проблема, и вы хотите решить ее с помощью регулярных выражений? Теперь у вас 2 проблемы :)
Кромстер говорит, что поддерживает Монику
2
@ Кром Я полагаю, ты, наверное, просто шутишь, но есть ли какие-то аргументы за этот комментарий? Использование регулярного выражения - это всего лишь краткий (сопоставить сетку с рецептом одной строкой кода) и гибкий (соответствует всем требованиям этой задачи) способ сопоставления с набором данных (содержимым сетки). Я не вижу существенных недостатков по сравнению с собственным алгоритмом сопоставления, и он упрощает весь процесс.
Дэвид Гувейя
2
@DavidGouveia, это просто фраза для людей, которые не слишком знакомы с Regex. Если они решают решить проблему с регулярным выражением, у них теперь есть две проблемы: (1) реальная проблема, которую они хотят решить (2) написание шаблона регулярного выражения для решения этой проблемы
iamserious
2
Возвращаясь к вопросу «теперь у вас две проблемы» - у Regex будут проблемы, как только у вас будет больше элементов, чем диапазон печати ASCII, если ваш процессор regex не поддерживает юникод, и вы можете гарантировать, что определенные комбинации не сработают в компиляторе NFA regex. вверх. Вы можете собрать свой собственный DFA (довольно легко на самом деле), чтобы соответствовать шаблонам; но регулярное выражение будет лучшим способом прототипирования.
Джонатан Дикинсон
3

Я не могу рассказать вам, как работает Minecraft 1 - хотя я уверен, что если вы посмотрите на MCP (если у вас есть легальная копия Minecraft), вы сможете узнать.

Я бы реализовал это следующим образом:

  1. Иметь некоторый дисковый словарь / hashmap ( B + Tree / SQL-Light ) - значение будет идентификатором элемента результата рецепта.
  2. Когда пользователь создает что-то, просто найдите первую строку / столбец с элементом НЕЗАВИСИМО ; объединить их в смещение.
  3. Найти последнюю строку / столбец с элементом, опять же, независимо.
  4. Вычислите ширину и высоту от предметов и добавьте их к ключу.
  5. Зациклите диапазон только что вычисленной ограничительной рамки и добавьте идентификатор каждого элемента (используя свой обычный for (y) { for (x) }).
  6. Посмотрите ключ в базе данных.

Например, скажем, у нас есть два ингредиента; X и Y и пробелы, являющиеся *. Возьмите следующий рецепт:

**X
**Y
**Y

Сначала мы разрабатываем ограничивающую рамку, уступая (2,0)-(2,2). Поэтому наш ключ будет выглядеть так [1][3](1 ширина, 3 высоты). Затем мы зацикливаемся на каждом элементе внутри ограничительной рамки и добавляем идентификатор, таким образом, ключ становится [1][3][X][Y][Y]- вы затем ищите это в своем словаре / БД, и вы получите результат этого рецепта.

Чтобы объяснить независимость на шаге 2 более четко, рассмотрите следующий рецепт:

*XX
XXX
XX*

Верхний / левый угол явно равен 0,0, однако первый элемент, с которым вы обычно сталкиваетесь, будет 0,1 или 1,0 (в зависимости от вашего цикла). Однако, если найти первый непустой столбец, а также первую непустую строку и объединить эти координаты, вы получите 0,0 - тот же принцип применяется к нижней / правой части ограничительной рамки.

Джонатан Дикинсон
источник
В репозитории Bukkit нет кода Minecraft, вам понадобится MCP (и копия Minecraft)
BlueRaja - Danny Pflughoeft
Разве это не обратная сторона вашего другого ответа?
Дэвид Эйк
@DavidEyk (это мой первый ответ) не совсем, он больше зависит от структуры hashmap (будь то bigtable-like или in-memory). Причина, по которой я снова ответил, заключается в том, что меня беспокоили коллизии хешей, приводящие к низкой производительности - по крайней мере, в хэш-карте в памяти. Мой другой ответ будет работать лучше для большего количества элементов и структуры в памяти - где это будет работать лучше, если это будет в SQL / и т. Д.
Джонатан Дикинсон