| OberonCore https://forum.oberoncore.ru/ |
|
| Алгоритмы точек. https://forum.oberoncore.ru/viewtopic.php?f=27&t=1750 |
Страница 1 из 2 |
| Автор: | Alexey Veselovsky [ Четверг, 06 Август, 2009 20:15 ] |
| Заголовок сообщения: | Алгоритмы точек. |
Есть такая широко известная игра точки. По моему, игрушка эта с т.з. алгоритмики довольна интересна даже если не углубляться в дебри создания ИИ. Ну, например алгоритм определение областей окружения с поледующей их обводкой на карте. Если решать задачу в лоб, то можно легко получить комбинаторный взрыв и, как следствие, непримемлемое время работы (а в некоторых случаях ещё и не приемлемое потребление памяти). Кстати, у большенства реализаций этой игры обводка рисуется неверно (хотя и быстро). У кого какие идеи относительно построения такого алгоритма и его реализации? PS. Интересно было бы посмотреть насколько помогают/мешают средства различных ЯП для решения вот этой вот задачи. Так что предлагаю выкладывать сюда рабочие реализации алгоритма на различных ЯП: C, CP, CPP, Haskell, Python, etc. Будет наглядно видно читабельность алгоритма, скорость его работы, и, возможно. влияение языка на мышление. PS. Не забываем что нужно не только найти контур, но и его нарисовать. Предположим у нас для этого есть некая функция DrawLine(Point, Point, Color) ну и для рисование точки DrawPoint(Point,Color) |
|
| Автор: | Alexey Veselovsky [ Понедельник, 10 Август, 2009 17:13 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Вот тут имеется java-версия точек. Поиграл немного, оказалось что они тоже неверно определяют обводку. Во вложенном файла пример неправильного определения красной обводки. Вложение:
Комментарий к файлу: Пример неправильной обводки.
points.png [ 17.93 КБ | Просмотров: 11107 ] |
|
| Автор: | Vlad [ Понедельник, 10 Август, 2009 17:30 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Alexey Veselovsky писал(а): PS. Интересно было бы посмотреть насколько помогают/мешают средства различных ЯП для решения вот этой вот задачи. Так что предлагаю выкладывать сюда рабочие реализации алгоритма на различных ЯП: C, CP, CPP, Haskell, Python, etc. Будет наглядно видно читабельность алгоритма, скорость его работы, и, возможно. влияение языка на мышление. PS. Не забываем что нужно не только найти контур, но и его нарисовать. Предположим у нас для этого есть некая функция DrawLine(Point, Point, Color) ну и для рисование точки DrawPoint(Point,Color) Давайте четче формализуем: на входе координаты точек и цвет, на выходе последовательность DrawLine(Point, Point, Color), охватывающая максимальное количество "чужих" точек и максимальную площадь. Если решений будет больше одного, то подбираем такую входную последовательность, на которой какое-то из решений будет проигрывать 
|
|
| Автор: | Илья Ермаков [ Понедельник, 10 Август, 2009 17:35 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Алгоритм тут, видимо, должен быть - распространение волны из внешнего пространства. Учитывающее точки заданного цвета. На днях студенту собираюсь предложить реализовать. |
|
| Автор: | Alexey Veselovsky [ Понедельник, 10 Август, 2009 17:56 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Vlad писал(а): Давайте четче формализуем: на входе координаты точек и цвет, на выходе последовательность DrawLine(Point, Point, Color), охватывающая максимальное количество "чужих" точек и максимальную площадь. Если решений будет больше одного, то подбираем такую входную последовательность, на которой какое-то из решений будет проигрывать На входе у нас последовательность ходов. Ходы всегда чередуются. Ход синих, ход красных, снова ход синих и т.д. Ход -- это всегда новая точка. У точки есть цвет, координаты. Координаты точек никогда не совпадают. На выходе у нас должна быть правильная картина последовательных окружений. В конечном итоге да, должно быть множество DrawLine(Point, Point, Color) (в таком виде порядок рисования вроде как значения не имеет). |
|
| Автор: | Alexey Veselovsky [ Понедельник, 10 Август, 2009 18:30 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Илья Ермаков писал(а): Алгоритм тут, видимо, должен быть - распространение волны из внешнего пространства. Учитывающее точки заданного цвета. На днях студенту собираюсь предложить реализовать. Ну, там есть ещё пожалуй пара тонкостей. А на чем будет реализовывать студент? А, главное, что? Собственно саму игру (на двух человек) или же лишь какой-то кусок? |
|
| Автор: | Илья Ермаков [ Понедельник, 10 Август, 2009 18:57 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Игру, на пару человек - чтоб щёлкать по очереди мышкой. Реализовывать, естественно, на КП. |
|
| Автор: | PGR [ Понедельник, 10 Август, 2009 19:31 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
http://en.wikipedia.org/wiki/Convex_hull http://en.wikipedia.org/wiki/Convex_hull_algorithms |
|
| Автор: | Илья Ермаков [ Понедельник, 10 Август, 2009 19:40 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Нет, это тут совсем не годится. Выпуклая оболочка, от заданного множества точек, да ещё для действительных пространств. Как Вы будете определять множество точек, относительно которых строить оболочку? Перебирать все? При этом Вам надо провести оболочку только через точки, которые рядом. Или показать, что провести её нельзя. Обычный волновой метод нужен. |
|
| Автор: | Alexey Veselovsky [ Вторник, 11 Август, 2009 10:22 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
PGR писал(а): http://en.wikipedia.org/wiki/Convex_hull http://en.wikipedia.org/wiki/Convex_hull_algorithms Ну, попробуйте реализовать нечто рабочее 
|
|
| Автор: | Alexey Veselovsky [ Вторник, 11 Август, 2009 10:24 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Илья Ермаков писал(а): Обычный волновой метод нужен. Волновой это один из возможных вариантов. Задачка хороша тем что вариантов множество. + тут интересно посмотреть как народ формализует задачу. |
|
| Автор: | Иван Горячев [ Среда, 12 Август, 2009 01:44 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
А попавшие в собственное окружение "живые" точки в чей баланс записываются? Т.е. должен ли я при построении области избегать окружения своих? |
|
| Автор: | Alexey Veselovsky [ Среда, 12 Август, 2009 10:32 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Иван Горячев писал(а): А попавшие в собственное окружение "живые" точки в чей баланс записываются? Т.е. должен ли я при построении области избегать окружения своих? Ни в чей. Считается сколько ты окружил чужих а не сколько сохранил своих. Окруженные тобой твои просто лучше защищены от окружения противником. Вообще, см. вики -- там подробно расписаны правила. |
|
| Автор: | Илья Ермаков [ Среда, 12 Август, 2009 14:53 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Там не совсем ясно. Например, если я окружил противника, а он внутри держит в окружении моих - то они не считаются его? Типа, я их освободил, так? )) |
|
| Автор: | Alexey Veselovsky [ Суббота, 15 Август, 2009 17:52 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Илья Ермаков писал(а): Там не совсем ясно. Например, если я окружил противника, а он внутри держит в окружении моих - то они не считаются его? Типа, я их освободил, так? )) Так. |
|
| Автор: | Илья Ермаков [ Суббота, 15 Август, 2009 22:30 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Процесс идёт )) Задачка действительно тонкая. Общая идея ясна, но "дьявол в деталях". |
|
| Автор: | Илья Ермаков [ Среда, 19 Август, 2009 20:43 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Докладаю )) Играет программулина, кучу тонких мест вроде разрешили; вот остался нюанс с окружением - если в пустую область ставится точка противником, которая достраивает свою область. Но тоже ясно уже, как делать... |
|
| Автор: | PGR [ Воскресенье, 23 Август, 2009 14:46 ] | ||||
| Заголовок сообщения: | Re: Алгоритмы точек. | ||||
Alexey Veselovsky писал(а): Ну, попробуйте реализовать нечто рабочее Вот мой вариант решения на C++  Для запуска понадобятся библиотеки Qt.
|
|||||
| Автор: | Илья Ермаков [ Воскресенье, 23 Август, 2009 14:57 ] |
| Заголовок сообщения: | Re: Алгоритмы точек. |
Так )) Пора выкладывать нашу игру. Мы тут уже два дня рубимся в сетевую версию ) Работа стоит ) Надо причесать и завтра постараться опубликовать. |
|
| Автор: | Alexey Veselovsky [ Воскресенье, 23 Август, 2009 15:20 ] | |||
| Заголовок сообщения: | Re: Алгоритмы точек. | |||
PGR писал(а): Alexey Veselovsky писал(а): Ну, попробуйте реализовать нечто рабочее Вот мой вариант решения на C++ Для запуска понадобятся библиотеки Qt. Чо-то глючит оно:
|
||||
| Страница 1 из 2 | Часовой пояс: UTC + 3 часа |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|
