开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 查看源码
microbeWay.h
资源名称：Visual_C++GameDevelop.rar　[点击查看]
上传用户：sycq158
上传日期：2008-10-22
资源大小：15361k
文件大小：16k
源码类别：

游戏

开发平台：

Visual C++

microbeWay.h：源码内容
  1. // Copyright: 胡小民，丁展 2002.5
  3. #include "stdio.h"
  4. #include "stdlib.h"
  5. #include "iostream.h"
  6. #include "maze.h"
  7. #include "mazeMake.h"
  8. /*
  9. const int MAX_MStack_SIZE=1000;
  12. const int SIZEX_MAZE=15;
  13. const int SIZEY_MAZE=15;
  15. const int EXIT_ROW=SIZEX_MAZE-2;
  16. const int EXIT_COL=SIZEY_MAZE-2;
  18. const int MAX_ANT_NUM=4;
  21. int maze[SIZEX_MAZE][SIZEY_MAZE];
  22. bool mark[SIZEX_MAZE][SIZEY_MAZE]; // record that some path is not accessable
  23. int pos[SIZEX_MAZE][SIZEY_MAZE]; // record all objects position at the same time
  25. // tell others that this path cannot be accessed in fact it describe the new maze
  27. bool found=false;
  28. int step=0;
  29. */
  30. //class element;
  31. class MStack;
  32. //class offsets;
  34. //int Max(int x,int y ,int z,int w);
  35. //void GenerateMaze();
  36. long  MSearchPath(MStack& _MStack);
  37. void MInitMark();
  38. //void ShowMaze();
  39. //void SimpleMaze();
  40. void MAllocate(MStack _MStackarray[],int n);
  41. void MInitAll();
  42. int MMin(int x,int y ,int z,int w);
  43. /*
  44. bool Square1(int i,int j)
  45. {
  46. if(maze[i-1][j]&&maze[i][j-1]&&maze[i-1][j-1])
  47. return true;
  48. return false;
  49. }
  50. bool Square0(int i,int j)
  51. {
  52. if(!maze[i-1][j]&&!maze[i][j-1]&&!maze[i-1][j-1])
  53. return true;
  54. return false;
  55. }
  56. //----------------------------//
  57. class element
  58. {
  59. public:
  60. int row;
  61. int col;
  62. int dir;
  63. };*/
  64. /*
  65. bool EqualElement(const element a,const element b)
  66. {
  67. if(a.col==b.col&&a.row==b.row)
  68. return true;
  69. else
  70. return false;
  71. }*/
  72. /*
  73. class offsets
  74. {
  75. public:
  76. int vert;
  77. int horiz;
  78. public:
  79. void GetValue(int vert=0,int horiz=0)
  80. {
  81. this->vert=vert;
  82. this->horiz=horiz;
  83. }
  84. };*/
  85. //---------------------------//
  86. //offsets move[4];
  88. class MStack
  89. {
  90. private:
  91. int top;
  92. element error;
  93. int count;
  94. public:
  95. element stack[MAX_STACK_SIZE];
  96. public:
  97. bool classmark[CONST_MAZEX][CONST_MAZEY];
  98. int method; // method是对走法的处理，顺时针，逆时针等等
  99. public:
  100. MStack():top(-1)
  101. {
  102. MMinitMark();
  103. }
  104. void NewAntsCame()
  105. {
  106. MMinitMark();
  107. classmark[1][1]=true;
  108. AddMStack(1,1,1);
  109. row=1;
  110. col=1;
  111. dir=1;
  112. next_row=0;
  113. next_col=0;
  114. dir=0;
  115. count=0;
  116. pos[1][1]++;
  117. //------------------
  118. count++;
  119. position=DeleteMStack();
  120. row=position.row;
  121. col=position.col;
  122. dir=position.dir;
  124. }
  125. void SetDir(int dir)
  126. {
  127. this->dir=dir;
  128. }
  129. void MStackEmpty()
  130. {
  131. top=-1;
  133. }
  134. element DeleteMStack()
  135. {
  136. if(top==-1)
  137. return error;
  138. else
  139. return stack[top--];
  140. }
  141. bool AddMStack(const element & pa)
  142. {
  143. if(top==MAX_STACK_SIZE-1)
  144. return false;
  145. else
  146. {
  147. stack[++top]=pa;
  148. return true;
  149. }
  150. }
  152. bool AddMStack(int row,int col,int dir)
  153. {
  154. if(top==MAX_STACK_SIZE-1)
  155. return false;
  156. else
  157. {
  158. top++;
  159. stack[top].row=row;
  160. stack[top].col=col;
  161. stack[top].dir=dir;
  162. return true;
  163. }
  164. }
  165. bool Empty()
  166. {
  167. if(top==-1)
  168. return true;
  169. else
  170. return false;
  171. }
  172. void MMinitMark();
  173. //
  174. private:
  175. int row,col,next_row,next_col,dir;
  176. element position;
  177. public:
  178. int MSearchPathStepByStep();
  179. bool TestDir(int dir);
  180. bool TestDirection(int dir);
  181. int GetLength()
  182. {
  183. return top;
  184. }
  185. element GetCurrentPosition()
  186. {
  187. element temp;
  188. temp.row=row;
  189. temp.col=col;
  190. temp.dir=0  ; // temp.dir=dir;
  191. return temp;
  192. }
  193. element GetLastPosition()
  194. {
  195. element temp;
  196. temp.row=next_row;
  197. temp.col=next_col;
  198. temp.dir=0;
  199. return temp;
  200. }
  201. ~MStack()
  202. {}
  204. };
  205. //--------------independent-------------------//
  206. void MStack::MMinitMark()
  207. {
  209. int i,j;
  210. for(i=0;i<SIZEX_MAZE;i++)
  211. for(j=0;j<SIZEY_MAZE;j++)
  212. {
  213. if(maze[i][j]==1)
  214. classmark[i][j]=true;
  215. else
  216. classmark[i][j]=false;
  217. }
  218. }
  220. bool MStack::TestDir(int dir)
  221. {
  222. this->dir=dir;
  223. if(this->dir<0||this->dir>3)
  224. return false;
  225. next_row=row+move[dir].vert;
  226. next_col=col+move[dir].horiz;
  227. if(next_row==EXIT_ROW&&next_col==EXIT_COL)
  228. {
  229. found=true;
  230. ::pos[next_row][next_col]++;
  231. ::pos[row][col]--;
  233. position.row=row;
  234. position.col=col;
  235. position.dir=--dir;
  236. AddMStack(position);
  237. row=next_row;
  238. col=next_col;
  239. dir=3;
  240. AddMStack(row,col,dir);
  241. count++;
  242. return true;
  243. }
  244. else
  245. //   墙 在栈里
  246. if(!maze[next_row][next_col]&&!classmark[next_row][next_col])
  247. {
  248. classmark[next_row][next_col]=true;
  249. ::pos[row][col]--;
  250. ::pos[next_row][next_col]++;
  251. position.row=row;
  252. position.col=col;
  253. position.dir=++this->dir;
  254. AddMStack(position);
  255. row=next_row;
  256. col=next_col;
  257. this->dir=0;
  258. count++;
  259. return true;
  260. }
  262. return false;
  263. }
  265. bool MStack::TestDirection(int dir)
  266. {
  267. this->dir=dir;
  268. if(this->dir<0||this->dir>3)
  269. return false;
  270. int num=0;
  271. while(num<4)
  272. {
  273. this->dir=this->dir%4;
  274. next_row=row+move[this->dir].vert;
  275. next_col=col+move[this->dir].horiz;
  276. if(next_row==EXIT_ROW&&next_col==EXIT_COL)
  277. {
  278. found=true;
  279. classmark[next_row][next_col]=true;
  280. ::pos[next_row][next_col]++;
  281. ::pos[row][col]--;
  283. position.row=row;
  284. position.col=col;
  285. position.dir=--dir;
  286. AddMStack(position);
  287. row=next_row;
  288. col=next_col;
  289. dir=3;
  290. AddMStack(row,col,dir);
  291. count++;
  292. return true;
  293. }
  294. else
  295. if(!maze[next_row][next_col]&&!classmark[next_row][next_col])
  296. {
  297. classmark[next_row][next_col]=true;
  298. ::pos[row][col]--;
  299. ::pos[next_row][next_col]++;
  300. position.row=row;
  301. position.col=col;
  302. position.dir=++this->dir;
  303. AddMStack(position);
  304. row=next_row;
  305. col=next_col;
  306. this->dir=0;
  307. count++;
  308. return true;
  309. }
  310. else
  311. {
  312. ++this->dir;
  313. num++;
  314. if(num==4)
  315. {
  316. count++;
  317. ::pos[row][col]--;
  318. position=DeleteMStack();
  319. row=position.row;
  320. col=position.col;
  321. this->dir=position.dir;
  322. ::pos[row][col]++;
  323. return false;
  324. }
  325. }
  326. }
  328. return false;
  329. }
  331. int MStack::MSearchPathStepByStep()
  332. {
  334. while(dir<4&&!found)
  335. {
  336. next_row=row+move[dir].vert;
  337. next_col=col+move[dir].horiz;
  338. if(next_row==EXIT_ROW&&next_col==EXIT_COL)
  339. {
  340. found=true;
  341. classmark[next_row][next_col]=true;
  342. ::pos[next_row][next_col]++;
  343. ::pos[row][col]--;
  345. position.row=row;
  346. position.col=col;
  347. position.dir=--dir;
  348. AddMStack(position);
  349. row=next_row;
  350. col=next_col;
  351. dir=0;
  352. AddMStack(row,col,dir);
  353. count++;
  355. }
  356. else
  357. {
  358. if(!maze[next_row][next_col]&&!classmark[next_row][next_col]&&!mark[next_row][next_col])
  359. {
  360. classmark[next_row][next_col]=true;
  361. ::pos[row][col]--;
  362. ::pos[next_row][next_col]++;
  364. position.row=row;
  365. position.col=col;
  366. position.dir=++dir;
  367. AddMStack(position);
  368. row=next_row;
  369. col=next_col;
  370. dir=0;
  371. count++;
  372. return 0;
  373. }
  374. else
  375. {
  376. ++dir;
  377. if(dir==4)
  378. {
  379. if(!Empty()&&!found)
  380. {
  381. count++;
  382. ::pos[row][col]--;
  383. position=DeleteMStack();
  384. row=position.row;
  385. col=position.col;
  386. dir=position.dir;
  387. ::pos[row][col]++;
  388. return 0;
  389. }
  390. else
  391. return -1;
  392. }
  393. }
  394. }
  395. }
  397. if(found)
  398. {
  399. return count;
  400. }
  401. else
  402. {
  403. return 0;
  404. }
  406. }
  407. /*
  408. void SimpleMaze()
  409. {
  410. int i=1,j=1;
  411. maze[i][j]=0;
  412. int k;
  413. while(i!=EXIT_ROW||j!=EXIT_COL)
  414. {
  415. if(i==EXIT_ROW)
  416. {
  417. while(j!=EXIT_COL)
  418. maze[i][++j]=0;
  419. break;
  420. }
  421. if(j==EXIT_COL)
  422. {
  423. while(i!=EXIT_ROW)
  424. maze[++i][j]=0;
  425. break;
  426. }
  427. k=rand()%2;
  428. if(k==0)
  429. {
  430. i++;
  431. maze[i][j]=0;
  432. continue;
  433. }
  434. if(k==1)
  435. {
  436. j++;
  437. maze[i][j]=0;
  438. continue;
  439. }
  440. }
  442. }
  443. void GenerateMaze()
  444. {
  445. int i,j;
  446. int i1,j1;
  447. for(i=0;i<SIZEX_MAZE;i++)
  448. for(j=0;j<SIZEY_MAZE;j++)
  449. maze[i][j]=1;
  450. SimpleMaze();
  451. for(i=2;i<SIZEX_MAZE-2;i++)
  452. for(j=2;j<SIZEY_MAZE-2;j++)
  453. {
  454. if(Square1(i,j))
  455. {
  456. i1=i-rand()%2;
  457. j1=j-rand()%2;
  458. maze[i1][j1]=0;
  459. }
  460. }
  462. MStack _MStack;
  463. if(MSearchPath(_MStack)==0)
  464. {
  465.    SimpleMaze();
  466. }
  468. }
  469. void ShowMaze()
  470. {
  471. int i=0,j=0;
  472. for(i=1;i<SIZEX_MAZE-1;i++)
  473. {
  474. for(j=1;j<SIZEY_MAZE-1;j++)
  475. cout<<maze[i][j]<<" ";
  476. cout<<endl;   
  477. }
  479. }*/
  480. void MInitMark()
  481. {
  482. int i,j;
  483. for(i=0;i<SIZEX_MAZE;i++)
  484. for(j=0;j<SIZEY_MAZE;j++)
  485. {
  486. mark[i][j]=false;
  487. pos[i][j]=0;
  488. }
  489. move[0].GetValue(-1,0);
  490. move[1].GetValue(0,1);
  491. move[2].GetValue(1,0);
  492. move[3].GetValue(0,-1);
  493. }
  495. long MSearchPath(MStack & _MStack)
  496. {
  497. int row,col,next_row,next_col,dir;
  498. long count=0;
  499. bool found=false;
  500. element position;
  501. MInitMark();
  502. mark[1][1]=true;
  503. _MStack.AddMStack(1,1,1);
  504. while(!_MStack.Empty()&&!found)
  505. {
  506. position=_MStack.DeleteMStack();
  507. row=position.row;
  508. col=position.col;
  509. dir=position.dir;
  510. while(dir<4&&!found)
  511. {
  513. next_row=row+move[dir].vert;
  514. next_col=col+move[dir].horiz;
  515. if(next_row==EXIT_ROW&&next_col==EXIT_COL)
  516. found=true;
  517. else
  518. if(!maze[next_row][next_col]&&!mark[next_row][next_col])
  519. {
  520. mark[next_row][next_col]=1;
  521. position.row=row;
  522. position.col=col;
  523. position.dir=++dir;
  524. _MStack.AddMStack(position);
  525. row=next_row;
  526. col=next_col;
  527. dir=0;
  528. count++;
  530. }
  531. else
  532. ++dir;
  533. }
  534. }
  535. if(found)
  536. {
  537. return count;
  538. }
  539. else
  540. return 0;
  541. }
  544. void MInitAll()
  545. {
  546. GenerateMaze();
  547. MInitMark();
  548. }
  550. int MMin(int x,int y ,int z,int w)
  551. {
  552. int m=x*y*z*w;
  553. int count;
  554. if(m==0)
  555. {
  556. count=0;
  557. if(x==0)
  558. count+=1;
  559. if(y==0)
  560. count+=2;
  561. if(z==0)
  562. count+=4;
  563. if(w==0)
  564. count+=8;
  565. return count;
  566. }
  567. return 0;
  568. }
  570. void MAllocate(MStack _MStackarray[],int n)
  571. {
  572. int x,y;
  573. int count=0;
  574. int i=0;
  575. int dir=0;
  576. element position;
  577. int turn=0;
  578. // int length=0;
  579. int countnum=0;
  580. bool once=true;
  582. int pos[CONST_MAZEX][CONST_MAZEY]; // record all objects position at the same time
  583. MStack newMStack[CONST_ANT_NUM];
  586. ::step++;
  587. for(i=0;i<n;i++)
  588. newMStack[i]=_MStackarray[i];
  590. for(i=0;i<SIZEX_MAZE;i++)
  591. for(int j=0;j<SIZEY_MAZE;j++)
  592. {
  593. pos[i][j]=::pos[i][j];
  594. }
  597. for(x=1;x<SIZEX_MAZE-1;x++)
  598. for(y=1;y<SIZEY_MAZE-1;y++)
  599. {
  600. if(pos[x][y]<=0)
  601. continue;
  602. else
  603. {
  604. position.row=x;
  605. position.col=y;
  606. position.dir=1;
  608. count=MMin(maze[x-1][y],maze[x+1][y],maze[x][y-1],maze[x][y+1]);
  610. switch(count)
  611. {
  612. case 0: cout<<"false "<<endl;break;
  613. case 1:
  614. case 2:
  615. case 4:
  616. case 8:
  617. {
  618. for(i=0;i<n;i++)
  619. {
  620. if(EqualElement(_MStackarray[i].GetCurrentPosition(),position))
  621. {
  622. if(count==1)
  623. dir=0;   //all go to (x-1,y)
  624. else if(count==2)
  625. dir=2; // all go to(x+1,y)
  626. else if(count==4)
  627. dir=3; // all to to (x,y-1)
  628. else if(count==8)
  629. dir=1; // all go to (x,y+1)
  630. // newMStack[i].SetDir(dir);
  631. newMStack[i].TestDirection(dir);
  632. // //if((++countnum)==n) return;
  633. }
  634. }
  635. break;
  636. }
  637. case 3:
  638. case 5:
  639. case 6:
  640. {
  641. turn=0;
  642. for(i=0;i<n;i++)
  643. {
  644. if(EqualElement(_MStackarray[i].GetCurrentPosition(),position))
  645. {
  646. if(turn==0)
  647. {
  648. if(count== 3 || count ==5)
  649. dir=0;
  650. else if(count==6) // all go to (x+1,y) and (x,y-1)
  651. dir=2;
  652. newMStack[i].TestDirection(dir);
  653. turn=1;
  654. }
  655. else
  656. {
  657. if(count==3)
  658. dir=2; // all to (x-1,y) and (x+1,y)
  659. else if(count==5 || count==6)
  660. dir=3; // all go to (x-1,y) and (x,y-1)
  661. newMStack[i].TestDirection(dir);
  662. turn=0;
  663. }
  664. }
  665. }
  666. break;
  667. }
  668. case 7:
  669. case 11:
  670. case 13:
  671. case 14:
  672. {
  673. // 7: all go to (x-1,y) and (x+1,y) and (x,y-1)
  674. // 11:  all go to (x-1,y) and (x+1,y) and (x,y+1)
  675. // 13: all go to (x-1,y) and (x,y-1) and (x,y+1)
  676. // 14: all go to (x+1,y) and (x,y-1) and (x,y+1)
  677. turn=0;
  678. for(i=0;i<n;i++)
  679. {
  680. if(EqualElement(_MStackarray[i].GetCurrentPosition(),position))
  681. {
  682. switch(turn)
  683. {
  684. case 0:
  685. if(count==7 || count ==11 || count==13)
  686. dir=0;
  687. else
  688. dir=2;
  689. newMStack[i].TestDirection(dir);
  690. turn=1;
  691. break;
  692. case 1:
  693. if(count==7 || count==11)
  694. dir=2;
  695. else 
  696. dir=3;
  697. newMStack[i].TestDirection(dir);
  698. turn=2;
  699. break;
  700. case 2:
  701. if(count==7)
  702. dir=3;
  703. else
  704. dir=1;
  705. newMStack[i].TestDirection(dir);
  706. turn=0;
  707. break;
  708. }
  709. }
  710. }
  711. break;
  712. }
  714. case 9: // all go to (x-1,y) and (x,y+1)
  715. case 10: // all go to (x+1,y) and (x,y+1)
  716. case 12: // all go to (x,y-1) and (x,y+1)
  717. {
  718. turn=0;
  719. for(i=0;i<n;i++)
  720. {
  721. if(EqualElement(_MStackarray[i].GetCurrentPosition(),position))
  722. {
  723. switch(turn)
  724. {
  725. case 0:
  726. if(count==9)
  727. dir=0;
  728. else if(count==10)
  729. dir=2;
  730. else if(count==12)
  731. dir=3;
  732. newMStack[i].TestDirection(dir);
  733. turn=1;
  734. break;
  735. case 1:
  736. dir=1;
  737. newMStack[i].TestDirection(dir);
  738. turn=0;
  739. break;
  740. }
  741. }
  742. }
  743. break;
  744. }
  745. case 15:
  746. {
  747. turn=0;
  748. for(i=0;i<n;i++)
  749. {
  750. if(EqualElement(_MStackarray[i].GetCurrentPosition(),position))
  751. {
  752. switch(turn)
  753. {
  754. case 0:
  755. dir=0;
  756. newMStack[i].TestDirection(dir);
  757. turn=1;
  758. break;
  759. case 1:
  760. dir=1;
  761. newMStack[i].TestDirection(dir);
  762. turn=2;
  763. break;
  764. case 2:
  765. dir=2;
  766. newMStack[i].TestDirection(dir);
  767. turn=3;
  768. break;
  769. case 3:
  770. dir=3;
  771. newMStack[i].TestDirection(dir);
  772. turn=3;
  773. break;
  774. }
  775. }
  776. }
  777. break;
  778. }
  779. default:
  780. break;
  782. }
  783. }
  784. }
  785. for(i=0;i<n;i++)
  786. _MStackarray[i]=newMStack[i];
  788. }
  790. /*
  791. void main()
  792. {
  793. MMinitAll();
  794. ShowMaze();
  795. int i;
  797. cout<<endl<<" this is the final result "<<endl;
  798. //-----------------final test--------------------------------------//
  799. MMinitMark();
  800. MStack _MStackarray[MAX_ANT_NUM];
  802. for(i=0;i<MAX_ANT_NUM;i++)
  803. _MStackarray[i].NewAntsCame ();
  804. found=false;
  805. int tag=0;
  806. element position;
  807. bool x; 
  808. element temp;
  809. int j;
  810. while(1)
  811. {
  812. MAllocate(_MStackarray,MAX_ANT_NUM);
  813. for(i=0;i<MAX_ANT_NUM;i++)
  814. {
  815. for(j=0;j<_MStackarray[i].GetLength();j++)
  816. {
  817. temp=_MStackarray[i].MStack[j];
  818. }
  819. }
  820. cout<<endl;
  821. for(i=1;i<SIZEX_MAZE-1;i++)
  822. {
  823. for(j=1;j<SIZEY_MAZE-1;j++)
  824. cout<<pos[i][j]<<"  ";
  825. cout<<"      ";
  826. for(j=1;j<SIZEY_MAZE-1;j++)
  827. cout<<maze[i][j]<<"  ";
  829. cout<<endl;
  830. }
  832. for(i=0;i<MAX_ANT_NUM;i++)
  833. {
  834. position=_MStackarray[i].GetCurrentPosition();
  835. if(position.row==EXIT_ROW&&position.col==EXIT_COL)
  836. {
  837. tag=i;
  838. break;
  839. }
  840. x=found;
  841. }
  843. if(tag)
  844. break;
  845. if(found==true)
  846. break;
  847. }
  848. cout<<endl;
  849. cout<<"------------------final test------------------"<<endl;
  850. for(i=0;i<_MStackarray[tag].GetLength()+1;i++)
  851. {
  852. cout<<_MStackarray[tag].MStack[i].row<<"--"<<_MStackarray[tag].MStack[i].col<<";";
  853. }
  854. }
  855. */