Поиск пути

[Волгоградец]

Вот придумал алгоритм поиска пути - чистая математика. Координаты препятствий берутся из XML. Просьба посмотреть на предмет глюков и недочетов (может я чего не увидел). Когда отполирую код - выложу, может кому пригодится...

[Punk T-34]

Пригодится! Уже пригодится!
По-мучал его изрядно. С виду никаких багов. Только при первом клике ролик обращается к локалхосту. Это так надо? Что это?

[Psycho Tiger]

Уряяя, я сделаю свою рпгшку
Зачет, продолжай работать.)

[VovkaMorkovka]

То, что ты сделал, напоминает метод потенциалов попробуй сделать вогнутое препятствие, например в форме буквы П и тебя ждут сюрпризы.
Короче, зачет, но работать есть над чем

[Badim]

метод, реализация А*.

/*
===============================================================================
= 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);

[TERRORist]

ммм

Напоминает волновой алгоритм, я баловался с ним как то, с вогнутостями проблем он не имеет.

Вобще, за идею 4, за реализацию 3, а за выбор технологии вобще 0. Потому что в данном случае рационален метод точек видимости, тогда путь занимал бы до 5 точек.

З.Ы сорри смотрел на скрипт выше когда писал))) за технологию - 5, спасибо ^_^

[lexa2000lexa]

Не знаю как это у меня получилось . но после энной манипуляции с шариком шарик стал перемешаться только внутри фигур
картинку прикрепил.

[TERRORist]

У меня только сегодня дошли руки ддописать, что в алгоритме серьезная ошибка - он не учитывает длину пути, а считает только по количеству пройденных узлов. Идти он должен (до квадратика) по красной линии (потому что это кратчайший путь) а идет он по фиолетовой. Баг

а еще, три тысячи строк кода - это ужасно.

И еще, хотелось бы увидеть то же самое но с 100 объектами

[NoCD]

Есть хорошая статья по поиску пути http://www.delphigfx.narod.ru/doc/path.htm

[Волгоградец]

TERRORist, ага, это баг - исправлю. Спасибо, что подсказал.
Насчет кода: с чего ты взял, что там 3000 строк? Я его, по-моему, не выкладывал... Там около 700 строчек (считая комментарии, отступы);