typedefunsignedintuint;
1. typedefstd::vector<int>CRow;
2. //相当于把CLabyrinth定义成一个整型的二维数组
3. typedefstd::vector<CRow>CLabyrinth;

classCPoint
1. {
3. public:
4. intcol;//列
5. introw;//行
7. public:
8. //构造函数，接受行和列的初始化
9. CPoint(intc=0,intr=0)
10. :col(c)
11. ,row(r)
12. {
13. return;
14. }
15. //赋值操作
16. CPoint&operator=(constCPoint&pt)
17. col=pt.col;
18. row=pt.row;
19. return*this;
20. //比较操作
21. booloperator==(returncol==pt.col&&row==pt.row;
22. //判断该位置是否合法
23. boolallRight()
24. returncol>=0&&row>=0;
25. };
26. typedefstd::vector<CPoint>CRoute;

{
1. protected:
2. //装有迷宫数据的二维数组
3. CLabyrinthm_xLabyrinth;
4. //起点位置
5. CPointm_ptBeginning;
6. //终点位置
7. CPointm_ptEnding;
8. //记录路线的数组
9. CRoutem_vRoute;
10. //枚举表示起点、终点的值
11. enum{Beginning=-1,Ending=-2};
12. //枚举表示障碍物与可走区的值
13. enum{CanntGo=0,CanGo=1};
14. //枚举是否找到终点
15. enum{FoundEnding=0,NotFoundEnding=1};
16. //判断某个位置是否已在路线数组中，用于别走重复的路
17. boolisRepeat(boolbRes=false;
18. CRoute::iteratorit=m_vRoute.begin();
19. for(;it!=m_vRoute.end();it++){
20. CPointpt0=*it;
21. if(pt0==pt){
22. bRes=true;
23. break;
24. }
25. returnbRes;
26. //将某一位置加入路线数组
27. voidadvance(constCPoint&ptTo)
28. m_vRoute.push_back(ptTo);
29. //将路线数组最后一个位置弹出
30. voidback()
31. m_vRoute.pop_back();
32. //判断某一位置是否是起点
33. boolisBeginning(constCPoint&pt)
34. returnm_ptBeginning==pt;
35. //判断某一位置是否是终点
36. boolisEnding(returnm_ptEnding==pt;
37. /*-----------------核心算法------------------------*/
38. //判断某一位置是否可以向上移动
39. CPointcanUp(constCPoint&ptCurrent)//接受当前位置
40. CPointptRes=CPoint(-1,-1);
41. intcol=ptCurrent.col;
42. introw=ptCurrent.row;
43. if(row>0){
44. CPointptNext=CPoint(col,row-1);//上移后位置
45. //检查上移后位置是否已经走过，以免寻路过程中绕圈子进入死循环
46. if(!isRepeat(ptNext)){
47. //获得迷宫二维数组中上移后位置的属性（起点、终点、可走、障碍）
48. intnAttr=m_xLabyrinth[ptNext.row][ptNext.col];
49. //如果上移后位置为可走或到达终点，则设定返回值为上移后的位置
50. if(nAttr==CanGo||nAttr==Ending){
51. ptRes=ptNext;
52. returnptRes;//如果上移后位置不可走则返回非法的位置
53. //以下判断某一位置可否移动的原理大致与上相同，就不多说了
54. //判断某一位置是否可以向下移动
55. CPointcanDown(constCPoint&ptCurrent)
56. CPointptRes=CPoint(-1,-1);
57. intcol=ptCurrent.col;
58. introw=ptCurrent.row;
59. if(row<m_xLabyrinth.size()-1){
60. CPointptNext=CPoint(col,row+1);
61. intnAttr=m_xLabyrinth[ptNext.row][ptNext.col];
62. returnptRes;
63. //判断某一位置是否可以向左移动
64. CPointcanLeft(if(col>0){
65. CPointptNext=CPoint(col-1,row);
66. //判断某一位置是否可以向右移动
67. CPointcanRight(if(col<m_xLabyrinth[0].size()-1){
68. CPointptNext=CPoint(col+1,0); background-color:inherit">/*
69. *判断某一位置是否可以向四周移动，如果判断到某一位置可以移动，则递归进入该位置判断。
70. *如果该位置没有任何位置可移动，则返会上级位置并且调用back函数。如果走到终点，
71. *则立刻返回枚举值FoundEnding，上级位置检查到返回值为FoundEnding，也直接返回。
72. */
73. intfindRoute(intnRes=NotFoundEnding;//默认返回值为没有找到终点
74. CPointptNext=CPoint(-1,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> advance(ptCurrent);//将当前位置加入路线数组
75. //判断当前位置是否是终点，如果是终点则不进行下面的判断，将返回值设置为找到终点
76. if(isEnding(ptCurrent)){
77. nRes=FoundEnding;
78. }else{//按上左下右的顺序判断有无可走路径
79. //尝试向上
80. ptNext=canUp(ptCurrent);//获取向上走后的位置
81. //判断向上走后的位置是否是合法位置，若不合法，则表明上走到了迷宫的边缘，或者上面没有可走路径
82. if(ptNext.allRight()){
83. //上述判断成功，则将向上移动后的位置传入给自己，进行递归。当该函数退出，查看返回值是否为找到终点。若找到终点则立刻返回FoundEnding
84. if(findRoute(ptNext)==FoundEnding){
85. returnnRes;
86. //下列尝试四周位置是否可走的代码与上述大体相同，就不多说了
87. //尝试向左
88. ptNext=canLeft(ptCurrent);
89. if(findRoute(ptNext)==FoundEnding){
90. nRes=FoundEnding;
91. returnnRes;
92. //尝试向下
93. ptNext=canDown(ptCurrent);
94. //尝试向右
95. ptNext=canRight(ptCurrent);
96. //检测是否到达终点，若没有到达终点，则立刻从路线表中删除该位置
97. if(nRes!=FoundEnding){
98. back();
99. //构造函数
100. CLabyrinthAI()
101. return;
102. //带有初始化迷宫数组构造函数
103. CLabyrinthAI(constCLabyrinth&vLabyrinth)
104. m_xLabyrinth=vLabyrinth;
105. getBeginning();
106. getEnding();
107. //初始化迷宫数组
108. voidsetLabyrinth(//查找起点
109. voidgetBeginning()
110. uintnRow=0;
111. for(;nRow<m_xLabyrinth.size();nRow++){
112. CRowxRow=m_xLabyrinth[nRow];
113. uintnCol=0;
114. for(;nCol<xRow.size();nCol++){
115. intn=xRow[nCol];
116. if(n==Beginning){
117. m_ptBeginning=CPoint(nCol,nRow);
118. break;
119. //查找终点
120. voidgetEnding()
121. uintnRow=0;
122. for(;nRow<m_xLabyrinth.size();nRow++){
123. CRowxRow=m_xLabyrinth[nRow];
124. uintnCol=0;
125. for(;nCol<xRow.size();nCol++){
126. intn=xRow[nCol];
127. if(n==Ending){
128. m_ptEnding=CPoint(nCol,nRow);
129. //调用核心算法函数，输出获得的路线
130. voidAI()
131. findRoute(m_ptBeginning);
132. if(!m_vRoute.empty()){
133. CPointpt=*it;
134. std::cout<<"("<<pt.row<<","<<pt.col<<")";
135. if(it!=m_vRoute.end()-1){
136. std::cout<<"->";
137. else{
138. std::cout<<std::endl;
139. //如果没有找到路线到达终点
140. std::cout<<"Sorrycannotfileanywaystogetending."<<std::endl;
141. };

然后来到main函数

//用VC6.0貌似不需要给main传参数，那我就偷一下懒
1. intmain()
2. //定义迷宫数组，定义成C风格的二维数组方便查看
3. intvLabyrinthArray[][4]={
4. {1,-1,1}
5. ,{1,1}
6. };
7. //以下代码为将C风格的二维数组导入成C++风格的二维数组
8. intnRowNum=sizeof(vLabyrinthArray)/sizeof(vLabyrinthArray[0]);
9. intnColNum=sizeof(vLabyrinthArray[0])/sizeof(int);
10. CLabyrinthvLabyrinth;
11. for(introw=0;row<nRowNum;row++){
12. CRowxRow;
13. intcol=0;col<nColNum;col++){
14. intn=vLabyrinthArray[row][col];
15. xRow.push_back(n);
16. vLabyrinth.push_back(xRow);
17. //实例化CLabyrinthAI
18. CLabyrinthAIxAI(vLabyrinth);
19. //打出路线
20. xAI.AI();
21. //使程序暂停，方便查看数据
22. system("Pause");
23. return0;
24. }

以上代码同样加了注释，相信了解C++的同学都能看懂。

运行截图：

（Dos的，有点丑……）

三，Javascript版

顺便我也把C++版的移植到了Javascript上，代码如下：

functionCLabyrinthAI(){
1. vars= s.m_xLabyrinth=newArray(newArray());
2. s.m_ptBeginning={};
3. s.m_ptEnding={};
4. s.m_vRoute=newArray();
5. s.Beginning=-1;
6. s.Ending=-2;
7. s.CannotGo=0;
8. s.CanGo=1;
9. s.FoundEnding=0;
10. s.NotFoundEnding=1;
11. CLabyrinthAI.prototype.initAI=function(){
12. this;
13. s.getBeginning();
14. s.getEnding();
15. CLabyrinthAI.prototype.isRepeat=function(pt){
16. varbRes=false;
17. for(varn=0;n<s.m_vRoute.length;n++){
18. varpt0=s.m_vRoute[n];
19. if(pt0.col==pt.col&&pt0.row==pt.row){
20. CLabyrinthAI.prototype.advance=function(ptTo){
21. this.m_vRoute.push(ptTo);
22. CLabyrinthAI.prototype.back=this.m_vRoute.splice(this.m_vRoute.length-1,1);
23. CLabyrinthAI.prototype.isBeginning=if(this.m_ptBeginning.col==pt.col&&this.m_ptBeginning.row==pt.row){
24. return }else{
25. CLabyrinthAI.prototype.isEnding=function(pt){
26. this.m_ptEnding.col==pt.col&&this.m_ptEnding.row==pt.row){
27. true;
28. CLabyrinthAI.prototype.canUp=function(ptCurrent){
29. varptRes={col:-1,row:-1};
30. varcol=ptCurrent.col;
31. varrow=ptCurrent.row;
32. if(row>0){
33. varptNext={col:col,row:row-1};
34. if(!s.isRepeat(ptNext)){
35. varnAttr=s.m_xLabyrinth[ptNext.row][ptNext.col];
36. if(nAttr==s.CanGo||nAttr==s.Ending){
37. CLabyrinthAI.prototype.canDown=if(row<s.m_xLabyrinth.length-1){
38. CLabyrinthAI.prototype.canLeft=varptNext={col:col-1,row:row};
39. CLabyrinthAI.prototype.canRight=if(col<s.m_xLabyrinth[0].length-1){
40. varptNext={col:col+1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> CLabyrinthAI.prototype.allRight=function(p){
41. if(p.col>=0&&p.row>=0){
42. CLabyrinthAI.prototype.findRoute=function(ptCurrent){
43. varnRes=s.NotFoundEnding;
44. varptNext={col:-1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> s.advance(ptCurrent);
45. if(s.isEnding(ptCurrent)){
46. nRes=s.FoundEnding;
47. ptNext=s.canUp(ptCurrent);
48. if(s.allRight(ptNext)){
49. if(s.findRoute(ptNext)==s.FoundEnding){
50. nRes=s.FoundEnding;
51. ptNext=s.canLeft(ptCurrent);
52. ptNext=s.canDown(ptCurrent);
53. ptNext=s.canRight(ptCurrent);
54. if(nRes!=s.FoundEnding){
55. s.back();
56. CLabyrinthAI.prototype.getBeginning=varnRow=0;nRow<s.m_xLabyrinth.length;nRow++){
57. varxRow=s.m_xLabyrinth[nRow];
58. varnCol=0;nCol<xRow.length;nCol++){
59. varn=xRow[nCol];
60. if(n==s.Beginning){
61. s.m_ptBeginning={col:nCol,row:nRow};
62. CLabyrinthAI.prototype.getEnding=function(){
63. varnRow=0;nRow<s.m_xLabyrinth.length;nRow++){
64. varxRow=s.m_xLabyrinth[nRow];
65. varnCol=0;nCol<xRow.length;nCol++){
66. varn=xRow[nCol];
67. if(n==s.Ending){
68. s.m_ptEnding={col:nCol,row:nRow};
69. CLabyrinthAI.prototype.AI=function(data){
70. s.m_xLabyrinth=data;
71. s.initAI();
72. s.findRoute(s.m_ptBeginning);
73. returns.m_vRoute;
74. };

虽然这套算法是研究出来了，但是还不能判断是否为最近路线，因此有待更新。不过以现在的算法，开发一个SLG应该不是问题了。

※感谢我的哥哥与我一起讨论其中的原理。

源代码下载：

http://files.cnblogs.com/yorhom/findRoute.rar

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!