Pull to refresh
1
Karma
0
Rating
Олег Будишевский @MaxiMonster

User

  • Followers 1
  • Following

WebView или история о том, как в KolibriOS браузер писался

А как-же JavaScript? Или только HTML разметка?

Изобретаем JPEG

Отличная статья!

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

Скажите мне, какой из варинтов будет запускаться 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;
...

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

Я с вами не согласен, покажите пожалуйста место в коде, где функция setBlankAsDeadblockRec будет вызываться 2*N*M раз.

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

Прошу прощения, неудачно вставил код, и не успевал отредактировать.
Вот он:
...
  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 секунды. Боюсь, что есть смысл замерять скорость работы, на одном железе, и то меняется после каждого перезапуска, в зависимости от состояния ОС.

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

И опять-же, здесь говорится о конкретно етом лабиринте.

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

Алгоритм приведенный в статье работает 0,00761 секунды. Это без сканирования и построения изображения.

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

По той причине, что я подошел не правильно к применению алгоритма к данному лабиринту. А именно, без изменения рисунка. Волновой алгоритм применялся к лабиринту 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жды. И чем больше таких узлов будет тем дольше будет работать алгоритм.

Information

Rating
Does not participate
Location
Киев, Киевская обл., Украина
Date of birth
Registered
Activity