守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 495|回复: 1

[算法/性能优化] navMeshAstarPath地图寻路算法

[复制链接]
  • TA的每日心情
    擦汗
    2018-4-10 15:18
  • 签到天数: 447 天

    [LV.9]以坛为家II

    1742

    主题

    2094

    帖子

    13万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    562
    贡献
    29
    金币
    51581
    钢镚
    1422

    开源英雄守望者

    发表于 2015-7-15 12:08:12 | 显示全部楼层 |阅读模式
    本帖最后由 破晓 于 2015-7-15 14:02 编辑



    1. package {
    2.     import flash.display.Sprite;
    3.     import flash.events.Event;
    4.     import flash.events.MouseEvent;
    5.     import flash.utils.getTimer;

    6.     /**
    7.      * ...
    8.      * http://wonderfl.net/c/lDKs
    9.      * http://www.cnblogs.com/neoragex2002/archive/2007/09/09/887556.html
    10.      * @author sliz http://game-develop.net/
    11.      */
    12.     public class Main extends Sprite {
    13.         private var d:Delaunay;
    14.         private var astar:AStar;
    15.         private var g:Grid;

    16.         public function Main():void {
    17.             if (stage)
    18.                 init();
    19.             else
    20.                 addEventListener(Event.ADDED_TO_STAGE, init);
    21.         }

    22.         private function init(e:Event = null):void {
    23.             removeEventListener(Event.ADDED_TO_STAGE, init);
    24.             d = new Delaunay(400, 400);
    25.             var c:Number = 300;
    26.             while (c-- > 0){
    27.                 d.add(400 * Math.random(), 400 * Math.random());
    28.             }
    29.             for each (var t:Triangle in d.triangles){
    30.                 if (Math.random() < 0.2){
    31.                     t.walkAble = false;
    32.                 }
    33.             }

    34.             g = new Grid();
    35.             g.delaunay = d;
    36.             g.calculateLinks();
    37.             astar = new AStar(g);
    38.             g.startNode = d.triangles[int(d.triangles.length * Math.random())];
    39.             g.endNode = d.triangles[int(d.triangles.length * Math.random())];

    40.             stage.addEventListener(MouseEvent.CLICK, onclick);
    41.             astar.findPath();
    42.             draw();
    43.         }

    44.         private function onclick(e:MouseEvent):void {
    45.             g.startNode = g.endNode;
    46.             for each (var t:Triangle in d.triangles){
    47.                 if (isPointInTriangle(t.node0.point.x, t.node0.point.y, t.node1.point.x, t.node1.point.y, t.node2.point.x, t.node2.point.y, mouseX, mouseY)){
    48.                     g.endNode = t;
    49.                     break;
    50.                 }
    51.             }
    52.             if (g.startNode && g.endNode){
    53.                 trace(astar.findPath(), astar.path);
    54.                 draw();
    55.             }
    56.         }

    57.         private function draw():void {
    58.             graphics.lineStyle(0);
    59.             for each (var t:Triangle in d.triangles){
    60.                 if (t.walkAble)
    61.                     graphics.beginFill(0xffffff);
    62.                 else
    63.                     graphics.beginFill(0xff0000);
    64.                 graphics.moveTo(t.node0.point.x, t.node0.point.y);
    65.                 graphics.lineTo(t.node1.point.x, t.node1.point.y);
    66.                 graphics.lineTo(t.node2.point.x, t.node2.point.y);
    67.                 graphics.lineTo(t.node0.point.x, t.node0.point.y);
    68.             }
    69.             if (astar.path){

    70.                 for (var i:int = 0; i < astar.path.length; i++){
    71.                     t = astar.path[i];
    72.                     if (i == 0)
    73.                         graphics.beginFill(0xffff00);
    74.                     else if (i == astar.path.length - 1)
    75.                         graphics.beginFill(0x00ffff);
    76.                     else
    77.                         graphics.beginFill(0xff00ff);
    78.                     graphics.moveTo(t.node0.point.x, t.node0.point.y);
    79.                     graphics.lineTo(t.node1.point.x, t.node1.point.y);
    80.                     graphics.lineTo(t.node2.point.x, t.node2.point.y);
    81.                     graphics.lineTo(t.node0.point.x, t.node0.point.y);
    82.                 }
    83.             }
    84.         }

    85.         public static function multiply(px1:Number, py1:Number, px2:Number, py2:Number, px3:Number, py3:Number):int {
    86.             return (px1 - px3) * (py2 - py3) - (px2 - px3) * (py1 - py3);
    87.         }

    88.         public static function isPointInTriangle(px1:Number, py1:Number, px2:Number, py2:Number, px3:Number, py3:Number, px:Number, py:Number):Boolean {
    89.             var v:int = multiply(px1, py1, px2, py2, px3, py3);
    90.             if (v * multiply(px1, py1, px2, py2, px, py) <= 0){
    91.                 return false;
    92.             }
    93.             if (v * multiply(px2, py2, px3, py3, px, py) <= 0){
    94.                 return false;
    95.             }
    96.             if (v * multiply(px3, py3, px1, py1, px, py) <= 0){
    97.                 return false;
    98.             }
    99.             return true;
    100.         }
    101.     }

    102. }

    103. import flash.geom.Point;

    104. class AStar {
    105.     private var open:BinaryHeap;
    106.     private var grid:Grid;
    107.     private var endNode:Triangle;
    108.     private var startNode:Triangle;
    109.     private var _path:Array;
    110.     private var nowversion:int = 1;
    111.     public var heuristic:Function;

    112.     public function AStar(grid:Grid){
    113.         this.grid = grid;
    114.         heuristic = distance;
    115.     }

    116.     private function justMin(x:Object, y:Object):Boolean {
    117.         return x.f < y.f;
    118.     }

    119.     public function findPath():Boolean {
    120.         endNode = grid.endNode;
    121.         nowversion++;
    122.         startNode = grid.startNode;
    123.         open = new BinaryHeap(justMin);
    124.         startNode.g = 0;
    125.         return search();
    126.     }

    127.     private function distance(t1:Triangle):Number {
    128.         var t2:Triangle = endNode;
    129.         var c:Number = Math.sqrt((t1.cx - t2.cx) * (t1.cx - t2.cx) + (t1.cy - t2.cy) * (t1.cy - t2.cy));
    130.         return c;
    131.     }

    132.     public function search():Boolean {
    133.         var node:Triangle = startNode;
    134.         node.version = nowversion;
    135.         while (node != endNode){
    136.             var len:int = node.links.length;
    137.             for (var i:int = 0; i < len; i++){
    138.                 var test:Triangle = node.links[i].node;
    139.                 var cost:Number = node.links[i].cost;
    140.                 var g:Number = node.g + cost;
    141.                 var h:Number = heuristic(test);
    142.                 var f:Number = g + h;
    143.                 if (test.version == nowversion){
    144.                     if (test.f > f){
    145.                         test.f = f;
    146.                         test.g = g;
    147.                         test.h = h;
    148.                         test.parent = node;
    149.                     }
    150.                 } else {
    151.                     test.f = f;
    152.                     test.g = g;
    153.                     test.h = h;
    154.                     test.parent = node;
    155.                     open.ins(test);
    156.                     test.version = nowversion;
    157.                 }
    158.             }
    159.             if (open.a.length == 1){
    160.                 return false;
    161.             }
    162.             node = open.pop() as Triangle;
    163.         }
    164.         buildPath();
    165.         return true;
    166.     }

    167.     private function buildPath():void {
    168.         _path = [];
    169.         var node:Triangle = endNode;
    170.         path.push(node);
    171.         while (node != startNode){
    172.             node = node.parent;
    173.             path.unshift(node);
    174.         }
    175.     }

    176.     public function get path():Array {
    177.         return _path;
    178.     }
    179. }

    180. class BinaryHeap {
    181.     public var a:Array = [];
    182.     public var justMinFun:Function = function(x:Object, y:Object):Boolean {
    183.         return x < y;
    184.     };

    185.     public function BinaryHeap(justMinFun:Function = null){
    186.         a.push(-1);
    187.         if (justMinFun != null)
    188.             this.justMinFun = justMinFun;
    189.     }

    190.     public function ins(value:Object):void {
    191.         var p:int = a.length;
    192.         a[p] = value;
    193.         var pp:int = p >> 1;
    194.         while (p > 1 && justMinFun(a[p], a[pp])){
    195.             var temp:Object = a[p];
    196.             a[p] = a[pp];
    197.             a[pp] = temp;
    198.             p = pp;
    199.             pp = p >> 1;
    200.         }
    201.     }

    202.     public function pop():Object {
    203.         var min:Object = a[1];
    204.         a[1] = a[a.length - 1];
    205.         a.pop();
    206.         var p:int = 1;
    207.         var l:int = a.length;
    208.         var sp1:int = p << 1;
    209.         var sp2:int = sp1 + 1;
    210.         while (sp1 < l){
    211.             if (sp2 < l){
    212.                 var minp:int = justMinFun(a[sp2], a[sp1]) ? sp2 : sp1;
    213.             } else {
    214.                 minp = sp1;
    215.             }
    216.             if (justMinFun(a[minp], a[p])){
    217.                 var temp:Object = a[p];
    218.                 a[p] = a[minp];
    219.                 a[minp] = temp;
    220.                 p = minp;
    221.                 sp1 = p << 1;
    222.                 sp2 = sp1 + 1;
    223.             } else {
    224.                 break;
    225.             }
    226.         }
    227.         return min;
    228.     }
    229. }

    230. class Delaunay {

    231.     //----------------------------------------
    232.     //VARIABLES

    233.     //点群
    234.     private var _points:Array;
    235.     //三角形の集まり
    236.     private var _triangles:Array;
    237.     private var stageWidth:Number;
    238.     private var stageHeight:Number;

    239.     /*
    240.      * コンストラクタ
    241.      */
    242.     public function Delaunay(w:Number, h:Number){
    243.         stageWidth = w;
    244.         stageHeight = h;
    245.         //Security.allowDomain("*");
    246.         //Security.allowDomain("planet-ape.net");
    247.         //Security.allowDomain("wonderfl.net");
    248.         //Security.allowDomain("swf.wonderfl.net");
    249.         //初期化
    250.         _initialize();
    251.     }

    252.     /*
    253.      * 初期化
    254.      */
    255.     private function _initialize():void {

    256.         _points = new Array();
    257.         _triangles = new Array();

    258.         //ステージの大きさの三角形2つを用意
    259.         _points.push(new Node(0, 0, 0));
    260.         _points.push(new Node(1, stageWidth, 0));
    261.         _points.push(new Node(2, stageWidth, stageHeight));
    262.         _points.push(new Node(3, 0, stageHeight));
    263.         _triangles.push(new Triangle(_points[0], _points[1], _points[2]));
    264.         _triangles.push(new Triangle(_points[0], _points[2], _points[3]));
    265.     }

    266.     /*
    267.      * アップデート
    268.      */ /*private function _updateHandler(event : Event) : void {
    269.        _interaction();
    270.        // _draw();
    271.      }*/

    272.     /*
    273.      * インタラクション
    274.      */
    275.     private function _interaction():void {
    276.         //一時保持の三角形群
    277.         var localTriangles:Array = new Array();
    278.         //辺
    279.         var edges:Array;
    280.         //多角形
    281.         var polygon:Array;
    282.         //ポイント群ループ
    283.         for (var k:int = 4; k < _points.length; k++){
    284.             var node:Node = _points[k];
    285.             localTriangles = new Array();
    286.             edges = new Array();

    287.             for (var i:String in _triangles){
    288.                 //点が外接円
    289.                 var tri:Triangle = _triangles[i];
    290.                 if (inOuterCircle(node.point.x, node.point.y, tri)){
    291.                     edges.push(new Edge(tri.node0, tri.node1));
    292.                     edges.push(new Edge(tri.node1, tri.node2));
    293.                     edges.push(new Edge(tri.node2, tri.node0));
    294.                 } else {
    295.                     localTriangles.push(tri);
    296.                 }
    297.             }
    298.             //edgesからpolygonを作る(重複辺の削除
    299.             polygon = new Array();
    300.             for (i in edges){
    301.                 var edge0:Edge = edges[i];
    302.                 //重複チェック
    303.                 var flg:Boolean = false;
    304.                 for (var j:String in polygon){
    305.                     var edge1:Edge = polygon[j];
    306.                     if (judgeEdges(edge0, edge1)){
    307.                         flg = true;
    308.                         polygon.splice(j, 1);
    309.                         break;
    310.                     }
    311.                 }
    312.                 //データが存在しない場合は追加
    313.                 if (!flg)
    314.                     polygon.push(edges[i]);
    315.             }
    316.             //polygonから三角形を作って挿入
    317.             for (i in polygon){
    318.                 var tri1:Triangle = new Triangle(polygon[i].node0, polygon[i].node1, node);
    319.                 localTriangles.push(tri1);
    320.             }
    321.         }
    322.         if (localTriangles.length > 1)
    323.             _triangles = localTriangles;
    324.     }

    325.     /*
    326.      * 同じ辺かどうかの判定
    327.      */
    328.     private function judgeEdges(edge:Edge, edge0:Edge):Boolean {
    329.         if (edge.node0.id == edge0.node0.id && edge.node1.id == edge0.node1.id){
    330.             return true;
    331.         }
    332.         if (edge.node1.id == edge0.node0.id && edge.node0.id == edge0.node1.id){
    333.             return true;
    334.         }
    335.         return false;
    336.     }



    337.     /*
    338.      * 外接円の内か外か
    339.      */
    340.     public function inOuterCircle(x:Number, y:Number, tri:Triangle):Boolean {
    341.         var node0:Node = tri.node0;
    342.         var node1:Node = tri.node1;
    343.         var node2:Node = tri.node2;

    344.         var d:Number = (node0.point.x * node0.point.x + node0.point.y * node0.point.y - x * x - y * y) * ((node1.point.x - x) * (node2.point.y - y) - (node2.point.x - x) * (node1.point.y - y)) + (node1.point.x * node1.point.x + node1.point.y * node1.point.y - x * x - y * y) * ((node2.point.x - x) * (node0.point.y - y) - (node2.point.y - y) * (node0.point.x - x)) + (node2.point.x * node2.point.x + node2.point.y * node2.point.y - x * x - y * y) * ((node0.point.x - x) * (node1.point.y - y) - (node0.point.y - y) * (node1.point.x - x));
    345.         return ((node1.point.x - node0.point.x) * (node2.point.y - node0.point.y) - (node1.point.y - node0.point.y) * (node2.point.x - node0.point.x) > 0) ? d > 0 : d <= 0;
    346.     }

    347.     /*
    348.      * マウスクリック時
    349.      */
    350.     public function add(x:Number, y:Number):void {
    351.         _points.push(new Node(_points.length, x, y));
    352.         _interaction();
    353.     }

    354.     public function get triangles():Array {
    355.         return _triangles;
    356.     }

    357.     public function get points():Array {
    358.         return _points;
    359.     }
    360. }

    361. class Edge {
    362.     private var _node0:Node;
    363.     private var _node1:Node;

    364.     public function Edge(node0:Node, node1:Node):void {
    365.         _node0 = node0;
    366.         _node1 = node1;
    367.     }

    368.     public function get node0():Node {
    369.         return _node0;
    370.     }

    371.     public function get node1():Node {
    372.         return _node1;
    373.     }
    374. }

    375. class Grid {
    376.     public var startNode:Triangle;
    377.     public var endNode:Triangle;
    378.     public var delaunay:Delaunay;

    379.     public function Grid(){

    380.     }

    381.     public function calculateLinks():void {
    382.         var ts:Array = delaunay.triangles;
    383.         for each (var t:Triangle in ts){
    384.             t.links = [];
    385.         }
    386.         for (var i:int = 0; i < ts.length; i++){
    387.             var t1:Triangle = ts[i];
    388.             if (!t1.walkAble)
    389.                 continue;
    390.             for (var j:int = i + 1; j < ts.length; j++){
    391.                 var t2:Triangle = ts[j];
    392.                 if (!t2.walkAble)
    393.                     continue;
    394.                 var t1ns:Array = [t1.node0, t1.node1, t1.node2];
    395.                 var t2ns:Array = [t2.node0, t2.node1, t2.node2];
    396.                 var counter:int = 0;
    397.                 for (var m:int = 0; m < t1ns.length; m++){
    398.                     for (var n:int = 0; n < t2ns.length; n++){
    399.                         if (t1ns[m] == t2ns[n]){
    400.                             counter++;
    401.                         }
    402.                     }
    403.                 }
    404.                 if (counter > 1){
    405.                     var c:Number = Math.sqrt((t1.cx - t2.cx) * (t1.cx - t2.cx) + (t1.cy - t2.cy) * (t1.cy - t2.cy));
    406.                     t1.links.push(new Link(t2, c));
    407.                     t2.links.push(new Link(t1, c));
    408.                 }
    409.             }
    410.         }
    411.     }

    412. }

    413. class Link {
    414.     public var node:Triangle;
    415.     public var cost:Number;

    416.     public function Link(node:Triangle, cost:Number){
    417.         this.node = node;
    418.         this.cost = cost;
    419.     }

    420. }

    421. class Node {
    422.     private var _id:int;
    423.     private var _point:Point;

    424.     public function Node(id:int, x:Number, y:Number){
    425.         _id = id;
    426.         _point = new Point(x, y);
    427.     }

    428.     public function get id():int {
    429.         return _id;
    430.     }

    431.     public function get point():Point {
    432.         return _point;
    433.     }
    434. }

    435. class Triangle {


    436.     public var walkAble:Boolean = true;
    437.     public var version:int = 1;
    438.     public var links:Array;
    439.     public var f:Number;
    440.     public var g:Number;
    441.     public var h:Number;
    442.     public var parent:Triangle;

    443.     private var _node0:Node;
    444.     private var _node1:Node;
    445.     private var _node2:Node;
    446.     private var edge0:Edge;
    447.     private var edge1:Edge;
    448.     private var edge2:Edge;

    449.     public var cx:Number;
    450.     public var cy:Number;

    451.     public function Triangle(node0:Node, node1:Node, node2:Node):void {
    452.         _node0 = node0;
    453.         _node1 = node1;
    454.         _node2 = node2;
    455.         cx = (_node0.point.x + _node1.point.x + _node2.point.x) / 3;
    456.         cy = (_node0.point.y + _node1.point.y + _node2.point.y) / 3;
    457.     }

    458.     public function get node0():Node {
    459.         return _node0;
    460.     }

    461.     public function get node1():Node {
    462.         return _node1;
    463.     }

    464.     public function get node2():Node {
    465.         return _node2;
    466.     }
    467. }
    复制代码





    本文来自:http://wonderfl.net/c/re9l

    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

  • TA的每日心情
    开心
    2019-2-24 01:34
  • 签到天数: 3 天

    [LV.2]偶尔看看I

    0

    主题

    38

    帖子

    868

    积分

    上士

    Rank: 5Rank: 5

    威望
    20
    贡献
    0
    金币
    14
    钢镚
    0
    发表于 2019-2-24 02:33:45 | 显示全部楼层
    感谢分享!~
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2019-5-24 21:22 , Processed in 0.041411 second(s), 31 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表