Доброго времени суток! Поговорим о такой вещи как поиск пути, чаще всего, конечно используемой в играх. В одних играх боты просто ходят взад-вперед по заранее предопределенному пути. В других юниты двигаются в определенном направлении, пока не встретят препятствие. Бывает что препятствия вообще не учитываются. Ну и наконец игры в которых юниты находят кратчайший путь до нужного им места в обход препятствий. Вот об этом и будет беседа.
Итак, как это работает. Алгоритмов поиска пути и их модификаций на самом деле достаточно много. Один из хорошо зарекомендовавших себя — AStar (А*), младший и более шустрый брат алгоритма Дейкстры. Его особенность в том, что он работает эвристически (грубо говоря интуитивно). Он обходит узел за узлом, переходя в теоретически наиболее ближний к цели узел, попутно корректируя путь, если это не так.
На сколько тот или иной узел близок к целевому определяется суммой расстояний от начального узла до текущего и от текущего до конечного. Например так:
g — стоимость пути от начального узла до текущего. Как видно на изображениях выше g складывается из стоимости всех пройденных узлов.
h — эвристическая стоимость пути от текущего узла до конечного. Мы не знаем ее наверняка, а рассчитываем, какова эта стоимость была бы если бы мы двигались по прямой.
На самом деле разные реализации алгоритма могут немного отличаться друг от друга. Здесь я рассчитываю h по теореме Пифагора, в других реализациях вы можете увидеть пересчет количества узлов до конечой точки или умножение вектора x на вектор y. Здесь всем заведует отношение скорости выполнения к возможной погрешности. Я же сейчас не ставлю перед собой задачи сделать наиболее быструю реализацию алгоритма, поэтому могу себе позволить более точные вычисления.
А теперь в коде:
Класс сетки/карты:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
package { public class Grid { private var _nodes:Vector.<Vector.<Node>>; private var _width:int; private var _height:int; public function Grid(width:int = 25, height:int = 25, walkableMap:Array = null) { _width = width; _height = height; _nodes = new Vector.<Vector.<Node>>(); for (var x:int = 0; x < _width; x++) { _nodes[x] = new Vector.<Node>(); for (var y:int = 0; y < _height; y++) { _nodes[x][y] = new Node(x, y, true); if (walkableMap && !walkableMap[x][y]) Node(_nodes[x][y]).walkable = false; } } } public function getNode(x:int = 0, y:int = 0):Node { return (x < 0 || x >= _width)?null:(y < 0 || y >= _height)?null:_nodes[x][y]; } public function get nodes():Vector.<Vector.<Node>> { return _nodes; } } } |
Класс узла:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
package { public class Node { private var _g:Number; private var _h:Number; private var _f:Number; private var _x:int; private var _y:int; private var _walkable:Boolean; private var _parentNode:Node; public function Node(x:int, y:int, walkable:Boolean) { _x = x; _y = y; _walkable = walkable; } public function get g():Number { return _g; } public function set g(value:Number):void { _g = value; } public function get h():Number { return _h; } public function set h(value:Number):void { _h = value; } public function get f():Number { return _f; } public function set f(value:Number):void { _f = value; } public function get parentNode():Node { return _parentNode; } public function set parentNode(value:Node):void { _parentNode = value; } public function get walkable():Boolean { return _walkable; } public function set walkable(value:Boolean):void { _walkable = value; } public function get x():int { return _x; } public function get y():int { return _y; } } } |
И непосредственно класс поиска пути:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
package { /** * Поиск пути */ public class PathFinder { private static const ALIGNED:int = 1; private static const DIAGONAL:Number = 1.4; private static var _closed:Vector.<Node>; private static var _opened:Vector.<Node>; private static var _path:Vector.<Node>; public static function getPath(start:Node, end:Node, grid:Grid):Vector.<Node> { _closed = new Vector.<Node>(); _opened = new Vector.<Node>(); _path = new Vector.<Node>(); start.g = 0; start.h = getDistance(start, end); start.f = start.g + start.h; start.parentNode = null; _opened.push(start); var currentNode:Node; while (_opened.length) { currentNode = _opened[0]; _closed.push(_opened.shift()); for (var x:int = currentNode.x-1; x <= currentNode.x+1; x++) { for (var y:int = currentNode.y-1; y <= currentNode.y+1; y++) { var testedNode:Node = grid.getNode(x, y); if (!testedNode || !testedNode.walkable || _closed.indexOf(testedNode) != -1) continue; if (_opened.indexOf(testedNode) == -1) { testedNode.g = currentNode.g + getLocalDistance(currentNode, testedNode); testedNode.h = getDistance(currentNode, testedNode); testedNode.f = testedNode.g + testedNode.h; testedNode.parentNode = currentNode; _opened.push(testedNode); } else { var tempG:Number = currentNode.g + getLocalDistance(currentNode, testedNode); if (tempG < testedNode.g) { testedNode.g = tempG; testedNode.f = testedNode.g + testedNode.h; testedNode.parentNode = currentNode; } } } } _opened.sort(sortOpen); if (_opened.length && _opened[0] == end) return pathReconstruct(_opened[0]); } return null; } private static function pathReconstruct(lastNode:Node):Vector.<Node> { while (lastNode.parentNode) { _path.push(lastNode); lastNode = lastNode.parentNode; } _path.reverse(); return _path; } private static function sortOpen(one:Node, two:Node):Number { return one.f - two.f; } private static function getDistance(one:Node, two:Node):Number { var catX:int = Math.abs(two.x - one.x); var catY:int = Math.abs(two.y - one.y); return Math.sqrt(catX * catX + catY * catY); } private static function getLocalDistance(one:Node, two:Node):Number { return (one.x == two.x || one.y == two.y)?ALIGNED:DIAGONAL; } } } |
Использовать довольно просто:
|
1 2 3 |
var grid:Grid = new Grid(25, 25); //Создает сетку 25 x 25 третьим параметром можно передать вектор проходимостей var path:Vector.<Node> = PathFinder.getPath(grid.nodes[0][0], grid.nodes[24][24], grid); trace(path); |
Я привел вполне работоспособную, но в тоже время достаточно простую реализацию этого алгоритма. В реальных проектах вы вероятно захотите ввести еще стоимость клеток, ведь поверхность земли бывает неоднородной (лед, болота, зыбучие пески). Так же вы можете попробовать его ускорить, например, возможно положительно скажется на скорости работы замена пересортировки вектора открытого списка на сохранение индекса следующего узла. Или замена формулы вычисления стоимости h на более легкую. Вобщем желаю вам удачи в экспериментах!
И конечно же пример:
(клик — поиск пути и перемещение, Ctrl+клик — изменение проходимости узла)