Comments 2
Спасибо, по алгоритмам очень полезно было почитать. Про чатик правильно подмечено, что он зачастую отнимал немало времени, но без него было бы не то, ой не то.
Большое спасибо за Вашу статью. После прочтения её и статьи от Commandos, я стал понимать, почему мой лучший результат был таким не радужным (удалось войти в первую сотню, и то не надолго, в основном на 100-200 местах болтался).
Моя стратегия была намного проще.
Ключевым местом в механизме принятия решений была цепочка правил, которые срабатывали в зависимости от ситуации вокруг или передавали управление дальше по цепочке.
Первые несколько версий вообще не умели в поиск пути, а обход препятствий осуществлялся по факту застревания. Волшебник просто ходил за союзными миньонами, пока не натыкался на противников и не срабатывало более приоритетное правило.
После был прикручен обход препятствий по касательной. Т. е. если луч, построенный от центра волшебника до цели пересекал окружность с центром в центре препятствия и радиусом равном сумме радиусов волшебника и препятствия, то результирующий угол поворота волшебника отклонялся минимальную величину, при которой траектория волшебника шла по касательной к препятствию.
Через несколько игр я обнаружил, что подбор бонусов дает ощутимое преимущество, после чего пришлось реализовывать полноценный поиск пути по путевым точкам в дополнение к обходу препятствий. За основу был взят алгоритм Ли, с добавлением к нему возможности учет веса вершин и ребер графа (вес ребер зависел от длины ребра и наличия на ребре врагов, а вершины только от наличия врагов). Граф состоял всего из 5 точек: углы карты и центр. Для реализации плавного движения, в окрестностях точек результирующее направление движения получалось сложением углов до ближайшей точки и до следующей.
К сожалению, после второго раунда у меня совершенно не осталось времени на стратегию. К тому же, я писал код из расчета на один раз и он, в конце концов, превратился в слабочитаемую лапшу из костылей.
Последнее, изменение при поиске пути было сделано уже после финала. Я попытался воспользоваться методом потенциальных полей вместо обхода пути по касательной, но, к сожалению, такое решение только ухудшило ситуацию.
Не уверен, что кому-то интересны подробности реализации работы моей стратегии, потому, если кому интересно, можете поковырять код по ссылке. За боль в области глаз при взляде на этот код, ответственности не несу. Вы были предупреждены.
Моя стратегия была намного проще.
Ключевым местом в механизме принятия решений была цепочка правил, которые срабатывали в зависимости от ситуации вокруг или передавали управление дальше по цепочке.
Первые несколько версий вообще не умели в поиск пути, а обход препятствий осуществлялся по факту застревания. Волшебник просто ходил за союзными миньонами, пока не натыкался на противников и не срабатывало более приоритетное правило.
После был прикручен обход препятствий по касательной. Т. е. если луч, построенный от центра волшебника до цели пересекал окружность с центром в центре препятствия и радиусом равном сумме радиусов волшебника и препятствия, то результирующий угол поворота волшебника отклонялся минимальную величину, при которой траектория волшебника шла по касательной к препятствию.
Через несколько игр я обнаружил, что подбор бонусов дает ощутимое преимущество, после чего пришлось реализовывать полноценный поиск пути по путевым точкам в дополнение к обходу препятствий. За основу был взят алгоритм Ли, с добавлением к нему возможности учет веса вершин и ребер графа (вес ребер зависел от длины ребра и наличия на ребре врагов, а вершины только от наличия врагов). Граф состоял всего из 5 точек: углы карты и центр. Для реализации плавного движения, в окрестностях точек результирующее направление движения получалось сложением углов до ближайшей точки и до следующей.
К сожалению, после второго раунда у меня совершенно не осталось времени на стратегию. К тому же, я писал код из расчета на один раз и он, в конце концов, превратился в слабочитаемую лапшу из костылей.
Последнее, изменение при поиске пути было сделано уже после финала. Я попытался воспользоваться методом потенциальных полей вместо обхода пути по касательной, но, к сожалению, такое решение только ухудшило ситуацию.
Не уверен, что кому-то интересны подробности реализации работы моей стратегии, потому, если кому интересно, можете поковырять код по ссылке. За боль в области глаз при взляде на этот код, ответственности не несу. Вы были предупреждены.
Sign up to leave a comment.
Как искать путь к победе на Russian AI Cup 2016, но не в том направлении