Войти
ПрограммированиеФорумОбщее

Поиск пути: сглаживание

Страницы: 1 2 3 Следующая »
#0
13:36, 29 авг. 2014

Делаю волновой алгоритм по регулярной сетке, с добавлением "цены" прохода по клеткам.
Возник такой вопрос, как можно на пустой карте сделать "линию" между двумя точками
когда ищем путь по уже построенной карте.

первая идея была понижать цену шага если этот путь сокращает расстояние и т.д.
Получилось чу-чуть лучше

вместо

000000000000000
0*0000000000000
00*000000000000
000*00000000000
0000*0000000000
00000*000000000
000000*********

получить


000000000000000
0*0000000000000
00**00000000000
0000**000000000
000000**0000000
00000000**00000
0000000000*****

но хотелось более правильную картинку

есть способы её получить?

в идеале получить прямую по Брезенхэму ^_^


#1
14:02, 29 авг. 2014

IROV..
> Получилось чу-чуть лучше
Через расстояния от начальной и конечной точки

#2
14:16, 29 авг. 2014

CasDev
расшифруй :)

#3
14:58, 29 авг. 2014

Минимальное расстояние до начальной точки
> 000000000000000
> 0*0000000000000
> 00**00000000000
> 0000**000000000
> 000000**0000000
> 00000000**00000
> 0000000000*****

Минимальное расстояние до конечной точки
> 000000000000000
> 0*****000000000
> 000000**0000000
> 00000000**00000
> 0000000000**000
> 000000000000**0
> 00000000000000*

distanceA = расстояние от проверяемой точки до начальной
distanceB = расстояние от проверяемой точки до конечной
min = sqrt(distanceA^2 + distanceB^2)
> 000000000000000
> 0**000000000000
> 000***000000000
> 000000**0000000
> 00000000**00000
> 0000000000***00
> 0000000000000**

#4
15:06, 29 авг. 2014

CasDev
сейчас проверим

***********************************

  • *o********************************
  • **o*******************************
  • ***o******************************
  • ****ooooooooooooooooooooooo*******
  • ***************************o******
  • ****************************o*****
  • *****************************o****
  • **********************************
  • **********************************
  • уже интересней

            float mdd = 100000.f;
            uint32_t mi = 0;
    
            for( uint32_t i = 0; i != 8; ++i )
            {
              uint16_t px = p.x + cell_angle_to_deltha_x[i];
              uint16_t py = p.y + cell_angle_to_deltha_y[i];
    
              if( px >= m_width || py >= m_height )
              {
                continue;
              }
    
              point pp(px, py);
              float d1 = s_point_distance_f( pp, m_to );
              float d2 = s_point_distance_f( pp, m_from );
    
              float dd = sqrtf(d1 * d1 + d2 * d2);
    
              if( mdd > dd )
              {
                mdd = dd;
                mi = i;
              }
            }

    может где-то ошибся? :)

      //////////////////////////////////////////////////////////////////////////
      inline static float s_point_distance_f( point p0, point p1 )
      {
        float ax = (float)(p1.x - p0.x);
        float ay = (float)(p1.y - p0.y);
    
        return sqrtf(ax * ax + ay * ay);
      }
    #5
    15:47, 29 авг. 2014

    IROV..
    Я торможу.
    Корень из суммы квадратов дистанций нах не нужен, можно судить по сумме дистанций от начальной и конечной точки.

    Теория то простая
    Image Hosted by PiXS.ru

    #6
    16:06, 29 авг. 2014

    CasDev

    #7
    16:28, 29 авг. 2014

    CasDev

  • *********#************************
  • *****o***#************************
  • ******o**#************************
  • *******o*#************************
  • ********o#************************
  • ********o#****ooooooo*************
  • ********o#***o*******oooo*********
  • ********o#**o************ooooo****
  • ********o#*o**********************
  • ********ooo***********************
  • но по ходу у меня концептуально не правильно :)

    попробую сейчас запоминать "барьер" откуда пришла "волна" и брать её за основу

    #8
    16:49, 29 авг. 2014

    IROV..
    И тут все довольно просто
    Image Hosted by PiXS.ru

    #9
    17:01, 29 авг. 2014

    Ищи среднее между поиском пути и оптимальной линией
    https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

    #10
    17:06, 29 авг. 2014

    CasDev
    А в чем магия треугольник? :)

    #11
    17:07, 29 авг. 2014

    Osiris
    Алгоритм поиска пути с помощью брезенхема уже был написан, и там все корректно работало, но он не мог учитывать "весы" узлов

    #12
    17:17, 29 авг. 2014

    Твоя задача сперва найти граф, по которому можно провести отрезки из точки А в точку Б.
    Ищутся они следующим образом.

    1. Из точки А в точку Б проводится прямая - она проходит без препятствий - оке.
    Нашли препятствие? Отлично
    2. Берем точки, примыкающие к препятствию. Точкой С будет точка, наиболее удаленная от точек А и Б.
    Далее по п.1. исследуем отрезок А и С. Если он отл - берем отрезок С и Б.

    Ну все просто же.
    Image Hosted by PiXS.ru
    P|S не стесняемся пользовать увеличительные очки :)

    Да алгоритм чуть косячный, но идея вроде понятна. Примыкающие точки надо брать только из тех точек, которые построены обычным построением с А до Б.
    Наглядно это видно из примера если строить из Б в А.

    #13
    17:41, 29 авг. 2014

    CasDev
    > 1. Из точки А в точку Б проводится прямая - она проходит без препятствий - оке.
    > Нашли препятствие? Отлично
    Прям тут ошибка, я не могу проводить прямые, есть веса, например в пару шагов от тебя есть "Спец" дорога по которой в 10 раз быстрее :) тут только волновой, только хардкор :)

    #14
    17:56, 29 авг. 2014

    IROV..
    И на эту закавыку свой лом находится.
    Простой пример.
    Ты массив точек заполняешь с учетом весов. По нему строишь точками любой путь с минимальным весом.
    Далее проходишь по этому пути. И смотришь у каждой точки - нет ли точек с таким же весом РЯДОМ? Если нет - точка графа.
    Если есть - исключаешь из графа.
    Имея граф точек, т.е. отрезки - пробуешь соединить их по вышеприведенному алгоритму.

    Стоп - не так.

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

    Страницы: 1 2 3 Следующая »
    ПрограммированиеФорумОбщее

    Тема в архиве.