|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
Поиск пути. Помогите понять где я не прав.
Доброго врмени суток.
Есть задача нахождения пути в в игрушке. Поле - матрица состоящая из обозначеных '-' занятых клеток и обозначенных '+' не занятых. Надо найти между двум опеределенными ячейками путь, причем такой, что бы он обладал не более чем двумя поворотами. Естественно пришла в голову мысль использовать модификацию волнового алгоритма. Вот оригинал: http://algolist.manual.ru/maths/grap...tpath/wave.php http://www.codenet.ru/progr/alg/way.php Модификация должна была бы заключаться в том, что бы увеличивать вес волны при повороте а ни при удалении от начальной точки. то есть идея вот в чем: 1. мы задаем координаты точки входа. и обозначаем '0' (номер поворота) все связанные свободные клетки с тем же х или y 2. для каждой из них мы закрашиваем перпендикулярные перпендикулярные движению волны клетки '1' (номер поворота) с фиксированым х или у. 3. повторяем 2 для каждой новой клетки пока не найден путь к нужному элементу. Уточнение к коду: _global.wave_matrix двумерная матрица с полем матрица _global.trapA.x,_global.trapA.y - начальная точка, от которой идем _global.trapB.x,_global.trapB.y - конечная точка, которую надо достигнуть больше кажеться ничего нет загадочного. должно работать. но не работает. я про что то забыл точнее работает но не стабильно. Путь от А к Б может не находить, в то время как находит путь от Б к А. поэтому пришлось сдвоить проверку. Иногда не находит очевидный для человека путь. ПОМОГИТЕ ПОЖАЛУЙСТА. Где у меня в алгоритме логическая ошибка? Что я забыл? Вот сам код: function look_for_path(){ corners = {turns:new Array(),path_found:false,target_point:{x:_global.trapB.x,y:_global.trapB.y}}; corners = check_path({x:_global.trapA.x,y:_global.trapA.y},0,corners,null); if(corners.path_found==false){ clone_matrix(); corners = {turns:new Array(),path_found:false,target_point:{x:_global.trapA.x,y:_global.trapA.y}}; corners = check_path({x:_global.trapB.x,y:_global.trapB.y},0,corners,null); } if(corners.path_found==false){ trace("путь не найден"); }else{ trace("путь найден"); } } function check_path(point,turn,corners,dir){ corners.turns.push({x:point.x,y:point.y}); if( (turn==2)&& ( (point.x!==_global.trapB.x)&& (point.y!==_global.trapB.y) ) ){ return corners; } if(turn==3){ return corners; } if(dir!=2){ if(point.y<_global.wave_matrix[0].length){ for(k=point.y+1;k<_global.wave_matrix[0].length;k++){ if( (point.x==_global.trapB.x)&& (k==_global.trapB.y) ){ corners.turns.push({x:point.x,y:k}); corners.path_found=true; return corners; } if(_global.wave_matrix[point.x][k]!='-'){ if( (_global.wave_matrix[point.x][k]<=turn)&& (isNaN(_global.wave_matrix[point.x][k])==false) ){ continue; } if( ( (_global.wave_matrix[point.x][k]>turn)&& (isNaN(_global.wave_matrix[point.x][k])==false) )|| (_global.wave_matrix[point.x][k]=='+') ){ _global.wave_matrix[point.x][k]=turn; corners = check_path({x:point.x,y:k},turn+1,corners,2); if(corners.path_found==true){ return corners; } } }else{ break; } } } if(point.y>0){ for(r=point.y-1;r>=0;r--){ if( (point.x==_global.trapB.x)&& (r==_global.trapB.y) ){ corners.turns.push({x:point.x,y:r}); corners.path_found=true; return corners; } if(_global.wave_matrix[point.x][r]!='-'){ if( (_global.wave_matrix[point.x][r]<=turn)&& (isNaN(_global.wave_matrix[point.x][r])==false) ){ continue; } if( ( (_global.wave_matrix[point.x][r]>turn)&& (isNaN(_global.wave_matrix[point.x][r])==false) )|| (_global.wave_matrix[point.x][r]=='+') ){ _global.wave_matrix[point.x][r]=turn; corners = check_path({x:point.x,y:r},turn+1,corners,2); if(corners.path_found==true){ return corners; } } }else{ break; } } } } if(dir!=1){ if(point.x>0){ for(n=point.x-1;n>=0;n--){ if( (point.y==_global.trapB.y)&& (n==_global.trapB.x) ){ corners.turns.push({x:n,y:point.y}); corners.path_found=true; return corners; } if(_global.wave_matrix[n][point.y]!='-'){ if( (_global.wave_matrix[n][point.y]<=turn)&& (isNaN(_global.wave_matrix[n][point.y])==false) ){ continue; } if( ( (_global.wave_matrix[n][point.y]>turn)&& (isNaN(_global.wave_matrix[n][point.y])==false) )|| (_global.wave_matrix[n][point.y]=='+') ){ _global.wave_matrix[n][point.y]=turn; corners = check_path({x:n,y:point.y},turn+1,corners,1); if(corners.path_found==true){ return corners; } } }else{ break; } } } if(point.x<_global.wave_matrix.length){ for(t=point.x+1;t<_global.wave_matrix.length;t++){ if( (point.y==_global.trapB.y)&& (t==_global.trapB.x) ){ corners.turns.push({x:t,y:point.y}); corners.path_found=true; return corners; } if(_global.wave_matrix[t][point.y]!='-'){ if( (_global.wave_matrix[t][point.y]<=turn)&& (isNaN(_global.wave_matrix[t][point.y])==false) ){ continue; } if( ( (_global.wave_matrix[t][point.y]>turn)&& (isNaN(_global.wave_matrix[t][point.y])==false) )|| (_global.wave_matrix[t][point.y]=='+') ){ _global.wave_matrix[t][point.y]=turn; corners = check_path({x:t,y:point.y},turn+1,corners,1); if(corners.path_found==true){ return corners; } } }else{ break; } } } } return corners; }
__________________
Студия "Ночной народ" | http://nightfolk.net/ Последний раз редактировалось Bорон; 08.10.2008 в 09:01. |
Часовой пояс GMT +4, время: 19:52. |
|
« Предыдущая тема | Следующая тема » |
|
|