Скажите мне, какой из варинтов будет запускаться N*M раз, а какой 2*N*M, и какая разница в них:
Вариант №1:
...
procedure setBlankAsDeadblockRec(x,y:integer);
var k:integer;
begin
k:=0;
if LABIRINT[x+1,y]<>BLANK then inc(k);
if LABIRINT[x,y+1]<>BLANK then inc(k);
if LABIRINT[x-1,y]<>BLANK then inc(k);
if LABIRINT[x,y-1]<>BLANK then inc(k);
if k=4 then LABIRINT[x,y]:=DEADBLOCK;
if k=3 then
begin
LABIRINT[x,y]:=DEADBLOCK;
if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y)
else if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1)
else if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y)
else if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1);
end;
end;
...
procedure setDeadblock;
var i,j:integer;
begin
for i:=1 to N-1 do
for j:=1 to N-1 do
if LABIRINT[i,j]=blank then setBlankAsDeadblockRec(i,j);
end;
...
Вариант №2:
...
procedure setBlankAsDeadblockRec(x,y:integer);
var k:integer;
begin
k:=0;
if LABIRINT[i,j]=blank then
begin
if LABIRINT[x+1,y]<>BLANK then inc(k);
if LABIRINT[x,y+1]<>BLANK then inc(k);
if LABIRINT[x-1,y]<>BLANK then inc(k);
if LABIRINT[x,y-1]<>BLANK then inc(k);
if k=4 then LABIRINT[x,y]:=DEADBLOCK;
if k=3 then
begin
LABIRINT[x,y]:=DEADBLOCK;
if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y)
else if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1)
else if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y)
else if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1);
end;
end;
end;
...
procedure setDeadblock;
var i,j:integer;
begin
for i:=1 to N-1 do
for j:=1 to N-1 do
setBlankAsDeadblockRec(i,j);
end;
...
Прошу прощения, неудачно вставил код, и не успевал отредактировать.
Вот он:
...
if k=3 then
begin
LABIRINT[x,y]:=DEADBLOCK;
if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y);
if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1);
if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y);
if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1);
end;
...
Действительно, после изменения порядка проверки, скорость алгоритма выросла. Изменяем код в
procedure setBlankAsDeadblockRec(x,y:integer);
...
///смотрим ниже
...
И имеем скорость работы: 0,000431 секунды. Боюсь, что есть смысл замерять скорость работы, на одном железе, и то меняется после каждого перезапуска, в зависимости от состояния ОС.
По той причине, что я подошел не правильно к применению алгоритма к данному лабиринту. А именно, без изменения рисунка. Волновой алгоритм применялся к лабиринту 1802*1802, с дорогой, толщиной в 4 пикселя, а прохождение производилось по-пиксельно.
Согласен, но для прохода всего лабиринта обычной рекурсией, функцие придется при выходе на дорогу, которая окажется тупиковой, будет возвращаться, в таком случае, все тупиковые дороге будут пройдены 2 раза. Что снижает скорость работы алгоритма.
Представленная рекурсивная функция, завершает работать только в том случае, если «находимся на дороге, а вокруг все стены» и «если находимся на дороге, а вокруг 1 стена и 2 дороги». И не проходит по одним и тем-же дорогам.
Ничего не произойдет. Будет точно такой-же результат (я попробовал на всякий случай). Здесь перебор всего массива осуществлен только для того чтоб найти все тупиковые точки, тоесть:
if LABIRINT[x,y]=blank then //...Если мы стоим на дороге...
begin
if LABIRINT[x-1,y]<>BLANK then k:=k+1;
if LABIRINT[x,y-1]<>BLANK then k:=k+1;
if LABIRINT[x+1,y]<>BLANK then k:=k+1;
if LABIRINT[x,y+1]<>BLANK then k:=k+1;
if k=4 then LABIRINT[x,y]:=DEADBLOCK;
if k=3 then//...и вокруг нас 3 стены...
begin
LABIRINT[x,y]:=DEADBLOCK; //...помечаем место где мы стоим как тупик..
if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y);//Переходим на место которое не является стенкой...
if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1);//-//-
if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y);//-//-
if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1);//-//-
end;
end;//...в противном случае выходим из функции...
И еще, возможно это вас сбивает с толку, когда вызывается рекурсивная функция setBlankAsDeadblockRec(i,j), возвращение в цикл происходит только после выхода из нее.
К сожалению, все неудачные пробы (код) не сохранился. Есть идея написать реализации нескольких алгоритмов, которые предложены в комментариях, и сравнить скорость работы конкретно на этом лабиринте.
Алгоритм такой:
Выполнять рекурсивную функцию по всем точкам дорог лабиринта:
1. Если мы стоим на дороге и вокруг нас 3 стены, помечаем место где мы стоим как тупик, в противном случае выходим из функции;
2. Переходим на место которое не является стенкой из пункта №1, и повторяем пункт №1;
Этот код необходим, для прохода всех точек, и обнаружения тупиковых.
Если такая найдена, запускается рекурсивная функция setBlankAsDeadblockRec(i,j) с координатами тупиковой позиции, и заполняется «дедблоками» до выхода из тупиковой дороги, продолжаем setDeadblock (перебор всех точек).
Ваше предложение приведет к выходу из функции.
Алгоритмы «одной руки» и А* рабочие, но не быстрые (по отношению к этому лабиринту). Поскольку все тупиковые узлы которые алгоритм проходит он проходит 2жды. И чем больше таких узлов будет тем дольше будет работать алгоритм.
Вариант №1:
Вариант №2:
Вот он:
И имеем скорость работы: 0,000431 секунды. Боюсь, что есть смысл замерять скорость работы, на одном железе, и то меняется после каждого перезапуска, в зависимости от состояния ОС.
Представленная рекурсивная функция, завершает работать только в том случае, если «находимся на дороге, а вокруг все стены» и «если находимся на дороге, а вокруг 1 стена и 2 дороги». И не проходит по одним и тем-же дорогам.
И еще, возможно это вас сбивает с толку, когда вызывается рекурсивная функция setBlankAsDeadblockRec(i,j), возвращение в цикл происходит только после выхода из нее.
Этот код необходим, для прохода всех точек, и обнаружения тупиковых.
Если такая найдена, запускается рекурсивная функция setBlankAsDeadblockRec(i,j) с координатами тупиковой позиции, и заполняется «дедблоками» до выхода из тупиковой дороги, продолжаем setDeadblock (перебор всех точек).
Ваше предложение приведет к выходу из функции.