pushboxai.cpp

基于CGX库的推箱子游戏. CGX库源码已在之前上传了.

#include "StdAfx.h"
#include "PushBoxAI.h"

void CPushBoxAI::Init(struct _PushStatus& status)
{
 /* 写死的一个地图，实际应用中应替换成从文件中读入。略。 */
 char *map = {
  "    XXXXX"
  "    X  *X"
  "XXX XOO X"
  "X?X X O X"
  "X?XXX XX "
  "X?    XX "
  "X  X   XX"
  "XXXX   XX"
  "   XXXXX "
 };
 char *p = map;
 m_nHeight = 9;
 m_nWidth = 9;
 m_nBoxCount = 0;
 for ( int j = 0; j < 9; j++ )
  for ( int i = 0; i < 9; i++, p++ )
  {
   switch(*p)
   {
   case ' ': m_Map[i][j] = MAP_EMPTY; break;
   case 'X': m_Map[i][j] = MAP_BLOCK; break;
   case '?': m_Map[i][j] = MAP_HOLE; break;
   case '*': status.x = i; status.y = j; m_Map[i][j] = MAP_EMPTY; break;
   default: // O
    status.boxx[m_nBoxCount] = i;
    status.boxy[m_nBoxCount] = j;
    m_Map[i][j] = MAP_EMPTY;
    m_nBoxCount++;
    break;
   }
  }
}

TryResult CPushBoxAI::TryDir(_PushStatus status, int level, int dx, int dy)
{
 int x = status.x + dx;
 int y = status.y + dy;
 /* 超出地图范围？失败 */
 if ( x < 0 || x >= m_nWidth || y < 0 || y >= m_nHeight ) return trFailed;
 /* 碰到阻挡？失败 */
 if ( m_Map[x][y] == MAP_BLOCK ) return trFailed;
 int nLeft = m_nBoxCount;
 status.x = x;
 status.y = y;
 for ( int i = 0; i < m_nBoxCount; i++ )
 {
  if ( x == status.boxx[i] && y == status.boxy[i] )
  {
   // 碰到了箱子。尝试推动它
   int m = status.boxx[i] + dx;
   int n = status.boxy[i] + dy;
   // 尝试推动箱子出地图？失败
   if ( m < 0 || m >= m_nWidth || n < 0 || n >= m_nHeight ) return trFailed;
   // 箱子碰到阻挡？失败
   if ( m_Map[m][n] == MAP_BLOCK ) return trFailed;
   // 箱子碰到其它箱子？失败
   for ( int j = 0; j < m_nBoxCount; j++ )
    if ( j != i && m == status.boxx[j] && n == status.boxy[j] )
     return trFailed;// crash
   status.boxx[i] = m;
   status.boxy[i] = n;
  }
  // 箱子到达目的地？
  if ( m_Map[status.boxx[i]][status.boxy[i]] == MAP_HOLE ) nLeft--;
 }
 /* 超出现有最短步数？失败 */
 if (level >= m_nMinSteps) return trUnknown;

 // 当前状态如果已经失败或者已经访问，则此步也失败
 if (GetStatus(status) != nsNone) return trFailed;
 // 记录当前路径
 if ( (int)m_vStepLog.size() == level ) m_vStepLog.push_back(status);
 else if ( (int)m_vStepLog.size() > level ) m_vStepLog[level] = status;
 // 所有箱子都到达了目的地
 if (nLeft == 0)
 {
  m_nMinSteps = level;
  // 将当前路径拷贝到成功路径中，并且更新最小步数变量
  m_vSuccLog.clear();
  std::insert_iterator< std::vector<struct _PushStatus> > iter( m_vSuccLog, m_vSuccLog.end() );
  copy( m_vStepLog.begin(), m_vStepLog.end(), iter );
  // 返回成功
  return trSuccess; // success
 }
 // 设置当前状态为正在访问，并且访问下面的状态
 SetStatus(status, nsVisiting);
 int n = 0;
 enum TryResult tr;
 bool bSucc = false;
 tr = TryDir(status, level + 1, -1, 0);
 if ( tr != trFailed ) n++;
 if ( tr == trSuccess ) bSucc = true;
 tr = TryDir(status, level + 1, 1, 0);
 if ( tr != trFailed ) n++;
 if ( tr == trSuccess ) bSucc = true;
 tr = TryDir(status, level + 1, 0, -1);
 if ( tr != trFailed ) n++;
 if ( tr == trSuccess ) bSucc = true;
 tr = TryDir(status, level + 1, 0, 1);
 if ( tr != trFailed ) n++;
 if ( tr == trSuccess ) bSucc = true;
 // 如果后续状态都无法访问或不成功，则当前状态也死亡。否则恢复当前状态为未访问。
 if ( n == 0 ) SetStatus(status, nsDead);
 else SetStatus(status, nsNone);
 if ( bSucc ) return trSuccess;
 else if ( n > 0 ) return trUnknown;
 else return trFailed;
}

bool CPushBoxAI::Execute(void)
{
 m_nMinSteps = 1000;
 int n = 0; 
 struct _PushStatus status;
 // 一定要初始化为全0
 memset(&status, 0, sizeof(struct _PushStatus));
 // 初始化地图和开始时的状态
 Init(status);
 // 开始访问相邻四个方向
 if ( TryDir(status, 0, -1, 0) == trSuccess ) n++;
 if ( TryDir(status, 0, 1, 0) == trSuccess ) n++;
 if ( TryDir(status, 0, 0, -1) == trSuccess ) n++;
 if ( TryDir(status, 0, 0, 1) == trSuccess ) n++;
 return n > 0;
}

void CPushBoxAI::DumpMaze(struct _PushStatus status)
{
 for ( int j = 0; j < m_nHeight; j++ )
 {
  for ( int i = 0; i < m_nWidth; i++ )
  {
   char c = m_Map[i][j];
   for ( int k = 0; k < m_nBoxCount; k++ )
    if ( i == status.boxx[k] && j == status.boxy[k] )
    {
     c = 'O';
     break;
    }
   if ( i == status.x && j == status.y ) c = '*';
   printf("%c", c);
  }
  printf("\n");
 }
}