IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Волновой алгоритм, Обьясните по человечески
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


Ну ни как не могу врубится в волновой алгоритм! Плиз пример кода простой и понятный!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Путь в двумерном лабиринте - волновой алгоритм
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


Эту статью я уже нагугливал =( Volvo, если не труднол мог бы ты коменты поставить там где пример на паскале и выложить сюда?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


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


Гость






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

Попробуй совместить программу с Алголиста с этими комментариями...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Каждый раз пробегать весь мосив , допустим ищю 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;



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


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

Вот как я сделал (извените что на фениксе я думаю будет понятно они с паскалем очень схожи)
Код
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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


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

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

Сообщение отредактировано: XaMMaX -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


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

Сообщение отредактировано: XaMMaX -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

С опытом у тебя это будет получаться все лучше, но только если начнешь пробовать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Нормально дается, стараешься, и выходит. В начале так и должно быть. Давай, приходи, будем смотреть. И паскалевский код я хоть подебажить смогу smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(XaMMaX @ 22.11.2006 20:53) *

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


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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 85
Пол: Мужской
Реальное имя: max

Репутация: -  0  +


А я исключил это сразу =) Ну раз правильно двигаюсь дальше! Ещё приду!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Приходи smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 7:39
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name