A */Dijkstraのアルゴリズムの簡単な実装（パスカル）

Question

この記事では、この記事のhttp://www.policyalmanac.org/games/aStarTutorial.htmを使用して、A * path findingアルゴリズム（今はDijkstraのアルゴリズム、つまりヒューリスティックなし）を実装しようとしています。しかし、私のコードで何が間違っているのか分かりません（パスが間違っています）。代わりに空のBEGIN ... ENDの

。それはすでに開いてリストにある場合

が、対策としてGのコストを使用して、その 乗にこのパスが優れているかどうかを確認します。このステップでなければなりません。 Gのコストが低いということは、これがより良いパスであることを意味する を意味します。その場合は、正方形の親を の現在の正方形に変更し、正方形のGとFのスコアを再計算します。

しかし、斜めの動きがないので重要ではないと思います。

uses 
    crt; 

const 
    MAXX = 20; 
    MAXY = 25; 

type 
    TArr = array [0..MAXY, 0..MAXX] of integer; 

    TCell = record 
     x: integer; 
     y: integer; 
    end; 

    TListCell = record 
     x: integer; 
     y: integer; 
     G: integer; 
     parent: TCell; 
    end; 

    TListArr = array [1..10000] of TListCell; 

    TList = record 
     arr: TListArr; 
     len: integer; 
    end; 

var 
    i, j, minind, ind, c: integer; 
    start, finish: TCell; 
    current: TListCell; 
    field: TArr; 
    opened, closed: TList; 

procedure ShowField; 
var 
    i, j: integer; 
begin 
    textcolor(15); 
    for i := 0 to MAXX do 
    begin 
     for j := 0 to MAXY do 
     begin 
      case field[j, i] of 
       99: textcolor(8); // not walkable 
       71: textcolor(14); // walkable 
       11: textcolor(10); // start 
       21: textcolor(12); // finish 
       15: textcolor(2); // path 
       14: textcolor(5); 
       16: textcolor(6); 
      end; 
      write(field[j, i], ' '); 
     end; 
     writeln; 
    end; 
    textcolor(15); 
end; 


procedure AddClosed(a: TListCell); 
begin 
    closed.arr[closed.len + 1] := a; 
    inc(closed.len); 
end; 


procedure AddOpened(x, y, G: integer); 
begin 
    opened.arr[opened.len + 1].x := x; 
    opened.arr[opened.len + 1].y := y; 
    opened.arr[opened.len + 1].G := G; 
    inc(opened.len); 
end; 

procedure DelOpened(n: integer); 
var 
    i: integer; 
begin 
    AddClosed(opened.arr[n]); 
    for i := n to opened.len - 1 do 
     opened.arr[i] := opened.arr[i + 1]; 
    dec(opened.len); 
end; 


procedure SetParent(var a: TListCell; parx, pary: integer); 
begin 
    a.parent.x := parx; 
    a.parent.y := pary; 
end; 


function GetMin(var a: TList): integer; 
var 
    i, min, mini: integer; 
begin 
    min := MaxInt; 
    mini := 0; 
    for i := 1 to a.len do 
     if a.arr[i].G < min then 
     begin 
      min := a.arr[i].G; 
      mini := i; 
     end; 

    GetMin := mini; 
end; 


function FindCell(a: TList; x, y: integer): integer; 
var 
    i: integer; 
begin 
    FindCell := 0; 
    for i := 1 to a.len do 
     if (a.arr[i].x = x) and (a.arr[i].y = y) then 
     begin 
      FindCell := i; 
      break; 
     end; 
end; 


procedure ProcessNeighbourCell(x, y: integer); 
begin 
    if (field[current.x + x, current.y + y] <> 99) then // if walkable 
     if (FindCell(closed, current.x + x, current.y + y) <= 0) then // and not visited before 
      if (FindCell(opened, current.x + x, current.y + y) <= 0) then // and not added to list already 
      begin 
       AddOpened(current.x + x, current.y + y, current.G + 10); 
       SetParent(opened.arr[opened.len], current.x, current.y); 
       // field[opened.arr[opened.len].x, opened.arr[opened.len].y]:=16; 
      end 
       else 
      begin 

      end; 
end; 


begin 
    randomize; 
    for i := 0 to MAXX do 
     for j := 0 to MAXY do 
      field[j, i] := 99; 

    for i := 1 to MAXX - 1 do 
     for j := 1 to MAXY - 1 do 
      if random(5) mod 5 = 0 then 
       field[j, i] := 99 
      else field[j, i] := 71; 

    // start and finish positions coordinates 
    start.x := 5; 
    start.y := 3; 
    finish.x := 19; 
    finish.y := 16; 
    field[start.x, start.y] := 11; 
    field[finish.x, finish.y] := 21; 

    ShowField; 

    writeln; 

    opened.len := 0; 
    closed.len := 0; 
    AddOpened(start.x, start.y, 0); 
    SetParent(opened.arr[opened.len], -1, -1); 
    current.x := start.x; 
    current.y := start.y; 

    repeat 
     minind := GetMin(opened); 
     current.x := opened.arr[minind].x; 
     current.y := opened.arr[minind].y; 
     current.G := opened.arr[minind].G; 
     DelOpened(minind); 

     ProcessNeighbourCell(1, 0); // look at the cell to the right 
     ProcessNeighbourCell(-1, 0); // look at the cell to the left 
     ProcessNeighbourCell(0, 1); // look at the cell above 
     ProcessNeighbourCell(0, -1); // look at the cell below 

     if (FindCell(opened, finish.x, finish.y) > 0) then 
      break; 
    until opened.len = 0; 

    // count and mark path 
    c := 0; 
    while ((current.x <> start.x) or (current.y <> start.y)) do 
    begin 
     field[current.x, current.y] := 15; 
     ind := FindCell(closed, current.x, current.y); 
     current.x := closed.arr[ind].parent.x; 
     current.y := closed.arr[ind].parent.y; 
     inc(c); 
    end; 


    ShowField; 
    writeln(c); 
    readln; 
end. 

編集 2月1日'12：それは今作品のように:)

Answer 1

あなたは各隣人を訪問するためにカット＆ペーストするのではなく、ループを使用するためのプログラムを書き換える必要があります。あなたは、次のようなバグを避けることができますことを行う場合は、次の

if (field[current.x, current.y - 1] <> 99) then 
    if (FindCell(closed, current.x, current.y - 1) <= 0) then 
     if (FindCell(opened, current.x + 1, current.y) <= 0) then 

（最後の行で矛盾current.x + 1, current.yを参照してください。あなたはループを記述ちょうど

ProcessCell(x+1, y); 
ProcessCell(x-1, y); 
ProcessCell(x, y-1); 
ProcessCell(x, y-1); 

にリファクタリングしていない場合は

neighbor_offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)] 
for offset in neighbor_offsets: 
    neighbor = current + offset 
    if is_walkable(neighbor) and not is_visited(neighbor): 
     # Open 'neighbor' with 'current' as parent: 
     open(neighbor, current) 

     # Perhaps check if the goal is reached: 
     if neighbor == finish: 
      goal_reached = True 
      break 

：）ループに関して

---

、私はこの（擬似Pythonのようなもの）を考えていました

それは大きな改善です。

Answer 2

youreのコードのかなり多くを掲示更新されたコードは、マーキングも固定パスは、（そこにあるか、またはその代わりとすべきである）、に見え、あなたが失敗した場所を絞り込んでみましたか？

あなたのコードをウィキペディアのpseudocodeと比較しましたか？あなたは*私は今、私はAを学ぶために使用される非常に同じであると認識され（リンク

記事：

またダイクストラは0

編集のヒューリスティックとだけ*であることを覚えておいてください、面白い）は、図示されたステップを含んでいる私はあなたがその地図/グリッドを作り直し、その上で実装を実行することをお勧めします。次に、画像をステップ実行します。

1. オープンリストに8つの初期ネイバーが追加されていますか。彼らは正しい親を持っていますか？
2. ヒューリスティックに基づいてスキャンされる正しいノードが次に選択されていますか？
3. 閉じたノードのリストは正しいですか？
4. のように...