|
|
|||||
Поиск пути
Вот придумал алгоритм поиска пути - чистая математика. Координаты препятствий берутся из XML. Просьба посмотреть на предмет глюков и недочетов (может я чего не увидел). Когда отполирую код - выложу, может кому пригодится...
|
|
|||||
Пригодится! Уже пригодится!
По-мучал его изрядно. С виду никаких багов. Только при первом клике ролик обращается к локалхосту. Это так надо? Что это? Последний раз редактировалось Punk T-34; 04.07.2008 в 17:24. |
|
|||||
блогер
Регистрация: Jun 2005
Адрес: Господи пожалуйста не Новосибирск
Сообщений: 6,598
Записей в блоге: 17
|
Уряяя, я сделаю свою рпгшку
Зачет, продолжай работать.)
__________________
Тут мужик танцует и поёт про флэш |
|
|||||
[+3 13.02.08]
Регистрация: Apr 2006
Сообщений: 421
|
То, что ты сделал, напоминает метод потенциалов попробуй сделать вогнутое препятствие, например в форме буквы П и тебя ждут сюрпризы.
Короче, зачет, но работать есть над чем |
|
|||||
метод, реализация А*.
/* =============================================================================== = PATHFINDING FUNCTION =------------------------------------------------------------------------------ = Version: 1.1.4 = Last changes: jul 15 (1.0.0) - first version = aug 09 (1.0.1) - several speed improvements, thanks tonypa = aug 10 (1.0.2) - even more speed improvements by tonypa (again) = aug 31 (1.0.3) - return NULL if error (instead of error string) = aug 31 (1.1.3) - added cornering option. thanks for LAlex for = his suggestions = 2004 may 28 (1.1.4) - fixed "undefined != 0" error on MX 2004 when = compiling as flash 7. Thanks Inkog for finding = the error and the solution =------------------------------------------------------------------------------ = This function finds the path between two points (the START and the END point) = on a given map, taken into account walls/obstacles and terrain costs. = = It uses an A* ("a star") algorithm with heuristic approximation for a faster = result. Much of this function is basic on theory learnt from this language = independent tutorial: = http://www.policyalmanac.org/games/aStarTutorial.htm =------------------------------------------------------------------------------ = How to use: = = my_path_array = findPath (map, start_y, start_x, end_y, end_x) = = Parameters: = map = bidimensional array with rows and columns. Each cell contains a value = of 0 (wall) or 1+ (terrain - the higher, the more expensive to ride) =============================================================================== */ findPath = function(map, startY, startX, endY, endX) { if (startY == undefined || startX == undefined) return null; // Error: no starting point if (endY == undefined || endX == undefined) return null; // Error: no ending point // Caches dimensions var mapH = map.length; var mapW = map[0].length; // New status arrays var mapStatus = []; for (var i=0; i<mapH; i++){ mapStatus[i] = []; for (var j=0; j<mapW; j++){ mapStatus[i][j]={}; } } // Finds the way given a certain path // Constants/configuration - change here as needed! -------------------------------- var HV_COST = 10; // "Movement cost" for horizontal/vertical moves var D_COST = 14; // "Movement cost" for diagonal moves var ALLOW_DIAGONAL = false; // If diagonal movements are allowed at all var ALLOW_DIAGONAL_CORNERING = false; // If diagonal movements over corners are allowed // Complimentary functions ========================================================= isOpen = function (y, x) { // Return TRUE if the point is on the open list, false if otherwise return mapStatus[y][x].open; }; isClosed = function (y, x) { // Return TRUE if the point is on the closed list, false if otherwise return mapStatus[y][x].closed; }; nearerSquare = function() { // Returns the square with a lower movementCost + heuristic distance // from the open list var minimum = 999999; var indexFound = 0; var thisF = undefined; var thisSquare = undefined; var i = openList.length; // Finds lowest while (i-->0) { thisSquare = mapStatus[openList[i][0]][openList[i][1]]; thisF = thisSquare.heuristic + thisSquare.movementCost; if (thisF <= minimum) { minimum = thisF; indexFound = i; } } // Returns lowest return indexFound; }; closeSquare = function(y, x) { // Drop from the open list var len = openList.length; for (var i=0; i < len; i++) { if (openList[i][0] == y) { if (openList[i][1] == x) { openList.splice(i, 1); break; } } } // Closes an open square mapStatus[y][x].open = false; mapStatus[y][x].closed = true; }; openSquare = function(y, x, parent, movementCost, heuristic, replacing) { // Opens a square if (!replacing) { openList.push([y,x]); mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false}; } mapStatus[y][x].parent = parent; mapStatus[y][x].movementCost = movementCost; }; // Ok, now go back to our regular schedule. Find the path! ------------------------- // Now really starts var openList = new Array(); openSquare (startY, startX, undefined, 0); // Loops until there's no other way to go OR found the exit while (openList.length > 0 && !isClosed(endY, endX)) { // Browse through open squares var i = nearerSquare(); var nowY = openList[i][0]/1; var nowX = openList[i][1]/1; // Closes current square as it has done its purpose... closeSquare (nowY, nowX); // Opens all nearby squares, ONLY if: //trace('__now:['+nowX+","+nowY+"]"); for (var j=nowY-1; j<(nowY+2); j++) { for (var k=nowX-1; k<(nowX+2); k++) { if (j >= 0 && j < mapH && k >= 0 && k < mapW && map[j][k] != 0) { //if (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX) && (ALLOW_DIAGONAL_CORNERING || j==nowY || k==nowX || (map[j][nowX] != 0 && map[nowY][k] != 0))) { // If not outside the boundaries or at the same point or a diagonal (if disabled) or a diagonal (with a wall next to it)... // And if not a wall... if (!isClosed(j,k)) { // And if not closed... THEN open. //var py=mapStatus[nowY][nowX].parent[0]; //var px=mapStatus[nowY][nowX].parent[1]; //var pcost=mapStatus[nowY][nowX].movementCost; //if(py!=undefined){pcost=mapStatus[py][px].movementCost;}; var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]); //trace("___map("+k+","+j+")="+map[j][k]+","+movementCost+'['+mapStatus[nowY][nowX].movementCost+',('+nowX+','+nowY+')]'); //gfx_mc.sur_map[k][j]=movementCost; //trace('('+k+','+j+') from ['+nowX+","+nowY+"]"); //gfx_mc.sur_map_type[k][j]=100; if (isOpen(j,k)) { // Already opened: check if it's ok to re-open (cheaper) if (movementCost < mapStatus[j][k].movementCost) { // Cheaper: simply replaces with new cost and parent. //trace('__replace:('+k+','+j+') for ('+nowX+','+nowY+")"); openSquare (j, k, [nowY, nowX], movementCost, undefined, true); // heuristic not passed: faster, not needed 'cause it's already set } } else { // Empty: open. var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10; openSquare (j, k, [nowY, nowX], movementCost, heuristic, false); } } else { // Already closed, ignore. } } } } } //Ended var pFound = isClosed(endY, endX); // Was the path found? // Clean up temporary functions //delete isOpen; //delete isClosed; //delete nearerSquare; //delete closeSquare; //delete openSquare; if (pFound) { // Ended with path found; generates return path var returnPath = []; var nowY = endY; var nowX = endX; var movCost=mapStatus[nowY][nowX].movementCost; while ((nowY != startY || nowX != startX)) { returnPath.push([nowX,nowY,movCost]); var newY = mapStatus[nowY][nowX].parent[0]; var newX = mapStatus[nowY][nowX].parent[1]; nowY = newY; nowX = newX; movCost=mapStatus[nowY][nowX].movementCost; } returnPath.push([startX,startY,0]); var path_xy=[]; for(var i=returnPath.length-1;i>-1;i--){ path_xy.push(returnPath[i]); } //trace("____path:"+ path_xy.join('|')); return path_xy; } else { // Ended with 0 open squares; ran out of squares, path NOT found return null; } }; //ASSetPropFlags(_global, "findPath", 1, 0); |
|
|||||
ммм
Напоминает волновой алгоритм, я баловался с ним как то, с вогнутостями проблем он не имеет. Вобще, за идею 4, за реализацию 3, а за выбор технологии вобще 0. Потому что в данном случае рационален метод точек видимости, тогда путь занимал бы до 5 точек. З.Ы сорри смотрел на скрипт выше когда писал))) за технологию - 5, спасибо ^_^ Последний раз редактировалось TERRORist; 07.07.2008 в 23:18. |
|
|||||
Регистрация: Sep 2005
Сообщений: 950
|
Не знаю как это у меня получилось . но после энной манипуляции с шариком шарик стал перемешаться только внутри фигур
картинку прикрепил. Последний раз редактировалось lexa2000lexa; 08.07.2008 в 16:06. |
|
|||||
У меня только сегодня дошли руки ддописать, что в алгоритме серьезная ошибка - он не учитывает длину пути, а считает только по количеству пройденных узлов. Идти он должен (до квадратика) по красной линии (потому что это кратчайший путь) а идет он по фиолетовой. Баг
а еще, три тысячи строк кода - это ужасно. И еще, хотелось бы увидеть то же самое но с 100 объектами Последний раз редактировалось TERRORist; 09.07.2008 в 20:26. |
|
|||||
Регистрация: Jan 2006
Адрес: Novosibirsk
Сообщений: 353
|
Есть хорошая статья по поиску пути http://www.delphigfx.narod.ru/doc/path.htm
|
Часовой пояс GMT +4, время: 11:10. |
|
« Предыдущая тема | Следующая тема » |
|
|