OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 20:36

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Алгоритмы точек.
СообщениеДобавлено: Четверг, 06 Август, 2009 20:15 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Есть такая широко известная игра точки.

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 17:13 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Вот тут имеется java-версия точек. Поиграл немного, оказалось что они тоже неверно определяют обводку. Во вложенном файла пример неправильного определения красной обводки.

Вложение:
Комментарий к файлу: Пример неправильной обводки.
points.png
points.png [ 17.93 КБ | Просмотров: 11016 ]


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 17:30 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Alexey Veselovsky писал(а):
PS. Интересно было бы посмотреть насколько помогают/мешают средства различных ЯП для решения вот этой вот задачи. Так что предлагаю выкладывать сюда рабочие реализации алгоритма на различных ЯП: C, CP, CPP, Haskell, Python, etc. Будет наглядно видно читабельность алгоритма, скорость его работы, и, возможно. влияение языка на мышление.

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


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 17:35 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Алгоритм тут, видимо, должен быть - распространение волны из внешнего пространства. Учитывающее точки заданного цвета.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 17:56 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Vlad писал(а):
Давайте четче формализуем: на входе координаты точек и цвет, на выходе последовательность DrawLine(Point, Point, Color), охватывающая максимальное количество "чужих" точек и максимальную площадь. Если решений будет больше одного, то подбираем такую входную последовательность, на которой какое-то из решений будет проигрывать :)


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 18:30 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Алгоритм тут, видимо, должен быть - распространение волны из внешнего пространства. Учитывающее точки заданного цвета.

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


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 18:57 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Игру, на пару человек - чтоб щёлкать по очереди мышкой.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 19:31 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
http://en.wikipedia.org/wiki/Convex_hull
http://en.wikipedia.org/wiki/Convex_hull_algorithms


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Понедельник, 10 Август, 2009 19:40 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Нет, это тут совсем не годится. Выпуклая оболочка, от заданного множества точек, да ещё для действительных пространств.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Вторник, 11 Август, 2009 10:22 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
PGR писал(а):
http://en.wikipedia.org/wiki/Convex_hull
http://en.wikipedia.org/wiki/Convex_hull_algorithms


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Вторник, 11 Август, 2009 10:24 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Обычный волновой метод нужен.


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Среда, 12 Август, 2009 01:44 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 10:37
Сообщения: 875
Откуда: Россия, Владивосток
А попавшие в собственное окружение "живые" точки в чей баланс записываются? Т.е. должен ли я при построении области избегать окружения своих?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Среда, 12 Август, 2009 10:32 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Иван Горячев писал(а):
А попавшие в собственное окружение "живые" точки в чей баланс записываются? Т.е. должен ли я при построении области избегать окружения своих?


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Среда, 12 Август, 2009 14:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Там не совсем ясно.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Суббота, 15 Август, 2009 17:52 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Там не совсем ясно.

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


Так.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Суббота, 15 Август, 2009 22:30 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Процесс идёт )) Задачка действительно тонкая. Общая идея ясна, но "дьявол в деталях".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Среда, 19 Август, 2009 20:43 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Докладаю ))

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Воскресенье, 23 Август, 2009 14:46 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Alexey Veselovsky писал(а):
Ну, попробуйте реализовать нечто рабочее ;-)

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


Вложения:
Points.src.rar [1.55 КБ]
Скачиваний: 566
Points.exe.rar [16.27 КБ]
Скачиваний: 479
Points.png
Points.png [ 8.42 КБ | Просмотров: 10679 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Воскресенье, 23 Август, 2009 14:57 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Так )) Пора выкладывать нашу игру.
Мы тут уже два дня рубимся в сетевую версию ) Работа стоит )

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Алгоритмы точек.
СообщениеДобавлено: Воскресенье, 23 Август, 2009 15:20 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
PGR писал(а):
Alexey Veselovsky писал(а):
Ну, попробуйте реализовать нечто рабочее ;-)

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


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


Вложения:
points2.png
points2.png [ 6.91 КБ | Просмотров: 10671 ]
points1.png
points1.png [ 8.33 КБ | Просмотров: 10671 ]
Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB