Есть игра в которой игроки по-очереди ставят точки на клеточном поле на перекрестии линий. Нужно окружить как можно больше вражеских точек. Как только ты окружаешь точку, ты через свои точки(которые окружают) провожишь линию(даже если внутри есть много точек и даже если они тоже так сказать "укреплены"). "Укреплены" значит, что враг не может проводить линию через твою линию.

Я решил сделать такаю игру на компе. Я написал структуру, в которой есть:
1) координаты (x, y)
2) кем установлена точка
3) координаты окружающих 8-ми точек (xU, yU, xD, yD, ...)
4) 8 переменных принадлежности окружающих точек какому-либо игроку, т.е. кем установлена, к примеру, точка сверху.
5) 8 булевских переменных: соеденены ли точки?!

У меня в программе все переменный для каждой точки уже вычисляются, кроме последних 8ми.
Сколько не мучил, не знаю как сделать.

Какой алгоритм можете посоветовать?

P.S. И как можно узнать какие точки попали в круг.
P.P.S. Я пишу на Си++ и точки у меня представлены 2-мерным массивом размеров 29 на 29.

Ты VB знаешь, я кстати точно такую же игру пишу. Я уже написал проставление точек и т.д. и т.п., и вот теперь надо написать логику, если переключишься на VB я могу тебе исходники переслать и будет вместе работать над игрой, возможно вдвоем что-нить и получится.

а кто-нибудь еще не хотел бы заняться этой проблемой...

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

Цитата(OXOTHUK @ 13.12.2005, 18:16)

но тут не знаешь с какой точки начать

Я считаю что надо так. Сначала надо проверить первая это точка или нет. Если первая то общет вообще не нужен. Если это не первая точка то обсчет надо начинать с последней поставленной точки, и надо считать так чтобы он проходил через все точки. Если комп прошел через все точки и вернулся в первоначальную, то тогда все замкнуто точками, если комп не вернулся то тогда ничего точками не замкнуто.

Я бы мог подключиться. Пишу на С/С++. Для графики использую SDL. Смогу,может, что поделать после 25 декабря.

Цитата

вернулся в первоначальную

А если несколько колец? И ведь кольца не может быть если внутри нет хотя бы 1ной вражеской точки.

Цитата(OXOTHUK @ 15.12.2005, 11:34)

А если несколько колец? И ведь кольца не может быть если внутри нет хотя бы 1ной вражеской точки.

Впринципе правильно, значит нужен еще алгоритм нахождения находится ли в данном так сказать полигоне вражеская точка либо надо проверять точки противника (ну например, если ходится игрок 1, то по жесткой логике нужно проверять все точки игрока 2).
Добавлено @ 16:49

Цитата(powerfox @ 14.12.2005, 14:48)

Пишу на С/С++. Для графики использую SDL.

Я поясни (расшифруй) пожалуйста, что такое SDL, и в чем ты пишешь на C++ (Borland Builder or MSVC)?

SDL - графическая библиотека(со своим API). Там есть функции для загрузки картинок(bmp, jpeg, png и др.), просто рисования, воспроизведения звуков, для работы со временем. На изучение SDL не требуется много времени(SDL совместима и с Java, Delphi - если не ошибаюсь).
Я работаю с MinGW(портирован с gcc) в Windows, в Linux с gcc.
Про SDL
На русском:
-хороший туториал поищи на plg.lrn.ru. Адрес более старого(несильно отличается http://pmg.org.ru/galaxy2d/SDLtutorial.zip
-документация http://plg.lrn.ru/temp/html_ru/

Сайт SDL - www.libsdl.org

Можно через массивы сделать (легко) как проверить на окружение только 1-ой точки. А там как-нибудь дальше вытечет.
Алгоритм:
Массив строчек (пусть dots) размером (пусть) 29 на 29 - dots[29][29] (так на Си, не знаю как VB).
Например:
если точка dots[2][2] - Player 2 и dots[1][2] - Player 1 и dots[3][2] - Player 1 и dots[2][1] - Player 1 и dots[2][3] - Player 1, то 4 точки игрока 1 в кольцо:
010
121
010.
Тут надо подумать как несколько точек окружать...

По-моему нужно что-то другое, так будет сложно делать большие окружения. После 26-го присоединюсь.

Цитата(OXOTHUK @ 18.12.2005, 17:07)

Тут надо подумать как несколько точек окружать...

Это все понятно. Я думаю, что может быть надо попробовать найти какую нибудь закономерность и затем свести все это
к перемножению матриц?

Цитата

перемножению матриц?

А как их меремножать? Я мало с матрицами работал.

Помню такую игру, в детстве играл.
Мне эта проблема напоминает нахождение циклов в ненаправленном циклическом графе. В данном случае вершины - это точки (вашего цвета), и ребро существует между двумя вершинами только если они находятся на расстоянии в одну клетку друг от друга, т.е. если в случае цикла между ними можно нарисовать линию. Собственно алгоритм нахождения циклов я не знаю, но уверен что поиск на гугле даст искомый результат. Тут только не учитывается, если ваши точки окружают хотя бы одну точку противника.

Немного подумал и понял чуть-чуть логику окружения. Геометрическая фигура. Противник ставит точку(первый). Комп должен ставить точки отличающиеся на одну координату, когда противник ставит рядом точку, то изменяются и увеличиваются координаты будущих точек.

Я с одним человеком поиграю в эту игру и попытаюсь выявить закономерность. Мы оба играем хорошо и выстраиваем такие баталии, что ого-го. Потом скажу, что получилось.

Начинать нужно с простого - разработать графические библиотеки, сделать "детский интеллект" ------------> усовершенствовать, осознать ------------------------->спроектировать, написать. Всё просто

Графа у меня есть, даже рисование связывающих линий, но только если булевская переменная, отвечающая за связывание, равна true. А это - то о чём я спрашивал в самом начале. Интелект не так обязательно, можно начинать игру делать с мультиплеера. А поиграть с другом пока, ещё не получилось.

Поищите по форуму, про AI для этой игры были раньше обсуждения (на будущее). И про нахождения обведенных точек...

Это сообщение отредактировал(а) p0s0l - 30.12.2005, 16:24

p0s0l
А чё в поиске-то ввести(хотя бы примерно)?! Я ведь и не знаю как называется и как её называли раньше когда обсуждали. Искал - не нашёл.

В принципе нужно только определять, что часть линии, а что - её конец(две булевы переменные в структуре точки). Окружение происходит, когда у соседних точек значения 1;0 и 0;1.
Добавлено @ 17:12

Цитата(OXOTHUK @ 9.12.2005, 12:13)

P.S. И как можно узнать какие точки попали в круг.

Две крайние точки окружения по оси Oy: разность x1-x2, В окружении все точки с координатами (y; x1..x2).

powerfox
про это уже говорили - а если в окружении много точек и вопрос (в начале) был задан как установить значения булевских.

недавно нашел на делфе написана, там искай...