A* помогите пожалуйста

Здравствуйте дорогие друзья! Если кто-то может, помогите пожалуйста, сам никак не могу справиться...
Мне нужно реализовать алгоритм нахождения путей на гексагональной карте в координатах смещения (но можно и в кубических, не принципиально). Код Луа, по возможности, чтобы принимал данные вида {{x=1,y=1}{x=9,y=7}}, а на выходе давал таблицу нодов вида {{x=1,y=1}...,...,... }
Определение соседей, с прочтением карты есть, из препятствий только края карты и "твёрдые" гексы...
Для TIC-80, все результаты труда - для общего пользования.

 

Помнится, глазел на lua-star, но до пользования руки не дошли.

 

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

 

Алгоритм подсчета количества путей при обходе двумерной карты c левого верхнего угла в правый нижний. Возможные "ходы" - только вправо или вниз
На входе:
arg - "карта" (0 - проходимая клетка, 1 - непроходимая)
pos - стартовая позиция
nRet - количество найденных на данный момент путей
Язык JavaScript

Код:

export function foo(arg, pos, nRet) {
  let height = arg.length;
  let width = arg[0].length;
 
  let x = pos[0];
  let y = pos[1];
 
  if (x == width - 1 && y == height - 1) {
    nRet++; return nRet;
  }

  if (x + 1 < width && !arg[y][x + 1])
    nRet = foo(arg, [x + 1, y], nRet);
  if (y + 1 < height && !arg[y + 1][x])
    nRet = foo(arg, [x, y + 1], nRet);
  return nRet;
}

Тестовый пример запуска

Код:

  let a = [
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
  ];
 
  let ret = foo(a, [0, 0], 0);

 

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

 

А вообще, задача интересная. Вот, например, такой получается алгоритм поиска кратчайшего пути через большие сложные препятствия и прочие лабиринты. Работает методом перебора, так что сканировать сразу всю карту не рекомендуется. Можно задействовать, например, при приближении к препятствию, чтобы ограничить область. С другой стороны, это я привык писать под контроллеры на R.Pi, а на нормальном компе может и так сойдет. Сейчас там задано ходить только по прямой, но элементарно модифицируется, чтобы добавить диагонали или даже поддержку гексагональных карт.

ЗЫ: А еще в алгоритм можно добавить больше математики, чтобы ограничить область, отсеяв заведомо неоптимальные и тупиковые варианты.

Код на Perl:

Код:

my @map_raw = qw /
    111111111111111111111111111111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111111111111111111111111111111
    111111110000000000000000000000100000000000000000000000000000000000000011111
    111110000000000000000000000111100000000000000000000000000000000000000001111
    111111000000000000000000000010000000000000000000000000000000000000001111111
    111000000000000001000000000010000000000000000000000000000000000000011111111
    110000000000000001000000000011000000000000000000000000000000000000001111111
    100000000000000001100000000001000000000000111111111111110000000000001111111
    000000000000000000111111111111000000000000100000000000000000000000111111111
    110000000000000000000000000001000000000000100000000000000000000001111111111
    111000000000011111111111111111111111111111100000000000000001111111111111111
    111000000000010000000000000001000000000000000111100000000000011111111111111
    111100000000010000000000000001000000000000000111110000000000001111111111111
    111110000000011111000000000001000000000000000011100000000000000111111111111
    111000000000000000000000001111111100000000000001000000000000111111111111111
    111111111111111111111111111111111111111111111111110000011111111111111111111
    111111111111111111111111111111111111111111111111111110000111111111111111111
    111111111111111111111111111111111111111111111111111111100111111111111111111
/;

my $start_path = {x => 47, y => 5};
my $end_path = {x => 10, y => 20};

use Storable qw/dclone/;
my ($map, $matrix) = ({}, []);
@{$matrix} = map {[map {{pass => $_}} split(//, $_)]} reverse @map_raw;
for (my $i = 0; $i <= $#{$matrix}; $i++) {
    for (my $j = 0; $j <= $#{$matrix->[$i]}; $j++) {
        $map->{$j}->{$i} = $matrix->[$i]->[$j];
    }
}

my $path = find_path($map, $start_path, $end_path);

sub find_path {
    my ($map, $start_path, $end_path) = @_;
    my ($pathes, $index) = ({}, 1);

    my ($x, $y) = ($start_path->{x}, $start_path->{y});
    $map->{$x}->{$y}->{path} = 1;
    $pathes->{$index} = [{x => $x, y => $y}];

    while (scalar keys %{$pathes}) {
        foreach my $cur (keys %{$pathes}) {
            my $old = dclone($pathes->{$cur});
            my $steps = find_steps($map, $pathes->{$cur}->[-1]);
            for (my $i = 0; $i <= $#{$steps}; $i++) {
                my $new = $cur;
                my ($sx, $sy) = ($steps->[$i]->{x}, $steps->[$i]->{y});
                if ($i > 0) {
                    $index++;
                    $new = $index;
                    $pathes->{$new} = dclone($old);
                }
                push @{$pathes->{$new}}, $steps->[$i];
                $map->{$sx}->{$sy}->{path} = 1;
                if ($sx == $end_path->{x} && $sy == $end_path->{y}) {
                    return $pathes->{$new};
                }
            }
            delete $pathes->{$cur} unless (scalar @{$steps});
        }
    }
    return;
}

sub find_steps {
    my ($map, $path) = @_;
    my ($x, $y) = ($path->{x}, $path->{y});

    my $steps = [];
    my @pass = (
        {x => $x, y => $y+1},
        {x => $x-1, y => $y},
        {x => $x+1, y => $y},
        {x => $x, y => $y-1},
    );
    foreach my $i (@pass) {
        my $cell //= $map->{$i->{x}}->{$i->{y}};
        if ($cell && !$cell->{path} && $cell->{pass}) {
            push @{$steps}, $i;
        }
    }
    return $steps;
}

Результат:

 

@Helmut, большое спасибо, буду разбираться.

Пока что удалось реализовать такую штуку на Lua (я не программист, и к сожалению, изучаю язык параллельно с разработкой, что сами понимаете...)


function ast(m1,m2)

local clos={}
local w={x=m1.x,y=m1.y}
table.insert(clos,w)
local adj_1 = w

for op=1,30 do
if adj_1==nil then return open end
local open ={}
local adj = neib(adj_1)
local adjgoal = neibgoal(adj_1)

for k,v in ipairs(adjgoal)do
if v.x==m2.x and v.y==m2.y then
return clos
end
end
for k,v in ipairs(adj)do
table.insert(open,v)
end

adj_1=adjdist(open,m2)
table.insert(clos,adj_1)
end

return clos
end




Как видите, алгоритм пока что спотыкается в "ложбинах", и ищет не самый короткий путь, но работа продолжается.