person.cpp

回溯法实现的走迷宫方法

#include "stdafx.h"
#include "person.h"

CPerson::CPerson(const vector< vector<MYPOINT> > &map)
{
	m_Map = map;
	m_x = 1;
	m_y = 1;
}

void CPerson::ReStart(const vector< vector<MYPOINT> > &map)
{
	m_Map = map;
	m_x = 1;
	m_y = 1;
}

int CPerson::SearchDir()
{
	if (0 == m_x && 1 == m_y ) return -1;

	//go forward
	while ( m_Map[m_y][m_x].dir < 4 )
	{
		switch ( m_Map[m_y][m_x].dir )
		{
		case 0://up
			if ( m_Map[m_y-1][m_x].access && -1 == m_Map[m_y-1][m_x].LastDir &&
				 m_Map[m_y][m_x].LastDir != 2 ) 
			{
				m_Map[m_y][m_x].dir++;	
				m_y--;
				m_Map[m_y][m_x].LastDir = 0;
                return 0;
			}
			m_Map[m_y][m_x].dir++;	
			break;
		case 1://right
			if ( m_Map[m_y][m_x+1].access && -1 == m_Map[m_y][m_x+1].LastDir &&
				 m_Map[m_y][m_x].LastDir != 3 ) 
			{
				m_Map[m_y][m_x].dir++;
				m_x++;
				m_Map[m_y][m_x].LastDir=1;			
				return 1;
			}
			m_Map[m_y][m_x].dir++;				
			break;
		case 2://down
			if ( m_Map[m_y+1][m_x].access && m_Map[m_y+1][m_x].LastDir == -1 &&
				 m_Map[m_y][m_x].LastDir != 0 ) 
			{
				m_Map[m_y][m_x].dir++;
				m_y++;
				m_Map[m_y][m_x].LastDir=2;
				return 2;
			}
			m_Map[m_y][m_x].dir++;
			break;
		case 3://left
			if ( m_Map[m_y][m_x-1].access && m_Map[m_y][m_x-1].LastDir == -1 &&
				 m_Map[m_y][m_x].LastDir != 1 ) 
			{
				m_Map[m_y][m_x].dir++;
				m_x--;
				m_Map[m_y][m_x].LastDir=3;
				return 3;
			}
			m_Map[m_y][m_x].dir++;
   			break;
		}
	}

	//go back
	int dir;
	m_Map[m_y][m_x].access = 0;
	switch ( m_Map[m_y][m_x].LastDir )
	{
	case 0:
	    dir = 2;
		m_y++;
		break;
	case 1:
		dir = 3;
		m_x--;
		break;
	case 2:
		dir = 0;
		m_y --;
		break;
	case 3:
		dir = 1;
		m_x ++;
		break;
	}
	return dir;
}

//create a maze map
void  CreateMap(vector< vector<MYPOINT> > &map)
{
      for(int i=0;i<map.size();++i)
		  for(int j=0;j<map[0].size();++j)
		  {
			map[i][j].access = 0;
			map[i][j].dir    = 0;
			map[i][j].LastDir= -1; 
		  }
		  for(i=1;i<map.size()-1;++i)
		  for(int j=1;j<map[0].size()-1;++j)
		  {
			// probability 1/2,this point is access
			int acc = rand() % 2;
			if ( acc ) map[i][j].access = 1;
			else map[i][j].access = 0;
		  }

		map[1][1].LastDir = -1;map[1][0].access = 1;
	    for(i=1;i<map[0].size()-40;++i) map[1][i].access = 1;
		for(i=1;i<=6;++i) map[i][map[0].size()-41].access = 1;
		for(i=map[0].size()-41;i<map[0].size()-30;++i) map[6][i].access = 1;
		for(i=7;i<map.size()-10;++i) map[i][map[0].size()-31].access = 1;
		for(i=map[0].size()-31;i<map[0].size()-1;++i) map[map.size()-11][i].access = 1;
		for(i=map.size()-11;i<map.size()-1;++i) map[i][map[0].size()-2].access = 1;

	  // probability 1/3 ,have a access
      int acc = rand()%3;
      bool find = false ;
	  if ( acc ) find = true;
      if ( !find ) map[map.size()-2][map[0].size()-2].access = 0; 
}