Суббота, 16 Ноября 2019, 01:28

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Конструкторы игр и лёгкие в освоении системы разработки игр » Game Maker Studio » Алгоритм обхода поля (двумерного массива) по спирали/улитке (Прошу помощи в разработке алгоритма)
Алгоритм обхода поля (двумерного массива) по спирали/улитке
AloparДата: Понедельник, 09 Сентября 2019, 18:24 | Сообщение # 1
уже был
Сейчас нет на сайте
Уважаемы эксперты, профессионалы и просто любители геймдева.

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

Описание проблемы

В процессе разработки пошаговой стратегии столкнулся с проблемой размещения юнитов на поле боя, а именно:
• Есть поле боя, представляет из себя сетку с клетками
• В каждой клетке может размещаться до 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;
    }
   }
  }

Добавлено (10 Сентября 2019, 22:53)
---------------------------------------------
Подсказали с решением на другом форуме, может кому будет полезно.

Решением оказалось не заморачиваться со спиралью а просто использовать алгоритм обхода в ширину :)

Вот что получилось:
В коде для тестирования алгоритма просто собирается массив точек и потом выводится на отрисовку по клеткам на карте.

Код

/// @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;


Сообщение отредактировал Alopar - Понедельник, 09 Сентября 2019, 18:59
StormTДата: Среда, 11 Сентября 2019, 18:47 | Сообщение # 2
участник
Сейчас на сайте
Благодаря тебе открыл для себя continue - никогда не видел и не использовал.


Форум игроделов » Конструкторы игр и лёгкие в освоении системы разработки игр » Game Maker Studio » Алгоритм обхода поля (двумерного массива) по спирали/улитке (Прошу помощи в разработке алгоритма)
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2019 Рейтинг