[Алгоритмы] Поиск пути без Нод

[caseyryan]

Ищу алгоритм для поиска пути в обход физических тел Nape (хотя в принципе не важно, можно просто любых прямоугольных тел), без использования нод как в А*. Кто-нибудь встречал готовые решения? Ну или просто знает в какую сторону копать. Производительность в этом случае очень важна, так как игра мобильная

[caseyryan]

Сделал. Решение придумал такое:
При первом запуске, после расстановки всех тел нейпа, происходит пробежка по всей карте через установленные промежутки (60 пикселей оказалось вполне достаточно), и в каждой из этих точек делается проверка

private function calculateWalkableSurface():Array {
 
	var tilesX:	int 	= stage.stageWidth / _tileSize;
	var tilesY:	int 	= stage.stageHeight / _tileSize;
	var tiles:	Array 	= [];
 
	for (var i:int = 0; i < tilesY; i++) {
		var posY:int = (i * _tileSize) + _tileSize * .5;
		tiles[i] = [];
		for (var j:int = 0; j < tilesX; j++) {
			var posX:int = (j * _tileSize) + _tileSize * .5;
			var tileValue:int = getTileValue(posX, posY);
			tiles[i][j] = tileValue;
		}
	}
	return tiles;
}
 
/// возвращает 1 если плитка непроходима, и 0 если препятствия нет
private function getTileValue(x:int, y:int):int {
	var bodies:BodyList = _space.bodiesUnderPoint(new Vec2(x, y));
	var value:int = 0;
	if (bodies.length) {
		// динамические и кинематические тела не считаются препятствием
		if (bodies.at(0).type == BodyType.STATIC) {
			value = 1;
		}
	}
	return value;
}

В итоге формируется двумерный массив с числами 0 или 1, который и скармливается алгоритму A* Star. Сам алгоритм взял вот этот
Путь конечно не идеальный, можно и более плавным сделать, какими-нибудь кривыми безье или просто рулёжкой. Но для моей цели вполне подойдет и такой.

Щелкаем в любом месте мышью, чтобы переставить игрока (треугольник). Или щелчок + пробел, чтобы переставить врага (круг)

DifferentTests.swf   (328.5 Кб)

[samana]

без использования нод как в А*

и скармливается алгоритму A* Star

Хитро) Главное, что всё получилось в итоге.

[caseyryan]

Как я понял, других вариантов не много. Рейкаст, который более ресурсоемкий, либо деление карты на секторы, как в анрил https://udn.epicgames.com/Three/Navi...Reference.html
Остановился на самом простом