Авто-организованная / умная система инвентаризации?

11

на прошлой неделе я работал над системой инвентаризации с Unity3D. Сначала я получил помощь от ребят из Design3, но прошло немного времени, пока мы не разделили путь, потому что мне действительно не нравилось, как они делали свой код, у него не было никакого запаха ООП вообще.

Я сделал еще несколько шагов вперед - предметы занимают более одного слота, продвинутая система размещения (предметы стараются найти наилучшую близкую посадку), локальная система мыши (мышь попадает в ловушку в области активной сумки) и т. Д.

Вот демонстрация моей работы.

То, что мы хотели бы иметь в нашей игре, это функция автоорганизации, а не автосортировка. Мы хотим эту функцию, потому что наш инвентарь будет в режиме реального времени - не так, как в Resident Evil 1,2,3 и т. Д., Где вы могли бы приостановить игру и сделать что-то в вашем инвентаре. Теперь представьте себя в сложной ситуации, окруженной зомби, и у вас нет пуль, вы оглядываетесь вокруг, вы видите, что поблизости есть пули, поэтому вы идете за ними и пытаетесь поднять их, но они не не подходит! вы посмотрите на свой инвентарь и обнаружите, что если вы реорганизуете некоторые предметы, он подойдет! - теперь у игрока - в этой ситуации нет времени на реорганизацию, потому что он окружен зомби и умрет, если он остановится и организует инвентарь, чтобы освободить место (помните инвентарь в режиме реального времени, без пауз) - не будет разве было бы хорошо, чтобы это произошло автоматически? - Да!

(Я полагаю, что это было реализовано в некоторых играх, таких как Dungeon Siege или что-то в этом роде, так что обязательно выполнимо)

взгляните на эту картинку, например:

Что делает автосортировка

Да, так что если вы автоматически сортируете проблему, вы получите ваши пробелы, но это плохо, потому что: 1- Дорого: не требуется целой операции сортировки, чтобы освободить эти пробелы, на первом рисунке просто сдвиньте красный элемент на снизу слева, и вы получите те же пробелы, которые вы получили от автосортировки. 2- Это раздражает игрока: «Кто F сказал вам, чтобы переупорядочить мои вещи?»

Я не спрашиваю «Как написать код» для этого, я просто прошу некоторые указания, где искать, какие алгоритмы задействованы? Это связано с графиками и кратчайшими путями? Я надеюсь, что нет, потому что мне не удалось продолжить учебу в колледже: / Но даже если это так, просто скажите мне, и я изучу все, что связано.

Обратите внимание, что может быть более одного решения. Поэтому я думаю, что первое, что я должен сделать, это выяснить, является ли ситуация «разрешимой» - если я знаю, как определить, разрешима ситуация или нет, то я могу «решить» ее. Мне просто нужно знать условия, которые делают его «разрешимым». И я считаю, что для этого должен быть некоторый алгоритм / структура данных.

Вот картинка для более чем одного решения попытки уместить предмет размером 1х3:

введите описание изображения здесь

Стрелки показывают только одно из решений, но если вы посмотрите, вы найдете более одного. Это то, что я в конечном итоге не автосортировки, но найти решение и применить его.

Заметьте, что если я потрачу на это время, я придумаю способ ее решить, но это будет не самый лучший способ, это все равно, что держать руль автомобиля ногами, а не руками! XD Или просто пытаться решить проблему, которая требует массивов, но вы еще не знаете об их существовании! Так каков правильный подход к этому?

Обновления от комментария

@Stephen Я действительно не гуру в Alogs, вы упомянули «рюкзак», а @BlueRaja - Дэнни Пфлугхёфт упомянул алгоритм упаковки 2D-бинов. Они как-то связаны / одинаковы? - Я все еще не понимаю, как мне подойти к этому.

И да, я уже использую «эвристический», но я действительно не знал, что я был: D, он находит первый доступный слот и проверяет, подходит ли элемент там.

Я не знаю, будет ли работать порядок элементов, основанный на их «объемности» (которую я называю nSlotsRequired = nRowsReq * nColsRec), потому что у вас есть элементы 2x2 и 1x4, например, они имеют одинаковую объемность, но имеют разные формы и будут иметь другой эффект от того, как пойдут остальные предметы. ТАК... :/

Я смотрел это видео, мне очень понравилась идея полной упаковки, но я удивляюсь, как это сделать, поскольку инвентарь 2D. Я даже не уверен, что ключевым моментом здесь является упаковка бина, потому что, правда, у меня может быть более одной сумки, но в нашей игре это будет только одна сумка. Итак, дело в том, чтобы поместить вещи в «одну» сумку, и не более того. Так что примеры в этом видео (трубы и автобусы) не совсем соответствуют моей проблеме. Также смотрел некоторые вещи об этом рюкзаке, я не видел, как «ценность» связана с моими предметами / инвентарем, но я думаю, что «вес» такой же, как объемность, не уверен.

vexe
источник
7
Это двухмерная бин-упаковка, которая является NP-Complete. Таким образом, любой алгоритм, который скажет вам, сможете ли вы подогнать все элементы, будет неэффективным (в худшем случае). Вы можете найти довольно хорошие алгоритмы приближения, однако.
BlueRaja - Дэнни Пфлугхофт
Именно поэтому я выбрал (более распространенную в наши дни) модель инвентаря типа «один слот на элемент» вместо этого. Хотелось бы, чтобы у меня было решение, я отказался от этой проблемы ...
Ryno
@ BlueRaja-DannyPflughoeft Интересно, доступен ли простой / эффективный алгоритм, если элементы были ограничены определенными формами?
congusbongus
Ограничение форм не уменьшает сложность, а просто облегчает размышления, так что вы думаете, что сложность была обработана, аааик.
Патрик Хьюз
@VeXe Извините, я пропустил обновление вашего вопроса. Упаковка бен и рюкзак не то же самое. Но обе проблемы с упаковкой. «Ценность» в вашем случае - это форма и размер ваших предметов инвентаря.
Стивен

Ответы:

8

Это вариант проблемы с рюкзаком. Как Дэнни Пфлюгофт упоминает, что это NP-Complete. Это означает, что это не может быть решено за линейное время, если я правильно помню.

Но вы можете попытаться решить эту проблему в несколько шагов. Это в основном проблема сортировки.

Я бы начал с расчета «громоздкости» каждого элемента: это можно рассчитать несколькими способами:

  • громоздкость = max (длина, ширина);

  • громоздкость = длина * ширина

  • громоздкость = sqrt (длина * ширина)

Затем начните складывать предметы с наибольшим количеством очков в инвентарь. Так как они, скорее всего, не поместятся в оставшееся пространство позже. Мелкие предметы подойдут всегда.

Вам нужна эвристика (причудливое название для образованного гадания ;-)) для вашей стратегии размещения. Что-то вроде попытки разместить предметы в первом свободном слоте сверху слева или что-то в этом роде.

Думаю, стратегия сортировки инвентаря Diablo II работала несколько схоже. Такие вещи, как мечи и копья, в конечном итоге окажутся слева вверху, затем одежда и доспехи, затем баклер и так далее.

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

Стивен
источник
1
NP-полная - это набор задач со сложностью выше полиномиальной. Для относительно небольшого запаса (менее тысячи наименований я бы сказал :)) даже экспоненциальный алгоритм работал бы довольно быстро, потому что один шаг такого алгоритма занимает очень мало времени. Тем не менее, использование вашей идеи должно быть достаточно хорошим и простым, чем реализация алгоритма динамического программирования -> +1
MartinTeeVarga
спасибо за ответ. Да, инвентарь не должен быть потенциально бесконечным, поэтому экспоненциальные алгоритмы должны работать нормально ^^
Стивен
@ sm4: тысяча - это, как правило, огромное количество задач для NP-Complete. Помните, что эти проблемы O (2 ^ n) - даже 2 ^ 64 вычислительно невозможно!
BlueRaja - Дэнни Пфлугхофт
3

Хаха, @ Всем, кто помог, спасибо. Мне удалось наконец решить это. Вот что я в основном сделал:

IEnumerator AddItem_Sorted (Item item)
  1. Тривиальное условие: проверьте, есть ли у нас минимальные nRequiredSlots для элемента, чтобы уместиться, если у нас есть, продолжайте ...
  2. мы опустошим всю сумку - поместив элементы в заполнитель (список или что-то)
  3. добавьте нужный элемент в ОЧЕНЬ последний слот / место, в которое он может поместиться, убедившись, что он имеет горизонтальную форму
  4. используя уменьшающийся алгоритм первой подгонки, мы добавим остальные наши предметы
  5. во время добавления мы будем использовать динамическое программирование (запоминание), чтобы запомнить тот индекс, к которому мы добавляем (индекс следующего доступного слота)
  6. если все добавления успешны, нам удалось подобрать нужный товар и каким-то образом отсортировать пакет - от больших до маленьких.
  7. если мы не можем добавить все элементы, это означает, что это не было решаемой ситуацией, поэтому мы должны вернуть пакет в предыдущее состояние
  8. Один из способов сделать это (вышел из моего сознания) - скопировать состояние сумки перед всей этой операцией, а затем, если она потерпит неудачу, мы вернемся к этому предыдущему состоянию, или даже лучше, во время '' опустошая сумку, мы запоминаем, где находился каждый элемент, так что если операция не удалась, мы вернем их - используя AddItem (item, index) - по их предыдущим индексам :)
  9. весь этот процесс может занять время, поэтому мы могли бы разделить нагрузку на отдельные кадры, используя мой прекрасный выход :)
  10. СДЕЛАНО ! \ м / (@ ~ 9:00)

ОБНОВИТЬ:

  1. Я создал массив, в котором хранятся индексы всех добавленных элементов, поэтому мне не нужно искать и искать занятые слоты, чтобы освободить их - большое повышение.

  2. нет необходимости добавлять в последний слот, фактически иногда это может не сработать, я добавил нужный элемент к остальным другим элементам и отсортировал их вместе с ними.

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

vexe
источник
Пожалуйста! :) Я хотел бы поблагодарить BlueRaja - Дэнни Пфлюгофта за упоминание упаковки бина, @Stephen за идею объемности и Ричарда Бакленда за его лекцию по динамическому программированию и все лекции.
досадно