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