Волновой алгоритм, Обьясните по человечески Опции

[XaMMaX]

Ну ни как не могу врубится в волновой алгоритм! Плиз пример кода простой и понятный!!

[volvo]

Путь в двумерном лабиринте - волновой алгоритм

[XaMMaX]

Эту статью я уже нагугливал =( Volvo, если не труднол мог бы ты коменты поставить там где пример на паскале и выложить сюда?

[XaMMaX]

Единственное что мне пришло в голову это:
Каждый раз пробегать весь мосив , допустим ищю 1 пробегаю массив и каждому найденому 1 применяю процедуру(для обозначения 2) потом так же с два и т.д. но ресурсов я чувствую это сожрёт не меренно =) Volvo, HELP!!!

[volvo]

Объяснение алгоритма (только без программы) есть здесь:
Волновой алгоритм - Построение крaтчaйшего мaршрутa

Попробуй совместить программу с Алголиста с этими комментариями...

[Michael_Rybak]

Каждый раз пробегать весь мосив , допустим ищю 1 пробегаю массив и каждому найденому 1 применяю процедуру

Молодец. Это правильно, и это будет работать, но, действительно, медленно.
Вместо того, чтобы каждый раз бегать по всему массиву, лучше заведи еще другой, линейный массив записей (x, y), в который пихай все вершины, в которые что-пишешь. И просто иди по нему слева направо. Вроде такого:

type TCoord = record x, y: integer end;
var pp: array[1 .. 100] of TCoord;
    np: integer; //количество пройденных клеток
    mark: array[1 .. 10, 1.. 10] of integer;

procedure Wave(i0, j0: integer);
  var i, j, cp: integer;
      p, p1: TCoord;
begin
  //все поле заполняем минус единицами
  for i := 1 to 10 do
    for j := 1 to 10 do
      mark[i, j] := 1;

  if a[i0, j0] = 0 then
    exit; //клацнули по пустой клетке

  //в начале обошли только клацнутую клетку
  mark[i0, j0] := 0;
  p.x := i0;
  p.y := j0;
  np := 1;
  pp[1] := p;

  cp := 1;
  while cp <= np do begin
    p := pp[cp]; //текущая клетка
    if (p.x < 10) and (a[p.x + 1, p.y] = 0) and (mark[p.x + 1, p.y] = -1) then begin
      p1.x := p.x + 1;
      p1.y := p.y;
      mark[p1.x, p1.y] := mark[p.x, p.y] + 1;
      np := np + 1;
      pp[np] := p1;
    end;
    if (p.x > 1) and (a[p.x - 1, p.y] = 0) and (mark[p.x - 1, p.y] = -1) then begin
      ...
    end;
    if (p.y < 10) and ...
    if (p.y > 1) and ...
 
    cp := cp + 1;
  end;
end;

[XaMMaX]

Мда чё то не работает =(

Вот как я сделал (извените что на фениксе я думаю будет понятно они с паскалем очень схожи)

Код

process wave(i0,j0);
private
i;j;cp;
struct p;
x;
y;
end  

struct p1;
x;
y;
end

begin        

from i=1 to 9 step 1
  from j=1 to 9 step 1
    mark[i][j]=-1;
  end
end  
            
mark[i0][j0]=0;  
p.x=i0;
p.y=j0;
np=1;
pp[1].x=p.x;
pp[1].y=p.y;
cp=1;            
while cp<=np :  
    p.x = pp[cp].x;
    p.y = pp[cp].y;
    if ((p.x < 10) and (balls[p.x + 1][ p.y].color == 0) and (mark[p.x + 1][ p.y] == -1))
      p1.x = p.x + 1;
      p1.y = p.y;
      mark[p1.x][p1.y] = mark[p.x][p.y] + 1;
      np++;
      pp[np].x = p1.x;
      pp[np].y = p1.y;   write(0,0,10,0,"right");
    end;                
    if ((p.x > 1) and (balls[p.x - 1][ p.y].color == 0) and (mark[p.x - 1][ p.y] == -1))
      p1.x = p.x - 1;
      p1.y = p.y;
      mark[p1.x][p1.y] = mark[p.x][p.y] + 1;
      np++;
      pp[np].x = p1.x;
      pp[np].y = p1.y;   write(0,0,20,0,"left");
    end;
    if ((p.y < 10) and (balls[p.x][p.y+1].color == 0) and (mark[p.x][p.y+1] == -1))
      p1.x = p.x;
      p1.y = p.y + 1;
      mark[p1.x][p1.y] = mark[p.x][p.y] + 1;
      np++;
      pp[np].x = p1.x;
      pp[np].y = p1.y;   write(0,0,30,0,"down");
    end;
    if ((p.y > 1) and (balls[p.x][p.y-1].color == 0) and (mark[p.x][p.y-1] == -1))
      p1.x = p.x;
      p1.y = p.y - 1;
      mark[p1.x][p1.y] = mark[p.x][p.y] + 1;
      np++;
      pp[np].x = p1.x;
      pp[np].y = p1.y;     write(0,0,40,0,"up");
    end;    
    cp++;    
    frame;
end          

from i=1 to 9 step 1
  from j=1 to 9 step 1
    write(0,i*20,j*20,0,mark[i][j]);
    frame;
  end
end  
frame;  
end

Сообщение отредактировано: XaMMaX - 20.11.2006 20:00

[Michael_Rybak]

Ты забыл увеличить номер обрабатываемой клетки (cp := cp + 1;)

Сообщение отредактировано: Michael_Rybak - 20.11.2006 18:58

[XaMMaX]

Так опменял но чёто странные результаты(такое чувство что выполняется обработка только раз =() Может в фениксе while по другому юзается =( Тогда под repeat перестрою! Так как мне тогда условия поставить(да наверное глупый вопрос, но ника не доходит)? И вот что за фигня выходит(на скрине)


Хотя думаю дело не в фениксе где то ошибка в коде while правильно работает =(

Сообщение отредактировано: XaMMaX - 20.11.2006 19:22

[XaMMaX]

Ничё не пойму повторяется вроде правильно =\ Плиз помогите, а то буду чувствую неделю сидеть и всё равно не надуматьв чём ошибка =(

Сообщение отредактировано: XaMMaX - 20.11.2006 19:52

[Michael_Rybak]

Не ну как это называется. У тебя есть полное описание, есть мой псевдокод, а ты даешь мне код на фениксе, который я в жизни не видел, и спрашиваешь, что не работает. Ты умеешь пользоваться средствами отладки? Если их в фениксе нет, повставляй кучу write'ов, и определи, сколько раз выполняется цикл, в какой последовательности обрабатываются клетки и т.д.

С опытом у тебя это будет получаться все лучше, но только если начнешь пробовать.

[Гость]

Ну да ты прав =) Попробую в паскале сделать сначала =) Ну завтра на свежую голову лучше ждите завтра думаю пару вопросов ещё будет (хотя надеюсь вопросов больше не будет и справлюсь сам, но к сожалению это мой первый лайнс и даётся мне кое как) ^_^

[Michael_Rybak]

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

[XaMMaX]

Алилую даже на паскаль переписывать не пришлось =) Половина алгоритма сделана! Осталось теперь находить сам путь вот сдесь у меня появилась проблемма =(Michael_Rybak, как ты это делаеш? Я начал так смотрю четыре ближние клетки нахожу наименьшую потом делаю то же с наименьшой и т.д. правильно? Я создал отдельную матрицу и путь обозначил цифрами 1 =)

[Michael_Rybak]

Я начал так смотрю четыре ближние клетки нахожу наименьшую потом делаю то же с наименьшой и т.д. правильно? Я создал отдельную матрицу и путь обозначил цифрами 1 =)

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

[XaMMaX]

А я исключил это сразу =) Ну раз правильно двигаюсь дальше! Ещё приду!

[Michael_Rybak]

Приходи