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

打开的列表需要是优先级队列。这是一个允许新进入者根据他们的优先级或重要性“推入”的队列，但我们总是从前面收缩。现在你可以用一个数组和每个插入进行排序，但这会很慢。链接列表不会有太大帮助（链接列表的缓存性能非常差）。真的，你需要一个专门写好的优先队列，尽可能地将它们保存在内存中。