на прошлой неделе я работал над системой инвентаризации с 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. Я даже не уверен, что ключевым моментом здесь является упаковка бина, потому что, правда, у меня может быть более одной сумки, но в нашей игре это будет только одна сумка. Итак, дело в том, чтобы поместить вещи в «одну» сумку, и не более того. Так что примеры в этом видео (трубы и автобусы) не совсем соответствуют моей проблеме. Также смотрел некоторые вещи об этом рюкзаке, я не видел, как «ценность» связана с моими предметами / инвентарем, но я думаю, что «вес» такой же, как объемность, не уверен.
Ответы:
Это вариант проблемы с рюкзаком. Как Дэнни Пфлюгофт упоминает, что это NP-Complete. Это означает, что это не может быть решено за линейное время, если я правильно помню.
Но вы можете попытаться решить эту проблему в несколько шагов. Это в основном проблема сортировки.
Я бы начал с расчета «громоздкости» каждого элемента: это можно рассчитать несколькими способами:
громоздкость = max (длина, ширина);
громоздкость = длина * ширина
громоздкость = sqrt (длина * ширина)
Затем начните складывать предметы с наибольшим количеством очков в инвентарь. Так как они, скорее всего, не поместятся в оставшееся пространство позже. Мелкие предметы подойдут всегда.
Вам нужна эвристика (причудливое название для образованного гадания ;-)) для вашей стратегии размещения. Что-то вроде попытки разместить предметы в первом свободном слоте сверху слева или что-то в этом роде.
Думаю, стратегия сортировки инвентаря Diablo II работала несколько схоже. Такие вещи, как мечи и копья, в конечном итоге окажутся слева вверху, затем одежда и доспехи, затем баклер и так далее.
Я думаю, что вам действительно нужно попробовать это и настроить алгоритм (другой объемный расчет, другой эвристический), пока он не будет работать достаточно разумно.
источник
Хаха, @ Всем, кто помог, спасибо. Мне удалось наконец решить это. Вот что я в основном сделал:
ОБНОВИТЬ:
Я создал массив, в котором хранятся индексы всех добавленных элементов, поэтому мне не нужно искать и искать занятые слоты, чтобы освободить их - большое повышение.
нет необходимости добавлять в последний слот, фактически иногда это может не сработать, я добавил нужный элемент к остальным другим элементам и отсортировал их вместе с ними.
Как вы можете видеть из видео, его нужно немного оптимизировать, сортировка не идеальна, я бы хотел использовать полную упаковку бинов, но она уже снижает производительность. Я открыт для любых предложений по оптимизации, еще раз спасибо :)
источник