简单的井字过3关，5子棋等的多子棋的游戏算法实现

posted by David Chen at September 14, 2008, 1:27 PM

以下这个算法很简单，未用代码验证过。

1) 定义类Point
  class Point {
      int pno; //索引，唯一, 在网格中的位置(左上角为0,向右为1)
      int r; //point所在的行
       int c; //所在的列
       Player player; //如果该点还未放子，则为null;多对一关联
       boolean samePlayer ( Point p ) {
         return p!=null && player.equals(p.player);
      }
  }

2) 定义玩家类Player
  class Player {
      int pid; //玩家索引号，唯一
      boolean equals (Object player) {
          return (player != null && pid == ((Player) player).pid);
      }
  }

3) 定义全局变量
  int totalColumns; int totalRows; List allPoints;

4) 当某玩家占领一个点的时候，将该点看成p0,其周边的点看成p1~p8,由此计算连线的状态。
如图，p0.pno是p0在网格中的位置(左上角为0,0,向右为0,1)，
  p1.pno = p0.pno - (totalColumns + 1);
  ... ...
  p8.pno = p0.pno + (totalColumns + 1);

5) 取得Point的函数 Point getPoint( int pno ) {}
取得Player的函数 Player getPlayer( int pid ) {}

6) 递归函数, gameN 表示n子棋游戏
  int count( Point p, int gameN ) {
     int total1 = 1, total2 = 1, total3 = 1, total4 = 1;
     // 初始为1,是因为包括p这个点
     // 计算 p1 ~ p8
     int direction1 = (totalColumns + 1);
     Point p1 = getPoint( p.pno - direction1 );
     Point p8 = getPoint( p.pno + direction1 );
     //... ... p2 ~ p8
     if( p.samePlayer(p1) ) {
         total1 += count( p1, -1 * direction1 ) + count( p8, direction1 );
         if( gameN <= total1 ) return total1;
     }
     if( p.samePlayer(p2) ) {
         total2 += count( p2, -1 * direction2 ) + count( p7, direction2 );
         if( gameN <= total2 ) return total2;
     }
     if( p.samePlayer(p3) ) {
         total3 += count( p3, -1 * direction3 ) + count( p6, direction3 );
         if( gameN <= total3 ) return total3;
     }
     if( p.samePlayer(p4) ) {
         total4 += count( p4, -1 * direction4 ) + count( p5, direction4 );
         if( gameN <= total4 ) return total4;
     }
     return Math.max(total1, Math.max(total2, Math.max(total3, total4)));
  }

  int count( Point p,  int direction) {
     int total = 0;
     // 计算 direction 方向上的点
      Point tmp = getPoint( p.pno + direction );
     if( p.samePlayer(tmp) ) {
         total = 1;
         total += count( tmp, direction);
     }
     return total;
  }