Здравствуйте.
Решил попробовать написать небольшую RTS и заодно расширить свою теоретическую базу. Для меня это первый опыт чего-то подобного. Очевидно, сразу столкнулся с проблемой поиска пути.
Суть проблемы: есть группы юнитов, которые должны уничтожить друг-друга. Игрок ими не управляет а просто смотрит сражение. Так вот, требуется чтобы юниты во время сражения не скапливались в кучу, наползая друг на друга, а обходили друг-друга, как препятствия. Если кто-то играл в Warcraft 3, будет понятно, о чем идет речь. Там у юнитов есть такая характеристика, как физический размер, что не позволяет им проходить насквозь.
Посмотрел алгоритм A*, но не уверен, насколько он подойдет в такой схеме, т.к. юнитов может быть довольно много и все они перемещаются. Возможно, какая-нибудь модификация этого алгоритма подойдет. Мне сложно сказать. Зная здешний контингент, пошел с вопросом сюда. Может у кого-нибудь будут мысли на этот счет.
Вот ссылка на то, что происходит без поиска пути:
http://www.fastswf.com/1BXhKwg
Сейчас запустил варкрафт, чтобы посмотреть, как там это работает. Увидел, что юниты действительно обходят друг-друга, как обычные препятствия. То есть, по-видимому, клетки, которые они занимают в данный момент времени помечаются как непроходимые.