c - 带有数组的 C 实现中的 Star 算法？

Question

我是新来的。我正在尝试自己用 C 实现 A-Star 算法。我不知道如何使用 Hashmaps 或 Lists(但我也愿意学习，只要它们对我来说足够简单)所以我使用数组。

问题很简单:有一个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

open list需要是优先队列。那是一个队列，可以让新进入者根据优先级或重要性“插入”，但我们总是通过从前面拿来退缩。现在您可以天真地使用数组并在每次插入时进行排序，但这会很慢。链表不会有太大帮助(链表的缓存性能非常差)。确实，您需要一个专门编写的优先级队列，它在内存中尽可能多地保持在一起。