一,说在前面的话
大概在半年前,看见一到信息竞赛题:在任意方格阵中设置障碍物,确定起始点后,求这两点之间路径。当时觉得蛮有意思的,但是没有时间去做,今天花了两个小时来实现它。据说有一个更高级的寻路算法叫做a*, 那我就把我的算法叫做W*。
这个算法主要用于解迷宫和实现战棋游戏(SLG)的寻路。
首先讲一讲我的算法的思路:
我们先确定起始点,然后从起点出发,按一定顺序判断这个位置上下左右是否有可走的位置,如果发现有可走的位置,则递归进入该位置的判断。在递归的同时记录所走的路线。当发现某个位置无路可走,则删除路线的最后一个位置并返回上级位置进行判断。如此反复尝试最终找到路线。
说了这么多,就来讲解一下代码吧。
二,讲解部分
包含头文件(全部都是stl中的):
- #include <map>
- #include <vector>
- #include <iostream>
为几个冗长的类型重命名,用来使后来的代码更明了。
- typedef unsigned int uint;
- typedef std::vector<int> CRow;
-
- typedef std::vector<CRow> CLabyrinth;
定义一个类类型表示二维数组中的位置:
- class CPoint
- {
-
- public:
-
- int col;
- int row;
-
- public:
-
-
- CPoint(int c = 0, int r = 0)
- : col(c)
- , row(r)
- {
- return;
- }
-
-
- CPoint& operator=(const CPoint& pt)
- {
- col = pt.col;
- row = pt.row;
- return *this;
- }
-
-
- bool operator==(const CPoint& pt)
- {
- return col == pt.col && row == pt.row;
- }
-
-
- bool allRight()
- {
- return col >= 0 && row >= 0;
- }
-
- };
-
- typedef std::vector<CPoint> CRoute;
然后到了核心类类型CLabyrinthAI
- {
-
- protected:
-
-
- CLabyrinth m_xLabyrinth;
-
- CPoint m_ptBeginning;
-
- CPoint m_ptEnding;
-
- CRoute m_vRoute;
-
- public:
-
-
- enum{Beginning = -1, Ending = -2};
-
- enum{CanntGo = 0, CanGo = 1};
-
- enum{FoundEnding = 0, NotFoundEnding = 1};
-
- protected:
-
-
- bool isRepeat(const CPoint& pt)
- {
- bool bRes = false;
- CRoute::iterator it = m_vRoute.begin();
- for(; it != m_vRoute.end(); it++){
- CPoint pt0 = *it;
- if(pt0 == pt){
- bRes = true;
- break;
- }
- }
- return bRes;
- }
-
-
- void advance(const CPoint& ptTo)
- {
- m_vRoute.push_back(ptTo);
- }
-
-
- void back()
- {
- m_vRoute.pop_back();
- }
-
-
- bool isBeginning(const CPoint& pt)
- {
- return m_ptBeginning == pt;
- }
-
-
- bool isEnding(const CPoint& pt)
- {
- return m_ptEnding == pt;
- }
-
-
-
- CPoint canUp(const CPoint& ptCurrent)
- {
- CPoint ptRes = CPoint(-1, -1);
- int col = ptCurrent.col;
- int row = ptCurrent.row;
- if(row > 0){
- CPoint ptNext = CPoint(col, row - 1);
-
- if(!isRepeat(ptNext)){
-
- int nAttr = m_xLabyrinth[ptNext.row][ptNext.col];
-
- if(nAttr == CanGo || nAttr == Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- }
-
-
-
-
- CPoint canDown(const CPoint& ptCurrent)
- {
- CPoint ptRes = CPoint(-1, -1);
- int col = ptCurrent.col;
- int row = ptCurrent.row;
- if(row < m_xLabyrinth.size() - 1){
- CPoint ptNext = CPoint(col, row + 1);
- if(!isRepeat(ptNext)){
- int nAttr = m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == CanGo || nAttr == Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- }
-
-
- CPoint canLeft(const CPoint& ptCurrent)
- {
- CPoint ptRes = CPoint(-1, -1);
- int col = ptCurrent.col;
- int row = ptCurrent.row;
- if(col > 0){
- CPoint ptNext = CPoint(col - 1, row);
- if(!isRepeat(ptNext)){
- int nAttr = m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == CanGo || nAttr == Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- }
-
-
- CPoint canRight(const CPoint& ptCurrent)
- {
- CPoint ptRes = CPoint(-1, -1);
- int col = ptCurrent.col;
- int row = ptCurrent.row;
- if(col < m_xLabyrinth[0].size() - 1){
- CPoint ptNext = CPoint(col + 1, row);
- if(!isRepeat(ptNext)){
- int nAttr = m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == CanGo || nAttr == Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- }
-
-
-
-
-
-
- int findRoute(const CPoint& ptCurrent)
- {
- int nRes = NotFoundEnding;
- CPoint ptNext = CPoint(-1, -1);
-
- advance(ptCurrent);
-
-
- if(isEnding(ptCurrent)){
- nRes = FoundEnding;
- }else{
-
- ptNext = canUp(ptCurrent);
-
- if(ptNext.allRight()){
-
- if(findRoute(ptNext) == FoundEnding){
- nRes = FoundEnding;
- return nRes;
- }
- }
-
-
- ptNext = canLeft(ptCurrent);
- if(ptNext.allRight()){
- if(findRoute(ptNext) == FoundEnding){
- nRes = FoundEnding;
- return nRes;
- }
- }
-
- ptNext = canDown(ptCurrent);
- if(ptNext.allRight()){
- if(findRoute(ptNext) == FoundEnding){
- nRes = FoundEnding;
- return nRes;
- }
- }
-
- ptNext = canRight(ptCurrent);
- if(ptNext.allRight()){
- if(findRoute(ptNext) == FoundEnding){
- nRes = FoundEnding;
- return nRes;
- }
- }
- }
-
-
- if(nRes != FoundEnding){
- back();
- }
-
- return nRes;
- }
-
-
- public:
-
-
- CLabyrinthAI()
- {
- return;
- }
-
-
- CLabyrinthAI(const CLabyrinth& vLabyrinth)
- {
- m_xLabyrinth = vLabyrinth;
- getBeginning();
- getEnding();
- }
-
-
- void setLabyrinth(const CLabyrinth& vLabyrinth)
- {
- m_xLabyrinth = vLabyrinth;
- }
-
-
- void getBeginning()
- {
- uint nRow = 0;
- for(; nRow < m_xLabyrinth.size(); nRow++){
- CRow xRow = m_xLabyrinth[nRow];
- uint nCol = 0;
- for(; nCol < xRow.size(); nCol++){
- int n = xRow[nCol];
- if(n == Beginning){
- m_ptBeginning = CPoint(nCol, nRow);
- break;
- }
- }
- }
- }
-
-
- void getEnding()
- {
- uint nRow = 0;
- for(; nRow < m_xLabyrinth.size(); nRow++){
- CRow xRow = m_xLabyrinth[nRow];
- uint nCol = 0;
- for(; nCol < xRow.size(); nCol++){
- int n = xRow[nCol];
- if(n == Ending){
- m_ptEnding = CPoint(nCol, nRow);
- break;
- }
- }
- }
- }
-
-
- void AI()
- {
- findRoute(m_ptBeginning);
- if(!m_vRoute.empty()){
- CRoute::iterator it = m_vRoute.begin();
- for(; it != m_vRoute.end(); it++){
- CPoint pt = *it;
- std::cout << "(" << pt.row << ", " << pt.col << ")";
- if(it != m_vRoute.end() - 1){
- std::cout << "->";
- }else{
- std::cout << std::endl;
- }
- }
- }else{
-
- std::cout << "Sorry cannot file any ways to get ending." << std::endl;
- }
- }
-
- };
代码都加上了注释,大家可以慢慢看。
如果上述过程把你搅晕了,那就用图来为你解答吧。
然后来到main函数
-
- int main()
- {
-
- int vLabyrinthArray[][4] = {
- {1,0,-1,1}
- , {1,0,0,1}
- , {0,0,1,1}
- , {0,1,1,0}
- , {0,1,1,1}
- , {-2,1,0,0}
- };
-
-
- int nRowNum = sizeof(vLabyrinthArray) / sizeof(vLabyrinthArray[0]);
- int nColNum = sizeof(vLabyrinthArray[0]) / sizeof(int);
-
- CLabyrinth vLabyrinth;
- for(int row = 0; row < nRowNum; row++){
- CRow xRow;
- for(int col = 0; col < nColNum; col++){
- int n = vLabyrinthArray[row][col];
- xRow.push_back(n);
- }
- vLabyrinth.push_back(xRow);
- }
-
-
- CLabyrinthAI xAI(vLabyrinth);
-
- xAI.AI();
-
-
- system("Pause");
-
- return 0;
- }
以上代码同样加了注释,相信了解C++的同学都能看懂。
运行截图:
(Dos的,有点丑……)
三,Javascript版
顺便我也把C++版的移植到了Javascript上,代码如下:
- function CLabyrinthAI(){
- var s = this;
- s.m_xLabyrinth = new Array(new Array());
- s.m_ptBeginning = {};
- s.m_ptEnding = {};
- s.m_vRoute = new Array();
- s.Beginning = -1;
- s.Ending = -2;
- s.CannotGo = 0;
- s.CanGo = 1;
- s.FoundEnding = 0;
- s.NotFoundEnding = 1;
- }
- CLabyrinthAI.prototype.initAI = function(){
- var s = this;
- s.getBeginning();
- s.getEnding();
- }
- CLabyrinthAI.prototype.isRepeat = function(pt){
- var s = this;
- var bRes = false;
- for(var n = 0; n < s.m_vRoute.length; n++){
- var pt0 = s.m_vRoute[n];
- if(pt0.col == pt.col && pt0.row == pt.row){
- bRes = true;
- break;
- }
- }
- return bRes;
- };
- CLabyrinthAI.prototype.advance = function(ptTo){
- this.m_vRoute.push(ptTo);
- };
- CLabyrinthAI.prototype.back = function(){
- this.m_vRoute.splice(this.m_vRoute.length-1,1);
- };
- CLabyrinthAI.prototype.isBeginning = function(pt){
- if(this.m_ptBeginning.col == pt.col && this.m_ptBeginning.row == pt.row){
- return true;
- }else{
- return false;
- }
- };
- CLabyrinthAI.prototype.isEnding = function(pt){
- if(this.m_ptEnding.col == pt.col && this.m_ptEnding.row == pt.row){
- return true;
- }else{
- return false;
- }
- };
- CLabyrinthAI.prototype.canUp = function(ptCurrent){
- var s = this;
- var ptRes = {col:-1,row:-1};
- var col = ptCurrent.col;
- var row = ptCurrent.row;
- if(row > 0){
- var ptNext = {col:col,row:row - 1};
- if(!s.isRepeat(ptNext)){
- var nAttr = s.m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == s.CanGo || nAttr == s.Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- };
- CLabyrinthAI.prototype.canDown = function(ptCurrent){
- var s = this;
- var ptRes = {col:-1,row:-1};
- var col = ptCurrent.col;
- var row = ptCurrent.row;
- if(row < s.m_xLabyrinth.length - 1){
- var ptNext = {col:col,row:row + 1};
- if(!s.isRepeat(ptNext)){
- var nAttr = s.m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == s.CanGo || nAttr == s.Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- };
- CLabyrinthAI.prototype.canLeft = function(ptCurrent){
- var s = this;
- var ptRes = {col:-1,row:-1};
- var col = ptCurrent.col;
- var row = ptCurrent.row;
- if(col > 0){
- var ptNext = {col:col-1,row:row};
- if(!s.isRepeat(ptNext)){
- var nAttr = s.m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == s.CanGo || nAttr == s.Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- };
- CLabyrinthAI.prototype.canRight = function(ptCurrent){
- var s = this;
- var ptRes = {col:-1,row:-1};
- var col = ptCurrent.col;
- var row = ptCurrent.row;
- if(col < s.m_xLabyrinth[0].length - 1){
- var ptNext = {col:col+1,row:row};
- if(!s.isRepeat(ptNext)){
- var nAttr = s.m_xLabyrinth[ptNext.row][ptNext.col];
- if(nAttr == s.CanGo || nAttr == s.Ending){
- ptRes = ptNext;
- }
- }
- }
- return ptRes;
- };
- CLabyrinthAI.prototype.allRight = function(p){
- if(p.col >= 0 && p.row >= 0){
- return true;
- }else{
- return false;
- }
- };
- CLabyrinthAI.prototype.findRoute = function(ptCurrent){
- var s = this;
- var nRes = s.NotFoundEnding;
- var ptNext = {col:-1,row:-1};
-
- s.advance(ptCurrent);
-
- if(s.isEnding(ptCurrent)){
- nRes = s.FoundEnding;
- }else{
- ptNext = s.canUp(ptCurrent);
- if(s.allRight(ptNext)){
- if(s.findRoute(ptNext) == s.FoundEnding){
- nRes = s.FoundEnding;
- return nRes;
- }
- }
-
- ptNext = s.canLeft(ptCurrent);
- if(s.allRight(ptNext)){
- if(s.findRoute(ptNext) == s.FoundEnding){
- nRes = s.FoundEnding;
- return nRes;
- }
- }
-
- ptNext = s.canDown(ptCurrent);
- if(s.allRight(ptNext)){
- if(s.findRoute(ptNext) == s.FoundEnding){
- nRes = s.FoundEnding;
- return nRes;
- }
- }
-
- ptNext = s.canRight(ptCurrent);
- if(s.allRight(ptNext)){
- if(s.findRoute(ptNext) == s.FoundEnding){
- nRes = s.FoundEnding;
- return nRes;
- }
- }
- }
- if(nRes != s.FoundEnding){
- s.back();
- }
-
- return nRes;
- };
- CLabyrinthAI.prototype.getBeginning = function(){
- var s = this;
- for(var nRow = 0; nRow < s.m_xLabyrinth.length; nRow++){
- var xRow = s.m_xLabyrinth[nRow];
- for(var nCol = 0; nCol < xRow.length; nCol++){
- var n = xRow[nCol];
- if(n == s.Beginning){
- s.m_ptBeginning = {col:nCol,row:nRow};
- break;
- }
- }
- }
- };
- CLabyrinthAI.prototype.getEnding = function(){
- var s = this;
- for(var nRow = 0; nRow < s.m_xLabyrinth.length; nRow++){
- var xRow = s.m_xLabyrinth[nRow];
- for(var nCol = 0; nCol < xRow.length; nCol++){
- var n = xRow[nCol];
- if(n == s.Ending){
- s.m_ptEnding = {col:nCol,row:nRow};
- break;
- }
- }
- }
- };
- CLabyrinthAI.prototype.AI = function(data){
- var s = this;
- s.m_xLabyrinth = data;
- s.initAI();
- s.findRoute(s.m_ptBeginning);
- return s.m_vRoute;
- };
设计原理和C++版差不多,只是没有CPoint类而已。
虽然这套算法是研究出来了,但是还不能判断是否为最近路线,因此有待更新。不过以现在的算法,开发一个SLG应该不是问题了。
※感谢我的哥哥与我一起讨论其中的原理。
源代码下载: