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

Question

简介

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

问题

该算法的一部分涉及对方向进行排序(使用插入排序，因为数组太小了)-向前，向后、向上和向下。

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

1. 状态：如果d方向的路径已经探索
2. 距离：路径p末端的正方形到端点的距离-x和y差异的最小值
3. 长度：路径的实际长度

排序时，我将比较因子1。如果它们相等，我比较因子2。如果因子2相等，我继续到3。如果任何两个因子小于或大于，我会返回。由于某些原因，有时状态较低的路径会被推到后面。我对路径的排序出了问题

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]访问，因为当方向数组更改时，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的左侧。

解释：在几乎所有的语言中，&amp；和||短路。如果&&的左侧是false(或者||的左侧是true)，则该语言甚至不会评估右侧；它已经知道布尔函数的结果。在您的实例中，您不希望在j<0时对comparePathOptions(.)进行求值，因为这会使您越界。因此，在使用j作为索引之前，应将j与0进行比较。