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 - никогда не видел и не использовал.
|
|
| |