Скажем, вы хотите создать 3D-игру и позволить игрокам или мобильным игрокам отслеживать других существ, следуя их следам запахов. Есть ли известная структура данных, которая соответствует этому варианту использования?
Если у вас мало людей, возможно, вы можете сделать что-то вроде карты трехмерных координат и идентификатора объекта, но настоящий аромат работает по-другому, потому что он исчезает со временем, но медленно. И в большинстве случаев вы можете только приблизительно узнать, что там произошло, и приблизительно, сколько всего таких вещей было там. И приближение становится худшим со временем, пока не прошло.
Я предполагаю, что это похоже на то, чтобы начать с точного числа и постепенно терять наименее значимые цифры, пока вы не потеряете и самую значимую цифру. Но это не очень помогает мне, потому что идентификаторы сущностей обычно не кодируются, чтобы содержать тип сущности, в дополнение к его индивидуальному идентификатору.
Ответы:
Существует множество вариантов того, как вы можете это сделать; Я собираюсь предложить «очевидный для меня» выбор, но есть много вариантов, которые могут быть разработаны. Отказ от ответственности: я на самом деле не реализовал ничего подобного.
Во-первых, вам нужна структура данных, которая охватывает ваш мир. Если вы выполняете перемещение NPC в трехмерном пространстве, то, вероятно, у вас есть или в конечном итоге понадобится такая структура для целей поиска пути - скажем, навигационная сетка. Итак, давайте предположим, что мы можем добавить поле для ароматов к этому.
Итак, что мы вкладываем в это поле? Я предлагаю список записей ( запах , сила , время ). Этот список хранится на максимальной длине или ниже и сортируется по силе, поэтому слабые запахи будут отбрасываться. Запах может быть что - то явно определено для каждого объекта или объекта типа, или это может быть просто тип объекта - в зависимости от того, что вы хотите , чтобы иметь возможность отслеживать отчетливо. Время является отметка о времени, когда в последний раз был обновлен этот аромат запись.
Когда объект проходит через область (например, заданный треугольник навигационной сетки), пора обновить список запахов. Во-первых, уменьшите все сильные стороны в соответствии с количеством времени, прошедшего в соответствии со значением времени по сравнению с текущим временем - экспоненциальный спад, вероятно, является здесь разумным выбором. Затем добавьте запах текущего объекта в список, возможно, с силой, зависящей от типа объекта. Тогда, если список стал слишком длинным, отбросьте самую низкую силу.
Чтобы получить результат отслеживания, найдите аромат в списке для текущего местоположения, затем сделайте то же самое для всех его соседей и пройдите в направлении самого сильного запаха (это не то направление, из которого только что пришел трекер).
Для дополнительного реализма:
Распространение: периодически передавайте часть аромата в каждом месте своим соседям. Это сбивает с толку следы, но также означает, что стационарные вещи могут быть обнаружены (поиск пищи, трупов и т. Д.). (Это даже признанный ИИ, основанный на действиях, основанных исключительно на этом типе информации - ландшафт предоставляет информацию о том, каким путем можно получить конкретный ресурс и т. Д. Я забыл его название.) Основным недостатком является затраченное время. расчет диффузии везде.
Сильные запахи должны предотвращать обнаружение слабых запахов; разделите силу искомого запаха на силу самого сильного запаха и потерпите неудачу, если он слишком мал. Это может позволить преднамеренно запутать след человека.
источник
Я бы изменил технику, называемую картированием влияния, чтобы создать карту для ароматов. Он будет рассеиваться и исчезать естественным образом, смешиваться и соперничать с другими ароматами и, возможно, больше. Похоже, это будет делать именно то, что вам нужно, но это может быть более сложным, чем то, что вы хотите реализовать. По крайней мере, это должно дать вам несколько хороших идей, и это довольно просто реализовать поверх любой структуры, которую вы сейчас используете.
Учебник / объяснение, которое я нашел полезным.
источник