#cpp #алгоритм
Как можно установить в двумерный массив потенциал?
К примеру я задаю точки (X, Y) в которые нужно установить потенциал, например, хочу
в матрице установить потенциал размером 10 в координаты (2, 2) и вот что я ожидаю получить:
{
2, 4, 6, 4, 2,
4, 6, 8, 6, 4,
6, 8, 10, 8, 6,
4, 6, 8, 6, 4,
2, 4, 6, 4, 2
}
Т. е. нужно чтобы из данный точки градиентом расходились значения от максимального
к минимальному.
Как это можно сделать красиво? У меня есть лишь нелепые конструкции, которые выглядят
ужасно. Можно увидеть пример реализации такой штуки?
Для наглядности еще вот картинка:
Здесь установлены 2 точки, со значениями 10 и -10.
Еще о потенциалах:
Использование потенциальных полей в сценарии стратегии реального времени (Хабр)
Поиск пути: метод потенциальных полей
Ответы
Ответ 1
Когда начал писать ответ, заметил, что авторский массив «то что ожидаю получить» не совпадает с картинкой. Конкретики в этом вопросе мало. Поэтому приведу две разные версии таких полей. 1. Общий код Общий для обеих версий код: #include#include #define MAP_WIDTH 30 #define MAP_HEIGHT 30 void print_map(int* map, int w, int h) { for (int y = 0; y < MAP_HEIGHT; ++y) { for (int x = 0; x < MAP_WIDTH; ++x) { // Вместо нулей печатаем пробелы, чтобы не сломать глаза :) (map[x + y*MAP_WIDTH] == 0) ? printf(" ") : printf("%2i ", map[x + y*MAP_WIDTH]); } putchar('\n'); } } <...> int main() { int map[MAP_HEIGHT][MAP_WIDTH] = {{0}}; 2. Уменьшение веса точки в зависимости от расстояния до центра Вес каждой точки должен уменьшатся по мере удаления от центра. Но как? Если честно, я так и не смог подобрать правило, чтобы веса уменьшались как на картинке. Поэтому предоставлю код для линейного уменьшения весов. // map - матрица целых чисел, w, h -- его высота и ширина соответственно. // x и y -- координаты центра поля. // start_value -- очевидно, начальное значение. // attenuation_constant -- коэффициент затухания. void set_potential(int* map, int w, int h, int x, int y, int start_value, int attenuation_constant) { // Вычисляем максимальное удаление от центра по вертикали/горизонтали. int verical_and_horizontal_steps_nm = start_value / attenuation_constant; int box[2][2] = { {x - verical_and_horizontal_steps_nm + 2, y - verical_and_horizontal_steps_nm + 2}, {x + verical_and_horizontal_steps_nm - 1, y + verical_and_horizontal_steps_nm - 1} }; for (int dot_y = box[0][1]; dot_y < box[1][1]; ++dot_y) { for (int dot_x = box[0][0]; dot_x < box[1][0]; ++dot_x) { // Считаем расстояние до точки по формуле d = sqrt((x0-x1)^2 + (y0-y1)^2). int distance = sqrt((x-dot_x)*(x-dot_x) + (y-dot_y)*(y-dot_y)); // Значение текущей точки меняется линейно. int dot_value = start_value - distance * attenuation_constant; // Если точка не лежит на вертикали или горизонтали от центральной мы считаем // значение по-другому, т. к. диагональ квадрата всегда больше его стороны. // Т. к. длина стороны у нас -- 1, то длина диагонали будет sqrt(2). if (dot_y != y && dot_x != x) dot_value = start_value - round(sqrt(2) * distance * attenuation_constant); // Чтобы не было отрицательных коэффициентов по углам добавляем условие. map[dot_x + dot_y*MAP_WIDTH] = dot_value > 0 ? dot_value : 0; } } } Вот вывод для set_potential((int*)map, MAP_WIDTH, MAP_HEIGHT, 15, 15, 10, 2): 2 2 4 2 2 2 4 4 6 4 4 2 2 4 7 8 7 4 2 4 6 8 10 8 6 4 2 4 7 8 7 4 2 2 4 4 6 4 4 2 2 2 4 2 2 Не очень похоже на картинку, зато веса зависят непосредственно от расстояния до центра. 3. Даже не знаю, как назвать вариант. Смотрите сами… Если мы получше рассмотрим левую нижнюю (а вообще, любую) четверть картинки или массив «ожидания» автора, то заметим, что Все числа, расположенные на одной диагонали, равны; Каждое число на следующей диагонали (при расхождении от центра) ровно на один шаг (я назвал его коэффициентом затухания) больше любого числа на предыдущей диагонали; Длина каждой диагонали больше предыдущей на единицу. Сложно объяснить словами, взгляните сами (коэфф. затухания = 2): 1. 10 (- 2 = 8) 2. 8 8 (- 2 = 6) 3. 6 6 6 (- 2 = 4) 4. 4 4 4 4 (- 2 = 2) 5. 2 2 2 2 2 Четыре таких четверти (правильно повернутые) дадут нужную картинку (которая, кстати, является ромбом, что и нужно автору (см. комментарии к вопросу)). Алгоритм рисования очень простой, думаю, все будет понятно из кода: void set_potential2(int* map, int w, int h, int x, int y, int start_value, int attenuation_constant) { // Заполняем центр. map[x + y*MAP_WIDTH] = start_value; // Вычисляем максимальное удаление от центра по вертикали/горизонтали. int verical_and_horizontal_steps_nm = start_value / attenuation_constant; // Здесь i -- расстояние от центра до текущей точки. for (int i = 1; i < verical_and_horizontal_steps_nm; ++i) { int dot_value = start_value - attenuation_constant * i; // Заполняем левый нижний угол: // // dot_y = y+i -- переходим в точку максимального отдаления по вертикали от центра. // dot_x = x -- координата x точки равна координате центра. // do_y >= y; --dot_y -- пока находимся выше центра, поднимаемся вверх. // --dot_x -- смещаемся влево. // // Т. е. мы как-бы по ступенькам поднимаемся вверх-влево, вверх-влево, вверх-влево... // Для остальных углов меняем только направления в заголовке цикла. for (int dot_y = y+i, dot_x = x; dot_y >= y; --dot_y, --dot_x) // Тоже самое, что map[dot_x][dot_y] map[dot_x + dot_y*MAP_WIDTH] = dot_value; // Правый нижний угол for (int dot_y = y+i, dot_x = x; dot_y >= y; --dot_y, ++dot_x) map[dot_x + dot_y*MAP_WIDTH] = dot_value; // Левый верхний угол for (int dot_y = y-i, dot_x = x; dot_y <= y; ++dot_y, --dot_x) map[dot_x + dot_y*MAP_WIDTH] = dot_value; // Правый верхний угол for (int dot_y = y-i, dot_x = x; dot_y <= y; ++dot_y, ++dot_x) map[dot_x + dot_y*MAP_WIDTH] = dot_value; } } Вот что выдает алгоритм при set_potential2((int*)map, MAP_WIDTH, MAP_HEIGHT, 9, 9, 10, 2): 2 2 4 2 2 4 6 4 2 2 4 6 8 6 4 2 2 4 6 8 10 8 6 4 2 2 4 6 8 6 4 2 2 4 6 4 2 2 4 2 2 Автор привел обрезанный массив: { 2, 4, 6, 4, 2, 4, 6, 8, 6, 4, 6, 8, 10, 8, 6, 4, 6, 8, 6, 4, 2, 4, 6, 4, 2 } Обрежем наш результат: 2 4 6 4 2 4 6 8 6 4 6 8 10 8 6 4 6 8 6 4 2 4 6 4 2 Сходство налицо. Думаю, это именно то, что нужно было автору. По-моему, красота :) P. S. Код не очень, конечно, но для иллюстрации идеи — пойдет. P. S. S. Если честно, не знаю как правильно перевести «коэффициент затухания»: «attenuation constant» или «damping constant». Если кто исправит, будут признателен. Ответ 2
Ну, задайте какую-то функцию падения потенциала и вычисляйте потенциал в конкретных ячейках, исходя из их расстояния до центральной, и округляя значения до целых, если вам нужны именно они.Ответ 3
Вот еще способ (он иной чем описан выше): #ifndef POTENTIALFIELD_H #define POTENTIALFIELD_H #includetemplate class PotentialField { public: PotentialField() { size_x = x; size_y = y; fillAll(0.f); } /* x, y - координаты в матрице value - максимальное значение данной точки force - применяемая сила к данной точке (force * value) fixedRadius - рисовать только по радиусу а не по всей карте radius - радиус (работает только когда fixedRadius == true) */ void setPoint(size_t _x, size_t _y, float value, float force = 0.08f, bool fixedRadius = false, float radius = 0.f) { if (_x > size_x - 1 || _y > size_y - 1) // TODO: возможно стоит выкинуть исключение return; size_t distance = 0; for (size_t i = 0; i < size_y; i++) { for (size_t j = 0; j < size_x; j++) { if (fixedRadius && (j < _x - radius || j > _x + radius || i < _y - radius || i > _y + radius) ) continue; distance = getDistance(_x, _y, j, i); if (distance == 0) { matrix[i][j] = value * force; } else { matrix[i][j] += force * value / distance; } } } } float getDistance(float x1, float y1, float x2, float y2) { return std::sqrt( ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)) ); } // Матрица затирается заданным значением void fillAll(float val = 0.f) { float *ptr = &matrix[0][0]; float *end = &matrix[size_y - 1][size_x]; while (ptr < end) { *ptr = val; ++ptr; } } void print() { for (size_t i = 0; i < size_y; i++) { for (size_t j = 0; j < size_x; j++) { std::cout.width(5); std::cout.precision(2); std::cout << matrix[i][j] << ' '; } std::cout << std::endl; } } private: size_t size_x; size_t size_y; float matrix[y][x]; }; #endif Пример использования: int main(){ PotentialField<20, 20> field(); field.setPoint(0, 0, 10); } Создается поле размером 20 на 20, и в координаты x = 0, y = 0 устанавливается потенциал который распространяется по формуле force * value / distance Вдруг кому пригодиться =)
Комментариев нет:
Отправить комментарий