Ошибка в волновом алгоритме поиска пути

[Armageddets]

Всем доброго времени суток. Я занялся созданием поиска пути волновым алгоритмом, но в ходе тестирования я выявил ошибку. В общем смысл таков. Каждая цена соседней клетки должна увеличиваться на 100. Влево, вправо и вверх всегда увеличивается правильно. Но вот вниз считается правильно только до того момента первого хода. Как только персонаж сдвинулся с места. Цена клеток вниз считается не правильно. А именно начиная со второй клетки снизу прибавляется лишнее число 200. Никак не смог найти причину почему? По логике все реализовано правильно. А самое интересное, что если убрать увеличение цены вправо, и двигаться по одной клеточке вправо, то цены вниз считаются абсолютно правильно. Этот момент вообще сбивает с толку. В общем помогите мне исправить алгоритм так, чтобы вниз цены изменялись так же как и в остальные стороны. Я заранее всем благодарен.

https://yadi.sk/d/VjEbcoWdfaq8b

[FPaul]

1. Мне кажется, что это не совсем волновой алгоритм (по признаку отсутсвия структуры "очередь").
2. А кроме того, мне также кажется, что отсутсвует критерий "клетка уже рассматривалась", и нижняя учитывается при движении вниз, а также при попадании на неё слева и справа (=несколько раз). Вернее, она и должна рассматриваться несколько раз, но +100, в матрицу не должно заносится.
3. Мне, опять же, кажется, что волновой алгоритм в исходном виде здесь неприменим - т.к. присутсвует стоимость прохождения клетки. Наверное, лучше здесь использовать алгоритм Дейкстры для разряженного графа (для расчёта оптимального по затратам пути из одной клетки во все остальные), пересчитывая всё на каждом ходу, или алгоритм Флойда-Уоршелла (для расчёта оптимального по затратам пути из всех клеток во все остальные), рассчитав её один раз в начале игры. Единственно, взять эти алгоритмы в готовом виде не удастся - они используют представление графа в другом виде - но это меньшая проблема.
4. Чтобы проще учитавать +100 за каждую клетку, я бы просто посчитал длину пути и умножил на 100, без модификации каких либо матриц. При этом, учитывал бы возможность переполнения разрядной сетки.

Вот здесь Poma][a реализовывает алгоритм Дейкстры для разряженного графа.
------------------------
Возможно, что я неправильно понял исходник, и всё решение ограничится пунктом 4.

P.S. У меня нет Delphi, поэтому проверить не смогу.

[rrrFer]

выложи исходники на форум

[Poma][a]

Мне кажется, что это не совсем волновой алгоритм (по признаку отсутсвия структуры "очередь").

Именно волновой
С очередью уже bfs

А код.. Он на дельфийском.. И он не понятный..
Поэтому выложите лучше задание

[Armageddets]

Задание состоит следующее. Пишу стратегическую игру. У нас есть персонаж Hero, есть игровая карта Map (Двухмерный массив), и есть массив по размеру игровой карты для расстановки весов карты Hero.HeroWay. И есть штрафы/бонусы местности Hero.Ground. На данный момент штрафы местности все равны нулю, поэтому особой роли пока не играют, но затем будут играть, поэтому просто перемножить путь на 100 наверное не получится.

Теперь на словах опишу работу алгоритма (по крайней мере я стремился сделать так, может где-то и ошибся). Первый делом всем на всех клетках весам присваиваем нули. Соседние от героя клетки сразу же отмечаем сотнями. Далее в цикле мы пробегаем по всем клеткам и смотрим если найдена клетка, которая больше нуля (изначально это соседние клетки), то присваиваем всем соседним клеткам (диагонали я пока не учитываю) цену данной клетки+100. Но вот я никак не пойму почему вниз дополнительно пару сотен добавляется, ведь в алгоритме прописано, чтобы прибавлялись данные сотни в клетки, которые пустые. А если в них что-то уже записывалось и прибавлялось, то по идее не должно ничего добавляться.

Спасибо всем, кто откликнулся! Но проблему пока не нашел, умаю может в компиляторе проверки по отключать какие-то...

Алгоритм проставления весов таков:

    //Очищаем вес клеток в массиве размером с игровую карту
    for i:=0 to Game.MapWidth-1 do
    for j:=0 to Game.MapHeight-1 do
    HeroWay[i,j]:=0;

    //на соседнихклетках ставим сразу же сотни, чтобі потом в цикле увеличивать цифрі дальше
    if (Hero.X-1>=0) and (Map[Hero.X-1,Hero.Y].Grn>0) then
    Hero.HeroWay[Hero.X-1,Hero.Y]:=
    100+Hero.Ground[Map[Hero.X-1,Hero.Y].Grn];

    if (Hero.X+1<=Game.MapWidth-1) and (Map[Hero.X+1,Hero.Y].Grn>0) then
    Hero.HeroWay[Hero.X+1,Hero.Y]:=
    100+Hero.Ground[Map[Hero.X+1,Hero.Grn];

    if (Hero.Y-1>=0) and (Map[Hero.X,Hero.Y-1].Grn>0) then
    Hero.HeroWay[Hero.X,Hero.Y-1]:=
    100+Hero.Ground[Map[Hero.X,Hero.Y-1].Grn];

    if (Hero.Y+1<=Game.MapHeight-1) and (Map[Hero.X,Hero.Y+1].Grn>0) then
    Hero.HeroWay[Hero.X,Hero.Y+1]:=
    100+Hero.Ground[Map[Hero.X,Hero.Y+1].Grn];

    
    n:=0;
    while (n<30) do
    begin
      for i:=0 to Game.MapWidth-1 do
      for j:=0 to Game.MapHeight-1 do
      begin
        if (Map[i,j].Grn>0) and (Hero.HeroWay[i,j]>0) then
        begin
          //sleva
          if (i-1>=0) and (Map[i-1,j].Grn>0) and (Hero.HeroWay[i-1,j]=0) then
          begin
          Hero.HeroWay[i-1,j]:=Hero.HeroWay[i,j]+100+Hero.Ground[Map[i-1,j].Grn];
          end;
          //sprava
          if (i+1<=Game.MapWidth-1) and (Map[i+1,j].Grn>0) and (Hero.HeroWay[i+1,j]=0) then
          begin
          Hero.HeroWay[i+1,j]:=Hero.HeroWay[i,j]+100+Hero.Ground[Map[i+1,j].Grn];
          end;
          //sverhu
          if (j-1>=0) and (Map[i,j-1].Grn>0) and (Hero.HeroWay[i,j-1]=0) then
          begin
          Hero.HeroWay[i,j-1]:=Hero.HeroWay[i,j]+100+Hero.Ground[Map[i,j-1].Grn];
          end;
          //snizu
          if (j+1<=Game.MapHeight-1) and (Map[i,j+1].Grn>0) and (Hero.HeroWay[i,j+1]=0) then
          begin
          Hero.HeroWay[i,j+1] := Hero.HeroWay[i,j] +100+ Hero.Ground[Map[i,j+1].Grn];
          end;
        end;
      end;
    Inc(n);
    end;

[Poma][a]

FPaul уже писал, что волновой алгоритм при такой постановке задачи Вам не помощник. (Если я правильно понял, необходимо найти минимальный путь из одного элемента двумерного массива в другой. Причем стоимость перехода из a[i][j] в a[i+p][j+q] (где p, q принадлежат {-1, 0, 1} не везде одна и та же)

[FPaul]

Для понимания, где ошибка, на консольной программе в FreePascal, я бы поставил точки останова, образовал бы перечень наблюдаемых переменных, и прошёлся бы пошаговым отладчиком. Delphi продают за очень большие деньги, и в них тоже должен быть такой функционал.
И да, здесь бы подошел алг.Дейкстры для разр.гр. (смесь алг.Дейкстры и bfs), а лучше алг. Флойда-Уоршелла. Потому, что волновой алгоритм (алгоритм Ли) рассчитан на поиск пути на невзвешенном графе.

[Poma][a]

И да, можно использовать волновой.. Только он будет работать чуть дольше.. и реализация чуть сложнее (ибо там куча и все такое)

[Armageddets]

Да возможность ставить точки останова есть. Да и данный алгоритм минимальные пути влево, впаро и вверх всегда считает правильно. А вот вниз добавляет лишние 200 и тоже дадбше считает правильно. Вот надо эти 200 и отловить собственно.

А возможно и прийдется применить предложенные Вами алгоритмы. В любом случае. Спасибо всем!