Игра в точки на VB (не-ГО)

[zHackLeX]

Народ, пишу я, значит, игруху на 6-м бесе. Точки, типа. Наподобие "Го", но намного проще. Скриншот прилагается.
Правила общие:
1. Ходы чередуются.
2. Пустые области НЕ захватываются. (область не пустая, если в ней есть хоть одна вражья точка)
3. После захвата области делается ещё один ход.
Как написать процедурку, определяющую, где провести границы?

Реализовал через массив:

Код: Выделить всё

Type Point
    Color As Integer
    lnkFlags As Integer 'флаги направлений линий границ
    IsLinked As Boolean 'for debug purposes
End Type
Dim gArray(50, 60) As Point


Линкфлаг - "Ромашка связей" - восмибитное число, определяющее, в каких направлениях от точки исходят линии границ.
Как написать процедуру, рисующюю границы по ходу выставления точек?

[zHackLeX]

Кстати, что я уже имею:
+ Сырую "процедурку" (на целый лист) для удаления "левых" границ,
+ Уже очти додумал процедурку для удаления "левых" треугольников (когда три точки на минималном расстоянии друг от друга имеют в сумме (включая связи меж собой) <= 7 связей, все их связи нужно удалить.
- Всё это делается только при нажатии на спец. кнопку
- Всё это достточно медленно, т. к. для пересчёта "ромашки связей" - так я называю число, определяющее, в какие стороны от точки исходят связи. Как я это делаю: предположим, от точки исходят две связи: вверх и вниз-влево.

128[color=white]__1___2
64___*___4
32___16__8[/color]
(подчёркивание - чтобы не путать таблицу)
Записываем число: 32+1=33. Как я ищу связи по числу:
33 = 000100001: есть первая и шестая связи. (это, если кто не понял и хочет разобраться)
- Плохая функция перевода в двоичную систему - она строковая, а значит - медленная. Есть идеи, народ?

[alibek]

Сколько лекций из-за этой игры у нас было пропущено...
1. Начнем с конца: зачем тебе вообще переводить число в стринг? Работай непосредственно с числами, а разряды определяй через And или Or.
2. Сдается мне, перемудрил ты с lnkFlags. Связи можно сохранять разными способами, важнее вначале составить алгоритм, который будет находить замкнутые области.
И какие конкретно правила в твоей реализации? Когда мы играли, то точки, которые уже обведены, больше не участвуют, т.е. проводить линии через уже существующие линии нельзя. И можно использовать уже существующие линии, но только для своих точек и по внешнему контуру.
3. Хорошо, если бы обведенная область перекрашивалась в соответствующий цвет.
4. Когда-то я пытался тоже такое сделать, правда я начинал не с интерфейса, а с алгоритма определения областей. Если найду проект и там будет что-то полезное, выложу.

[zHackLeX]

Правила по ходу те же. Да, у нас тоже нельзя использовать уже захваченные точки, т. е. точки, которые уже закрашены.
Вопросы.
1) Ты писал про And/Or, как тебе определить с помощью And/Or, есть ли в двоичной записи числа 140 (128+8+4 или 10001100) единица на чётвёртой позиции (в данном примере есть, т. к. нумерация позиций - спарва), НЕ ПРИБЕГЯ К СТРОКАМ, они слишком медленные. Просто уже написаны процедуры GetDirectionValue(X,Y,X2,Y2) для сложения флагов, GetXByDirFlag, GetYByDirFlag, и две последние со строкой - преобразуют целое число в строку - двоичную запись, а затем уже - то, что требуется.
2)

Но только для своих точек и по внешнему контуру

Поясни?

3) Да всё дело в том, что НЕТ алгоритма определения, замкнута область, или нет. Всё я делаю так. Между каждыми соседними точками одного цвета, если этому не мешают уже проведённые границы, я провожу границы. Получается чушь. Потом я стираю "левые" границы по следующим правилам.
а) Если у трёх точек, находящихся на минимальном расстоянии друг от друга (Треугольник в половину одного квадрата), число линий связи в сумме (у всех трёх) не превышает 7, все их связи следует удалить.
б)Если у точки лишь одна связь, такую связь также следует удалить.
Вот так. А алгоритма вычисления замкнутой области просто НЕТ. Я вообще без понятия о том, как его реализовать. Поэтому с закраской подождём.
в) (в разработке) такая же фигня с целыми квадратами (связей не больше 13).
Только не надо смеяться!
ЗЫ. А метод хранения lnkFlags - очень удобный. Плохо только то, что его постоянно приходится конвертить в строку для выявления его двоичной записи.
ЗЫЫ. Если есть совсем другой способ определения границ - пиши, я всё переделаю, а то этот работает просто посредственно. Неиграбельно. И ещё.
Никак нельзя заставить комп пошевелить мозгами и походить самостоятельно? (типа AI)

[alibek]

Все очень просто.
Единица в четвертой позиции - это 2^(4-1)=2^3=8.
Проверяешь: MsgBox ((140 and = -> True
В общем случае для проверки на 1: (Value And 2^(n-1)) = 2^(n-1)
Проверка на 0: (Value Or Not(2^(n-1))) > 0

Советую использовать не возведение в степень, а заполнить массив P2(0...7) со степенями двойки, будет гораздо быстрее.

P.S. Убегаю на обед, спешу и возможно где-то будут ошибки. Приду и отвечу еще раз.

[alibek]

Ну начнем по порядку.
Для начала, использование And/Or. Я уже написал пример, теперь напишу более детально.

Код: Выделить всё

Option Explicit
...
Dim Power2(0 To 31) As Long
...
Sub Init()
...
Power2(0) = 1&
For I = 1 To 30
  Power2(I) = Power2(I-1) + Power2(I-1)
Next I
Power2(I) = &h80000000& 'т.к. в VB нет типа Unsigned
...
End Sub
...
Function CheckBit(ByVal Value As Long, ByVal BitPos As Long) As Boolean
'BitPos based on 1
CheckBit = ((Value And Power2(BitPos-1)) = Power2(BitPos-1))
End Function

Sub SetBit(ByRef Value As Long, ByVal BitPos As Long)
Value = (Value Or Power2(BitPos-1))
End Sub

Sub ClearBit(ByRef Value As Long, ByVal BitPos As Long)
Value = (Value And Not(Power(BitPos-1)))
End Sub

Sub SwitchBit(ByRef Value As Long, ByVal BitPos As Long)
Value = (Value Xor Power2(BitPos-1))
End Sub


Использование: If CheckBit(gArray(...).lnkFlags,1) Then MsgBox "Есть связь в 1). Процедуры SetBit, ClearBit и SwitchBit служат для установки, сброса и переключения битов соответственно.


Теперь по правилам: я имел ввиду, что нельзя использовать даже свои точки, если они уже находятся внутри закрашенной области.

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

А вот насчет AI я тебе не помощник. Сам долго думал, но ничего путного не придумал.

[sanches]

недавно тоже увлекся точками (однако лекции не пропускал )
насчет AI - http://pointsgame.narod.ru/
автору удалось реализовать довольно неплохой интеллект, правда в поздней игре на высоком уровне сложности комп думает очень долго.

[zHackLeX]

Как твоя программа работает без алгоритма определения замкнутого контура я вообще не представляю

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

[GSerg]

Да выкладывай, чего там...

[zHackLeX]

В общем, так. Ловите. Тока, чур не смеяться, я - новичок.
И ещё раз, когда уже посмотрите исходники. Никак нельзя функцию для границ - а то моя хромает.


ЗЫ. На комментарии забейте - мне просто неохота было их всех стирать. Но вопрос не снят.

ЗЗЫ. Насчёт алголиста. Так как я не представляю, что именно там искать, и как это интерпретировать, если найду (что под большим вопросом), то дайте хоть ссылку по конкретнее, что ли... Хотя живое объяснение куда понятнее

[GSerg]

Да, загрузил
Возникла пара бредовых идеек... Но что из них получицца - большой вопрос...

[zHackLeX]

Что за идеи? Давайте бредить коллективно!

[v@Mp!rO]

Постараюсь помочь хотя не очень в этом разбираюсь
Так-что если что не так не смейтесь(а скажите)

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

Опишем игровое поле не точками а квадратами(клеточками).
Каждый квадрат имеет 4 угла(точки).
Примерно так:

Public type u_rect
id as integer
corn(3) as point
End type

Dim pole(200) As u_rect

Далее всё легко, создадим цикл по u_rect.

n1 = ширина поля
n2 = высота поля
n = сторона u_rect

Всё это в пикселах(или как там удобнее)

количество квадратов это (n1 * n2) \ n^2

Далее ищем точки принадлежащие одному и тому же игроку и... соединяем их линеей.
И так в каждом квадрате!!!

Правда при добавлении ИИ прийдется добавить в структуру u_rect переменную для каждой грани(и диагонали) квадрата, что-бы знать соединяет ли грань(диагональ) две точки и кому она принадлежит.

И ещё, зачем ты храниш все функции в форме, по-моему легче создать модуль.

[zHackLeX]

Насчёт алгоритма - он не СЛОЖНЫЙ, а ДЛИННЫЙ. Ничего сложного я в нём не вижу. И ещё. В процедуре с треугольниками что-то работает не так. Никто не сможет помочь определить, что - именно?
Второе. Скорее всего этот алгоритм всё равно придётся сдать в утиль - нужен алгоритм, определяющий закрытые области. Как?
Мне поступил совет определить их рекурсивом, но как именно? У кого есть идеи?
Формат игрового поля старый. Кто забыл или не прочёл или что-то ещё, напомню.

Код: Выделить всё

Private type Point
    Value As Integer '2=Красная/1=синяя/0=левая
    lnkFlags As Integer '- флаги связи, cм. выше.
    IsLinked As Boolean 'Объяснять долго, кто смотрел листинг, знает :D
End Type
Dim gField(50,60) As Point


Нужно бы определить замкнутые области.
Зы. Да, кстати, мне тут пришла идея реализовать волновой алгоритм. Пойду писАть, напишу - приду... Но смотреть на форум буду обязательно.
(уходит)

[zHackLeX]

Ребята, дико извиняюсь, что не пишу, но у меня кончилась интернет-карта , а без неё инет в три раза дороже. Так что извините -- как только куплю, сразу обо всём напишу. пока.