Здравствуйте, VovkaMorkovka, Вы писали:


P>>Ну например waypoints. Посмотри например как в контре боты сделаны.
VM>waypoints — это, конечно, хорошо, спасибо за ответ.
VM>А как там сделано продвижение группы ботов, у меня как раз группа?

Не помню уже точно как они там бегают группами, вроде есть один "ведущий", а отсальные просто бегту за ним, т.е. по вейпоинтам бежит только 1, а остальные проотс кучкуются. Но там разные боты есть соответвенно они по разному бегают

Что бы придать ботам интеллекстулаьности и намёка на "групповые действия" можно реализовать всякие "фишечки"
Например в обороне:
1. Разделить карту на "зоны". Для каждой "зоны", задать "угрожаемые направления", например если за зону приняли комнату, то угрожаемыми направлениями могут стать двери и вентиляционные люки, откуда могут "переть" враги. Внутри зоны можно зарание расставить вэйпоинты с оптимальными позициями для обороны от "угрожаемых зон", причём фэйпоинты могут кроме информации о координатах содержать и другую полезную инфу, например наиболее выгодную "позу" (сидеть/лежать/стоять), направления куда надо время от времени "поглядывать на всякий случай" и т.д. Соответвенно группа ботов распределяет между собой угрожаемые направления, занимает оптимальные позиции для обороны.
2. Внутри каждой зоны могут быть дополнительгые угрожаемые зоны, например за предметами внутреннего интерьера (за ящиками), куда могут занырнуть прорвавшиеся внутрь враги. Такие зоны могут иметь нести дополинтельную инфорамцию о местах откуда выгоднее её обстреливать, например если враг за ящиком, то выгоднее забраться повыше, или может быть явно указано что в эту зону выгодно кидать гранаты, если там враг.

В наступлее соответвенно, посотмри как дивгается спецназ, они идут гуськом, при этом каждый член отряда держит под прицелом какую-то "угрожаемую зону", если таких угрожаемых зон меньше чем бойцов, то некоторые будут "на подхвате". Тот кто идёт спереди соответственно держит фронт, тот кто сзади тыл, те кто внутри группы держат фланги и поддерживают огнём первого и последнего.
Группа как праивло идёт от одной выгодной позици к другой, старается не привлекать к себе внимания, если есть контакт, то кто-то из группы может остановиться и "прикрывать огнём", а остальная часть группы резвым темпом рассыпается по выгодным позициям, кактолько кто-то из группы занял выгодную позицию он берёт на себя задачу "прикрывания", а тот кто прикрывал первым, если ещё жив, пытается свалить.
Как праивло группы стараются не вступать в бой в невыгодных для себя условиях и сначала занять какую-то более менее выгодную позицию. При этом практически всегда врага кто-то должен "занять/отвлеч" это как праивло прикрывающий, он даёт время группе с меньшими потерями занять выгодные позиции. Как правило это жертва, но тут как в шахматах, зачастую допустимо пожертвоавть пешку что бы выиграть позиционное преимущество.

В любом случае чем больше всякой полезной информации будет зарание рсположено на карте (выгодные нычки, где можно засеть, и куда надо обязательно заглянуть если идёшь мимо, всякие обходные пути и т.д.) тем легче будет написать вменяемых ботов.

Здравствуйте, VovkaMorkovka, Вы писали:


P>>Ну например waypoints. Посмотри например как в контре боты сделаны.
VM>waypoints — это, конечно, хорошо, спасибо за ответ.
VM>А как там сделано продвижение группы ботов, у меня как раз группа?

Как в контре сделано не знаю, но почему бы не взять пример с реала: сделать один из ботов в группе ведущим (командиром), а остальных из этой группы ведомыми (подчинёнными). При этом ведущий вычисляет путь и двигается по нему. Ведомые выплясывают некое подобие строя относительно ведущего. При этом ведущий может командовать ведомыми, указывать им желаемое положение относительно себя.
Как разновидность: ведущим может быть невидимый объект-помощник, который командует группой ботов.

Здравствуйте, VovkaMorkovka, Вы писали:

VM>Здравствуйте господа, я пишу счас игрушку в которой необходимо найти алгоритм движения группы ботов по прямоугльной карте к игроку, у меня есть такие варианты:
VM>1. Алгоритм A* для каждого, проблема в том, что он ищет путь непосредственно к игроку на что тратится процессорное время, а игрок — то движется, соответственно куча времени тратится вустую
VM>2. Алгоритм альфа — бета отсечения опять — же для каждого, проблема в том, что может не найти путь.
VM>3. Алгоритм трассировки — проблема в том, что не подходит для вогнутых фигур или надо сильно долго мурыжиться
VM>У кого есть какие варианты, буду рад любым конструктивным ответам? А может есть алгоритм учитывающий передвижение именно группы?
VM>p.s. Про алгоритм Дейкстры знаю, но он по моему здесь не подходит

Если ботов немного, то чем тебе A* не подходит?
при нормальной его реализации времени требует совсем мало.
В стратегах, где приходится постоянно искать маршруты для больших куч юнитов применяют подобные фичи:
1. Поиск пути для командира отряда. Для остальных поиск ведётся в точку возле командира (для сохранения строя). Если цель далеко, то обновления
каждые N игровых тактов
2. Уровень детализации. Сначала ищем маршрут на карте путей с меньшим разрешением, потом уточняем найденный маршрут.
3. дополнительные связи между элементами графа (карты путей). Вместо варианта с 8ю соседями можно взять больщее расстояние.
4. Отказ от stl'ных списков, и всего что использует операторы new\delete и же с ними- выделение памяти под новый элемент списка- слишком медленая операция. Вообще от списков стоит отказаться, если работаешь на растровой карте, юзай массивы.
5. Список closed в А* можно вообще убрать, вместо него помечать каждый узел
6. В качестве списка open очень хорошо работает двоичная куча. На больших картах она работает ОЧЕНЬ быстро.
7. Разбиение на комнаты\подобласти. Как правило это области, из любой точки которой можно безпрепядственно добраться в другую (выпуклые),
или области, для которых уже рассчитаны готовые маршруты. Обычно задание этих областей скидывают на дизайнеров уровня, но если напрячь мозги можно и автоматизировать.

вообщем пункты 4,5,6 ускоряют производительность как минимум раз в 10

Здравствуйте господа, я пишу счас игрушку в которой необходимо найти алгоритм движения группы ботов по прямоугльной карте к игроку, у меня есть такие варианты:
1. Алгоритм A* для каждого, проблема в том, что он ищет путь непосредственно к игроку на что тратится процессорное время, а игрок — то движется, соответственно куча времени тратится вустую
2. Алгоритм альфа — бета отсечения опять — же для каждого, проблема в том, что может не найти путь.
3. Алгоритм трассировки — проблема в том, что не подходит для вогнутых фигур или надо сильно долго мурыжиться
У кого есть какие варианты, буду рад любым конструктивным ответам? А может есть алгоритм учитывающий передвижение именно группы?
p.s. Про алгоритм Дейкстры знаю, но он по моему здесь не подходит

Ну например waypoints. Посмотри например как в контре боты сделаны.

P>Ну например waypoints. Посмотри например как в контре боты сделаны.
waypoints — это, конечно, хорошо, спасибо за ответ.
А как там сделано продвижение группы ботов, у меня как раз группа?

Здравствуйте, VovkaMorkovka, Вы писали:


P>>Ну например waypoints. Посмотри например как в контре боты сделаны.
VM>waypoints — это, конечно, хорошо, спасибо за ответ.
VM>А как там сделано продвижение группы ботов, у меня как раз группа?

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

Здравствуйте, VovkaMorkovka, Вы писали:

В общем столкнулся я со следующей проблемой: когда боты окружили моего игрока со всех сторон, остальные продолжают искать путь, поскольку пути нет ищут его долго. Есть — ли какой нибудь алгоритм чтобы разрулить эту ситуацию? Я нашел алгоритм заливки, но он добавляет нагрузки процессору, причем довольно нехило... Т.е. говоря другими словами, подскажите, плиз, быстрый алгоритм заливки. Возможно такой, который применим в данной ситуации. Либо какой другой метод, чтобы разрулить проблему с окружением игорка ботами.

Здравствуйте, VovkaMorkovka, Вы писали:

VM>В общем столкнулся я со следующей проблемой: когда боты окружили моего игрока со всех сторон, остальные продолжают искать путь, поскольку пути нет ищут его долго. Есть — ли какой нибудь алгоритм чтобы разрулить эту ситуацию? Я нашел алгоритм заливки, но он добавляет нагрузки процессору, причем довольно нехило... Т.е. говоря другими словами, подскажите, плиз, быстрый алгоритм заливки. Возможно такой, который применим в данной ситуации. Либо какой другой метод, чтобы разрулить проблему с окружением игорка ботами.

Сделать так чтобы не бот искал игрока, а игрок бота? По идее это должно работать намного быстрее не только в описанном случае, но и во всех остальных. Какой смысл вызывать поиск пути для каждого бота если можно найти кратчайший путь за один проход?

Здравствуйте, Аноним, Вы писали:

А>Сделать так чтобы не бот искал игрока, а игрок бота? По идее это должно работать намного быстрее не только в описанном случае, но и во всех остальных. Какой смысл вызывать поиск пути для каждого бота если можно найти кратчайший путь за один проход?

Спасибо, весьма хорошая мысль, буду пробовать

Здравствуйте, Аноним, Вы писали:

А>Сделать так чтобы не бот искал игрока, а игрок бота? По идее это должно работать намного быстрее не только в описанном случае, но и во всех остальных. Какой смысл вызывать поиск пути для каждого бота если можно найти кратчайший путь за один проход?

В общем я подумал — не получается так как Вы предлагаете. Дело в следующем: бот ведь тоже может быть не достижим от игрока, т.е. находиться в окружении других ботов. В случае, когда бот ищет и находится в окружении определение того, что до игрока дойти нельзя происходит довольно быстро. Я попробую применить другую стратегию:проверять находится — ли игрок в окружении, т.е. внутри замкнутого контура из непроходимых клеток. Соответственно родился вопрос: подскажите максимально быстрый алгоритм заливки...

Здравствуйте, VovkaMorkovka, Вы писали:

VM>Здравствуйте, VovkaMorkovka, Вы писали:

VM>В общем столкнулся я со следующей проблемой: когда боты окружили моего игрока со всех сторон, остальные продолжают искать путь, поскольку пути нет ищут его долго. Есть — ли какой нибудь алгоритм чтобы разрулить эту ситуацию? Я нашел алгоритм заливки, но он добавляет нагрузки процессору, причем довольно нехило... Т.е. говоря другими словами, подскажите, плиз, быстрый алгоритм заливки. Возможно такой, который применим в данной ситуации. Либо какой другой метод, чтобы разрулить проблему с окружением игорка ботами.

Ну начать надо с того что бы опредлится какое поведение бота в такой ситуации ты считаешь правильным?
Например я бы попробовал сделать так — когда при поиске пути бот натывается на другого бота, он "спрашивает" его не знает ли тот путь к игроку? Если тот бот знает точный путь (он уже приёшл к игроку) он просто указывает спраасившему кротчайший путь — на этом поиск заканчивается.
Что бы бот не пытался ломится через своего товарища, можно проверить — если тот бот тсоит очень близко к игроку, то поиск прекращается, если бот стоит далеко, то просто ищется обходной путь, таким образом что бы можно было обежать преградившего дорогу бота и попасть на указанный им путь. Причём если этот поиск обходного пути вокруг преградившего дорогу бота не увенчался успехом в 10-20 иттераций, то считать что обежать невозможно.

Здравствуйте, VovkaMorkovka, Вы писали:

А>>Сделать так чтобы не бот искал игрока, а игрок бота? По идее это должно работать намного быстрее не только в описанном случае, но и во всех остальных. Какой смысл вызывать поиск пути для каждого бота если можно найти кратчайший путь за один проход?

VM>В общем я подумал — не получается так как Вы предлагаете. Дело в следующем: бот ведь тоже может быть не достижим от игрока, т.е. находиться в окружении других ботов. В случае, когда бот ищет и находится в окружении определение того, что до игрока дойти нельзя происходит довольно быстро. Я попробую применить другую стратегию:проверять находится — ли игрок в окружении, т.е. внутри замкнутого контура из непроходимых клеток. Соответственно родился вопрос: подскажите максимально быстрый алгоритм заливки...

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

Здравствуйте, Phoenics, Вы писали:


P>Например я бы попробовал сделать так — когда при поиске пути бот натывается на другого бота, он "спрашивает" его не знает ли тот путь к игроку? Если тот бот знает точный путь (он уже приёшл к игроку) он просто указывает спраасившему кротчайший путь — на этом поиск заканчивается.

Я сделал так, использовал рекурсивный алгоритм заливки от игрока с некоторой глубиной рекурсии. Глубина зависит от количества ботов, если заливка дошла до клетки с некоторым расстоянием от той, в которой находится игрок, то игрок не окружен и можно к нему двигаться. Это самое расстояние от клетки игрока до той в которую надо придти как раз и регулирует глубина рекурсии.
Возможно будет проблема "пробки". Т.е. представим себе туннель, игрок и основная масса ботов посередине, т.е. делят туннель на две части. Выход из окружения есть, но не в ту часть туннеля в котором находится ищущий бот.

Выхода из этой ситуации я вижу два:
1) Делать карту такой, чтобы всегда существовал хотябы один путь из одной части в другую
2) Некоторым образом определить, что образовалась пробка, и применить алгоритм заливки чтоб определить в какой части карты находится бот
3) Для всех ситуаций я ограничиваю число итераций делая его равным, скажем 300 причем поиск произвожу не сразу для всех ботов, а помещаю каждого бота в очередь, на один игровой цикл у меня не более одного поиска для бота, а может быть и меньше.


P>Что бы бот не пытался ломится через своего товарища, можно проверить — если тот бот тсоит очень близко к игроку, то поиск прекращается, если бот стоит далеко, то просто ищется обходной путь, таким образом что бы можно было обежать преградившего дорогу бота и попасть на указанный им путь. Причём если этот поиск обходного пути вокруг преградившего дорогу бота не увенчался успехом в 10-20 иттераций, то считать что обежать невозможно.

А так может не получится потому, что может существовать длинный обходной путь из одной части карты в другую, бот походит — походит вокруг и не найдет пути хотя он, возможно и есть.

VM>А так может не получится потому, что может существовать длинный обходной путь из одной части карты в другую, бот походит — походит вокруг и не найдет пути хотя он, возможно и есть.

Это реалистично, т.к. эмитируется незнание ботов топологии карты. Человек бы тоже наткнувшись на пробку в узком месте из союзника не побежал бы через полкарты а побродив децел рядом подождалбы пока препятские исчезнет (союзник уйдёт) или попытался бы его убрать — например попросить прегродившего путь отойти.

Есть толпа ботов, боты используют для поиска клетки в которую идти алгоритм A*. Из клетки в соседнюю перемещаются не скачком, а за некоторый промежуток времени. Отсюда понятно, что бот может пересекать до четырех клеток включительно. Соответственно боты могут сталкиваться. Нужно разрулить эту ситуацию, т.е. если два бота столкнулись то один должен дать пройти другому. Проблема состоит в определении того, бота, которому надо отойти + необходимо учесть то, что столкнуться могут и более чем два бота.
Всем зараннее спасибо,
Владимир

Здравствуйте, VovkaMorkovka, Вы писали:

VM>Есть толпа ботов, боты используют для поиска клетки в которую идти алгоритм A*. Из клетки в соседнюю перемещаются не скачком, а за некоторый промежуток времени. Отсюда понятно, что бот может пересекать до четырех клеток включительно. Соответственно боты могут сталкиваться. Нужно разрулить эту ситуацию, т.е. если два бота столкнулись то один должен дать пройти другому. Проблема состоит в определении того, бота, которому надо отойти + необходимо учесть то, что столкнуться могут и более чем два бота.
VM>Всем зараннее спасибо,
VM>Владимир

Есть такая книжка "Искуственный интеллект в компьютерных играх", автор если мне не изменяет память Алекс Дж. Шампандар. На озоне вроде были ещё, хотя в обычном книжном её нашёл. Там одна из первых глав про движение неигровых персонажей. Рекомендую почитать.

Здравствуйте, Phoenics, Вы писали:

P>Есть такая книжка "Искуственный интеллект в компьютерных играх", автор если мне не изменяет память Алекс Дж. Шампандар. На озоне вроде были ещё, хотя в обычном книжном её нашёл. Там одна из первых глав про движение неигровых персонажей. Рекомендую почитать.

Дык купил и читаю, но к сожалению в первых главах ничего нового для себя не нашел. Книжка дает только обзор методов, но, к сожалению не дает конкретных методов решения той или иной задачи

Здравствуйте, VovkaMorkovka, Вы писали:

VM>Есть толпа ботов, боты используют для поиска клетки в которую идти алгоритм A*. Из клетки в соседнюю перемещаются не скачком, а за некоторый промежуток времени. Отсюда понятно, что бот может пересекать до четырех клеток включительно. Соответственно боты могут сталкиваться. Нужно разрулить эту ситуацию, т.е. если два бота столкнулись то один должен дать пройти другому. Проблема состоит в определении того, бота, которому надо отойти + необходимо учесть то, что столкнуться могут и более чем два бота.

Наверно ты как-то анализируешь ситуацию для каждого бота из множества _по очереди_.
Вот первый бот, который обнаружил перед собой препятствие в виде своих товарищей, пусть им даст команду отойти, ну а если это не свои, тогда…