Я вот решился наконец написать логическую игру "точки". Сделал кучу возможно никому и ненужных настроек (размер поля, изменение точек при захвате и многое другое).
Написал нерекурсивный и довольно экономичный алгоритм поиска самой короткой линии захвата, но вот одна проблема мне надо залить область ограниченную этими линиям (значения массива 2- линия захвата, 0 - пустая клетка).
Я использовал рекурсивную заливку, но она сильно долгая .
На algolist.manual.ru есть хороший (я думаю) алгоритм заливки, но все алгоритмы, что там есть написаны на C, а C я не знаю .

Если у кого есть предложения по заливке или желание перевести алгоритмы из C в Delphi, то буду благодарен.

А может можно построить регион(CreatePolygonRgn) по этим точкам и заполнять его функцией FillRgn? Или я что то не так понял?

Это сообщение отредактировал(а) <Spawn> - 15.8.2003, 13:33

Вот тебе примерчик:

Код

procedure TForm1.Button1Click(Sender: TObject); type TPoints=array[0..3] of TPoint; var Points:TPoints; Rgn:HRGN; dc:HDC; FillBrush:TBrush; i:integer; begin try Randomize; for i:=0 to 3 do  begin   Points[i].X:=Random(400);   Points[i].Y:=Random(400);  end; Rgn:=CreatePolygonRgn(Points,4,WINDING); Dc:=GetDC(Handle); FillBrush:=TBrush.Create; FillBrush.Color:=clRed; FillRgn(Dc,Rgn,FillBrush.Handle); finally ReleaseDc(Handle,Dc); DeleteObject(Rgn); FreeAndNil(FillBrush); end; end;

Это сообщение отредактировал(а) <Spawn> - 15.8.2003, 13:34

А я так понял, что у Immortal есть матрица, состоящая из 2 и 0. Например:

0 0 0 0 0 0 0 0 0 0 0
0 2 2 0 0 0 2 0 0 0 0
2 0 0 2 0 2 0 2 2 0 0
2 0 0 0 2 0 0 0 2 0 0
0 2 2 2 0 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0

И это должно закраситься вот так:

0 0 0 0 0 0 0 0 0 0 0
0 * * 0 0 0 * 0 0 0 0
* * * * 0 * * * * 0 0
* * * * * * * * * 0 0
0 * * * 0 * * * 0 0 0
0 0 0 0 0 0 0 0 0 0 0

Т.е. координаты концов отрезков ему как бы так сразу и неизвестны.

Хотя это только предположения...

Если это та игра в точки, про которую я думаю, то любую "захваченную" область можно разбить на элементарные составляющие - треугольники.
Таким образом, обработав все игровое поле, можно построить соответствующие треугольники с заливкой (используй Canvas.Poligon)

Конечно сиасмбо за предоставленную информуцию, но мне нодо нечто иное.
У меня есть массив в котором я собираюсь производить заливку в начале кождого хода он пуст (все 0)
игра происходит на другом массиве. Как только ставится точка которая образует замкнутую линию, я нахожу эту линию (уже написал алгоритм) и уже тогда эту линию я отмечаю на этом массиве. Точку внутри области я тоже знаю.

Мне надо что бы программа из точки внутри прошлась по области оганиченной линией (этими самыми 2), побывав на каждой точке всего желательно один раз. Что программа будет изменять, оказавшись на кождой из внутренних точек это моя забота (там организуется счётчик захваченных тобою точек).

Например:

0 0 0 0 0 0
0 2 2 0 0 0
2 * * 2 0 0
2 * * * 2 0
0 2 2 2 0 0
0 0 0 0 0 0

* - точки (элементы массива), которые должны просматриваться прогой.

А закрашивать область в какой-то цвет мне совсем не надо

За раннее спасибо.

Цитата(Immortal @ 15.8.2003, 12:42)

Я использовал рекурсивную заливку, но она сильно долгая .

Immortal, Я так понимаю, массивы максимум 100х100 (ни фига себе захват! ), как на таких маленьких площадях маожет быть медленной заливка? Выложи код, посмотрим.

Заливка медленна относительно.
Моя заливка такая;

Код

procedure Enemy(x,y: Byte); var o: Byte; begin  tempArray[x,y].param := 1;                                    {Здесь выполняются некоторые действия по реализации счётчика}  //заливка  for o := 0 to 3 do    if tempArray[x+vector[o*2].x,y+vector[o*2].y].param = 0 then      Enemy(x+vector[o*2].x,y+vector[o*2].y); end;

tempArray - мой массив по которому я реализую заливку
vector - массив Point с напрвлениями

1. Алгоритм рекурсивный, отсюда следует требуется довольно много памяти;
2. При просмотре окружающих точек за каждый вызов просматриваются 4 точки, отсюда следует, что при захвате области в 100 точек просмотров будут 400.

Если ставишь точку ты это работает быстро, но в алгоритме интеллекта таких просмитров будет довольно много.

А ты проверял свой код, он рабочий
Я имею ввиду: он полностью обходит весь замкнутый "регион" и заполняет массив единицами?
Мне кажется, что нет, так как у тебя рекурсия происходит сразу же после первого найденного значения 0 в массиве, и остальные рядом находящиеся ячейки могут так и остаться нулями (а возможно и нет, все зависит от формы "региона" и выбора начальной точки для "заливки")

Ты ошибаешься &-ray Рекурсия успешно обходит 4-х связную область.
Объясню тебе: да рекурсия вызывается сразу как обнаружит вокруг текущей точки хотя бы один 0, но даже если эта ветка не зальёт всю область, то вокруг этой точки будут проверятся оставшиеся 3 точки и если какая-то будет не залита, то будет создана ещё ветка (я поэтому и написал эту тему в форум, так как в каждом вызове функции приходится просматривать четыре точки вокруг текущей).

Такой алгоритм зальёт любую 4-х связную область при любой начальной точки (лишь бы точка была внутри области)

Только после такой заливки приходится пробегать всё поле (без этого никак) и очищять от 1 и 2, да и рекурсия долгая и требует много памяти.

------
Я был бы благодарен если бы у кого нибудь нашёлся алгоритм, заливающий область имея в распоряжении массив всех вершин (в данном случае всех точек цепи), Причём желательно без необходиимости временного массива (в рекурсии приходится заполнять 1, что бы она не стала бесконечной).
Такой алгоритм есть на algolist.manual.ru, но он на C, а я С не знаю.

Запостите сюда этот код на С, думаю найдутся люди, кому будет не лень перевести. А вообще батенька надо С изучать.....

Ну ладно я хотел по хорошему, а вы сами напросились

Код

/*=====================================================  V_FP1 * Более эффективная по сравнению с V_FP0 подпрограмма * однотонной заливки многоугольника методом построчного * сканирования. * * Дублирувание занесения пикселов практически отсутствует * */ #include <stdio.h> #include <graphics.h> #define MAXARR 300  /* Макс кол-во вершин многоугольника  */ #define MAXLST 300  /* Макс размер списка активных ребер  */ /*---------------------------------------------------- FILSTR * Заливает строку iy от ixn до ixk * * void FILSTR (int kod, int iy, int ixn, int ixk) */ void FILSTR (kod, iy, ixn, ixk) int kod, iy, ixn, ixk; {   while (ixn <= ixk) putpixel (ixn++, iy, kod); }  /* FILSTR */ /*--------------- Глобалы процедуры закраски ---------------*/ static int   KOD, NWER; /* Код заливки и кол-во вершин      */ static float *pt_X;     /* Массивы входных координат вершин */ static float *pt_Y; static int   IBGIND;        /* Номер след вершины в списке */ static int   IEDG[MAXARR];  /* Y-коорд вершин по возрастан */ static int   INOM[MAXARR];  /* и их номера в исх масс Py   */ /* Список активных ребер */ static int   IDLSPI;        /* Длина списка активных ребер */ static int   IYREB[MAXLST]; /* Макс Y-коорд активных ребер */ static float RXREB[MAXLST]; /* Тек  X-коорд активных ребер */ static float RPRIR[MAXLST]; /* Х-приращение на 1 шаг по Y  */ static float RYSL[MAXLST];  /* Dy между тек и соседн верш  */                            /* Dy <= 0.0 - обычная вершина */                            /*     > 0.0 - локал экстремум */ /*---------------------------------------------------- FORSPI * int  FORSPI (int IYBEG) * *  1) Формирует элементы списка для ребер, *     начинающихся в IYBEG; *  2) Вычиcляeт IBGIND - индeкc нaчaлa следующей *     вepшины в cпиcкe вepшин; *  3) Возвращает IYSLED - Y кoopдинaтy ближaйшeй *     вepшины, дo кoтopoй мoжнo зaливaть бeз *     пepecтpoйки cпиcкa. * *  Глoбaльныe вeличины : * *  KOD    - код заливки *  NWER   - кoл-вo вepшин в иcxoднoм мнoгoyгoльникe, *  *pt_X  - X-кoopдинaты иcxoднoгo мнoгoyгoльника, *  *pt_Y  - Y-кoopдинaты иcxoднoгo мнoгoyгoльника, *  IEDG   - yпopядoчeнный пo вoзpacтaнию мaccив *           Y кoopдинaт вepшин иcxoднoгo мнoгoyгoльн *  INOM   - INOM[i] зaдaeт нoмep вepшины в иcxoднoм *           мнoгoyгoльникe для IEDG[i], *  IBGIND - индeкc мaccивoв IEDG, INOM *           oпpeдeляeт гдe мoжeт нaчaтьcя ребpo, *  IDLSPI - длинa пocтpoeннoгo cпиcкa aктивныx ребep, *           cocтoящeгo из : *           IYREB  - мaкc кoopдинaты ребep, *           RXREB  - внaчaлe мин, зaтeм тeкyщaя X-кoopдинaтa, *           RPRIR  - пpиpaщeниe к X-кoopдинaтe нa 1 шaг пo Y, *           RYSL   - пpизнaк тoгo чтo зa вepшинa : *                    <= 0 - oбычнaя, *                     > 0 - лoкaльный экcтpeмyм *                     пepeceчeниe cтpoки зaкpacки *                     c экcтpeмyмoм cчитaeтcя зa 2 тoчки, *                     c oбычнoй - зa 1; */ static int  FORSPI (IYBEG) int  IYBEG; {   int   i,ikledg,intek,intabs,isd;   int   iyt,ixt,nrebra,inc,inpred,inposl;   float xt, xc, yt, yc, dy; /* ikledg = кoл-вo вepшин c дaнным IYBEG */   ikledg= 0;   for (i=IBGIND; i<=NWER; ++i)      if (IEDG[i] != IYBEG) break; else ++ikledg; /* Цикл пocтpoeния cпиcкa aктивныx ребep   и зaкpaшивaниe гopизонтальных ребep */   for (i=1; i<=ikledg; ++i) { /* Bычисл номера текущей вершины */      intek= INOM[IBGIND+i-1];      intabs= abs (intek);      xt= pt_X[intabs];      yt= pt_Y[intabs]; /*  Bычисл номеров предыд и послед вершин */      if ((inpred= intabs - 1) < 1) inpred= NWER;      if ((inposl= intabs + 1) > NWER) inposl= 1; /* * По заданным : *    NWER   - кол-во вершин, *    intek  - номер текущей вершины, *    isd = 0/1 - правилу выбора соседней вершины - *                предыдущая/последующая *    вычиcляeт dy, *    Еcли dy <  0 тo вepшинa yжe oбpaбoтaнa, *    Еcли dy == 0 тo вepшины нa oдном Y *                 Пpи этoм cтpoитcя гopизoнтaльный oтpeзoк. *                 Фaкт зaкpacки гopизoнтaльнoгo ребpa *                 oтмeчaeтcя oтpицaтeльным знaчeниeм *                 cooтвeтcтвyющeгo знaчeния INOM. *    Еcли dy >  0 тo фopмиpyeтcя нoвый элeмент cпиcкa *                 aктивныx ребep */      for (isd=0;  isd<=1; ++isd) {         if (!isd) nrebra= inc= inpred; else {            inc= inposl;  nrebra= intabs;         }         yc= pt_Y[inc];         dy= yc - yt;         if (dy < 0.0) continue;         xc= pt_X[inc];         if (dy != 0.0) goto DYNE0;            if ((inc= INOM[nrebra]) < 0) continue;            INOM[nrebra]= -inc;            iyt= yt;            inc= xc;            ixt= xt;            FILSTR (KOD, iyt, inc, ixt);            continue; DYNE0:   ++IDLSPI;         IYREB[IDLSPI]= yc;         RXREB[IDLSPI]= xt;         RPRIR[IDLSPI]= (xc - xt) / dy;         inc= (!isd) ? inposl : inpred;         RYSL[IDLSPI]=  pt_Y[inc] - yt;      }   /* цикла по isd */   }  /* построения списка активных ребер */ /*  Bычисление Y ближайшей вершины */   if ((i= (IBGIND += ikledg)) > NWER) i= NWER;   return (IEDG[i]); } /* Процедуры FORSPI */ /*-----------------------------------------------------  V_FP1 * Однотонно заливает многоугольник, * заданный координатами вершин * * void V_FP1 (int pixel, int kol, float *Px, float *Py) * */ void V_FP1 (pixel, kol, Px, Py) int  pixel, kol;  float *Px, *Py; { int  i,j,k,l; int  iytek;    /* Y текущей строки сканирования        */ int  iymin;    /* Y-мин при сортировке массива Y-коорд */ int  iybeg;    /* Мин Y-координата заливки  */ int  iymak;    /* Max Y-координата заливки  */ int  iysled;   /* Y кoopд ближaйшeй вepшины, дo кoтopoй */               /* можно зaливaть бeз пepecтpoйки cпиcкa */ int  newysl; int  ixmin;    /* X-мин при сортировке для тек строки */ int  ixtek;    /* X-тек при сортировке для тек строки */ int  irabx[MAXLST]; /* X-коорд пересечений в строке сканир */   KOD= pixel;    /* Параметры в глобалы */   NWER= kol;   pt_X= Px;   pt_Y= Py; /*  Построение массивов Y и их номеров */   for (i= 1; i<=NWER; ++i) {IEDG[i]= Py[i];  INOM[i]= i; } /*  Cовместная сортировка массивов IEDG, IHOM */   for (i= 1; i<=NWER; ++i) {      iymin= IEDG[i];      k= 0;      for (j=i+1; j<=NWER; ++j)         if ((l= IEDG[j]) < iymin) {iymin= l; k= j; }      if (k) {         IEDG[k]= IEDG[i]; IEDG[i]= iymin;         iymin= INOM[k];         INOM[k]= INOM[i]; INOM[i]= iymin;      }   } /* Hачальные присвоения */   IDLSPI= 0;   IBGIND= 1;   iybeg= IEDG[1];   iymak= IEDG[NWER]; /* Формирование начального списка акт ребер */   iysled= FORSPI (iybeg);   if (!IDLSPI) goto KOHGFA; /* Горизонтальная раскраска по списку */ ZALIWKA:   for (iytek=iybeg; iytek<=iysled; ++iytek) {      if (iytek == iysled) {    /* Y-координата перестройки */         newysl= FORSPI (iytek);         if (!IDLSPI) goto KOHGFA;      } /* Bыборка и сортировка X-ов из списка ребер */      l= 0;      for (i=1; i<=IDLSPI; ++i)         if (RYSL[i] > 0.0) irabx[++l]= RXREB[i];         else RYSL[i]= 1.0;      for (i=1;  i<=l; ++i) {         ixmin= irabx[i];         k= 0;         for (j=i+1;  j<=l; ++j) {            ixtek= irabx[j];            if (ixtek < ixmin) {k= j; ixmin= ixtek; }         }         if (k) {irabx[k]= irabx[i];  irabx[i]= ixmin; }      }  /* цикла сортировки */ /*  Cобственно заливка */      for (j=1;  j<=l-1;  j+= 2)         FILSTR (KOD,iytek,irabx[j],irabx[j+1]);      for (j=1;  j<=IDLSPI; ++j)        /*  Приращения X-ов */         RXREB[j]= RXREB[j] + RPRIR[j];   }  /* цикла горизонтальной раскраски */   if (iysled == iymak) goto KOHGFA; /*  Bыбрасывание из списка всех ребер с YMAK ребра == YSLED */   i= 0; M1:++i; M2:if (i > IDLSPI) goto WYBROSILI;      if (IYREB[i] != iysled) goto M1;         --IDLSPI;         for (j=i;  j<=IDLSPI; ++j) {            IYREB[j]= IYREB[k= j+1];            RXREB[j]= RXREB[k];            RPRIR[j]= RPRIR[k];         }         goto M2; WYBROSILI:   iybeg= iysled + 1;   iysled= newysl;   goto ZALIWKA; KOHGFA:; }  /* V_FP1 */

Это заливка графической области по пикселям, но ведь что мне мешает использовать вместо пикселей мои точки.

И ещё здесь заливается многоугольник если известны его вершины, а у меня изветно не только это, но и координаты кождого граничащего элемента (точки), може это можно использовать для упрощения.

Но это не главное, главное переведите кто-нибудь её на Delphi :-(

Кстати к ней пралагалась Сортировка методом распределяющего подсчета:

Код

int  Max_число;        /* Верхняя граница значений */ int  *Повтор;          /* Длина этого массива = Max_число */ int  Кол_чисел;        /* Кол-во сортируемых чисел */ int  *Исходный_массив; /* Длина этого массива >= Кол_чисел */ int  *Результат;       /* Длина этого массива >= Кол_чисел */ int  ii,jj, kk;        /* Рабочие переменные */ Обнуляется служебный массив для подсчета числа повторений исходных кодов.   for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0; Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:   for (ii= 0; ii < Кол_чисел; ++ii) {      jj= Исходный_массив[ii];      Повтор[jj]= Повтор[jj] + 1;   } Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:   jj= 0;   for (ii=0; ii<Max_число; ++ii) {      jj= jj + Повтор[ii];      Повтор[ii]= jj;   } Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:   for (ii= 0; ii < Кол_чисел; ++ii) {      jj= Исходный_массив[ii];      kk= Повтор[jj];      Результат[kk]= jj;      Повтор[jj]= Повтор[jj] - 1;   }

Help me :-)

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

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

Immortal, может тебе просто твой Enemy под asm переделать ?
Я проверял - ускорение на больших площадях от 3 до 5 раз...