algorithm - 自主解迷宫机器人与故障路径排序

Question

介绍

我正在构建一个迷宫赛跑者机器人，其目标是能够从给定的起点到给定的终点穿越迷宫。我自己设计了算法 - 我坚持在查看以前的工作之前让我自己的实现工作。

问题

部分算法涉及对方向进行排序(使用插入排序，因为数组很小)- forward, backward, up ，并且下降他们的前景如何。

我在排序时遇到了一些问题，它根据三个因素对方向进行排序

1. 状态如果d方向的路径已经被探索过？
2. 距离:路径 p 末端的正方形到端点的距离 - x 和 y 的最小值不同
3. 长度:路径的实际长度。

排序时，我比较因子1，如果相等，我比较因子2。如果因子2相等，我继续3。如果任何两个因子小于或< em>超过，我返回了。出于某种原因，有时状态较低的路径会被推到后面。我对路径的排序出了点问题。

enter code here

有什么想法吗？

代码

    /*------------( Getting the best direction to go in )----------------    */
    /*
     * 0: North
     * 1: East
     * 2: South
     * 3: West
     */
    int  bestDirection(Point _curr_pos){
    Vec4 statuses/*1 for unexplored(better), 2 for explored(worse)*/,
        distances ,
        lengths = collectDistancesToWalls(),
        availablities = {POINT_REACHABLE, POINT_REACHABLE, POINT_REACHABLE, POINT_REACHABLE},
        directions = {0,1,2,3};

    //Give directions a length rating and distance rating and then sorts the directions, leaving the best direction in the front.

    //If we discover that we have already been in a location, we should block off the passage behind us leading to that location because it must be a loop.
    //Collecting the distance and length data. 
      for (int i=0; i < 4; i++) {
        Point direction_translated = translateOnAxisInDirection(_curr_pos, i, 1);

     //Converts the point to a reachable square - unnecessary to describe here. There is a domain specific problem which necessitates this function to be used. 
        Point heading_direction = pointToReachableSquare(direction_translated , i);

        //Distance from end of path to "headinglocation", the goal
        Point vec_to_end = subVec(heading_direction, headingLocation);
        distances[i]    =  min(absv(vec_to_end.x), absv(vec_to_end.y));
        statuses[i]     =  history[heading_direction.x][heading_direction.y].status;

        //If path is unreachable because of wall or something, then mark it as unreachable. 
        if (cmpVec(heading_direction, _curr_pos) || history[heading_direction.x][heading_direction.y].classification == WALL || !pointInIndBounds(direction_translated)) {
            availablities[i] = POINT_UNREACHABLE;
        }
    }

    //Insertion sort the distances.
    for (int i = 1; i < 4; i++) {
        int j = i - 1;
        while (
            comparePathOptions(
            statuses[i],
            distances[i],
            lengths[i],
            statuses[j],
            distances[j],
            lengths[j]
               ) == LESS_THAN && (j >= 0)) {
                int temp = directions[i];
                directions[i] = directions[j];
                directions[j] = temp;
                j--;
        }
    }

    //Return the first reachable direction. 
    int ind = 0;

    int dir = directions[ind];

    while (availablities[ directions[ind] ] == POINT_UNREACHABLE && (ind<4)) {
        dir = directions[ind+1];
        ind++;
    }

    return dir;
}

比较函数:

int relationship(int a, int b){
    if (a < b) return LESS_THAN;
    if (a > b) return MORE_THAN;
    return EQUAL;
}

//Edit this function
//TODO: Edit comparePathOptions.
//NOTE: Something
int comparePathOptions(int n_explored, int n_closeness, int n_length,
                 int b_explored, int b_closeness, int b_length){

    int objs[][3] = {
        {n_explored, n_closeness, n_length},
        {b_explored, b_closeness, b_length}
    };

    for (int i = 0; i < 3; i++){
        int rel = relationship(objs[1][i],objs[0][i]);
        if (rel!= EQUAL ) return rel;

    }
    return EQUAL;
}

已解决

多亏了@Kittsil，我的算法才起作用!您不是通过 j 和 i 访问 statuses、lengths 和 distances，而是通过 directions[i or j] 来完成，因为当 directions 数组改变时，i 和 j 停止引用当前方向。

编辑后的代码:

   while ( (j >= 0) &&
        comparePathOptions(
        statuses[  directions[i] ],
        distances[ directions[i] ],
        lengths[   directions[i] ],
        statuses[  directions[j] ],
        distances[ directions[j] ],
        lengths[   directions[j] ]
           ) == MORE_THAN ) {
            int temp = directions[i];
            directions[i] = directions[j];
            directions[j] = temp;
            j--;
    }

以及解决的迷宫:

x: 0, y: 0
H: 5, W:5, Ss:1
4|#####|
3|#####|
2|#####|
1|#####|
0|*::::|
  01234 
4|#####|
3|#####|
2|#####|
1|#####|
0| *:::|
  01234 
4|#####|
3|#####|
2|#####|
1|#####|
0|  *::|
  01234 
4|#####|
3|#####|
2|#####|
1|#####|
0|   *:|
  01234 
4|#####|
3|#####|
2|####:|
1|####:|
0|    *|
  01234 
4|#####|
3|#####|
2|####:|
1|####*|
0|     |
  01234 
4|#####|
3|#####|
2|::::*|
1|#### |
0|     |
  01234 
4|#####|
3|#####|
2|:::* |
1|#### |
0|     |
  01234 
4|#####|
3|#####|
2|::*  |
1|#### |
0|     |
  01234 
4|#####|
3|#####|
2|:*   |
1|#### |
0|     |
  01234 
4|:####|
3|:####|
2|*    |
1|#### |
0|     |
  01234 
4|:####|
3|*####|
2|     |
1|#### |
0|     |
  01234 
4|*####|
3| ####|
2|     |
1|#### |
0|     |
  01234 

Answer 1

您正在对 directions 进行排序数组，但您无法对其他数组进行排序；一旦你进行第一次交换，statuses , distances , 和 lengths不再与 directions 相关.

说明:问题出在您对比较函数的调用中。在这段代码中:

while (
  comparePathOptions(statuses[i],
                     distances[i],
                     lengths[i],
                     statuses[j],
                     distances[j],
                     lengths[j]) 
    == LESS_THAN && 
  (j >= 0)
) {
    int temp = directions[i];
    directions[i] = directions[j];
    directions[j] = temp;
    j--;
}

您正在使用 i和 j访问包含排序信息的数组。一旦i和 j与 directions[i] 不同和 directions[j] ，这不会像您预期的那样运行。你有两个选择:一，将您的电话改为 comparePathOptions(.)到

  comparePathOptions(statuses[directions[i]], 
                     distances[directions[i]], 
                     lengths[directions[i]],
                     statuses[directions[j]],
                     distances[directions[j]],
                     lengths[directions[j]]) 

OR，按照惯例，将您关心的信息存储在(非常小的)对象中并对这些对象的向量进行排序。

此外，当 j=-1 时，您在循环中越界了。和你比较。你应该移动 (j>=0)在 AND 的左侧。

说明:在几乎所有语言中，&& 和 ||是short-circuiting .如果 && 的左侧是false (或者 || 的左侧是 true )，语言甚至不会评估右侧；它已经知道 bool 函数的结果。在您的实例中，您不需要 comparePathOptions(.)在 j<0 时进行评估，因为这会让你出界。因此，你应该比较j至 0 在你使用j之前作为索引。