C數組實現中的星型算法？

Question

我是新來的。我試圖用C自己實現C中的A-Star算法。我不知道如何使用Hashmaps或者列表（但是我只要對我來說足夠簡單就可以開始學習），所以我使用數組。

問題很簡單：有一個NxN數組。你可以上/下或左/右，沒有對角線。水平比垂直運動更好（成本更低= 5）（高成本= 10）。

有一些障礙細胞。空白單元在NxN陣列中用數字0表示，而障礙單元的數量爲9.障礙單元出現在表格的一部分區域中（例如，如果表格是10 * 10並且獨立可能性有一個在每個小區中的障礙是0.1，將有大約10 9的表中。

隨着編號1的起點被表示並與圖2和3中的兩個最終的目標去，G1和G2。

#include<stdio.h> 
#include <stdlib.h> 

int main(void) { 
    //create a NxN array 

    int N, sX, sY, g1X,g1Y,g2X,g2Y,i,j,w; 
    double p; 
    float r; 
    printf("Give N\n"); 
    scanf("%d",&N); 
    printf("Give p\n"); 
    scanf("%lf",&p); 
    printf("Give S x k y\n"); 
    scanf("%d",&sX); 
    scanf("%d",&sY); 
    printf("Give G1 x & y\n"); 
    scanf("%d",&g1X); 
    scanf("%d",&g1Y); 
    printf("Give G2 x & y\n"); 
    scanf("%d",&g2X); 
    scanf("%d",&g2Y); 

    int table[N][N]; 

    for(i=0; i<N; i++){ 
     for (j=0; j<N; j++){ 

      r=(float)(rand() % 10)/10; // [0,1) 
      // printf("%f",&r); 
      if (sX==i && sY==j){ 
       table[i][j]=1; 
       //  printf("1"); 
      } 
      else if(g1X==i && g1Y==j){ 
       table[i][j]=2; 
       // printf("2"); 
      } 
      else if(g2X==i && g2Y==j){ 
       table[i][j]=3; 
       // printf("3"); 
      } 
      else if (p>=0 && r<=p){ 
       table[i][j]=9; 
       //  printf("9"); 
      } 
      else{ 
       table[i][j]=0; 
       // printf("0"); 
      } 


      printf("%d ",table[i][j]); 

     } 

     printf("\n"); 

    } 

    // Create the open list 


    int cX=sX, cY=sY; 

    while (cX!=g1X && cY!=g1Y) 
    { 
     int openList[4][2]; 
     //TOP 
     if(cX>0 && table[cX-1][cY]!=9){ 
      openList[0][0]=(cX-1); 
      openList[0][1]=cY; 
     } 
     else{ 
      openList[0][0]=-1; 
      openList[0][1]=-1; 
     } 

     //BOTTOM 
     if(cX+1<N && table[cX+1][cY]!=9){ 
      openList[1][0]=(cX+1); 
      openList[1][1]=cY; 
     } 
     else{ 
      openList[1][0]=-1; 
      openList[1][1]=-1; 
     } 
     //RIGHT 
     if(cY+1<N && table[cX][cY+1]!=9){ 
      openList[2][0]=cX; 
      openList[2][1]=(cY+1); 
     } 
     else{ 
      openList[2][0]=-1; 
      openList[2][1]=-1; 
     } 
     //LEFT 
     if(cY>0 && table[cX][cY-1]!=9){ 
      openList[3][0]=cX; 
      openList[3][1]=(cY-1); 
     } 
     else{ 
      openList[3][0]=-1; 
      openList[3][1]=-1; 
     } 

     printf("Open List of current cell:%d,%d\n",&cX, &cY); 
     for (i=0;i<4;i++){ 
      printf("%d , %d\n",openList[i][0],openList[i][1]); 

      cX=g1X; cY=g2Y; 
     } 
    } 
    return 0; 
} 

問題：

下面我已經試過這

1. 我知道我還沒有在打開的列表中添加當前單元格。我應該補充它吧？

2. openlist和closed list都應該是一個Hashmap？

3. 您認爲我應該與選定單元格的父級保持聯繫嗎？

Answer 1

打開的列表需要是優先級隊列。這是一個允許新進入者根據他們的優先級或重要性「推入」的隊列，但我們總是從前面收縮。現在你可以用一個數組和每個插入進行排序，但這會很慢。鏈接列表不會有太大幫助（鏈接列表的緩存性能非常差）。真的，你需要一個專門寫好的優先隊列，儘可能地將它們保存在內存中。