Войти
ПрограммированиеФорумИгровая логика и ИИ

Алгоритм обхода поля (двумерного массива) по спирали (улитке)

Страницы: 1 2 Следующая »
#0
18:15, 10 сен. 2019

Уважаемы эксперты, профессионалы и просто любители геймдева.

Прошу у вас помощи в реализации алгоритма обхода поля (двумерного массива) по расширяющейся спирали (улитке).

Описание проблемы
В процессе разработки пошаговой стратегии столкнулся с проблемой размещения юнитов на поле боя, а именно:
•  Есть поле боя, представляет из себя сетку с клетками
•  В каждой клетке может размещаться до 5 юнитов
•  При подготовке к бою указывается клетка, где должен быть размещен отряд
•  В отряде может быть любое количество юнитов от 1 до 1000

Логика работы основного механизма предполагается такая (ну и уже в принципе реализована):
•  Программа перебирает юнитов, и определяет, где они должны располагаться по заранее определенным X и Y координатам сетки
•  Программа проверяет сколько есть свободного места на клетке, если место есть, в нее размещается один юнит
•  Если места нет программа должна переходить к следующей клетке, и вот здесь проблема, в упор не могу придумать алгоритм для определения перебора в получения координат следующей клетки.

Третий день бьюсь… просмотрел разные алгоритмы в инете, для заполнения массивов цифрами по спирали, но не могу их осознать. И не могу применить в своем проекте. На данный момент есть только заранее описанное смещение на 8 клеток для размещения юнитов вокруг первой клетки, но это в корне не верно, так как позволяет размещать только 45 единиц…

Какой помощи хотелось бы дождаться
•  Возможно, на форуме уже обсуждалось что то подобное, буду рад ссылке.
•  Можно описать алгоритм на псевдокоде, Java, GMS2, но если будет дугой язык, то тоже буду благодарен.
•  Снабдить по необходимости комментариями
•  Возможно предложить другое решение? Может у меня развилось туннельное зрение, и я просто не вижу другого решения.

Если чего то не хватает пишите, сообщу.

Дополнительно
Среда разработки GMS2, язык тот же 😊

Сейчас собственно код выглядит вот так:

    var offset_x = 0;
    var offset_y = 0;
    var offset_r = 1;

    while(true){
      var bc = gr[# (cell_x + offset_x), (cell_y + offset_y) ];
      if( (bc + unit[? "size"]) <= 10 ){
        unit[? "cell_x"] = cell_x + offset_x;
        unit[? "cell_y"] = cell_y + offset_y;
        gr[# (cell_x + offset_x), (cell_y + offset_y) ] = gr[# (cell_x + offset_x), (cell_y + offset_y) ] + unit[? "size"];
        
        ds_list_add(global.liUnits, unit);
        unit_index++;
        break;
      }else{
        if( offset_x == 0 && offset_y == 0 ){
          offset_x = 0;
          offset_y = -1;
          continue;
        }
        if( offset_x == 0 && offset_y = -1 ){
          offset_x = 1;
          offset_y = -1;
          continue;
        }
        if( offset_x == 1 && offset_y == -1 ){
          offset_x = 1;
          offset_y = 0;
          continue;
        }
        if( offset_x == 1 && offset_y == 0 ){
          offset_x = 1;
          offset_y = 1;
          continue;
        }
        if( offset_x == 1 && offset_y == 1 ){
          offset_x = 0;
          offset_y = 1;
          continue;
        }
        if( offset_x == 0 && offset_y == 1 ){
          offset_x = -1;
          offset_y = 1;
          continue;
        }
        if( offset_x == -1 && offset_y == 1 ){
          offset_x = -1;
          offset_y = 0;
          continue;
        }
        if( offset_x == -1 && offset_y == 0 ){
          offset_x = -1;
          offset_y = -1;
          continue;
        }
      }
    }


#1
(Правка: 18:49) 18:32, 10 сен. 2019

это вот так их нужно расставлять?

        4
      4 3 4
    4 3 2 3 4
  4 3 2 1 2 3 4
    4 3 2 3 4
      4 3 4
        4
(точка "1" - это центр, "2","3" и т.д. это следующие "слои" спирали, для расстановки юнитов)

обход графа в ширину.


Alopar
> На данный момент есть только заранее описанное смещение на 8 клеток для
> размещения юнитов вокруг первой клетки, но это в корне не верно, так как
> позволяет размещать только 45 единиц…
вот это в корне верно!
Но вместо того чтобы хардкодить 8 смещений, ты можешь сгенерировать (кодом) список который бы охватывал бы всю карту (максимуальную по размеру).
И при размерещении просто проходишь список и расставляешь юниты относительно смещения.
Экономить будет время и силы координально.

#2
18:51, 10 сен. 2019

Ну в принципе можно и так :)


Я просто зациклился на

 3 3 3 3 3 
 3 2 2 2 3   
 3 2 1 2 3 
 3 2 2 2 3 
 3 3 3 3 3 
#3
(Правка: 18:56) 18:53, 10 сен. 2019

примерный код заполнения списка:

  rng := max(width, height)

  for rng:=1 to max(MaxMapwidth, MaxMapheight) do

    // по часовой ... с 12 часов до 3х)
    for y:=cy-rng to cy+1 do
      for x:=cx to cx+rng-1 do
        add_list(cx-x,cy-y);

    // по часовой ... с 3х часов до 6)
    for y:=cy downto cy-rng do
      for x:=cx+rng-1 downto cx+1 do
        add_list(cx-x,cy-y);

    // по часовой ... с 6 до 9)

    // по часовой ... с 9 до 12)
  end;
Alopar
> Я просто зациклился на
без разницы. Всё зависит от того, как ты "шаблонный" список заполнишь.

Хотя тут есть ньюансы.
Допустим у тебя 9 юнитов. Как должно быть заполнено поле?

. 4 .
. 5 .
. . .
или
. 1 .
1 5 1
. 1 .
или
. 1 1
. 5 1
. . 1
?

#4
18:56, 10 сен. 2019

skalogryz

Тот что надо не хардкодить а генерировать я понимаю, но алгоритм не могу осознать (про спираль)

Не совсем понял что тут имеется в виду:

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

#5
18:58, 10 сен. 2019

skalogryz

Если юнитов 9 должно быть

 . 4 . 
 . 5 .
 . .  .

#6
20:55, 10 сен. 2019

skalogryz
> обход графа в ширину.

var tx = ds_queue_create();  
var ty = ds_queue_create(); 
ds_queue_enqueue(tx, cell_x ); // 5 - это 
ds_queue_enqueue(ty, cell_y ); // 

// координаты соседних клеток
ofsx[0]=0; ofsy[0]=-1;
ofsx[1]=1; ofsy[1]=0;
ofsx[2]=0; ofsy[2]=1;
ofsx[3]=-1; ofsy[3]=0;

while (units>0)&&(!ds_queue_empty(tx))
{
   var mx = ds_queue_dequeue(tx); 
   var my = ds_queue_dequeue(ty);
   if (gr[# mx, my]!=0) continue; // если клетка уже занята, то смотрим что там дальше будет
   trace (mx, my);

   gr[# mx, my]=5; // ставим юниты
   units = units - 5; 

    // ставим все ещё незанятные соседние клетки на просмотр
   for (i = 0; i<4; i++)
   {
     var nx = mx + ofsx[i]; 
     var ny = my + ofsy[i];
     if ((nx>=0) && (ny>=0)&&( nx< ds_grid_width(gr))&&(ny < ds_grid_height(gr))
       &&(gr[# nx, ny]==0)
       )
     {
       ds_queue_enqueue(tx, nx)
       ds_queue_enqueue(ty, ny)
      }
       
   }
}
ds_queue_destroy(tx);
ds_queue_destroy(ty);
#7
21:22, 10 сен. 2019

На псевдокоде очевидно:

путь = 1

10:поступательно двигаться на путь
20:поворот на 90
30:поступательно двигаться на путь
40:поворот на 90
50:путь++
60:гото 10

Таки в чем проблема-то?

#8
(Правка: 21:46) 21:37, 10 сен. 2019

Alopar
> Третий день бьюсь… просмотрел разные алгоритмы в инете, для заполнения массивов цифрами по спирали, но не могу их осознать.
Да там вроде довольно несложно.
Берём "карандаш" и не отрывая от листочка рисуем:

    .J
GGGGFJ
HCCBFJ
HD0AFJ
HDEEEJ
HIIIII
Здесь буквами обозначены отрезки линий, до смены направления.
Замечаем, что длины линий образуют последовательность: 1, 1, 2, 2, 3, 3, 4, 4, ... .
Ну и дальше это влобно кодим.

Тема такая была, но гугл что-то неохотно помогает.

Код получается что-то вроде такого (не тестил):

int x=0,y=0; // Current position.
int dx[4]={+1, 0,-1, 0}; // X offsets.
int dy[4]={ 0,+1, 0,-1}; // Y offsets.
for(int r=0;r<R;++r) // Circle.
    for(int d=0;d<4;++d) // Direction.
        for(int i=0;i<1+2*r+d/2;++i) // Segment length.
        {
            output(x,y); // Fill table at x,y.
            x+=dx[d];
            y+=dy[d];
        }
Заполняет как на рисунке: против часовой стрелки, начиная с "вправо".

И jaguard схожее вроде говорит.

#9
(Правка: 22:11) 22:02, 10 сен. 2019

Alopar
> Я просто зациклился на
>
> 3 3 3 3 3
> 3 2 2 2 3
> 3 2 1 2 3
> 3 2 2 2 3
> 3 3 3 3 3
Ну и нормально ты зациклился. Из твоих колец видно, что нужно найти номер кольца, а потом индекс на кольце.
Если присмотреться внимательно, то начиная со второго кольца и дальше - каждое следующее кольцо на 4 больше чем предущее. Это классическая арифметическая прогрессия. n-ый член этой прогрессии вычисляется по формуле:
Изображение
Теперь если мы найдем n, то найдем и индекс кольца (я возьму индексацию с нуля, чтобы избавится от единицы):
n = floor( (idx - 1)/4 );
Теперь, когда мы нашли индекс кольца - нужно найти место элемента на кольце:
loop_idx = idx - (1+n*4)
Осталось понять как индекс на кольце перевести в координаты. Рассмотрим кольцо. Его условно можно разделить на 4 ребра:
edges | Алгоритм обхода поля (двумерного массива) по спирали (улитке)
Длина одного ребра равна n+2. Отсюда находим индекс ребра и индекс на ребре:
edge_idx = loop_idx / (n+2)
edge_pos_idx = loop_idx % (n+2)
По индексу ребра определяем начальную точку и направление, по которым собственно уже находитм координаты.

#10
(Правка: 22:45) 22:36, 10 сен. 2019

skalogryz

Всем большое спасибо, а skalogryz'у просто огромное :)


Я все равно пока не понимаю как это работает (может утром станет понятнее :)), но я переписал код под себя и теперь все просто идеально работает :)

Формируется массив с координатами потом на его основе пока рисуются точки. Потом доделаю под себя, тут уже дело техники :)

Вот в общем что получилось:

/// @function scr_draw_points

global.grField = ds_grid_create(ROOM_CELL_W, ROOM_CELL_H);

var result = [];
var gr = global.grField;

var units = 55;

var cell_x = 3;
var cell_y = 3;

var tx = ds_queue_create();  
var ty = ds_queue_create(); 
ds_queue_enqueue(tx, cell_x); // 5 - это 
ds_queue_enqueue(ty, cell_y); // 

// координаты соседних клеток
var ofsx = [];
var ofsy = [];

  ofsx[0] = 0;
  ofsy[0] = -1;
  
  ofsx[1] = 1;
  ofsy[1] = 0;
  
  ofsx[2] = 0;
  ofsy[2] = 1;
  
  ofsx[3] = -1;
  ofsy[3] = 0;
  
  ofsx[4] = 1;
  ofsy[4] = -1;

  ofsx[5] = 1;
  ofsy[5] = 1;

  ofsx[6] = -1;
  ofsy[6] = 1;

  ofsx[7] = -1;
  ofsy[7] = -1;
  
while( (units > 0) && (!ds_queue_empty(tx)) ){
   var mx = ds_queue_dequeue(tx);
   var my = ds_queue_dequeue(ty);
   if ( gr[# mx, my] != 0 ) continue; // если клетка уже занята, то смотрим что там дальше будет   

   gr[# mx, my] = 5; // ставим юниты   
   var sx = (mx * ROOM_CELL_SIZE + (ROOM_CELL_SIZE / 2));
   var sy = (my * ROOM_CELL_SIZE + (ROOM_CELL_SIZE / 2));
   
   var arrsize = array_height_2d(result);
   result[arrsize, 0] = sx;
   result[arrsize, 1] = sy;
   
   units = units - 5;

    // ставим все ещё незанятные соседние клетки на просмотр
   for(var i = 0; i < 8; i++){
     var nx = mx + ofsx[i]; 
   var ny = my + ofsy[i];
     if ( (nx >= 0) && (ny >= 0) && (nx < ds_grid_width(gr)) && (ny < ds_grid_height(gr)) && (gr[# nx, ny] == 0) ){
    ds_queue_enqueue(tx, nx);
    ds_queue_enqueue(ty, ny);
      }
   }
}
ds_queue_destroy(tx);
ds_queue_destroy(ty);

return result;

#11
22:41, 10 сен. 2019

Сорян, выше формулы неправильные. Там нужно из суммы членов получать индекс лупа :)

#12
1:38, 11 сен. 2019

Запилил таки функцию:
https://www.shadertoy.com/view/3scGWr

#13
10:12, 11 сен. 2019

MrShoor

Круто, но разобраться в ней не просто :)))
Я правильно понимаю что это по сути шейдерные инструкции?

#14
(Правка: 12:49) 12:48, 11 сен. 2019

Alopar
самое простое, без формул:

  • берешь rectangle и описываешь им стартовую точку
  • заполняешь точки на гранях юнитами (координаты берешь из вершин)
  • rectangle.inflate(1) и по новой пока не кончатся юниты или карта
  • Страницы: 1 2 Следующая »
    ПрограммированиеФорумИгровая логика и ИИ