llk_algorithm.c

连连看

/***************************************************************************
 *            llk_algorithm.c
 *
 *  Fri Sep 23 08:46:05 2005
 *  Copyright  2005  Alpher
 *  Email: [e-mail]
 ****************************************************************************/

/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#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<8;i++)
    for(j=0;j<16;j++)
      algorithm_game.data[i][j]=0;
  return TRUE;
}

gboolean
algorithm_game_begin(gpointer data) 
{
  /*get a random order of the card image list*/  
  if(algorithm_game.status == ALGORITHM_GAME_STOP)
  { 
    switch(GPOINTER_TO_INT(data))
    {
      case 1: 
              algorithm_game.row = 6;
              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 = 7;
              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 = 8;
              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 = 8;
              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 = 36;
  gint i,j=128;
  time_t t;
  GSList *picture_list = NULL, *tmp_node; /*Single list*/
  
  switch(algorithm_game.difficulty)
  {
    case 0:
          picture_type = 21;
          j = 72;
	  break;
    case 1:
          picture_type = 25;
          j = 98;
	  break;
    case 2:
          picture_type = 32;
          j = 128;
	  break;
    default:/*assert not reach*/
          break;
  }
    for(i=0;i<j;i++)
    {      
      picture_list = g_slist_prepend(picture_list,GINT_TO_POINTER(i/4 + 1));
    }
    srand((unsigned) time(&t));
    while(picture_list != NULL)
    {
      i = rand()%j; if(i == 0)i = 1;   
      /*i get a value within 0-j,so should exclude the situation of 0.
        and rand()/0 is illegal,so should not use rand()/(j-1) to exclude 0*/
      i--; /*switch to 0 based value.*/
      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; /*close the node's next node pointer,and so get a 1 node single list,and then free it.*/
        g_slist_free(tmp_node); /*free the single list.*/
      }
      else
      {
        tmp_node = g_slist_nth(picture_list,i);
        g_slist_nth(picture_list,i-1)->next = tmp_node->next;
        tmp_node->next = NULL;  /*close the node's next node pointer,and so get a 1 node single list,and then free it.*/
        g_slist_free(tmp_node); /*free the single list*/
      }
      j--;
    }
}

/*
  test if p1 and p2 can direct link or not. that is to say,the points between p1 and p2 
  at the same row or column are all empty.
  BE CARE:this function do not warrant p1 and p2 have the same type of image.
*/
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;
  }
}

/*
  test if p1 and p2 can link.
  first,test if p1 and p2 can direct link,if not,get p1's and p2's adjacent empty points at x and y direction,
  judge if the p1's adjacent empty point can direct link to p2's
*/
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) /*can direct link,no need to return the turn points.*/
  {
    return TRUE;
  }
  else
  {
    /*get adjacent empty points at x and y direction,judge point by point*/
    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;
    }
  }
}

/*
  free single list and the memory of the data it refer
*/
void 
algorithm_free_with_data(GSList *list)
{
  GSList *last;
  last = list;
  while (last)
  {
    g_free (last->data);
    last = last->next;
  }
  g_slist_free(list);
}

/*
  find up,down,left and right of point p,get the adjacent empty points,form a single list,and return it.
*/
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);
    }
  }
  /*in order to efficient the operation of insert node to a single list,above algorithm insert node at the front,
    and then reverse the list,and return.MUST reverse,or will not get the right points of turning.
  */
  return g_slist_reverse(p_list);
}

/*
  empty the data of the two points.
*/
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;
  /*add score*/
  algorithm_game.score += 20;
}

/*
  test if the current game situation have solution.
  return value:
  0: yes,have solution.
  1: no,need to shuffle the cards.
  2: the cards are all deleted,this level is clear.
*/
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;  /*exclude the situation of link to itself*/
	    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;
}

/*
  shuffle cards.
  read the remain cards in data array,form a single list.then traversal the data array,
  at every point that have cards,get a random card from the single list and put it there.
  BE CARE: the life value will be minimised in UI dealing function,because in this function,
  shuffle one time do not certainly get a game situation that have solution,so this function may
  be called more than one time.
*/
void 
algorithm_game_shuffle(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_shuffle(); 
  /*recursion call of this function,untill get a game situation that have solution.*/
}

void     
algorithm_game_change(struct AlgorithmPoint p1, struct AlgorithmPoint p2)
{
  switch(algorithm_game.level)
  {
    case 0:/*No Change*/
           algorithm_data_change_0(p1,p2);
           break;