Thuật toán sao không có chuyển động chéo

Question

Tình huống: Tôi đang cố dịch A * algoritm thành mã C++ khi không có chuyển động đường chéo cho phép nhưng tôi có một số hành vi lạ.

My câu hỏi: Có cần phải tính đến chi phí đường chéo ngay cả khi không có chuyển động chéo nào có thể. Khi tôi tính toán mà không có chi phí đường chéo (với hệ số 'heuristic' 10), tôi luôn có cùng số điểm 80 (bạn có thể thấy điều này trong bức ảnh thứ hai mà tôi tính toán điểm số, gscore và hscore) và điều này có vẻ thực sự lạ với tôi. Bởi vì điều này (hầu như tất cả các nút có một điểm số 80) các thuật toán dường như không hoạt động vì nhiều nút có cùng số điểm nhỏ nhất là 80.

Hoặc hành vi bình thường này và sẽ thực hiện sao A * mà không có đường chéo phải thực hiện nhiều công việc hơn (vì nhiều nút có cùng số điểm tối thiểu) ?.

Tôi không nghĩ rằng câu hỏi này có bất cứ điều gì để làm với mã của tôi hơn với lập luận của tôi, nhưng tôi gửi bài nó anyway:

pathFind.cpp

#include "pathFind.h" 
#include <queue> 
#include "node.h" 
#include <QString> 
#include <QDebug> 
#include <iostream> 

/** Pathfinding (A* algo) using Manhatten heuristics and assuming a monotonic, consistent 
* heuristic (the enemies do not change position) 
* 
* TODO: add variable terrain cost 
**/ 

//dimensions 
const int horizontalSize = 20; 
const int verticalSize = 20; 

//nodes sets 
static int closedNodes[horizontalSize][verticalSize]; //the set of nodes already evaluated 
static int openNodes[horizontalSize][verticalSize]; // the set of nodes to be evaluated; initialy only containing start node 
static int dir_map[horizontalSize][verticalSize]; //map of directions (contains parents-children connection) 

//directions 
const int dir=4; 
static int dirX[dir]={1,0,-1,0}; 
static int dirY[dir]={0,1,0,-1}; 

//test class 
static int map[horizontalSize][verticalSize]; //map of navigated nodes 
pathFind::pathFind(){ 
    //test 
    srand(time(NULL)); 
    //create empty map 
    for (int y=0;y<verticalSize;y++){ 
     for (int x=0;x<horizontalSize;x++){ 
      map[x][y]=0; 
     } 
    } 
    //fillout matrix 
    for (int x=horizontalSize/8;x<horizontalSize*7/8;x++){ 
     map[x][verticalSize/2]=1; 
    } 
    for (int y=verticalSize/8;y<verticalSize*7/8;y++){ 
     map[horizontalSize/2][y]=1; 
    } 

    //randomly select start and finish locations 
    int xA,yA,xB,yB; 
    int n=horizontalSize; 
    int m=verticalSize; 

    xA=6; 
    yA=5; 

    xB = 14; 
    yB = 12; 

    qDebug() <<"Map Size (X,Y): "<<n<<","<<m<<endl; 
    qDebug()<<"Start: "<<xA<<","<<yA<<endl; 
    qDebug()<<"Finish: "<<xB<<","<<yB<<endl; 


    // get the route 
    clock_t start = clock(); 
    QString route=calculatePath(xA, yA, xB, yB); 
    if(route=="") qDebug() <<"An empty route generated!"<<endl; 
    clock_t end = clock(); 
    double time_elapsed = double(end - start); 
    qDebug()<<"Time to calculate the route (ms): "<<time_elapsed<<endl; 
    qDebug()<<"Route:"<<endl; 
    qDebug()<<route<<endl<<endl; 
} 

QString pathFind::calculatePath(const int & xStart, const int & yStart,const int & xFinish, const int & yFinish){ 
    /** why do we maintain a priority queue? 
    * it's for maintaining the open list: everytime we acces the open list we need to find the node with the lowest 
    * fscore. A priority queue is a sorted list so we simply have to grab (pop) the first item of the list everytime 
    * we need a lower fscore. 
    * 
    * A priority queue is a data structure in which only the largest element can be retrieved (popped). 
    * It's problem is that finding an node in the queue is a slow operation. 
    **/ 
    std::priority_queue<node> pq[2]; //we define 2 priority list which is needed for our priority change of a node 'algo' 
    static int index; //static and global variables are initialized to 0 
    static node *currentNode; 
    static node *neighborNode; 
    //first reset maps 
    resetMaps(); 

    //create start node 
    static node * startNode; 
    startNode= new node(xStart,yStart,0,0); 
    startNode->updatePriority(xFinish, yFinish); 

    // push it into the priority queue 
    pq[index].push(*startNode); 

    //add it to the list of open nodes 
    openNodes[0][0] = startNode->getPriority(); 

    //A* search 
    //while priority queue is not empty; continue 
    while(!pq[index].empty()){ 
     //get current node with the higest priority from the priority list 
     //in first instance this is the start node 
     currentNode = new node(pq[index].top().getxPos(), 
           pq[index].top().getyPos(), 
           pq[index].top().getDistance(), 
           pq[index].top().getPriority()); 
     //remove node from priority queue 
     pq[index].pop(); 
     openNodes[currentNode->getxPos()][currentNode->getyPos()]=0; //remove node from open list 
     closedNodes[currentNode->getxPos()][currentNode->getyPos()]=1; //add current to closed list 

     //if current node = goal => finished => retrace route back using parents nodes 
     if (currentNode->getxPos()==xFinish && currentNode->getyPos()==yFinish){ 
      //quit searching if goal is reached 
      //return generated path from finish to start 
      QString path=""; 
      int x,y,direction; //in cpp you don't need to declare variables at the top compared to c 
      //currentNode is now the goalNode 
      x=currentNode->getxPos(); 
      y=currentNode->getyPos(); 
      while (!(x==xStart && y==yStart)){ 
       /** We start at goal and work backwards moving from node to parent 
       * which will take us to the starting node 
       **/ 
       direction=dir_map[x][y]; 
       path =(direction+dir/2)%dir+path; //we work our way back 
       //iterate trough our dir_map using our defined directions 
       x+=dirX[direction]; 
       y+=dirY[direction]; 
      } 

      //garbage collection; the memory allocated with 'new' should be freed to avoid memory leaks 
      delete currentNode; 
      while (!pq[index].empty()){ 
       pq[index].pop(); 
      } 
      return path; 

      //return path; 
     } else { 
      //add all possible neighbors to the openlist + define parents for later tracing back 
      //(four directions (int dir): up, down, left & right); but we want to make it 
      //as extendable as possible 
      for (int i=0; i<dir; i++){ 
       //define new x & y coord for neighbor 
       //we do this because we want to preform some checks before making this neighbore node 
       int neighborX = currentNode->getxPos()+dirX[i]; 
       int neighborY = currentNode->getyPos()+dirY[i]; 
       //check boundaries 
       //ignore if on closed list (was already evaluted) or if unwalkable (currently not implemented) 

       if (!(neighborX <0 || neighborY <0 || neighborX > horizontalSize || neighborY > verticalSize || 
         closedNodes[neighborX][neighborY]==1)){ 
        //ok -> generate neighbor node 
        neighborNode = new node (neighborX,neighborY,currentNode->getDistance(),currentNode->getPriority()); 
        //calculate the fscore of the node 
        neighborNode->updatePriority(xFinish,yFinish); 
        neighborNode->updateDistance(); 

        //if neighbor not in openset => add it 
        if(openNodes[neighborX][neighborY]==0){ 
         //add it to open set 
         openNodes[neighborX][neighborY]=neighborNode->getPriority(); 
         //add it to the priority queue (by dereferencing our neighborNode object 
         //pq is of type node; push inserts a new element; 
         //the content is initialized as a copy 
         pq[index].push(*neighborNode); 
         //set the parent to the node we are currently looking at 
         dir_map[neighborX][neighborY]=(i+dir/2)%dir; 

        //if neighbor is already on open set 
        //check if path to that node is a better one (=lower gscore) if we use the current node to get there 
        } else if(openNodes[neighborX][neighborY]>neighborNode->getPriority()) { 
         /** lower gscore: change parent of the neighbore node to the select square 
         * recalculate fscore 
         * the value of the fscore should also be changed inside the node which resides inside our priority queue 
         * however as mentioned before this is a very slow operation (is going to be the bottleneck of this implemention probably) 
         * we will have to manuall scan for the right node and than change it. 
         * 
         * this check is very much needed, but the number of times this if condition is true is limited 
         **/ 

         //update fscore inside the open list 
         openNodes[neighborX][neighborY]=neighborNode->getPriority(); 
         //update the parent node 
         dir_map[neighborX][neighborY]=(i+dir/2)%dir; 

         //we copy the nodes from one queue to the other 
         //except the -old-current node will be ignored 
         while (!((pq[index].top().getxPos()==neighborX) && (pq[index].top().getyPos()==neighborY))){ 
          pq[1-index].push(pq[index].top()); 
          pq[index].pop(); 
         } 
         pq[index].pop(); //remove the -old-current node 

         /** ?? **/ 
         if(pq[index].size()>pq[1-index].size()){ //??? is this extra check necessary? 
          index=1-index; //index switch 1->0 or 0->1 
         } 

         while(!pq[index].empty()){ 
          pq[1-index].push(pq[index].top()); 
          pq[index].pop(); 
         } 
         /** ?? **/ 


         index=1-index; //index switch 1->0 or 0->1 
         pq[index].push(*neighborNode); //and the -new-current node will be pushed in instead 
        } else delete neighborNode; 

       } 
      } 

      delete currentNode; 
     } 

    } return ""; //no path found 
} 

void pathFind::resetMaps(){ 
    for (int y=0;y<horizontalSize;y++){ 
     for (int x=0;x<verticalSize;x++){ 
      closedNodes[x][y]=0; 
      openNodes[x][y]=0; 
     } 
    } 
} 

node.cpp

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

/** constructor **/ 
node::node(int x,int y, int d,int p) 
{ 
    xPos=x; 
    yPos=y; 
    distance=d; 
    priority=p; 
} 

/** getters for variables **/ 
//current node xPosition 
int node::getxPos() const { 
    return xPos; 
} 

//current node yPosition 
int node::getyPos() const { 
    return yPos; 
} 

//gscore 
int node::getDistance() const { 
    return distance; 
} 

//fscore 
int node::getPriority() const { 
    return priority; 
} 

/** Updates the priority; the lower the fscore the higer the priority 
* the fscore is the sum of: 
* -path-cost (gscore) (which is the distance from the starting node to the current node) 
* -heuristic estimate (hscore) (which is an estimate of the distance from the current node to the destination node) 
* 
**/ 
void node::updatePriority(const int & xDest, const int & yDest){ 
    priority = distance + estimateDistance(xDest,yDest)*10; 
} 

void node::updateDistance(){//const int & direction 
    distance +=10; 
} 


/** Estimate function for the remaining distance to the goal 
* here it's based on the Manhattan distance; 
* which is the distance between two points in a grid based on a strictly horizontal & veritcal path; 
* => sum of vertical & horizontal components 
**/ 
const int & node::estimateDistance(const int & xDest, const int & yDest) const{ 
    static int xDistance,yDistance,totalDistance; 
    xDistance=xDest-xPos; 
    yDistance=yDest-yPos; 

    totalDistance=abs(xDistance)+abs(yDistance); 

    return (totalDistance); 
} 

/** class functor (I think) to compare elements using: 
* operator overloading: "<" gets overloaded which we are going to use in our priority queue 
* to determine priority of a node in our queue; 
* returns true if node a has a lower fscore compared to node b 
* 
* there is an ambiguity here: < -- >; better to make both > 
* also prototype is now friend which could probably be replaced with this for the first 
* argument; it advantage is that because of the friend function the operand order can be reversed 
* this doesn't really looks to favor our application; so should I use it or not? 
**/ 
bool operator<(const node & a, const node & b){ 
    return a.getPriority() > b.getPriority(); 
} 

Answer 1

Tôi nghĩ thuật toán của bạn không có vấn đề gì và nếu không có sẵn chuyển động đường chéo, bạn sẽ không cần phải tính đến nó. Khoảng cách Manhattan là một phương pháp heuristic đơn giản và khi bạn trở nên gần nút đích, hàm H cho các số nhỏ hơn mặc dù hàm G (khoảng cách từ nút đầu tiên đến đây) sẽ lớn hơn. Kết quả là, nhiều nút có cùng điểm số f.

Answer 2

tôi nghĩ rằng không quan trọng có bao nhiêu ô vuông có cùng điểm số Bcz bạn chọn một trong số đó. Như đã nói trong thuật toán chính của A *, "Với mục đích tốc độ, có thể nhanh hơn để chọn cái cuối cùng bạn thêm vào danh sách mở". Tôi hy vọng nó sẽ không phải là một probelm nếu bạn không xem xét chi phí chéo. Có vẻ thú vị như thế nào nó cho kết quả.

Tôi hy vọng bạn đã đọc bài viết này. Nếu không có một cái nhìn rõ ràng.

Answer 3

A * là toàn bộ chung - biểu đồ bạn cung cấp cho nó có thể là bất kỳ hình dạng nào. Nó chỉ quan tâm đến việc bạn có thể đi từ X sang Y chứ không phải vì sao. Nếu chuyển động chéo không được phép, nó không quan tâm. Và nó là khá tốt và hợp pháp đối với nhiều nút có cùng số điểm f- thực tế là được mong đợi.