Алгоритмы, применяемые при разработке игр.

[bllem]

А какие вы знаете/применяли?


Начну. Самая большая проблема в играх - поиск пути (будь то боты, или управление персом в логической игре). Яркий пример игра Герои меча и магии.

Мой способ решения: Создается дополнительный массив такого же размера. Далее пошаго во берется отточки отсчета все точки вокруг, на которые можно ступить, и проставляются туда 1, дальше от каждой единицы в каждую свободную, и еще н занятую числом клетку выставляется число 2 и тд. Думаю, где путь увидеть не сложно

Пример
1111111
00011Х1
1011101
1000001
1000001
1111011


$$$$$$$
989$$0$
$7$$$1$
$65432$
$76543$
$$$$5$$

 

[FEOFAN]

Сегодня сдавал по этому экзамен. Читай про генетические алгоритмы.

 

[Del]

AlgoList - алгоритмы, методы, исходники

You must be registered for see links

Довольно много полезных алгоритмов. Есть что почитать.

Изучал алгоритм поиска пути, когда писал скрипты для UO (но было это давно, ничего не осталось). За основу брал

You must be registered for see links

 

[bllem]

Есть вопрос по вышке (скорее всего).
У меня есть декартова система коордиат в пространстве (xyz), и плоскость, поделенная на сектора (квадраты), каждый квадрат 5х5 юнитов. Нужно, знаяя только координаты мыши на экране вычислить на какой квадрат (массив (-беск.;+беск)) попала мышка.

Пробовал решать через отношение между вектором OZ и вектором камеры, но мало что выходит.
Пробовал находить производную от уравнения вектора камеры (tg угла наклона к OX), и расчитывать исходя из этого отношения как с обыной плоскостью, но опять же не выходит.

 

[Dre.hz]

AlgoList - алгоритмы, методы, исходники

You must be registered for see links

Довольно много полезных алгоритмов. Есть что почитать.

Изучал алгоритм поиска пути, когда писал скрипты для UO (но было это давно, ничего не осталось). За основу брал

You must be registered for see links

Спасибо за ссылки!

 

[GrAndSE]

Мой способ решения: Создается дополнительный массив такого же размера. Далее пошаго во берется отточки отсчета все точки вокруг, на которые можно ступить, и проставляются туда 1, дальше от каждой единицы в каждую свободную, и еще н занятую числом клетку выставляется число 2 и тд. Думаю, где путь увидеть не сложно

А как быть с большой картой в 3D и сложными ибьектами, которые тоже в 3D? Круто прийдётся извернуться, чтобы такое провернуть для армии в три сотни солдат, которая движется и пытается обсходить препятствия на пересеченной местности на большой карте Тут и размеры массива хороши (если конечно по определенным критериям делать "бездетальную" карту) и с размером карты все больше и больше возрастает количество необходимых операций, что явно "неположительно" сказывается на производительности.
Более интерестный и правдоподобный (в плане реалистичности поведения персонажей в игре) подход:

Муравьи и математические алгоритмы

Алгоритм, описываемый в этой статье необходимый для оптимизации процесса разработки GPS сетей, базируется на поведении муравьев - "провизиантов". Муравьиная колония разрабатывает сеть оптимальных маршрутов (кратчайших и быстрейших) к источникам пищи используя вероятностный метод проб и ошибок. Муравьи - "провизианты" отмечают свои маршруты с помощью выброса химических веществ, называемых феромонами, варьируя их количество в зависимости от качества пищи и удаленности от гнезда. Муравьи, находящие кратчайший маршрут, могут возвращаться назад и курсировать между гнездом и источником пищи, накапливая на маршруте более высокий уровень феромонов при каждом проходе. Другие муравьи, находя феромоновый след, начинают следовать ему и закрепляют его добавочными феромонами.

Такое поведение является формой автокаталитического действия: чем больше муравьев следуют по маршруту, тем более привлекательным он становится. Поведение муравьев вызвало появление алгоритма оптимизации муравьиной колонии (ACO), разработанного Marco Dorigo из IRIDIA и успешно применяемого для решения многих комплексных задач оптимизации. Основная идея, лежащая в основе алгоритма ACS заключается в использовании механизма положительной обратной связи, который помогает найти наилучшее возможное решение в сложных задачах оптимизации. Результаты, получаемые при применении алгоритмов, основанных на действиях муравьиной колонии, так же хороши, как и при применении алгоритмов, основанных на метаэвристических алгоритмах общего назначения. Алгоритм ACS, являющийся частным случаем ACO, использует колонию виртуальных муравьев, ведущих себя как кооперативные агенты в математическом пространстве, в котором они могут искать и подтверждать найденные пути (решения) в целях поиска одного наиболее оптимального. Эти пути могут содержать в себе очень много информации. Наши искусственные муравьи имеют некоторую память и не действуют вслепую. Кроме того, мы принимаем, что время дискретно, а не непрерывно. В рамках алгоритма ACS, где каждый муравей двигается по замкнутому маршруту, количество феромонов вдоль маршрута увеличивается в зависимости от качества решения, найденного муравьем.

Взял с

You must be registered for see links

- благо помнил, что есть такие алгоритмы.

 

[GrAndSE]

Есть вопрос по вышке (скорее всего).
У меня есть декартова система коордиат в пространстве (xyz), и плоскость, поделенная на сектора (квадраты), каждый квадрат 5х5 юнитов. Нужно, знаяя только координаты мыши на экране вычислить на какой квадрат (массив (-беск.;+беск)) попала мышка.

А что это выходит у тебя задано? Каковы параметры камеры? Чем она определяется в пространстве?
Если угглом наклона относительно плосколсти OXY, то единственная загвоздка может возникнуть при использовании возможности zoom. Если таковой нет, то всё фактически эллементарно.

 

[bllem]

А что это выходит у тебя задано? Каковы параметры камеры? Чем она определяется в пространстве?
Если угглом наклона относительно плосколсти OXY, то единственная загвоздка может возникнуть при использовании возможности zoom. Если таковой нет, то всё фактически эллементарно.

У меня немного осложнено - смотри вложение.

 

[GrAndSE]

У меня немного осложнено - смотри вложение.

А можно тогда на вложении написать хоть чего-нибудь? А то я не силён в трактовании абстракций

 

[bllem]

это два угла поворота - вертикальный и горизонтальный.