llk_algorithm.c

连连看linux版V1.0,用C语言写的

#include "llk_algorithm.h"

gboolean 
algorithm_game_init(void)
{
  gint i,j;
  algorithm_game.difficulty = 0;
  algorithm_game.level = 0;
  algorithm_game.life = 0;
  algorithm_game.hint = 0;
  algorithm_game.score = 0;
  algorithm_game.status = ALGORITHM_GAME_STOP;
  for(i=0;i<9;i++)
    for(j=0;j<16;j++)
      algorithm_game.data[i][j]=0;
  return TRUE;
}

gboolean
algorithm_game_begin(gpointer data) 
{
  /*产生随机打乱的图片顺序*/  
  if(algorithm_game.status == ALGORITHM_GAME_STOP)
  { 
    switch(GPOINTER_TO_INT(data))
    {
      case 1: 
              algorithm_game.row = 7;
              algorithm_game.col = 12;
              algorithm_game.difficulty = 0;
	      algorithm_game.level = 0;
	      algorithm_game.life = 2;
	      algorithm_game.hint = 4;
	      algorithm_game.score = 0;
              break;
      case 2: 
              algorithm_game.row = 8;
              algorithm_game.col = 14;
              algorithm_game.difficulty = 1;
	      algorithm_game.level = 0;
	      algorithm_game.life = 3;
	      algorithm_game.hint = 6;
	      algorithm_game.score = 0;
              break; 
      case 3: 
              algorithm_game.row = 9;
              algorithm_game.col = 16;
              algorithm_game.difficulty = 2;
	      algorithm_game.level = 0;
	      algorithm_game.life = 4;
	      algorithm_game.hint = 8;
	      algorithm_game.score = 0;              
	      break;
      default:
              
              algorithm_game.row = 9;
              algorithm_game.col = 16;
              algorithm_game.difficulty = 2;
	      algorithm_game.level = 0;
	      algorithm_game.life = 4;
	      algorithm_game.hint = 5;
	      algorithm_game.score = 0;
    }
    algorithm_init_data();
    algorithm_game.status = ALGORITHM_GAME_RUN;
    return TRUE;
  }
  else
  {
    return FALSE;
  }
}

void algorithm_init_data(void)
{
  gint picture_type = 21;
  gint i,j;
  time_t t;
  GSList *picture_list = NULL, *tmp_node; /*单链表*/
  
  switch(algorithm_game.difficulty)
  {
    case 0:
          picture_type = 21;
	  break;
    case 1:
          picture_type = 28;
	  break;
    case 2:
          picture_type = 36;
	  break;
    default:/*assert not reach*/
          break;
  }
    for(i=1;i<=picture_type;i++)
    {
      picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(i));
      picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(i));
      picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(i));
      picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(i));
    }
    srand((unsigned) time(&t));
    j = picture_type * 4;
    while(picture_list != NULL)
    {
      i = rand()%j; if(i == 0)i = 1;   /*i取0-j,所以应该排除等于0的情况,而因为rand()/0是非法的,所以不能用rand()/(j-1)*/
      i--; /*转换成以0开始的坐标值*/
      algorithm_game.data[(j-1)/algorithm_game.col][(j-1)%algorithm_game.col] = GPOINTER_TO_INT(g_slist_nth_data(picture_list,i));
      if(i == 0)
      {
        tmp_node = picture_list;
        picture_list = picture_list->next;
        tmp_node->next = NULL;  /*把节点收尾,形成一个单节点的链,再释放之*/
        g_slist_free(tmp_node); /*释放整个链表*/
      }
      else
      {
        tmp_node = g_slist_nth(picture_list,i);
        g_slist_nth(picture_list,i-1)->next = tmp_node->next;
        tmp_node->next = NULL;  /*把节点收尾,形成一个单节点的链,再释放之*/
        g_slist_free(tmp_node); /*释放整个链表*/
      }
      j--;
    }
}

/*
  测试看p1和p2两点是否可以直接连接,也就是说,他们之间(同一行或者同一列)的点是否都为空点
  此函数不确保p1,p2有相同的图形
*/
gboolean algorithm_can_direct_link(struct AlgorithmPoint p1, struct AlgorithmPoint p2)
{
/*  if(p1.x > 0 && p1.x < algorithm_game.row && p1.y > 0 && p1.y < algorithm_game.col
    && p2.x > 0 && p2.x < algorithm_game.row && p2.y > 0 && p2.y < algorithm_game.col)
  g_assert(algorithm_game.data[p1.x][p1.y] == algorithm_game.data[p2.x][p2.y]);
*/
  /*g_print("Direct Link,x1: %d, y1: %d , x2: %d, y2:%d \n",p1.x,p1.y,p2.x,p2.y);*/
  if(p1.x == p2.x || p1.y == p2.y)
  {
    gint i;
    if(abs(p1.x - p2.x) + abs(p1.y - p2.y) <= 1)
    {
      return TRUE;
    }
    else
    {
      if(p1.x == p2.x && p1.x > -1 && p1.x < algorithm_game.row)
      {
	if(p1.y > p2.y)
	{
          for(i=p2.y+1; i<p1.y;i++)
	  {
	    if(algorithm_game.data[p1.x][i] > 0)
	      return FALSE;
	  }
	}
	else
	{
	  for(i=p1.y+1;i<p2.y;i++)
	  {
	    if(algorithm_game.data[p1.x][i] > 0)
	      return FALSE;
	  }
	}
      }
      else if(p1.y == p2.y && p1.y > -1 && p1.y < algorithm_game.col)
      {
        if(p1.x > p2.x)
	{
	  for(i=p2.x+1;i<p1.x;i++)
	  {
	    if(algorithm_game.data[i][p1.y] > 0)
	      return FALSE;
	  }
	}
	else
	{
	  for(i=p1.x+1;i<p2.x;i++)
	  {
	    if(algorithm_game.data[i][p1.y] > 0)
	      return FALSE;
	  }
	}
      }
      return TRUE;
    }
  }
  else
  {
    return FALSE;
  }
}

/*
  测试看p1和p2两点之间是否可以连接
  首先判断是否可以直接连接,如果不可以,再取p1和p2分别的x,y方向的相邻空点,然后看这些空点之间是否可以直接连接
*/
gboolean algorithm_can_link(struct AlgorithmPoint p1, struct AlgorithmPoint p2, struct AlgorithmPoint *pp3, struct AlgorithmPoint *pp4)
{
  if(algorithm_game.data[p1.x][p1.y] != algorithm_game.data[p2.x][p2.y])
  {
    return FALSE;
  }
  if(algorithm_can_direct_link(p1,p2) && pp3 == NULL) /*不许要返回折点位置*/
  {
    return TRUE;
  }
  else
  {
    /*取x,y数据,逐点判断*/
    GSList *p1_list=NULL,*p2_list=NULL;
    p1_list = algorithm_get_points(p1);
    p2_list = algorithm_get_points(p2);
/*    g_print("length_p1: %d, length_p2: %d \n",g_slist_length(p1_list),g_slist_length(p2_list));
    for(i=0;i<g_slist_length(p1_list);i++)
    {
      g_print("point:%d, %d",((struct AlgorithmPoint*)g_slist_nth_data(p1_list,i))->x,((struct AlgorithmPoint*)g_slist_nth_data(p1_list,i))->y);
    }
    g_print("\n");
    for(j=0;j<g_slist_length(p2_list);j++)
    {
      g_print("point:%d, %d",((struct AlgorithmPoint*)g_slist_nth_data(p2_list,j))->x,((struct AlgorithmPoint*)g_slist_nth_data(p2_list,j))->y);
    }
    g_print("\n");
*/
    if(p1_list == NULL || p2_list == NULL)
    {  return FALSE; }
    else
    {
      gint i,j;
      for(i=0;i<g_slist_length(p1_list);i++)
      {
        for(j=0;j<g_slist_length(p2_list);j++)
	{
	  if(algorithm_can_direct_link(*(struct AlgorithmPoint*)g_slist_nth_data(p1_list,i) ,*(struct AlgorithmPoint*)g_slist_nth_data(p2_list,j)))
	  {   
	    if(pp3 != NULL)  /* && pp4 != NULL*/
	    {
	      pp3->x = ((struct AlgorithmPoint*)g_slist_nth_data(p1_list,i))->x; 
	      pp3->y = ((struct AlgorithmPoint*)g_slist_nth_data(p1_list,i))->y;
	      pp4->x = ((struct AlgorithmPoint*)g_slist_nth_data(p2_list,j))->x;
	      pp4->y = ((struct AlgorithmPoint*)g_slist_nth_data(p2_list,j))->y;
	    }
	    algorithm_free_with_data(p1_list);
	    algorithm_free_with_data(p2_list);  
	    return TRUE;
	  }
	  /*g_print("can link over.\n"); */	 
	}
      }
      algorithm_free_with_data(p1_list);
      algorithm_free_with_data(p2_list);  
      return FALSE;
    }
  }
}

/*
  释放链表以及链表所挂载的数据所占的内存
*/
void algorithm_free_with_data(GSList *list)
{
  GSList *last;
  last = list;
  while (last)
    {
      g_free (last->data);
      last = last->next;
    }
  g_slist_free(list);
}

/*
  寻找p点上下左右的相邻空点,组合到一个单向链表中,返回
*/
GSList * algorithm_get_points(struct AlgorithmPoint p)
{
  struct AlgorithmPoint *tmp_point=NULL;
  GSList *p_list=NULL;
  gint i;
  /*g_print("Get Points,x1: %d, y1: %d \n",p.x,p.y);*/
  for(i=p.y + 1; i<=algorithm_game.col; i++)
  {
    /*p_list = algorithm_game.data[p.x][i] == 0 ? g_slist_prepend(p_list,ddd) : p_list;*/
    if(i < algorithm_game.col && algorithm_game.data[p.x][i] > 0)
    {
      break;
    }
    else
    {
      tmp_point = (struct AlgorithmPoint *)g_malloc(sizeof(struct AlgorithmPoint));
      tmp_point->x = p.x;
      tmp_point->y = i;
      p_list = g_slist_prepend(p_list,tmp_point);
    }
  }
  for(i=p.y - 1; i >= -1; i--)
  {
    /*p_list = algorithm_game.data[p.x][i] == 0 ? g_slist_prepend(p_list,ddd) : p_list;*/
    if(i > -1 && algorithm_game.data[p.x][i] > 0)
    {
      break;
    }
    else
    {
      tmp_point = (struct AlgorithmPoint *)g_malloc(sizeof(struct AlgorithmPoint));
      tmp_point->x = p.x;
      tmp_point->y = i;
      p_list = g_slist_prepend(p_list,tmp_point);
    }
  }
  for(i=p.x + 1; i<=algorithm_game.row; i++)
  {
    /*p_list = algorithm_game.data[p.x][i] == 0 ? g_slist_prepend(p_list,ddd) : p_list;*/
    if(i < algorithm_game.row && algorithm_game.data[i][p.y] > 0)
    {
      break;
    }
    else
    {
      tmp_point = (struct AlgorithmPoint *)g_malloc(sizeof(struct AlgorithmPoint));
      tmp_point->x = i;
      tmp_point->y = p.y;
      p_list = g_slist_prepend(p_list,tmp_point);
    }
  }
  for(i=p.x - 1; i >= -1; i--)
  {
    /*p_list = algorithm_game.data[p.x][i] == 0 ? g_slist_prepend(p_list,ddd) : p_list;*/
    if(i > -1 && algorithm_game.data[i][p.y] > 0)
    {
      break;
    }
    else
    {
      tmp_point = (struct AlgorithmPoint *)g_malloc(sizeof(struct AlgorithmPoint));
      tmp_point->x = i;
      tmp_point->y = p.y;
      p_list = g_slist_prepend(p_list,tmp_point);
    }
  }
  /*因为为了提高插入节点的效率,上面使用的是前项插入,为了在can_link中获得正确的折点位置,应该对链表进行倒序*/
  
  return g_slist_reverse(p_list);
}

/*
  消除两个点的数据
*/
void algorithm_link(struct AlgorithmPoint p1,struct AlgorithmPoint p2)
{
  algorithm_game.data[p1.x][p1.y] = 0;
  algorithm_game.data[p2.x][p2.y] = 0;
  /*加分*/
  algorithm_game.score += 20;
}

/*
  测试当前局面是否有解
  返回0: 表示有解
  返回1:表示无解,需要重新洗牌
  返回2:表示牌已经消完,这一关结束
*/
gint algorithm_game_no_solution(void)
{
  gint i,j;
  gint k,l;
  gint cards_num = 0;
  /*g_print("================================================================\n");*/
  for(i=0; i<algorithm_game.row ;i++)
  {
    for(j=0; j<algorithm_game.col ;j++)
    {
      if(algorithm_game.data[i][j] > 0)
      {
        cards_num++;
	for(k=i;k<algorithm_game.row;k++)
	{
	  for(l=0;l<algorithm_game.col;l++)
	  {
	    if(k == i && l == j)continue;  /*排除自己和自己相连的情况*/
	    if(algorithm_game.data[k][l] > 0)
	    {
	      struct AlgorithmPoint p1,p2;
	      p1.x = i; p1.y = j;
	      p2.x = k; p2.y = l;
	      if(algorithm_can_link(p1,p2,NULL,NULL))
	      {
	        /*g_print("p1:%d,%d -- p2:%d,%d can link.\n",p1.x,p1.y,p2.x,p2.y);*/
	        return 0;
	      }
	        /*g_print("p1:%d,%d -- p2:%d,%d can not link.\n",p1.x,p1.y,p2.x,p2.y);*/
	    }
	  }
	}
      }
    }
  }
  if(cards_num > 0)
  {
    return 1;
  }
  return 2;
}

/*
  洗牌
  把data数组中留下的牌读出来,列为单链表
  然后遍历data数组,在之前有牌的位置上放上一个从单链表中随机取出的一张牌ȡ�
  !!!!!洗牌时life生命值在ui的处理中减少,因为在那里要求一个有解的wash,所以变一次牌的话,这里的wash可能执行超过一次Һ��.
*/
void algorithm_game_wash(void)
{
  GSList *picture_list = NULL, *tmp_node; 
  gint i,j;
  time_t t;
  for(i=0; i < algorithm_game.row; i++)
  {
    for(j=0; j < algorithm_game.col; j++)
    {
      if(algorithm_game.data[i][j] > 0)
      {
        picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(algorithm_game.data[i][j]));
      }
    }
  }
  srand( (unsigned)time(&t) );
  for(i=0; i < algorithm_game.row; i++)
  {
    for(j=0; j < algorithm_game.col; j++)
    {
      if(algorithm_game.data[i][j] > 0)
      {
        gint m = rand()%g_slist_length(picture_list) ; if(m == 0) m=1;
        m--;
	tmp_node = g_slist_nth(picture_list,m);
	algorithm_game.data[i][j] = GPOINTER_TO_INT(tmp_node->data);
	if( m == 0 )
	{
	  picture_list = picture_list->next;
	  tmp_node->next = NULL;
	  g_slist_free(tmp_node);
	}
	else
	{
	  g_slist_nth(picture_list,m-1)->next = tmp_node->next;
	  tmp_node->next = NULL;
	  g_slist_free(tmp_node);
	}
      }
    }
  }
  if(algorithm_game_no_solution() == 1)algorithm_game_wash(); /*递归调用,直到得到一个有解的组合*/
}

void     algorithm_game_change(struct AlgorithmPoint p1, struct AlgorithmPoint p2)
{
  switch(algorithm_game.level)
  {
    case 0:/*不变化*/
           algorithm_data_change_0(p1,p2);
           break;
    case 1:/*向下*/
           algorithm_data_change_1(p1,p2);
           break;
    case 2:/*向左*/
           algorithm_data_change_2(p1,p2);
           break;
    case 3:/*上下分离*/
           algorithm_data_change_3(p1,p2);
           break;
    case 4:/*左右分离*/
           algorithm_data_change_4(p1,p2);
           break;
    case 5:/*上下集中*/
           algorithm_data_change_5(p1,p2);