OberonCore

Есть такая широко известная игра точки.

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

У кого какие идеи относительно построения такого алгоритма и его реализации?

PS. Интересно было бы посмотреть насколько помогают/мешают средства различных ЯП для решения вот этой вот задачи. Так что предлагаю выкладывать сюда рабочие реализации алгоритма на различных ЯП: C, CP, CPP, Haskell, Python, etc. Будет наглядно видно читабельность алгоритма, скорость его работы, и, возможно. влияение языка на мышление.

PS. Не забываем что нужно не только найти контур, но и его нарисовать. Предположим у нас для этого есть некая функция DrawLine(Point, Point, Color) ну и для рисование точки DrawPoint(Point,Color)

Вот тут имеется java-версия точек. Поиграл немного, оказалось что они тоже неверно определяют обводку. Во вложенном файла пример неправильного определения красной обводки.

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

Алгоритм тут, видимо, должен быть - распространение волны из внешнего пространства. Учитывающее точки заданного цвета.

На днях студенту собираюсь предложить реализовать.

На входе у нас последовательность ходов. Ходы всегда чередуются. Ход синих, ход красных, снова ход синих и т.д. Ход -- это всегда новая точка. У точки есть цвет, координаты. Координаты точек никогда не совпадают. На выходе у нас должна быть правильная картина последовательных окружений. В конечном итоге да, должно быть множество DrawLine(Point, Point, Color) (в таком виде порядок рисования вроде как значения не имеет).

Ну, там есть ещё пожалуй пара тонкостей.
А на чем будет реализовывать студент? А, главное, что? Собственно саму игру (на двух человек) или же лишь какой-то кусок?

Игру, на пару человек - чтоб щёлкать по очереди мышкой.

Реализовывать, естественно, на КП.

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

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

Обычный волновой метод нужен.

Ну, попробуйте реализовать нечто рабочее

Волновой это один из возможных вариантов. Задачка хороша тем что вариантов множество. + тут интересно посмотреть как народ формализует задачу.

А попавшие в собственное окружение "живые" точки в чей баланс записываются? Т.е. должен ли я при построении области избегать окружения своих?

Ни в чей. Считается сколько ты окружил чужих а не сколько сохранил своих. Окруженные тобой твои просто лучше защищены от окружения противником. Вообще, см. вики -- там подробно расписаны правила.

Там не совсем ясно.

Например, если я окружил противника, а он внутри держит в окружении моих - то они не считаются его? Типа, я их освободил, так? ))

Так.

Процесс идёт )) Задачка действительно тонкая. Общая идея ясна, но "дьявол в деталях".

Докладаю ))

Играет программулина, кучу тонких мест вроде разрешили; вот остался нюанс с окружением - если в пустую область ставится точка противником, которая достраивает свою область. Но тоже ясно уже, как делать...

Вот мой вариант решения на C++
Для запуска понадобятся библиотеки Qt.

Так )) Пора выкладывать нашу игру.
Мы тут уже два дня рубимся в сетевую версию ) Работа стоит )

Надо причесать и завтра постараться опубликовать.

Чо-то глючит оно: