algorithm - Autonomous Maze Solving Robot and Faulty Path Sorting -
intro
i'm building maze runner robot, goal capable of navigating through maze given starting point given ending point. designed algorithm myself - insist on getting own implementation working before looking @ previous work.
problem
part of algorithm involves sorting directions(using insertion sort, because array small) - forward, backward, up, , down in terms of how promising are.
i'm having problems sorting, sorts directions based on 3 factors
- status: if path in direction d explored?
- distance: distance of square @ end of path p endpoint - minimum of x , y different
- length: how long paths are.
when sorting, compare factor 1. if equal, compare factor 2. if factor 2 equal, continue 3. if 2 factors either less than or more than, return that. for reason, path lower status gets pushed back. going wrong sorting of paths.
enter code here any ideas?
code
/*------------( getting best direction go in )---------------- */ /* * 0: north * 1: east * 2: south * 3: west */ int bestdirection(point _curr_pos){ vec4 statuses/*1 unexplored(better), 2 explored(worse)*/, distances , lengths = collectdistancestowalls(), availablities = {point_reachable, point_reachable, point_reachable, point_reachable}, directions = {0,1,2,3}; //give directions length rating , distance rating , sorts directions, leaving best direction in front. //if discover have been in location, should block off passage behind leading location because must loop. //collecting distance , length data. (int i=0; < 4; i++) { point direction_translated = translateonaxisindirection(_curr_pos, i, 1); //converts point reachable square - unnecessary describe here. there domain specific problem necessitates function used. point heading_direction = pointtoreachablesquare(direction_translated , i); //distance end of path "headinglocation", 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 unreachable because of wall or something, mark 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 distances. (int = 1; < 4; i++) { int j = - 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 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; } the comparison functions:
int relationship(int a, int b){ if (a < b) return less_than; if (a > b) return more_than; return equal; } //edit function //todo: edit comparepathoptions. //note: 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} }; (int = 0; < 3; i++){ int rel = relationship(objs[1][i],objs[0][i]); if (rel!= equal ) return rel; } return equal; } solved
thanks @kittsil i've gotten algorithm work! instead of accessing statuses, lengths, , distances j , i, directions[i or j] because i , j stop referring current direction when directions array changed.
the edited code:
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--; } and solved maze:
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
you sorting directions array, fail sort other arrays; make first swap, statuses, distances, , lengths no longer correlate directions.
explanation: problem in call comparison function. in section of code:
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--; } you using i , j access arrays containing sorting information. i , j not same directions[i] , directions[j], not behave expect. have 2 options: one, change call comparepathoptions(.) to
comparepathoptions(statuses[directions[i]], distances[directions[i]], lengths[directions[i]], statuses[directions[j]], distances[directions[j]], lengths[directions[j]]) or, common practice, store information care in (very small) objects , sort vectors of these objects.
also, go out of bounds in loop when j=-1 , compare. should move (j>=0) left side of and.
explanation: in languages, && , || short-circuiting. if left side of && false (or left side of || true), language not evaluate right side; knows result of boolean function. in instance, not want comparepathoptions(.) evaluated when j<0, put out of bounds. therefore, should compare j 0 before use j index.
Comments
Post a Comment