Здравствуйте, господа :) У меня есть задача.
Имеется карта, которая должна обладать проходимыми и не проходимыми участками (например, стенами). Данная карта имеет 2 типа объектов: сборщик мусора и источник мусора. Эти объекты перемещаются только по проходимым участкам, огибая препятствия. Источники мусора должны перемещаться по карте случайным образом и в случайные моменты времени оставлять за собой мусор. У сборщиков мусора должна быть определенная зона видимости, и они должны патрулировать карту с целью обнаружения (в радиусе своей видимости) мусора и его захвата. У них должен быть ограниченный объем вместимости мусора и ограниченный запас электроэнергии. Разгрузка мусора должна осуществляться в специальной локации – свалке, а подзарядка батарей должна производиться на базе. При этом сборщик мусора должен учитывать запас энергии, чтобы суметь добраться до базы для подзарядки.
Вроде все нормально, но только вот я в 1ый раз делаю такую игру (сам взял, давно хотел начать), и опыта вообще нету. Сделал карту, есть возможность задания расположения базы, свалки, стен. Сейчас думаю, как сделать логику, но не выходит, куча вариантов, не знаю какой выбрать, и кручусь на месте. Вот есть база, выходит из нее робот, каким должно быть поведение робота- сборщика, чтобы оно все- таки в какой- то степени походило на целенаправленное движение по поиску мусора, т.к. случайное перемещение все- таки было бы (наверное, не естественно и глупо). Может быть задать область впереди 10 клеток, и случайным образом направляться туда в надежде найти мусор?Как организовать передвижение обратно?Все время следить за уровнем энергии и пересчитывать путь до базы A- алгоритмом?Помогите пожалуйста.
Если разрешен фейк, что мусоросборщику известна вся карта, то можно его направлять в то место, где скопление мусора.
Путь назад все время считать по полностью известной карте.
Если фейк не разрешен, то каждый сборщик может собирать информацию о карте сам по методу муравьев. Начальная цель - идти к рандомному маяку на неразведанной карте. С его точки зрения он оставляет за собой след, который наносит на свою карту (и другие сборщики тоже оставляют в его персональной карте след, если он их увидел). Правило для мусоросборщика - это избегать этих следов, поскольку мусор там недавно собран. Следы постепенно остывают.
У альянса сборщиков синхронизированная карта следов и разведанной местности, если по сюжету у них по сюжету есть средства связи (синхронизация зависит от типа средств связи, но это детали).
Путь назад все время считать только по разведанной области.
(ну а как бы еще нормальный человек решал такую задачу, если бы был сборщиком?)
PS Еще б прогнозировать, сколько мусора можно собрать на обратном пути, нужно ли ехать на свалку через базу или на базу через свалку.
Карта большая? Если не очень, то можно один раз для каждой ячейки просчитать, сколько нужно энергии на возвращение с этой ячейки на базу и потом просто сравнивать это значение с текущим уровнем энергии.
Алгоритмы поиска мусора могут быть самыми разнообразными, всё зависит от уровня "интеллекта" и скоординированности сборщиков. Простейший вариант - выбирать случайную точку и двигаться туда, по пути высматривая мусор. Другой вариант - движение по предзаданной траектории (раз уж речь идёт о патрулировании). Либо все сборщики могут двигаться по одной и той же траектории друг за другом с заданными интервалами, либо можно всю территорию разбить на сектора, каждому сборщику выделить определённый сектор и проложить для него траекторию в границах этого сектора.
Можно комбинировать - разбить на сектора, а потом внутри сектора выбирать случайную точку.
Ещё можно иметь несколько шаблонов движения (змейка, спираль, звезда, прямо вперёд...) и переключаться между ними по случайному триггеру.
Более сложные варианты - это уже можно запоминать уже вычищенные участки, запоминать частоту образования мусора в различных областях карты, визуально отслеживать источники мусора и преследовать их, и т.д.... ;)
Про возвращение, главный вопрос - мусор мешает проехать?
Если да, то все плохо.
Если нет - то есть 2 варианта
- карта известна - kirlan правильно сказал, что нужно посчитать сколько энергии надо и куда ехать для возврата из любой точки. Причем для любого размера карты, достаточно 1 раз пустить волну из базы по всей карте.
- карта неизвестна - тогда по способу Chipmunk, постоянно пересчитываем маршрут до базы по известной области.
CoolDev
"Волна" в любом случае нужна. Просто ее нужно изменять появляющимся/исчезающим "мусором".
После этого будь хоть тысяча сборщиков, любой из них будет проверять только клетки вокруг себя. Единственным препятствием останется "живая очередь", но чем-то ради быстроты придется пожертвовать.
CasDev
Мусор может заблокировать проезд и не дать мусорщику зарядится. К мусору добавятся разряженные мусоровозы :) Так что там сложно все, с непроезжабельным мусором.
kirlan
> Карта большая? Если не очень, то можно один раз для каждой ячейки просчитать,
> сколько нужно энергии на возвращение с этой ячейки на базу и потом просто
> сравнивать это значение с текущим уровнем энергии.
Ну да, я тоже так подумал, что если количество энергии 50, то свободное путешествие можно совершить в размере 25 шагов (путь до мусора + путь до свалки).
kirlan
> можно всю территорию разбить на сектора, каждому сборщику выделить определённый
> сектор и проложить для него траекторию в границах этого сектора.
kirlan
> Ещё можно иметь несколько шаблонов движения (змейка, спираль, звезда, прямо
> вперёд...) и переключаться между ними по случайному триггеру.
>
> Более сложные варианты - это уже можно запоминать уже вычищенные участки,
> запоминать частоту образования мусора в различных областях карты, визуально
> отслеживать источники мусора и преследовать их, и т.д.... ;)
Кстати, да, офигенные варианты, спасибо. И правда можно разбить на секторы, каждый сборщик мусора будет проезжать внутри сектора и например выполнять некоторую случайную (или нет) траекторию движения внутри сектора.
CoolDev
> К мусору добавятся разряженные мусоровозы :)
Ага, придется создавать сборщиков для сборщиков :D
Chipmunk
> С его точки зрения он оставляет за собой след, который наносит на свою карту (и
> другие сборщики тоже оставляют в его персональной карте след, если он их
> увидел). Правило для мусоросборщика - это избегать этих следов, поскольку мусор
> там недавно собран. Следы постепенно остывают.
Да, тоже очень офигенный вариант, так например, можно будет попробовать распаралелить сканирование секторов
Всем спасибо, НО если будут еще идеи, напишите, буду рад !
Манать у Вас всех столько идей, мне бы так
ICE3141592
Это не то чтобы идеи, это во многом сколлекционированные грабли :) Просто купи каску и начинай писАть :)
Тема в архиве.