RichCreator.git

using RichCreator.Utility.Maps;
using RichCreator.Utility.Structs;
using RichCreator.Utility.Utilitys;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace RichCreator.Utility.PathFinding
{
    /// <summary>
    /// DNF路径查找
    /// </summary>
    public class DNFPathFinding
    {
        public DNFPathFinding(HousePathInfo houseInfo)
        {
            this.HousePathInfo = houseInfo;
            InitPathFinder();
        }
 
        public DNFPathFinding(MapType mapType, Int32 houseIndex)
        {
            if (houseIndex < 0)
            {
                throw new ArgumentOutOfRangeException("houseIndex");
            }
            string info = null;
            if (mapType == MapType.Lingdong)
            {
                if (houseIndex > Lingdong.Length - 1)
                {
                    throw new ArgumentOutOfRangeException("houseIndex");
                }
                info = Lingdong[houseIndex];
            }
            else if (mapType == MapType.Kalete)
            {
                if (houseIndex > Kalete.Length - 1)
                {
                    throw new ArgumentOutOfRangeException("houseIndex");
                }
                info = Kalete[houseIndex];
            }
 
            try
            {
                this.HousePathInfo = HousePathInfo.FromJsonString(info);
            }
            catch (Exception e)
            {
                throw e;
            }
 
            InitPathFinder();
            
        }
 
        //凛冬
        private static readonly string[] Lingdong = new string[] {
            //0
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //1
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //2
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //3
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //4
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //5
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //6
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //7
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //8
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //9
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //10
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //11
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //12
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //13
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //14
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //15
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //16
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //17
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //18
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}",
            //19
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[],\"LocationPoints\":[],\"FindPathPoints\":[],\"LoopLines\":[],\"FindPathLines\":[]}"
 
        };
 
 
        //卡勒特
        private static readonly string[] Kalete = new string[] {
            //0：
            "{\"Width\":1350,\"Height\":901,\"Obstacles\":[{\"Points\":[{\"X\":1,\"Y\":357},{\"X\":803,\"Y\":359},{\"X\":1029,\"Y\":406},{\"X\":1229,\"Y\":361},{\"X\":1346,\"Y\":357},{\"X\":1346,\"Y\":1},{\"X\":0,\"Y\":3}],\"Length\":7},{\"Points\":[{\"X\":1348,\"Y\":739},{\"X\":1254,\"Y\":735},{\"X\":1250,\"Y\":696},{\"X\":1042,\"Y\":701},{\"X\":1042,\"Y\":726},{\"X\":252,\"Y\":735},{\"X\":243,\"Y\":680},{\"X\":1,\"Y\":700},{\"X\":1,\"Y\":900},{\"X\":1347,\"Y\":901}],\"Length\":10}],\"LocationPoints\":[{\"Point\":{\"X\":100,\"Y\":411},\"Parameter\":6},{\"Point\":{\"X\":591,\"Y\":410},\"Parameter\":5},{\"Point\":{\"X\":1077,\"Y\":408},\"Parameter\":4}],\"FindPathPoints\":[{\"X\":1213,\"Y\":401},{\"X\":122,\"Y\":404}],\"LoopLines\":[{\"P1\":{\"X\":122,\"Y\":404},\"P2\":{\"X\":1213,\"Y\":401}}],\"FindPathLines\":[]}",
            //1：
            "{\"Width\":1349,\"Height\":900,\"Obstacles\":[{\"Points\":[{\"X\":124,\"Y\":324},{\"X\":760,\"Y\":310},{\"X\":956,\"Y\":414},{\"X\":1124,\"Y\":372},{\"X\":1113,\"Y\":301},{\"X\":1346,\"Y\":297},{\"X\":1345,\"Y\":3},{\"X\":0,\"Y\":2},{\"X\":0,\"Y\":375}],\"Length\":9},{\"Points\":[{\"X\":1342,\"Y\":675},{\"X\":1189,\"Y\":675},{\"X\":1191,\"Y\":713},{\"X\":949,\"Y\":712},{\"X\":867,\"Y\":772},{\"X\":840,\"Y\":897},{\"X\":1345,\"Y\":899}],\"Length\":7},{\"Points\":[{\"X\":651,\"Y\":668},{\"X\":459,\"Y\":671},{\"X\":446,\"Y\":641},{\"X\":247,\"Y\":641},{\"X\":236,\"Y\":608},{\"X\":155,\"Y\":612},{\"X\":150,\"Y\":549},{\"X\":295,\"Y\":541},{\"X\":376,\"Y\":557},{\"X\":472,\"Y\":592},{\"X\":473,\"Y\":609},{\"X\":627,\"Y\":606}],\"Length\":12},{\"Points\":[{\"X\":565,\"Y\":815},{\"X\":464,\"Y\":737},{\"X\":0,\"Y\":721},{\"X\":1,\"Y\":896},{\"X\":839,\"Y\":894},{\"X\":851,\"Y\":815}],\"Length\":6}],\"LocationPoints\":[{\"Point\":{\"X\":270,\"Y\":462},\"Parameter\":0},{\"Point\":{\"X\":732,\"Y\":461},\"Parameter\":1},{\"Point\":{\"X\":1192,\"Y\":461},\"Parameter\":2},{\"Point\":{\"X\":708,\"Y\":344},\"Parameter\":8},{\"Point\":{\"X\":706,\"Y\":197},\"Parameter\":9},{\"Point\":{\"X\":706,\"Y\":53},\"Parameter\":10}],\"FindPathPoints\":[{\"X\":1211,\"Y\":323},{\"X\":193,\"Y\":419},{\"X\":1251,\"Y\":446},{\"X\":746,\"Y\":498},{\"X\":769,\"Y\":657},{\"X\":111,\"Y\":660}],\"LoopLines\":[{\"P1\":{\"X\":193,\"Y\":419},\"P2\":{\"X\":1251,\"Y\":446}}],\"FindPathLines\":[{\"P1\":{\"X\":193,\"Y\":419},\"P2\":{\"X\":746,\"Y\":498}},{\"P1\":{\"X\":746,\"Y\":498},\"P2\":{\"X\":1251,\"Y\":446}},{\"P1\":{\"X\":746,\"Y\":498},\"P2\":{\"X\":769,\"Y\":657}},{\"P1\":{\"X\":769,\"Y\":657},\"P2\":{\"X\":1251,\"Y\":446}},{\"P1\":{\"X\":769,\"Y\":657},\"P2\":{\"X\":193,\"Y\":419}},{\"P1\":{\"X\":1251,\"Y\":446},\"P2\":{\"X\":1211,\"Y\":323}},{\"P1\":{\"X\":769,\"Y\":657},\"P2\":{\"X\":1211,\"Y\":323}},{\"P1\":{\"X\":111,\"Y\":660},\"P2\":{\"X\":193,\"Y\":419}},{\"P1\":{\"X\":111,\"Y\":660},\"P2\":{\"X\":769,\"Y\":657}}]}",
            string.Empty,//2
            //3：
            "{\"Width\":1348,\"Height\":900,\"Obstacles\":[{\"Points\":[{\"X\":0,\"Y\":313},{\"X\":927,\"Y\":295},{\"X\":963,\"Y\":334},{\"X\":1275,\"Y\":314},{\"X\":1343,\"Y\":300},{\"X\":1343,\"Y\":2},{\"X\":1,\"Y\":1}],\"Length\":7},{\"Points\":[{\"X\":878,\"Y\":366},{\"X\":750,\"Y\":369},{\"X\":733,\"Y\":354},{\"X\":740,\"Y\":325},{\"X\":876,\"Y\":324}],\"Length\":5},{\"Points\":[{\"X\":1345,\"Y\":551},{\"X\":1170,\"Y\":587},{\"X\":1173,\"Y\":643},{\"X\":1275,\"Y\":713},{\"X\":1346,\"Y\":706}],\"Length\":5},{\"Points\":[{\"X\":285,\"Y\":307},{\"X\":312,\"Y\":576},{\"X\":195,\"Y\":626},{\"X\":208,\"Y\":691},{\"X\":153,\"Y\":723},{\"X\":150,\"Y\":897},{\"X\":2,\"Y\":896},{\"X\":0,\"Y\":319}],\"Length\":8},{\"Points\":[{\"X\":156,\"Y\":752},{\"X\":369,\"Y\":714},{\"X\":793,\"Y\":734},{\"X\":932,\"Y\":822},{\"X\":1032,\"Y\":814},{\"X\":1058,\"Y\":896},{\"X\":159,\"Y\":894}],\"Length\":7},{\"Points\":[{\"X\":1037,\"Y\":824},{\"X\":1243,\"Y\":820},{\"X\":1229,\"Y\":748},{\"X\":1269,\"Y\":718},{\"X\":1344,\"Y\":709},{\"X\":1345,\"Y\":896},{\"X\":1064,\"Y\":897}],\"Length\":7}],\"LocationPoints\":[{\"Point\":{\"X\":1108,\"Y\":329},\"Parameter\":8},{\"Point\":{\"X\":1107,\"Y\":182},\"Parameter\":9},{\"Point\":{\"X\":1107,\"Y\":37},\"Parameter\":10}],\"FindPathPoints\":[{\"X\":358,\"Y\":342},{\"X\":378,\"Y\":505},{\"X\":1270,\"Y\":415},{\"X\":1038,\"Y\":650}],\"LoopLines\":[{\"P1\":{\"X\":358,\"Y\":342},\"P2\":{\"X\":1038,\"Y\":650}}],\"FindPathLines\":[{\"P1\":{\"X\":358,\"Y\":342},\"P2\":{\"X\":1270,\"Y\":415}},{\"P1\":{\"X\":1270,\"Y\":415},\"P2\":{\"X\":1038,\"Y\":650}},{\"P1\":{\"X\":1270,\"Y\":415},\"P2\":{\"X\":378,\"Y\":505}},{\"P1\":{\"X\":378,\"Y\":505},\"P2\":{\"X\":358,\"Y\":342}},{\"P1\":{\"X\":378,\"Y\":505},\"P2\":{\"X\":1038,\"Y\":650}}]}",
            string.Empty,//4
            string.Empty,//5
            //6：
            "{\"Width\":1350,\"Height\":900,\"Obstacles\":[{\"Points\":[{\"X\":325,\"Y\":425},{\"X\":437,\"Y\":447},{\"X\":567,\"Y\":437},{\"X\":565,\"Y\":395},{\"X\":631,\"Y\":398},{\"X\":675,\"Y\":410},{\"X\":809,\"Y\":405},{\"X\":810,\"Y\":375},{\"X\":933,\"Y\":329},{\"X\":1279,\"Y\":303},{\"X\":1345,\"Y\":367},{\"X\":1345,\"Y\":5},{\"X\":1,\"Y\":6}],\"Length\":13},{\"Points\":[{\"X\":1347,\"Y\":481},{\"X\":1246,\"Y\":501},{\"X\":1235,\"Y\":551},{\"X\":1188,\"Y\":617},{\"X\":1192,\"Y\":669},{\"X\":1348,\"Y\":673}],\"Length\":6},{\"Points\":[{\"X\":1349,\"Y\":701},{\"X\":791,\"Y\":719},{\"X\":803,\"Y\":659},{\"X\":396,\"Y\":665},{\"X\":361,\"Y\":723},{\"X\":2,\"Y\":711},{\"X\":0,\"Y\":896},{\"X\":1345,\"Y\":898}],\"Length\":8}],\"LocationPoints\":[{\"Point\":{\"X\":1080,\"Y\":425},\"Parameter\":4},{\"Point\":{\"X\":592,\"Y\":427},\"Parameter\":5},{\"Point\":{\"X\":103,\"Y\":427},\"Parameter\":6}],\"FindPathPoints\":[{\"X\":174,\"Y\":537},{\"X\":1197,\"Y\":430},{\"X\":602,\"Y\":502}],\"LoopLines\":[{\"P1\":{\"X\":174,\"Y\":537},\"P2\":{\"X\":1197,\"Y\":430}}],\"FindPathLines\":[{\"P1\":{\"X\":174,\"Y\":537},\"P2\":{\"X\":602,\"Y\":502}},{\"P1\":{\"X\":602,\"Y\":502},\"P2\":{\"X\":1197,\"Y\":430}}]}",
            //7：
            "{\"Width\":1350,\"Height\":900,\"Obstacles\":[{\"Points\":[{\"X\":31,\"Y\":409},{\"X\":127,\"Y\":312},{\"X\":505,\"Y\":351},{\"X\":570,\"Y\":394},{\"X\":733,\"Y\":418},{\"X\":888,\"Y\":410},{\"X\":896,\"Y\":334},{\"X\":1066,\"Y\":328},{\"X\":1100,\"Y\":401},{\"X\":1315,\"Y\":425},{\"X\":1349,\"Y\":427},{\"X\":1343,\"Y\":1},{\"X\":4,\"Y\":4},{\"X\":1,\"Y\":341}],\"Length\":14},{\"Points\":[{\"X\":467,\"Y\":896},{\"X\":472,\"Y\":733},{\"X\":325,\"Y\":676},{\"X\":178,\"Y\":636},{\"X\":0,\"Y\":625},{\"X\":2,\"Y\":900}],\"Length\":6}],\"LocationPoints\":[{\"Point\":{\"X\":270,\"Y\":462},\"Parameter\":0},{\"Point\":{\"X\":730,\"Y\":463},\"Parameter\":1},{\"Point\":{\"X\":1191,\"Y\":463},\"Parameter\":2},{\"Point\":{\"X\":1078,\"Y\":499},\"Parameter\":4},{\"Point\":{\"X\":589,\"Y\":497},\"Parameter\":5},{\"Point\":{\"X\":100,\"Y\":498},\"Parameter\":6}],\"FindPathPoints\":[{\"X\":146,\"Y\":440},{\"X\":1226,\"Y\":720}],\"LoopLines\":[{\"P1\":{\"X\":146,\"Y\":440},\"P2\":{\"X\":1226,\"Y\":720}}],\"FindPathLines\":[]}",
            //8：
            "{\"Width\":1686,\"Height\":720,\"Obstacles\":[{\"Points\":[{\"X\":2,\"Y\":420},{\"X\":130,\"Y\":439},{\"X\":311,\"Y\":462},{\"X\":313,\"Y\":400},{\"X\":221,\"Y\":319},{\"X\":453,\"Y\":288},{\"X\":632,\"Y\":5},{\"X\":4,\"Y\":2}],\"Length\":8},{\"Points\":[{\"X\":574,\"Y\":104},{\"X\":743,\"Y\":319},{\"X\":961,\"Y\":306},{\"X\":1014,\"Y\":343},{\"X\":1099,\"Y\":326},{\"X\":1165,\"Y\":369},{\"X\":1534,\"Y\":365},{\"X\":1684,\"Y\":309},{\"X\":1680,\"Y\":4},{\"X\":633,\"Y\":5}],\"Length\":10},{\"Points\":[{\"X\":1682,\"Y\":470},{\"X\":1540,\"Y\":514},{\"X\":1442,\"Y\":590},{\"X\":1173,\"Y\":641},{\"X\":858,\"Y\":670},{\"X\":814,\"Y\":708},{\"X\":1681,\"Y\":715}],\"Length\":7}],\"LocationPoints\":[{\"Point\":{\"X\":277,\"Y\":501},\"Parameter\":0},{\"Point\":{\"X\":735,\"Y\":502},\"Parameter\":1},{\"Point\":{\"X\":1196,\"Y\":502},\"Parameter\":2},{\"Point\":{\"X\":1418,\"Y\":390},\"Parameter\":4},{\"Point\":{\"X\":930,\"Y\":387},\"Parameter\":5},{\"Point\":{\"X\":441,\"Y\":388},\"Parameter\":6}],\"FindPathPoints\":[{\"X\":186,\"Y\":483},{\"X\":1565,\"Y\":393},{\"X\":549,\"Y\":448}],\"LoopLines\":[{\"P1\":{\"X\":186,\"Y\":483},\"P2\":{\"X\":1565,\"Y\":393}}],\"FindPathLines\":[{\"P1\":{\"X\":186,\"Y\":483},\"P2\":{\"X\":549,\"Y\":448}},{\"P1\":{\"X\":549,\"Y\":448},\"P2\":{\"X\":1565,\"Y\":393}}]}",
            //9：
            "{\"Width\":1688,\"Height\":720,\"Obstacles\":[{\"Points\":[{\"X\":3,\"Y\":333},{\"X\":390,\"Y\":305},{\"X\":600,\"Y\":389},{\"X\":746,\"Y\":389},{\"X\":766,\"Y\":327},{\"X\":890,\"Y\":334},{\"X\":914,\"Y\":247},{\"X\":1092,\"Y\":225},{\"X\":1305,\"Y\":396},{\"X\":1489,\"Y\":346},{\"X\":1684,\"Y\":411},{\"X\":1683,\"Y\":3},{\"X\":3,\"Y\":3}],\"Length\":13},{\"Points\":[{\"X\":389,\"Y\":671},{\"X\":398,\"Y\":614},{\"X\":868,\"Y\":605},{\"X\":1037,\"Y\":631},{\"X\":1125,\"Y\":589},{\"X\":1536,\"Y\":632},{\"X\":1678,\"Y\":682},{\"X\":1682,\"Y\":715},{\"X\":378,\"Y\":715}],\"Length\":9}],\"LocationPoints\":[{\"Point\":{\"X\":274,\"Y\":500},\"Parameter\":0},{\"Point\":{\"X\":738,\"Y\":502},\"Parameter\":1},{\"Point\":{\"X\":1200,\"Y\":501},\"Parameter\":2},{\"Point\":{\"X\":1658,\"Y\":503},\"Parameter\":3}],\"FindPathPoints\":[{\"X\":216,\"Y\":456},{\"X\":1545,\"Y\":466},{\"X\":985,\"Y\":515}],\"LoopLines\":[{\"P1\":{\"X\":216,\"Y\":456},\"P2\":{\"X\":1545,\"Y\":466}}],\"FindPathLines\":[{\"P1\":{\"X\":216,\"Y\":456},\"P2\":{\"X\":985,\"Y\":515}},{\"P1\":{\"X\":985,\"Y\":515},\"P2\":{\"X\":1545,\"Y\":466}}]}",
            string.Empty,//10
            //11：
            "{\"Width\":1686,\"Height\":720,\"Obstacles\":[{\"Points\":[{\"X\":1678,\"Y\":410},{\"X\":1576,\"Y\":341},{\"X\":1258,\"Y\":344},{\"X\":1241,\"Y\":379},{\"X\":1153,\"Y\":380},{\"X\":849,\"Y\":377},{\"X\":765,\"Y\":353},{\"X\":598,\"Y\":352},{\"X\":498,\"Y\":387},{\"X\":0,\"Y\":360},{\"X\":1,\"Y\":1},{\"X\":1681,\"Y\":2}],\"Length\":12},{\"Points\":[{\"X\":1566,\"Y\":714},{\"X\":1502,\"Y\":662},{\"X\":875,\"Y\":654},{\"X\":780,\"Y\":660},{\"X\":550,\"Y\":636},{\"X\":365,\"Y\":614},{\"X\":183,\"Y\":626},{\"X\":72,\"Y\":636},{\"X\":10,\"Y\":655},{\"X\":0,\"Y\":715}],\"Length\":10}],\"LocationPoints\":[{\"Point\":{\"X\":929,\"Y\":450},\"Parameter\":5},{\"Point\":{\"X\":440,\"Y\":452},\"Parameter\":6},{\"Point\":{\"X\":1416,\"Y\":451},\"Parameter\":4}],\"FindPathPoints\":[{\"X\":71,\"Y\":469},{\"X\":1529,\"Y\":462},{\"X\":826,\"Y\":576}],\"LoopLines\":[{\"P1\":{\"X\":71,\"Y\":469},\"P2\":{\"X\":1529,\"Y\":462}}],\"FindPathLines\":[{\"P1\":{\"X\":71,\"Y\":469},\"P2\":{\"X\":826,\"Y\":576}},{\"P1\":{\"X\":826,\"Y\":576},\"P2\":{\"X\":1529,\"Y\":462}}]}",
            //12：
            "{\"Width\":2024,\"Height\":720,\"Obstacles\":[{\"Points\":[{\"X\":795,\"Y\":351},{\"X\":1897,\"Y\":323},{\"X\":2019,\"Y\":271},{\"X\":2019,\"Y\":4},{\"X\":1,\"Y\":2},{\"X\":3,\"Y\":347},{\"X\":111,\"Y\":400},{\"X\":200,\"Y\":377},{\"X\":294,\"Y\":344},{\"X\":560,\"Y\":351},{\"X\":623,\"Y\":381}],\"Length\":11},{\"Points\":[{\"X\":2020,\"Y\":614},{\"X\":1464,\"Y\":615},{\"X\":1137,\"Y\":589},{\"X\":895,\"Y\":606},{\"X\":855,\"Y\":715},{\"X\":2020,\"Y\":716}],\"Length\":6},{\"Points\":[{\"X\":525,\"Y\":715},{\"X\":451,\"Y\":589},{\"X\":156,\"Y\":603},{\"X\":2,\"Y\":495},{\"X\":2,\"Y\":716}],\"Length\":5}],\"LocationPoints\":[{\"Point\":{\"X\":270,\"Y\":461},\"Parameter\":0},{\"Point\":{\"X\":731,\"Y\":461},\"Parameter\":1},{\"Point\":{\"X\":1192,\"Y\":462},\"Parameter\":2},{\"Point\":{\"X\":1650,\"Y\":463},\"Parameter\":3},{\"Point\":{\"X\":1278,\"Y\":347},\"Parameter\":5},{\"Point\":{\"X\":788,\"Y\":347},\"Parameter\":6},{\"Point\":{\"X\":301,\"Y\":346},\"Parameter\":7},{\"Point\":{\"X\":628,\"Y\":175},\"Parameter\":8},{\"Point\":{\"X\":627,\"Y\":28},\"Parameter\":9}],\"FindPathPoints\":[{\"X\":201,\"Y\":457},{\"X\":1894,\"Y\":423},{\"X\":699,\"Y\":513}],\"LoopLines\":[{\"P1\":{\"X\":201,\"Y\":457},\"P2\":{\"X\":1894,\"Y\":423}}],\"FindPathLines\":[{\"P1\":{\"X\":201,\"Y\":457},\"P2\":{\"X\":699,\"Y\":513}},{\"P1\":{\"X\":699,\"Y\":513},\"P2\":{\"X\":1894,\"Y\":423}}]}",
            //13：
            "{\"Width\":2024,\"Height\":900,\"Obstacles\":[{\"Points\":[{\"X\":1607,\"Y\":189},{\"X\":1761,\"Y\":360},{\"X\":2022,\"Y\":405},{\"X\":2022,\"Y\":1},{\"X\":1565,\"Y\":1}],\"Length\":5},{\"Points\":[{\"X\":1350,\"Y\":400},{\"X\":1605,\"Y\":186},{\"X\":1562,\"Y\":1},{\"X\":121,\"Y\":1},{\"X\":335,\"Y\":410},{\"X\":385,\"Y\":402}],\"Length\":6},{\"Points\":[{\"X\":2017,\"Y\":719},{\"X\":1228,\"Y\":729},{\"X\":1137,\"Y\":666},{\"X\":667,\"Y\":689},{\"X\":417,\"Y\":671},{\"X\":123,\"Y\":649},{\"X\":121,\"Y\":891},{\"X\":2020,\"Y\":896}],\"Length\":8},{\"Points\":[{\"X\":294,\"Y\":564},{\"X\":121,\"Y\":566},{\"X\":122,\"Y\":19},{\"X\":322,\"Y\":394},{\"X\":233,\"Y\":457}],\"Length\":5},{\"Points\":[{\"X\":1,\"Y\":2},{\"X\":127,\"Y\":3},{\"X\":128,\"Y\":896},{\"X\":0,\"Y\":894}],\"Length\":4}],\"LocationPoints\":[{\"Point\":{\"X\":537,\"Y\":496},\"Parameter\":0},{\"Point\":{\"X\":997,\"Y\":497},\"Parameter\":1},{\"Point\":{\"X\":1458,\"Y\":497},\"Parameter\":2},{\"Point\":{\"X\":1918,\"Y\":496},\"Parameter\":3},{\"Point\":{\"X\":777,\"Y\":484},\"Parameter\":6},{\"Point\":{\"X\":1266,\"Y\":484},\"Parameter\":5},{\"Point\":{\"X\":1753,\"Y\":485},\"Parameter\":4}],\"FindPathPoints\":[{\"X\":425,\"Y\":495},{\"X\":1885,\"Y\":496},{\"X\":1294,\"Y\":541}],\"LoopLines\":[{\"P1\":{\"X\":425,\"Y\":495},\"P2\":{\"X\":1885,\"Y\":496}}],\"FindPathLines\":[{\"P1\":{\"X\":425,\"Y\":495},\"P2\":{\"X\":1294,\"Y\":541}},{\"P1\":{\"X\":1294,\"Y\":541},\"P2\":{\"X\":1885,\"Y\":496}}]}",
            //14：
            "{\"Width\":1687,\"Height\":901,\"Obstacles\":[{\"Points\":[{\"X\":98,\"Y\":310},{\"X\":408,\"Y\":314},{\"X\":418,\"Y\":425},{\"X\":530,\"Y\":416},{\"X\":593,\"Y\":451},{\"X\":721,\"Y\":452},{\"X\":762,\"Y\":449},{\"X\":783,\"Y\":337},{\"X\":840,\"Y\":302},{\"X\":1207,\"Y\":300},{\"X\":1239,\"Y\":321},{\"X\":1418,\"Y\":320},{\"X\":1584,\"Y\":378},{\"X\":1679,\"Y\":377},{\"X\":1681,\"Y\":4},{\"X\":4,\"Y\":4},{\"X\":0,\"Y\":436}],\"Length\":17},{\"Points\":[{\"X\":1681,\"Y\":717},{\"X\":1319,\"Y\":706},{\"X\":1165,\"Y\":653},{\"X\":1053,\"Y\":654},{\"X\":835,\"Y\":609},{\"X\":732,\"Y\":624},{\"X\":680,\"Y\":667},{\"X\":0,\"Y\":650},{\"X\":0,\"Y\":898},{\"X\":1682,\"Y\":898}],\"Length\":10}],\"LocationPoints\":[{\"Point\":{\"X\":278,\"Y\":481},\"Parameter\":0},{\"Point\":{\"X\":739,\"Y\":481},\"Parameter\":1},{\"Point\":{\"X\":1200,\"Y\":479},\"Parameter\":2},{\"Point\":{\"X\":1656,\"Y\":480},\"Parameter\":3}],\"FindPathPoints\":[{\"X\":140,\"Y\":474},{\"X\":1453,\"Y\":466},{\"X\":763,\"Y\":520},{\"X\":373,\"Y\":565}],\"LoopLines\":[{\"P1\":{\"X\":140,\"Y\":474},\"P2\":{\"X\":1453,\"Y\":466}}],\"FindPathLines\":[{\"P1\":{\"X\":140,\"Y\":474},\"P2\":{\"X\":373,\"Y\":565}},{\"P1\":{\"X\":140,\"Y\":474},\"P2\":{\"X\":763,\"Y\":520}},{\"P1\":{\"X\":373,\"Y\":565},\"P2\":{\"X\":763,\"Y\":520}},{\"P1\":{\"X\":763,\"Y\":520},\"P2\":{\"X\":1453,\"Y\":466}},{\"P1\":{\"X\":373,\"Y\":565},\"P2\":{\"X\":1453,\"Y\":466}}]}",
            string.Empty,//15
            //16：
            "{\"Width\":1687,\"Height\":901,\"Obstacles\":[{\"Points\":[{\"X\":3,\"Y\":385},{\"X\":257,\"Y\":388},{\"X\":655,\"Y\":320},{\"X\":711,\"Y\":264},{\"X\":1682,\"Y\":279},{\"X\":1682,\"Y\":1},{\"X\":0,\"Y\":4}],\"Length\":7},{\"Points\":[{\"X\":5,\"Y\":713},{\"X\":265,\"Y\":754},{\"X\":432,\"Y\":862},{\"X\":405,\"Y\":900},{\"X\":1,\"Y\":896}],\"Length\":5},{\"Points\":[{\"X\":720,\"Y\":883},{\"X\":825,\"Y\":776},{\"X\":1034,\"Y\":851},{\"X\":985,\"Y\":900},{\"X\":712,\"Y\":900}],\"Length\":5},{\"Points\":[{\"X\":1173,\"Y\":871},{\"X\":1569,\"Y\":644},{\"X\":1674,\"Y\":661},{\"X\":1684,\"Y\":772},{\"X\":1679,\"Y\":887},{\"X\":1187,\"Y\":893},{\"X\":1200,\"Y\":852}],\"Length\":7}],\"LocationPoints\":[{\"Point\":{\"X\":1391,\"Y\":410},\"Parameter\":4},{\"Point\":{\"X\":905,\"Y\":409},\"Parameter\":5},{\"Point\":{\"X\":416,\"Y\":410},\"Parameter\":6}],\"FindPathPoints\":[{\"X\":633,\"Y\":693},{\"X\":1494,\"Y\":434},{\"X\":139,\"Y\":505},{\"X\":834,\"Y\":367}],\"LoopLines\":[{\"P1\":{\"X\":139,\"Y\":505},\"P2\":{\"X\":1494,\"Y\":434}}],\"FindPathLines\":[{\"P1\":{\"X\":139,\"Y\":505},\"P2\":{\"X\":834,\"Y\":367}},{\"P1\":{\"X\":834,\"Y\":367},\"P2\":{\"X\":1494,\"Y\":434}},{\"P1\":{\"X\":633,\"Y\":693},\"P2\":{\"X\":1494,\"Y\":434}},{\"P1\":{\"X\":633,\"Y\":693},\"P2\":{\"X\":834,\"Y\":367}},{\"P1\":{\"X\":633,\"Y\":693},\"P2\":{\"X\":139,\"Y\":505}}]}",
            //17：
            "{\"Width\":1687,\"Height\":720,\"Obstacles\":[{\"Points\":[{\"X\":1681,\"Y\":368},{\"X\":1591,\"Y\":363},{\"X\":1487,\"Y\":252},{\"X\":1475,\"Y\":4},{\"X\":1683,\"Y\":3}],\"Length\":5},{\"Points\":[{\"X\":1348,\"Y\":358},{\"X\":544,\"Y\":345},{\"X\":534,\"Y\":453},{\"X\":115,\"Y\":450},{\"X\":0,\"Y\":390},{\"X\":0,\"Y\":3},{\"X\":1480,\"Y\":3},{\"X\":1487,\"Y\":245}],\"Length\":8},{\"Points\":[{\"X\":108,\"Y\":685},{\"X\":76,\"Y\":720},{\"X\":1682,\"Y\":718},{\"X\":1684,\"Y\":683}],\"Length\":4}],\"LocationPoints\":[{\"Point\":{\"X\":276,\"Y\":499},\"Parameter\":0},{\"Point\":{\"X\":736,\"Y\":502},\"Parameter\":1},{\"Point\":{\"X\":1198,\"Y\":500},\"Parameter\":2},{\"Point\":{\"X\":1655,\"Y\":502},\"Parameter\":3}],\"FindPathPoints\":[{\"X\":196,\"Y\":514},{\"X\":1622,\"Y\":491},{\"X\":605,\"Y\":518}],\"LoopLines\":[{\"P1\":{\"X\":196,\"Y\":514},\"P2\":{\"X\":1622,\"Y\":491}}],\"FindPathLines\":[{\"P1\":{\"X\":196,\"Y\":514},\"P2\":{\"X\":605,\"Y\":518}},{\"P1\":{\"X\":605,\"Y\":518},\"P2\":{\"X\":1622,\"Y\":491}}]}",
        };
 
        /// <summary>
        /// 房间信息
        /// </summary>
        public HousePathInfo HousePathInfo { get; private set; }
 
        /// <summary>
        /// 路径查找器
        /// </summary>
        public Dijkstra<ZTPoint> PathFinder { get; private set; }
 
        /// <summary>
        /// 定位字典
        /// </summary>
        private Dictionary<Int32, ZTPoint> LocationDic = new Dictionary<int, ZTPoint>();
 
        /// <summary>
        /// 屏幕坐标转地图坐标
        /// </summary>
        /// <param name="screenCoordinate"></param>
        /// <param name="locationParameter"></param>
        /// <param name="locationCoordinate"></param>
        /// <returns></returns>
        public ZTPoint ScreenToMapCoordinate(ZTPoint screenCoordinate,Int32 locationParameter,ZTPoint locationScreenCoordinate)
        {
            if (!LocationDic.ContainsKey(locationParameter))
            {
                throw new ArgumentOutOfRangeException("不存在的定位点,parameter:"+locationParameter.ToString());
            }
 
            //目标屏幕坐标+(定位点地图坐标-定位点屏幕坐标)
            return screenCoordinate.Add(LocationDic[locationParameter].Sub(locationScreenCoordinate));
        }
 
        /// <summary>
        /// 地图坐标转屏幕坐标
        /// </summary>
        /// <param name="mapCoordinate"></param>
        /// <param name="locationParameter"></param>
        /// <param name="locationCoordinate"></param>
        /// <returns></returns>
        public ZTPoint MapToScreenCoordinate(ZTPoint mapCoordinate, Int32 locationParameter, ZTPoint locationScreenCoordinate)
        {
            if (!LocationDic.ContainsKey(locationParameter))
            {
                throw new ArgumentOutOfRangeException("不存在的定位点,parameter:" + locationParameter.ToString());
            }
 
            //目标地图坐标-(定位点地图坐标-定位点屏幕坐标)
            return mapCoordinate.Sub(LocationDic[locationParameter].Sub(locationScreenCoordinate));
        }
 
        
        /// <summary>
        /// 寻找巡逻路线
        /// </summary>
        /// <param name="rolePosition"></param>
        public void FindLoopPath(ZTPoint rolePosition)
        {
 
        }
 
        /// <summary>
        /// 两点之间寻路
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        public List<ZTPoint> FindPath(ref ZTPoint start, ref ZTPoint end)
        {
 
            if (start.Equals(end))
            {
                return new List<ZTPoint>();
            }
 
            //查询两点间是否连通
            if (Iscross(start, end))
            {
                //两点直接连通
                return new List<ZTPoint>() { end };
            }
 
            //确保两点不在障碍物里
            bool inObstacle = EnsureNotInObstacle(ref start);
            inObstacle = EnsureNotInObstacle(ref end) || inObstacle;
 
            //查询两点间是否连通
            if (inObstacle && Iscross(start, end))
            {
                //两点直接连通
                return new List<ZTPoint>() { end };
            }
 
 
            //把两点添加到寻路网中
            AddToFinder(start, end);
 
            //寻路，组合路径
            List<ZTPoint> paths=this.PathFinder.ShortestPath(start, end);
 
            //去除寻路网中
            RemoveFromFinder(start, end);
            return paths;
        }
 
        /// <summary>
        /// 判断两点间是否连通 
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        private bool Iscross(ZTPoint start, ZTPoint end)
        {
 
            for (int i = 0; i < this.HousePathInfo.Obstacles.Count; i++)
            {
                Intersection interSection = GeometryHelper.IntersectionOf(new ZTLinePoint(start, end), this.HousePathInfo.Obstacles[i]);
                if (interSection != Intersection.None)
                {
                    return false;
                }
            }
            return true;
        }
 
        /// <summary>
        /// 是否在障碍物里，如果在障碍物里则返回最近的不在障碍物点
        /// </summary>
        /// <param name="point"></param>
        /// <returns>true:在障碍物，false:不在障碍物里</returns>
        private bool EnsureNotInObstacle(ref ZTPoint point)
        {
            ZTPoint source = new ZTPoint(point.X, point.Y);
            ZTPolygon obstacle = ZTPolygon.Empty;
            for (int i = 0; i < this.HousePathInfo.Obstacles.Count; i++)
            {
                ZTPolygon temp = this.HousePathInfo.Obstacles[i];
                if (GeometryHelper.IntersectionOf(point, temp) != Intersection.None)
                {
                    obstacle = this.HousePathInfo.Obstacles[i];
                    break;
                }
            }
            if (obstacle.Equals(ZTPolygon.Empty))
            {
                //不在障碍物内
                return false;
            }
 
            //计算距离障碍物外最近的距离
            double distance = 0;
            ZTPoint lastPoint = ZTPoint.Empty;
            for (int i = 0; i < obstacle.Points.Length; i++)
            {
                if (i == 0)
                {
                    lastPoint = obstacle.Points[i];
                    distance = GeometryHelper.GetPointDistance(lastPoint, point);
                }
                double lastDistance = GeometryHelper.GetNearestDistance(new ZTLinePoint(lastPoint, obstacle[i]), point);
                if (lastDistance < distance)
                {
                    distance = lastDistance;
                }
                if (distance <= 0)
                {
                    distance = 0;
                    break;
                }
            }
 
            //查找最近离开障碍物的点
            ZTPoint testPoint = new ZTPoint(point.X, point.Y);
            Int32 maxDistance = Math.Max(Math.Max(point.X, this.HousePathInfo.Width - point.X), Math.Max(point.Y, this.HousePathInfo.Height - point.Y));
            for (int i = (Int32)distance; i < maxDistance; i++)
            {
                //下
                if (point.Y + i <= this.HousePathInfo.Height)
                {
                    testPoint = new ZTPoint(point.X, point.Y + i);
                    if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
                    {
                        testPoint.Y += 10;
                        point = testPoint;
                        break;
                    }
                }
 
 
                //右
                if (point.X <= this.HousePathInfo.Width)
                {
                    testPoint = new ZTPoint(point.X + i, point.Y);
                    if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
                    {
                        testPoint.X += 10;
                        point = testPoint;
                        break;
                    }
                }
 
                //左
                if (point.X - i >= 0)
                {
                    testPoint = new ZTPoint(point.X - i, point.Y);
                    if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
                    {
                        testPoint.X -= 10;
                        point = testPoint;
                        break;
                    }
                }
 
                //上
                if (point.Y - i >= 0)
                {
                    testPoint = new ZTPoint(point.X, point.Y - i);
                    if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
                    {
                        testPoint.Y -= 10;
                        point = testPoint;
                        break;
                    }
                }
            }
 
            return true;
        }
 
        /// <summary>
        /// 初始化寻路器
        /// </summary>
        private void InitPathFinder()
        {
            this.PathFinder = new Dijkstra<ZTPoint>();
 
            //添加寻路路径
            ZTLinePoint line;
            for (int i = 0; i < this.HousePathInfo.FindPathLines.Count; i++)
            {
                line = this.HousePathInfo.FindPathLines[i];
                this.PathFinder.AddVertex(line.P1, line.P2, line.GetDistance());
            }
 
            //添加巡逻路径
            for (int i = 0; i < this.HousePathInfo.LoopLines.Count; i++)
            {
                line = this.HousePathInfo.LoopLines[i];
                this.PathFinder.AddVertex(line.P1, line.P2, line.GetDistance());
            }
 
            //定位点添加到字典
            for (int i = 0; i < this.HousePathInfo.LocationPoints.Count; i++)
            {
                ParametersPoint pp = this.HousePathInfo.LocationPoints[i];
                if (!this.LocationDic.ContainsKey(pp.Parameter))
                {
                    this.LocationDic.Add(pp.Parameter, pp.Point);
                }
            }
        }
 
        /// <summary>
        /// 向查找器中添加查找点
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        private void AddToFinder(ZTPoint start,ZTPoint end)
        {
            Int32 distance = 0;
            ZTPoint point;
            for (int i = 0; i < this.HousePathInfo.FindPathPoints.Count; i++)
            {
                point = this.HousePathInfo.FindPathPoints[i];
                if (Iscross(start, point))
                {
                    distance = (Int32)GeometryHelper.GetPointDistance(start, point);
                    this.PathFinder.AddVertex(start, point, distance);
                }
 
                if (Iscross(end,point))
                {
                    distance = (Int32)GeometryHelper.GetPointDistance(end, point);
                    this.PathFinder.AddVertex(end, point, distance);
                }
            }
            
        }
 
 
        /// <summary>
        /// 从查找器中移除查找点
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        private void RemoveFromFinder(ZTPoint start, ZTPoint end)
        {
            this.PathFinder.RemoveVertex(start);
            this.PathFinder.RemoveVertex(end);
        }
 
 
 
 
 
 
    }
}