Ну тогда.Ниже вы найдете демонстрацию поиска пути рабочей (и, более того, быстрой) волны.Существует два теста:
- 32x32 предварительно спроектированное подземелье, циклы 256 раз, пробеги 0,12 с - 0,13 с
- 320x320 большой, пустой, вход и выход находятся в противоположных углах, пробеги 0,03s - 0,04 с
Итак, проблема с учебниками и алгоритмами в том, что они идеально подходят для чистых небольших учебных пособий.Когда данных много, ну не так много.Если вы следовали этому уроку, он оставляет вас с классом получения и установки Node .Каждый раз, когда вы обращаетесь к получателю или установщику, вы вызываете вызов функции, что является относительно тяжелой операцией.Один раз, десять раз, сто раз - без проблем, но у вас есть 64K этих узлов, которые создают импульс производительности.Даже если вы не обращались к изображению получателя / установщика, есть все еще много экземпляров узлов, вы извлекаете их свойства ... вы получаете изображение, верно?
Когда я впервые сделал это нахождение пути волны вВ 2009 году я тоже наткнулся на путаницу экземпляров узлов и их свойств.Тогда 2-мерный массив целых, не годится.Затем я подумал о BitmapData классе, который может буквально представлять карту и содержать 32 бита данных на ячейку / пиксель.Каждая идея оказалась все еще слишком медленной.
Возможно, я мог бы подумать о одномерном представлении быстрее, но дело в том, что я работал с гексагональной картой, поэтому у каждой ячейки было 6 выходов, а не только4, немного сбивает с толку.
Тем не менее, в конце концов, я пришел к полной идее отображения области в одномерный массив и навигации по ней с помощью + 1 , Сдвиги -1 , + width и -width (ну, еще 2 для гексагональной топографии).Тогда мне не нужно было сложных вещей (и я не думаю, что они вам тоже нужны), таких как веса путей, просто чтобы найти кратчайший путь за приемлемый для UX период времени.
Если вы посмотрите наАлгоритмы поиска пути, это так просто.Нет x и y координаты.Нет пограничных проверок.Нет узловых объектов, нет свойств, нет дополнительных вызовов функций.Просто самая простая математика и несколько операций на каждую ячейку - как можно меньше.Вот почему это так быстро и эффективно.
Упомянутый класс Log , вы можете взять его в мой репо .
package
{
import flash.utils.getTimer;
import flash.display.Sprite;
import ru.delimiter.utils.Log;
/**
* ...
* @author Dmitry Yamaykin
*/
public class PathFinding extends Sprite
{
public function PathFinding()
{
super();
// Log is a debug output panel which allows you
// to see things if traces are unavailable
// or/and suppressed by the release build.
Log.create(this, true);
Log.log("[PathFinding] starts!");
testBig();
testSmall();
}
// The main data array that keeps obstacles,
// empty cells and those already passed by the wave.
private var map:Vector.<int> = new Vector.<int>;
// The front of the wave and the next front.
private var wave:Vector.<int> = new Vector.<int>;
private var froth:Vector.<int> = new Vector.<int>;
// Mapping the map back to the original data. Just for
// this demo, you probably won't need it with the real thing.
private var route:Vector.<int> = new Vector.<int>;
// Be extra careful with the 'w' argument, if you fumble with
// the width of the row, the whole thing will totally go astray.
private function findPath(source:Array, w:int, h:int):Array
{
var length:int = source.length;
var begin:int;
var end:int;
var i:int;
var steps:int;
var windex:int;
var findex:int;
var mindex:int;
map.fixed = false;
wave.fixed = false;
froth.fixed = false;
route.fixed = false;
// The brilliance of it: working with just a few instances
// that are set up in the very beginning and fixed to a
// certain amount of memory. No memory management while
// finding paths, no creating and disposing of instances,
// no Garbage Collector to kick in and do its thing.
map.length = length;
wave.length = w + h;
froth.length = w + h;
route.length = length;
map.fixed = true;
wave.fixed = true;
froth.fixed = true;
route.fixed = true;
// The main idea behind fast wave is mapping the source
// 2-dimensional data into 1-dimensional array of int
// values. Your position is indicated by a single
// index, +1 is 'go right', -1 is 'go left',
// +width and -width are 'go down' and 'go up' respectively.
// Just don't forget to add a solid impassable top and bottom
// lines (to avoid 'out of range' array errors) and a solid
// wall at the right (at least) so you don't flip over the
// data while going right from the rightmost position
// and left from the leftmost. It's far more efficient this
// way than additional code checks for borders.
for (i = 0; i < length; i++)
{
switch (source[i])
{
case '.':
map[mindex] = 0;
route[mindex] = i;
mindex++;
break;
case '#':
map[mindex] = -1;
route[mindex] = i;
mindex++;
break;
case 'X':
map[mindex] = -1;
route[mindex] = i;
end = mindex;
mindex++;
break;
case 'Y':
// We need it to be passable
// for wave to wash in there.
map[mindex] = 0;
route[mindex] = i;
begin = mindex;
mindex++;
break;
}
}
// Be careful with logging. It duplicates the output to the
// standard trace, which includes writing to a file
// (Flash thing, not my fault) which is really,
// like REALLY slow operation to do.
// Log.log(begin, '>', end);
// With just fixed [1, -1, w, -w] it will work a bit faster,
// bit the algorithm will prefer going in the straight lines,
// rather than wandering in diagonals and cutting the corners.
var AWX:int = 0;
var AWAY:Array;
var WAYS:Array =
[
[1, -1, w, -w],
[w, -w, 1, -1],
[-1, w, 1, -w],
[-w, 1, w, -1],
[1, -1, -w, w],
[w, -w, -1, 1],
[-1, 1, -w, w],
[w, -w, -1, 1],
[1, w, -1, -w],
[w, -1, -w, 1],
[-1, 1, w, -w],
[-w, w, 1, -1],
[1, -w, -1, w],
[w, 1, -w, -1],
[-1, -w, 1, w],
[w, -1, -w, 1],
];
// Lets the party begin.
wave[0] = end;
windex = 1;
// Repeat while wave front is not empty.
while (windex)
{
// Pick the next pattern of motion preferences.
if (--AWX < 0) AWX = WAYS.length - 1;
AWAY = WAYS[AWX];
// Go through all the points on the current wave front.
while (windex--)
{
var anindex:int = wave[windex];
// Try to move into the all
// possible directions from it.
for each (var ashift:int in AWAY)
{
// This value will be used a few times
// so it's better to calculate it once and store.
var awindex:int = anindex + ashift;
// Either -1 (impassable) or 1+
// (wave's been here already) means
// this spot is of no interest to us.
if (map[awindex]) continue;
// The 'path is found' routine.
if (awindex == begin)
{
// Log.log("THE WAY");
// The following code is just a dummy demo.
var result:Array = source.slice();
while (anindex != end)
{
result[route[anindex]] = '*';
anindex = map[anindex];
}
return result;
/**
* The main idea behind the result code
* is to unwind the calculated path,
* which is pretty easy because each
* affected map cell contains
* the index of the previous
* cell all the way back
* to the center of
* the wave.
*
result = [begin];
while (anindex != end)
{
result.push(anindex);
anindex = map[anindex];
}
result.push(end);
*
**/
}
// Add the empty cell to the
// next front line of the wave.
map[awindex] = anindex;
froth[findex++] = awindex;
}
}
// The next front line is formed,
// time to move on to the next iteration.
var xchange:Vector.<int> = froth;
var xindex:int = findex;
froth = wave;
findex = 0;
wave = xchange;
windex = xindex;
//Log.log(windex, wave);
}
// If we're here, that means the wave started
// at the 'end' point never hit the 'begin'.
trace("NO WAY");
return null;
}
// Tests pathfinding in a smaller dungeon: a multiple times.
private function testSmall():void
{
var X:XML = <root><![CDATA[
##################################
#.............#................#Y#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#.......#.......#........#.#
#.....#...............#..........#
#.....############################
#................................#
#................................#
#................................#
#................................#
#######..........................#
#................................#
#...####.........................#
#................................#
#................................#
#................................#
#................................#
#................................#
#................................#
#................................#
##################...............#
#................#...............#
#................#...............#
#...######.......#...............#
#........#.......#...............#
#........#.......#...............#
#........#.......#...............#
#X.......#.......................#
##################################
]]></root>;
var D:String = X.children()[0].toString().split("\r").join("");
var A:Array = D.split("");
var aTime:int = getTimer();
var R:Array;
for (var i:int = 255; i >= 0; i--)
{
R = findPath(A, 34, 34);
}
Log.log("");
Log.log("32 x 32, pre-designed, not empty, 256 times.");
Log.log("Elapsed", getTimer() - aTime, "ms.");
if (R) Log.log(R.join(""));
}
// Tests pathfinding in a big empty dungeon.
private function testBig():void
{
var D:String = "";
// Lets form a biiig empty field with
// entrance and exit at the opposite corners.
var TB:String = G("#", 322);
var TX:String = "#" + G(".", 319) + "X#";
var TY:String = "#Y" + G(".", 319) + "#";
var TE:String = "#" + G(".", 320) + "#";
D += TB;
D += TX;
for (var i:int = 0; i < 318; i++)
{
D += TE;
}
D += TY;
D += TB;
var A:Array = D.split("");
var aTime:int = getTimer();
var R:Array = findPath(A, 320, 320);
Log.log("");
Log.log("320 x 320, empty.");
Log.log("Elapsed", getTimer() - aTime, "ms.");
}
private function G(char:String, repeat:int):String
{
var result:String = char;
while (result.length < repeat)
{
result += result;
}
result = result.substr(0, repeat);
return result;
}
}
}