Доброго времени суток, уважаемые! К сожалению, из-за больничного режима, я не мог последний месяц опубликовать своё очередное изыскание на тему игры «Морской бой». Надеюсь, моя заметка окажется для кого-то полезной, и, даже если и будет частичным повторением, то в новой интерпретации.
Итак, сегодня я хотел бы обсудить вопрос расстановки (не оптимальной, а произвольной) кораблей перед боем. Слева вы видите пример результата работы рассматриваемого далее алгоритма: корабли в форме букв «R», «A», «H», «B» расставлены на игровом поле размером 5х15 с несколькими запрещёнными к использованию клетками (помечены зелёным цветом). Заинтересовавшихся прошу под кат.

Доброго времени суток, уважаемые! Так случилось, что вопросом программирования более-менее адекватного ИИ для игры «морской бой» я озадачился где-то в конце 2004 года. Быть может я, не имея должных руководств под рукой, изобретал тогда велосипед, но и в последствии, мне попадались потрясающие своей честностью алгоритмы: стрелять наобум, время от времени подглядывая у игрока расположение кораблей, для выравнивания баланса. В последствии я несколько раз улучшал алгоритм. По последним статьям на Хабре можно судить, что тема актуальна, к тому же — мне есть что добавить к написанному другими пользователями.
Итак, цель моей заметки: реализация оптимальной одной из стратегий атаки на корабли соперника, причём не только первое попадание, но и последующее «сопровождение ко дну». Отмечу, что корабли в моей реализации — почти (об этом ниже) произвольной формы.

Доброго времени суток!

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