git.sesse.net Git - vlc/blob - modules/video_filter/puzzle_mgt.c

   1 /*****************************************************************************
   2  * puzzle_mgt.c : Puzzle game filter - game management
   3  *****************************************************************************
   4  * Copyright (C) 2005-2009 VLC authors and VideoLAN
   5  * Copyright (C) 2013      Vianney Boyer
   6  * $Id$
   7  *
   8  * Authors: Antoine Cellerier <dionoea -at- videolan -dot- org>
   9  *          Vianney Boyer <vlcvboyer -at- gmail -dot- com>
  10  *
  11  * This program is free software; you can redistribute it and/or modify it
  12  * under the terms of the GNU Lesser General Public License as published by
  13  * the Free Software Foundation; either version 2.1 of the License, or
  14  * (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19  * GNU Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * along with this program; if not, write to the Free Software Foundation,
  23  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  24  *****************************************************************************/
  25
  26 /*****************************************************************************
  27  * Preamble
  28  *****************************************************************************/
  29
  30 #ifdef HAVE_CONFIG_H
  31 # include "config.h"
  32 #endif
  33 #include <math.h>
  34
  35 #include <vlc_common.h>
  36 #include <vlc_plugin.h>
  37 #include <vlc_filter.h>
  38 #include <vlc_rand.h>
  39
  40 #include "filter_picture.h"
  41
  42 #include "puzzle_bezier.h"
  43 #include "puzzle_lib.h"
  44 #include "puzzle_pce.h"
  45 #include "puzzle_mgt.h"
  46
  47 /*****************************************************************************
  48  * puzzle_bake: compute general puzzle data and allocate structures
  49  *****************************************************************************/
  50 int puzzle_bake( filter_t *p_filter, picture_t *p_pic_out, picture_t *p_pic_in)
  51 {
  52     filter_sys_t *p_sys = p_filter->p_sys;
  53     int i_ret = 0;
  54
  55     puzzle_free_ps_puzzle_array ( p_filter );
  56     puzzle_free_ps_pieces_shapes ( p_filter);
  57     puzzle_free_ps_pieces ( p_filter );
  58
  59     p_sys->s_allocated.i_rows =          p_sys->s_current_param.i_rows;
  60     p_sys->s_allocated.i_cols =          p_sys->s_current_param.i_cols;
  61     p_sys->s_allocated.i_planes =        p_sys->s_current_param.i_planes;
  62     p_sys->s_allocated.i_piece_types =   ((p_sys->s_current_param.b_advanced)?PIECE_TYPE_NBR:0);
  63     p_sys->s_allocated.i_pieces_nbr =    p_sys->s_allocated.i_rows * p_sys->s_allocated.i_cols;
  64     p_sys->s_allocated.b_preview =       p_sys->s_current_param.b_preview;
  65     p_sys->s_allocated.i_preview_size =  p_sys->s_current_param.i_preview_size;
  66     p_sys->s_allocated.i_border =        p_sys->s_current_param.i_border;
  67     p_sys->s_allocated.b_blackslot =     p_sys->s_current_param.b_blackslot;
  68     p_sys->s_allocated.b_near =          p_sys->s_current_param.b_near;
  69     p_sys->s_allocated.i_shape_size =    p_sys->s_current_param.i_shape_size;
  70     p_sys->s_allocated.b_advanced =      p_sys->s_current_param.b_advanced;
  71     p_sys->s_allocated.i_auto_shuffle_speed = p_sys->s_current_param.i_auto_shuffle_speed;
  72     p_sys->s_allocated.i_auto_solve_speed =   p_sys->s_current_param.i_auto_solve_speed;
  73     p_sys->s_allocated.i_rotate =        p_sys->s_current_param.i_rotate;
  74
  75     p_sys->ps_puzzle_array = malloc( sizeof( puzzle_array_t** ) * (p_sys->s_allocated.i_rows + 1));
  76     if( !p_sys->ps_puzzle_array )
  77         return VLC_ENOMEM;
  78
  79     for (int32_t r=0; r < p_sys->s_allocated.i_rows + 1; r++) {
  80         p_sys->ps_puzzle_array[r] = malloc( sizeof( puzzle_array_t* ) * (p_sys->s_allocated.i_cols + 1));
  81         if( !p_sys->ps_puzzle_array[r] )
  82             return VLC_ENOMEM;
  83         for (int32_t c=0; c < p_sys->s_allocated.i_cols + 1; c++) {
  84             p_sys->ps_puzzle_array[r][c] = malloc( sizeof( puzzle_array_t ) * p_sys->s_allocated.i_planes);
  85             if( !p_sys->ps_puzzle_array[r][c] )
  86                 return VLC_ENOMEM;
  87         }
  88     }
  89
  90     p_sys->ps_desk_planes = malloc( sizeof( puzzle_plane_t ) * p_sys->s_allocated.i_planes);
  91     if( !p_sys->ps_desk_planes )
  92         return VLC_ENOMEM;
  93     p_sys->ps_pict_planes = malloc( sizeof( puzzle_plane_t ) * p_sys->s_allocated.i_planes);
  94     if( !p_sys->ps_pict_planes )
  95         return VLC_ENOMEM;
  96
  97     for (uint8_t i_plane = 0; i_plane < p_sys->s_allocated.i_planes; i_plane++) {
  98         p_sys->ps_desk_planes[i_plane].i_lines = p_pic_out->p[i_plane].i_visible_lines;
  99         p_sys->ps_desk_planes[i_plane].i_pitch = p_pic_out->p[i_plane].i_pitch;
 100         p_sys->ps_desk_planes[i_plane].i_visible_pitch = p_pic_out->p[i_plane].i_visible_pitch;
 101         p_sys->ps_desk_planes[i_plane].i_pixel_pitch = p_pic_out->p[i_plane].i_pixel_pitch;
 102         p_sys->ps_desk_planes[i_plane].i_width = p_pic_out->p[i_plane].i_visible_pitch / p_pic_out->p[i_plane].i_pixel_pitch;
 103
 104         p_sys->ps_desk_planes[i_plane].i_preview_width = p_sys->ps_desk_planes[i_plane].i_width * p_sys->s_current_param.i_preview_size / 100;
 105         p_sys->ps_desk_planes[i_plane].i_preview_lines = p_sys->ps_desk_planes[i_plane].i_lines * p_sys->s_current_param.i_preview_size / 100;
 106
 107         p_sys->ps_desk_planes[i_plane].i_border_width = p_sys->ps_desk_planes[i_plane].i_width * p_sys->s_current_param.i_border / 2 / 100;
 108         p_sys->ps_desk_planes[i_plane].i_border_lines = p_sys->ps_desk_planes[i_plane].i_lines * p_sys->s_current_param.i_border / 2 / 100;
 109
 110         p_sys->ps_desk_planes[i_plane].i_pce_max_width = (( p_sys->ps_desk_planes[i_plane].i_width
 111                 - 2 * p_sys->ps_desk_planes[i_plane].i_border_width ) + p_sys->s_allocated.i_cols - 1 ) / p_sys->s_allocated.i_cols;
 112         p_sys->ps_desk_planes[i_plane].i_pce_max_lines = (( p_sys->ps_desk_planes[i_plane].i_lines
 113                 - 2 * p_sys->ps_desk_planes[i_plane].i_border_lines ) + p_sys->s_allocated.i_rows - 1 ) / p_sys->s_allocated.i_rows;
 114
 115         p_sys->ps_pict_planes[i_plane].i_lines = p_pic_in->p[i_plane].i_visible_lines;
 116         p_sys->ps_pict_planes[i_plane].i_pitch = p_pic_in->p[i_plane].i_pitch;
 117         p_sys->ps_pict_planes[i_plane].i_visible_pitch = p_pic_in->p[i_plane].i_visible_pitch;
 118         p_sys->ps_pict_planes[i_plane].i_pixel_pitch = p_pic_in->p[i_plane].i_pixel_pitch;
 119         p_sys->ps_pict_planes[i_plane].i_width = p_pic_in->p[i_plane].i_visible_pitch / p_pic_in->p[i_plane].i_pixel_pitch;
 120
 121         p_sys->ps_pict_planes[i_plane].i_preview_width = p_sys->ps_pict_planes[i_plane].i_width * p_sys->s_current_param.i_preview_size / 100;
 122         p_sys->ps_pict_planes[i_plane].i_preview_lines = p_sys->ps_pict_planes[i_plane].i_lines * p_sys->s_current_param.i_preview_size / 100;
 123
 124         p_sys->ps_pict_planes[i_plane].i_border_width = p_sys->ps_pict_planes[i_plane].i_width * p_sys->s_current_param.i_border / 2 / 100;
 125         p_sys->ps_pict_planes[i_plane].i_border_lines = p_sys->ps_pict_planes[i_plane].i_lines * p_sys->s_current_param.i_border / 2 / 100;
 126
 127         p_sys->ps_pict_planes[i_plane].i_pce_max_width = (( p_sys->ps_desk_planes[i_plane].i_width
 128                 - 2 * p_sys->ps_pict_planes[i_plane].i_border_width ) + p_sys->s_allocated.i_cols - 1 ) / p_sys->s_allocated.i_cols;
 129         p_sys->ps_pict_planes[i_plane].i_pce_max_lines = (( p_sys->ps_pict_planes[i_plane].i_lines
 130                 - 2 * p_sys->ps_pict_planes[i_plane].i_border_lines ) + p_sys->s_allocated.i_rows - 1 ) / p_sys->s_allocated.i_rows;
 131
 132         for (int32_t r = 0; r < p_sys->s_allocated.i_rows; r++)
 133             for (int32_t c = 0; c < p_sys->s_allocated.i_cols; c++) {
 134                 if ( r == 0 )
 135                     p_sys->ps_puzzle_array[r][c][i_plane].i_y = p_sys->ps_pict_planes[i_plane].i_border_lines;
 136                 if ( c == 0 )
 137                     p_sys->ps_puzzle_array[r][c][i_plane].i_x = p_sys->ps_pict_planes[i_plane].i_border_width;
 138                 p_sys->ps_puzzle_array[r][c][i_plane].i_width =
 139                     (p_sys->ps_pict_planes[i_plane].i_width - p_sys->ps_pict_planes[i_plane].i_border_width
 140                     - p_sys->ps_puzzle_array[r][c][i_plane].i_x) / ( p_sys->s_allocated.i_cols - c );
 141                 p_sys->ps_puzzle_array[r][c][i_plane].i_lines =
 142                     (p_sys->ps_pict_planes[i_plane].i_lines - p_sys->ps_pict_planes[i_plane].i_border_lines
 143                     - p_sys->ps_puzzle_array[r][c][i_plane].i_y) / ( p_sys->s_allocated.i_rows - r );
 144                 p_sys->ps_puzzle_array[r][c + 1][i_plane].i_x =
 145                     p_sys->ps_puzzle_array[r][c][i_plane].i_x + p_sys->ps_puzzle_array[r][c][i_plane].i_width;
 146                 p_sys->ps_puzzle_array[r + 1][c][i_plane].i_y =
 147                     p_sys->ps_puzzle_array[r][c][i_plane].i_y + p_sys->ps_puzzle_array[r][c][i_plane].i_lines;
 148             }
 149     }
 150
 151     p_sys->i_magnet_accuracy = ( p_sys->s_current_param.i_pict_width / 50) + 3;
 152
 153     if (p_sys->s_current_param.b_advanced && p_sys->s_allocated.i_shape_size != 0) {
 154         i_ret = puzzle_bake_pieces_shapes ( p_filter );
 155         if (i_ret != VLC_SUCCESS)
 156             return i_ret;
 157     }
 158
 159     i_ret = puzzle_bake_piece ( p_filter );
 160     if (i_ret != VLC_SUCCESS)
 161         return i_ret;
 162
 163     if ( (p_sys->pi_order != NULL) && (p_sys->ps_desk_planes != NULL) && (p_sys->ps_pict_planes != NULL)
 164         && (p_sys->ps_puzzle_array != NULL) && (p_sys->ps_pieces != NULL) )
 165         p_sys->b_init = true;
 166
 167     if ( (p_sys->ps_pieces_shapes == NULL) && (p_sys->s_current_param.b_advanced)
 168         && (p_sys->s_current_param.i_shape_size != 0) )
 169         p_sys->b_init = false;
 170
 171     return VLC_SUCCESS;
 172 }
 173
 174 void puzzle_free_ps_puzzle_array( filter_t *p_filter)
 175 {
 176     filter_sys_t *p_sys = p_filter->p_sys;
 177
 178     if (p_sys->ps_puzzle_array != NULL) {
 179         for (int32_t r=0; r < p_sys->s_allocated.i_rows + 1; r++) {
 180             for (int32_t c=0; c < p_sys->s_allocated.i_cols + 1; c++)
 181                 free( p_sys->ps_puzzle_array[r][c] );
 182             free( p_sys->ps_puzzle_array[r] );
 183         }
 184         free( p_sys->ps_puzzle_array );
 185     }
 186     p_sys->ps_puzzle_array = NULL;
 187
 188     free ( p_sys->ps_desk_planes );
 189     p_sys->ps_desk_planes = NULL;
 190
 191     free ( p_sys->ps_pict_planes );
 192     p_sys->ps_pict_planes = NULL;
 193
 194     return;
 195 }
 196
 197 /*****************************************************************************
 198  * puzzle_bake_piece: compute data dedicated to each piece
 199  *****************************************************************************/
 200 int puzzle_bake_piece( filter_t *p_filter)
 201 {
 202     int i_ret = puzzle_allocate_ps_pieces( p_filter);
 203     if (i_ret != VLC_SUCCESS)
 204         return i_ret;
 205
 206     filter_sys_t *p_sys = p_filter->p_sys;
 207
 208     /* generates random pi_order array */
 209     i_ret = puzzle_shuffle( p_filter );
 210     if (i_ret != VLC_SUCCESS)
 211         return i_ret;
 212
 213     int32_t i = 0;
 214     for (int32_t row = 0; row < p_sys->s_allocated.i_rows; row++) {
 215         for (int32_t col = 0; col < p_sys->s_allocated.i_cols; col++) {
 216             int32_t orow = row;
 217             int32_t ocol = col;
 218
 219             if (p_sys->pi_order != NULL) {
 220                 orow = p_sys->pi_order[i] / (p_sys->s_allocated.i_cols);
 221                 ocol = p_sys->pi_order[i] % (p_sys->s_allocated.i_cols);
 222             }
 223
 224             p_sys->ps_pieces[i].i_original_row = orow;
 225             p_sys->ps_pieces[i].i_original_col = ocol;
 226
 227             /* set bottom and right shapes */
 228             p_sys->ps_pieces[i].i_left_shape  = 0;
 229             p_sys->ps_pieces[i].i_top_shape   = 2;
 230             p_sys->ps_pieces[i].i_btm_shape   = 4;
 231             p_sys->ps_pieces[i].i_right_shape = 6;
 232
 233             if (p_sys->s_allocated.i_shape_size > 0) {
 234
 235                 if (orow < p_sys->s_allocated.i_rows - 1)
 236                     p_sys->ps_pieces[i].i_btm_shape = 4 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 237
 238                 if (ocol < p_sys->s_allocated.i_cols - 1)
 239                     p_sys->ps_pieces[i].i_right_shape = 6 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 240             }
 241
 242             /* set piece data */
 243             p_sys->ps_pieces[i].i_actual_angle   = 0;
 244             p_sys->ps_pieces[i].b_overlap        = false;
 245             p_sys->ps_pieces[i].i_actual_mirror  = +1;
 246             p_sys->ps_pieces[i].b_finished       = ((ocol == col) && (orow == row));
 247             p_sys->ps_pieces[i].i_group_ID       = i;
 248
 249             /* add small random offset to location */
 250             int32_t i_rand_x = 0;
 251             int32_t i_rand_y = 0;
 252             if (p_sys->s_current_param.b_advanced) {
 253                 i_rand_x = (( (unsigned) vlc_mrand48()) % ( p_sys->ps_desk_planes[0].i_pce_max_width + 1 ) ) - (int32_t) p_sys->ps_desk_planes[0].i_pce_max_width / 2;
 254                 i_rand_y = (( (unsigned) vlc_mrand48()) % ( p_sys->ps_desk_planes[0].i_pce_max_lines + 1 ) ) - (int32_t) p_sys->ps_desk_planes[0].i_pce_max_lines / 2;
 255             }
 256
 257             /* copy related puzzle data to piece data */
 258             if (p_sys->ps_puzzle_array != NULL) {
 259                 for (uint8_t i_plane = 0; i_plane < p_sys->s_allocated.i_planes; i_plane++) {
 260
 261                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_width = p_sys->ps_puzzle_array[row][col][i_plane].i_width;
 262                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_lines = p_sys->ps_puzzle_array[row][col][i_plane].i_lines;
 263                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_original_x = p_sys->ps_puzzle_array[orow][ocol][i_plane].i_x;
 264                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_original_y = p_sys->ps_puzzle_array[orow][ocol][i_plane].i_y;
 265                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_actual_x = p_sys->ps_puzzle_array[row][col][i_plane].i_x + i_rand_x *
 266                         p_sys->ps_desk_planes[i_plane].i_width / p_sys->ps_desk_planes[0].i_width;
 267                     p_sys->ps_pieces[i].ps_piece_in_plane[i_plane].i_actual_y = p_sys->ps_puzzle_array[row][col][i_plane].i_y + i_rand_y *
 268                         p_sys->ps_desk_planes[i_plane].i_lines / p_sys->ps_desk_planes[0].i_lines;
 269
 270                     if (i_plane == 0) {
 271
 272                         p_sys->ps_pieces[i].i_OLx = p_sys->ps_pieces[i].ps_piece_in_plane[0].i_original_x;
 273                         p_sys->ps_pieces[i].i_OTy = p_sys->ps_pieces[i].ps_piece_in_plane[0].i_original_y;
 274                         p_sys->ps_pieces[i].i_ORx = p_sys->ps_pieces[i].ps_piece_in_plane[0].i_original_x + p_sys->ps_pieces[i].ps_piece_in_plane[0].i_width - 1;
 275                         p_sys->ps_pieces[i].i_OBy = p_sys->ps_pieces[i].ps_piece_in_plane[0].i_original_y + p_sys->ps_pieces[i].ps_piece_in_plane[0].i_lines - 1;
 276
 277                         puzzle_calculate_corners( p_filter, i );
 278                     }
 279                 }
 280             }
 281             i++;
 282         }
 283     }
 284
 285     /* left and top shapes are based on negative right and bottom ones */
 286     puzzle_set_left_top_shapes( p_filter);
 287
 288     /* add random rotation to each piece */
 289     puzzle_random_rotate( p_filter);
 290
 291     return VLC_SUCCESS;
 292 }
 293
 294 /*****************************************************************************
 295  * puzzle_set_left_top_shapes: Set the shape ID to be used for top and left
 296  *                             edges of each piece. Those ID will be set to
 297  *                             be the negative of bottom or right of adjacent
 298  *                             piece.
 299  *****************************************************************************/
 300 void puzzle_set_left_top_shapes( filter_t *p_filter)
 301 {
 302     filter_sys_t *p_sys = p_filter->p_sys;
 303     /* for each piece on the desk... */
 304     for (uint16_t i_pce_B=0; i_pce_B < p_sys->s_allocated.i_pieces_nbr; i_pce_B++)
 305         /* ...search adjacent piece */
 306         for (uint16_t i_pce_A=0;     i_pce_A < p_sys->s_allocated.i_pieces_nbr; i_pce_A++)
 307         {
 308             if (     ( p_sys->ps_pieces[i_pce_A].i_original_row == p_sys->ps_pieces[i_pce_B].i_original_row )
 309                   && ( p_sys->ps_pieces[i_pce_A].i_original_col == p_sys->ps_pieces[i_pce_B].i_original_col-1 ) )
 310                 /* left shape is based on negative (invert ID LSB) right one */
 311                 p_sys->ps_pieces[i_pce_B].i_left_shape = (p_sys->ps_pieces[i_pce_A].i_right_shape - 6 ) ^ 0x01;
 312
 313             if (     ( p_sys->ps_pieces[i_pce_A].i_original_row == p_sys->ps_pieces[i_pce_B].i_original_row - 1 )
 314                   && ( p_sys->ps_pieces[i_pce_A].i_original_col == p_sys->ps_pieces[i_pce_B].i_original_col ) )
 315                 /* top shape is based on negative of bottom one
 316                  *                 top ID = bottom ID - 2
 317                  *                 negative ID = invert LSB
 318                  */
 319                 p_sys->ps_pieces[i_pce_B].i_top_shape = (p_sys->ps_pieces[i_pce_A].i_btm_shape - 2 ) ^ 0x01;
 320         }
 321 }
 322
 323 void puzzle_random_rotate( filter_t *p_filter)
 324 {
 325     filter_sys_t *p_sys = p_filter->p_sys;
 326     /* add random rotation to each piece */
 327     for (uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++)
 328     {
 329         p_sys->ps_pieces[i].i_actual_angle  = 0;
 330         p_sys->ps_pieces[i].i_actual_mirror = +1;
 331
 332         switch ( p_sys->s_current_param.i_rotate )
 333         {
 334           case 1:
 335                 puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 2 ) ) * 2, p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 336             break;
 337           case 2:
 338                 puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 4 ) ), p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 339             break;
 340           case 3:
 341                 puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 8 ) ), p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 342             break;
 343         }
 344         puzzle_calculate_corners( p_filter, i );
 345     }
 346 }
 347
 348 void puzzle_free_ps_pieces( filter_t *p_filter)
 349 {
 350     filter_sys_t *p_sys = p_filter->p_sys;
 351
 352     if (p_sys->ps_pieces != NULL) {
 353         for (uint32_t i_pce = 0; i_pce < p_sys->s_allocated.i_pieces_nbr; i_pce++)
 354             free( p_sys->ps_pieces[i_pce].ps_piece_in_plane );
 355         free( p_sys->ps_pieces );
 356     }
 357     p_sys->ps_pieces = NULL;
 358
 359     free( p_sys->pi_order );
 360     p_sys->pi_order = NULL;
 361
 362     free( p_sys->ps_pieces_tmp );
 363     p_sys->ps_pieces_tmp = NULL;
 364
 365     free( p_sys->pi_group_qty );
 366     p_sys->pi_group_qty = NULL;
 367
 368     return;
 369 }
 370
 371 int puzzle_allocate_ps_pieces( filter_t *p_filter)
 372 {
 373     filter_sys_t *p_sys = p_filter->p_sys;
 374     puzzle_free_ps_pieces(p_filter);
 375     p_sys->s_allocated.i_pieces_nbr = p_sys->s_allocated.i_rows * p_sys->s_allocated.i_cols;
 376     p_sys->ps_pieces = malloc( sizeof( piece_t) * p_sys->s_allocated.i_pieces_nbr );
 377     if( !p_sys->ps_pieces )
 378         return VLC_ENOMEM;
 379     for (uint32_t p = 0; p < p_sys->s_allocated.i_pieces_nbr; p++) {
 380         p_sys->ps_pieces[p].ps_piece_in_plane = malloc( sizeof( piece_in_plane_t) * p_sys->s_allocated.i_planes );
 381         if( !p_sys->ps_pieces[p].ps_piece_in_plane ) {
 382             for (uint32_t i=0;i<p;i++)
 383                 free(p_sys->ps_pieces[i].ps_piece_in_plane);
 384             free(p_sys->ps_pieces);
 385             p_sys->ps_pieces = NULL;
 386             return VLC_ENOMEM;
 387         }
 388     }
 389
 390     p_sys->ps_pieces_tmp = malloc( sizeof( piece_t) * p_sys->s_allocated.i_pieces_nbr );
 391     if( !p_sys->ps_pieces_tmp ) {
 392         for (uint32_t i=0;i<p_sys->s_allocated.i_pieces_nbr;i++)
 393             free(p_sys->ps_pieces[i].ps_piece_in_plane);
 394         free(p_sys->ps_pieces);
 395         p_sys->ps_pieces = NULL;
 396         return VLC_ENOMEM;
 397     }
 398     p_sys->pi_group_qty = malloc( sizeof( int32_t ) * (p_sys->s_allocated.i_pieces_nbr));
 399     if( !p_sys->pi_group_qty ) {
 400         for (uint32_t i=0;i<p_sys->s_allocated.i_pieces_nbr;i++)
 401             free(p_sys->ps_pieces[i].ps_piece_in_plane);
 402         free(p_sys->ps_pieces);
 403         p_sys->ps_pieces = NULL;
 404         free(p_sys->ps_pieces_tmp);
 405         p_sys->ps_pieces_tmp = NULL;
 406         return VLC_ENOMEM;
 407     }
 408     return VLC_SUCCESS;
 409 }
 410
 411 bool puzzle_is_valid( filter_sys_t *p_sys, int32_t *pi_pce_lst )
 412 {
 413     const int32_t i_count = p_sys->s_allocated.i_pieces_nbr;
 414
 415     if( !p_sys->s_current_param.b_blackslot )
 416         return true;
 417
 418     int32_t d = 0;
 419     for( int32_t i = 0; i < i_count; i++ ) {
 420         if( pi_pce_lst[i] == i_count - 1 ) {
 421             d += i / p_sys->s_allocated.i_cols + 1;
 422             continue;
 423         }
 424         for( int32_t j = i+1; j < i_count; j++ ) {
 425             if( pi_pce_lst[j] == i_count - 1 )
 426                 continue;
 427             if( pi_pce_lst[i] > pi_pce_lst[j] )
 428                 d++;
 429         }
 430     }
 431     return (d%2) == 0;
 432 }
 433
 434 int puzzle_shuffle( filter_t *p_filter )
 435 {
 436     filter_sys_t *p_sys = p_filter->p_sys;
 437
 438     int32_t i_pieces_nbr = p_sys->s_allocated.i_pieces_nbr;
 439
 440     do
 441     {
 442         int i_ret = puzzle_generate_rand_pce_list( p_filter, &p_sys->pi_order );
 443         if (i_ret != VLC_SUCCESS)
 444             return i_ret;
 445     } while( puzzle_is_finished( p_sys, p_sys->pi_order ) || !puzzle_is_valid( p_sys, p_sys->pi_order ) );
 446
 447
 448     if( p_sys->s_current_param.b_blackslot ) {
 449         for( int32_t i = 0; i < i_pieces_nbr; i++ )
 450             if( p_sys->pi_order[i] == i_pieces_nbr - 1 ) {
 451                 p_sys->i_selected = i;
 452                 break;
 453             }
 454     }
 455     else {
 456         p_sys->i_selected = NO_PCE;
 457     }
 458
 459     p_sys->b_shuffle_rqst = false;
 460     p_sys->b_finished = false;
 461
 462     return VLC_SUCCESS;
 463 }
 464
 465 int puzzle_generate_rand_pce_list( filter_t *p_filter, int32_t **pi_pce_lst )
 466 {
 467     filter_sys_t *p_sys = p_filter->p_sys;
 468
 469     int32_t i_pieces_nbr = p_sys->s_allocated.i_pieces_nbr;
 470
 471     if (pi_pce_lst != NULL )
 472         free( *pi_pce_lst );
 473     *pi_pce_lst = calloc( i_pieces_nbr, sizeof(**pi_pce_lst) );
 474     if( !*pi_pce_lst )
 475         return VLC_ENOMEM;
 476
 477     for( int32_t i = 0; i < i_pieces_nbr; i++ )
 478         (*pi_pce_lst)[i] = NO_PCE;
 479
 480     for( int32_t c = 0; c < i_pieces_nbr; ) {
 481         int32_t i = ((unsigned)vlc_mrand48()) % i_pieces_nbr;
 482         if( (*pi_pce_lst)[i] == NO_PCE )
 483             (*pi_pce_lst)[i] = c++;
 484     }
 485     return VLC_SUCCESS;
 486 }
 487
 488 bool puzzle_is_finished( filter_sys_t *p_sys, int32_t *pi_pce_lst )
 489 {
 490     for( uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++ )
 491         if( (int32_t)i != pi_pce_lst[i] )
 492             return false;
 493
 494     return true;
 495 }
 496
 497 int puzzle_piece_foreground( filter_t *p_filter, int32_t i_piece) {
 498     filter_sys_t *p_sys = p_filter->p_sys;
 499     piece_t *ps_pieces_tmp;        /* list [piece] of pieces data. Sort as per layers */
 500     uint32_t i_group_ID = p_sys->ps_pieces[i_piece].i_group_ID;
 501
 502     ps_pieces_tmp = malloc( sizeof( piece_t) * p_sys->s_allocated.i_pieces_nbr );
 503     if (!ps_pieces_tmp)
 504         return VLC_ENOMEM;
 505
 506     int32_t j=0;
 507
 508     memcpy( &ps_pieces_tmp[j], &p_sys->ps_pieces[i_piece], sizeof(piece_t) );
 509     j++;
 510
 511     for (uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++) {
 512         if ( ( p_sys->ps_pieces[i].i_group_ID == i_group_ID ) && ( (int32_t)i != i_piece ) ) {
 513             memcpy( &ps_pieces_tmp[j], &p_sys->ps_pieces[i], sizeof(piece_t));
 514             j++;
 515         }
 516     }
 517     for (uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++) {
 518         if ( p_sys->ps_pieces[i].i_group_ID != i_group_ID ) {
 519             memcpy( &ps_pieces_tmp[j], &p_sys->ps_pieces[i], sizeof(piece_t));
 520             j++;
 521         }
 522     }
 523
 524     free( p_filter->p_sys->ps_pieces );
 525     p_filter->p_sys->ps_pieces = ps_pieces_tmp;
 526
 527     return VLC_SUCCESS;
 528 }
 529
 530 void puzzle_count_pce_group( filter_t *p_filter) { /* count pce in each group */
 531     filter_sys_t *p_sys = p_filter->p_sys;
 532
 533     memset ( p_sys->pi_group_qty, 0, sizeof( int32_t ) * (p_sys->s_allocated.i_pieces_nbr) );
 534     for (uint32_t i_pce = 0; i_pce < p_sys->s_allocated.i_pieces_nbr; i_pce++)
 535         p_sys->pi_group_qty[p_sys->ps_pieces[i_pce].i_group_ID]++;
 536 }
 537
 538 /*****************************************************************************
 539  * puzzle_solve_pces_group: check if pieces are close together
 540  *                          and then combine in a group
 541  *****************************************************************************/
 542 void puzzle_solve_pces_group( filter_t *p_filter) {
 543     filter_sys_t *p_sys = p_filter->p_sys;
 544     int32_t i_dx, i_dy;
 545
 546     p_sys->i_solve_grp_loop++;
 547     p_sys->i_solve_grp_loop %= p_sys->s_allocated.i_pieces_nbr;
 548
 549     int32_t i_piece_A = p_sys->i_solve_grp_loop;
 550     piece_t *ps_piece_A = &p_sys->ps_pieces[i_piece_A];
 551
 552     for (uint32_t i_piece_B = 0; i_piece_B < p_sys->s_allocated.i_pieces_nbr; i_piece_B++)
 553     {
 554         piece_t *ps_piece_B = &p_sys->ps_pieces[i_piece_B];
 555
 556         if ( ps_piece_A->i_actual_angle != ps_piece_B->i_actual_angle || ps_piece_A->i_actual_mirror != ps_piece_B->i_actual_mirror )
 557             continue;
 558
 559         if ( (ps_piece_B->i_group_ID != p_sys->ps_pieces[i_piece_A].i_group_ID ) )
 560         {
 561             if ( abs(ps_piece_A->i_OTy - ps_piece_B->i_OTy )<3)
 562             {
 563                 if (    abs( ps_piece_A->i_ORx - ps_piece_B->i_OLx + 1 ) < 3
 564                      && abs( ps_piece_A->i_TRx - ps_piece_B->i_TLx + 1 ) < p_sys->i_magnet_accuracy
 565                      && abs( ps_piece_A->i_TRy - ps_piece_B->i_TLy ) < p_sys->i_magnet_accuracy
 566                      && abs( ps_piece_A->i_BRx - ps_piece_B->i_BLx + 1 ) < p_sys->i_magnet_accuracy
 567                      && abs( ps_piece_A->i_BRy - ps_piece_B->i_BLy ) < p_sys->i_magnet_accuracy )
 568                 {
 569                     i_dx = ps_piece_A->i_TRx - ps_piece_B->i_TLx + ps_piece_A->i_step_x_x;
 570                     i_dy = ps_piece_A->i_TRy - ps_piece_B->i_TLy;
 571
 572                     if (!ps_piece_B->b_finished)
 573                         puzzle_move_group( p_filter, i_piece_B, i_dx, i_dy);
 574                     else
 575                         puzzle_move_group( p_filter, i_piece_A, -i_dx, -i_dy);
 576
 577                     uint32_t i_group_ID = ps_piece_B->i_group_ID;
 578                     for (uint32_t i_for = 0; i_for < p_sys->s_allocated.i_pieces_nbr; i_for++)
 579                         if ( p_sys->ps_pieces[i_for].i_group_ID == i_group_ID)
 580                             p_sys->ps_pieces[i_for].i_group_ID = p_sys->ps_pieces[i_piece_A].i_group_ID;
 581                 }
 582             }
 583             else if ( abs(ps_piece_A->i_OLx - ps_piece_B->i_OLx ) < 3 )
 584             {
 585                 if (    abs(ps_piece_A->i_OBy - ps_piece_B->i_OTy + 1 ) < 3
 586                      && abs( ps_piece_B->i_TLx - ps_piece_A->i_BLx ) < p_sys->i_magnet_accuracy
 587                      && abs( ps_piece_B->i_TLy - 1 - ps_piece_A->i_BLy ) < p_sys->i_magnet_accuracy
 588                      && abs( ps_piece_B->i_TRx - ps_piece_A->i_BRx ) < p_sys->i_magnet_accuracy
 589                      && abs( ps_piece_B->i_TRy - 1 - ps_piece_A->i_BRy ) < p_sys->i_magnet_accuracy )
 590                 {
 591
 592                     i_dx = ps_piece_A->i_BLx - ps_piece_B->i_TLx;
 593                     i_dy = ps_piece_A->i_BLy - ps_piece_B->i_TLy + ps_piece_A->i_step_y_y;
 594
 595                     if (!ps_piece_B->b_finished)
 596                         puzzle_move_group( p_filter, i_piece_B, i_dx, i_dy);
 597                     else
 598                         puzzle_move_group( p_filter, i_piece_A, -i_dx, -i_dy);
 599
 600                     uint32_t i_group_ID = ps_piece_B->i_group_ID;
 601                     for (uint32_t i_for = 0; i_for < p_sys->s_allocated.i_pieces_nbr; i_for++)
 602                         if ( p_sys->ps_pieces[i_for].i_group_ID == i_group_ID)
 603                             p_sys->ps_pieces[i_for].i_group_ID = p_sys->ps_pieces[i_piece_A].i_group_ID;
 604                 }
 605             }
 606         }
 607
 608         if ( abs( ps_piece_A->i_OTy - ps_piece_B->i_OTy ) < 3 )
 609         {
 610             if (    abs( ps_piece_A->i_ORx - ps_piece_B->i_OLx + 1 ) < 3
 611                  && abs( ps_piece_A->i_TRx - ps_piece_B->i_TLx + 1 ) < p_sys->i_magnet_accuracy
 612                  && abs( ps_piece_A->i_TRy - ps_piece_B->i_TLy ) < p_sys->i_magnet_accuracy
 613                  && abs( ps_piece_A->i_BRx - ps_piece_B->i_BLx + 1 ) < p_sys->i_magnet_accuracy
 614                  && abs( ps_piece_A->i_BRy - ps_piece_B->i_BLy ) < p_sys->i_magnet_accuracy )
 615             {
 616                 ps_piece_B->i_left_shape = 0;
 617                 ps_piece_A->i_right_shape = 6;
 618             }
 619         }
 620         else if ( abs( ps_piece_A->i_OLx - ps_piece_B->i_OLx )<3 )
 621         {
 622             if (    abs( ps_piece_A->i_OBy - ps_piece_B->i_OTy + 1 )<3
 623                  && abs( ps_piece_B->i_TLx - ps_piece_A->i_BLx ) < p_sys->i_magnet_accuracy
 624                  && abs( ps_piece_B->i_TLy - 1 - ps_piece_A->i_BLy ) < p_sys->i_magnet_accuracy
 625                  && abs( ps_piece_B->i_TRx - ps_piece_A->i_BRx ) < p_sys->i_magnet_accuracy
 626                  && abs( ps_piece_B->i_TRy - 1 - ps_piece_A->i_BRy ) < p_sys->i_magnet_accuracy )
 627             {
 628                 ps_piece_B->i_top_shape = 2;
 629                 ps_piece_A->i_btm_shape = 4;
 630             }
 631         }
 632    }
 633 }
 634
 635 /*****************************************************************************
 636  * puzzle_solve_pces_accuracy: check if pieces are close to their final location
 637  *                             and then adjust position accordingly
 638  *****************************************************************************/
 639 void puzzle_solve_pces_accuracy( filter_t *p_filter) {
 640     filter_sys_t *p_sys = p_filter->p_sys;
 641
 642     p_sys->i_solve_acc_loop++;
 643     if (p_sys->i_solve_acc_loop >= p_sys->s_allocated.i_pieces_nbr) {
 644         p_sys->i_done_count = p_sys->i_tmp_done_count;
 645         p_sys->i_tmp_done_count = 0;
 646         p_sys->i_solve_acc_loop = 0;
 647         p_sys->b_finished = (p_sys->i_done_count == p_sys->s_allocated.i_pieces_nbr);
 648     }
 649
 650     piece_t *ps_piece = &p_sys->ps_pieces[p_sys->i_solve_acc_loop];
 651
 652     ps_piece->b_finished = false;
 653     if (    ps_piece->i_actual_mirror == 1
 654          && abs( ps_piece->i_TRx - ps_piece->i_ORx )  < p_sys->i_magnet_accuracy
 655          && abs( ps_piece->i_TRy - ps_piece->i_OTy )  < p_sys->i_magnet_accuracy
 656          && abs( ps_piece->i_TLx - ps_piece->i_OLx )  < p_sys->i_magnet_accuracy
 657          && abs( ps_piece->i_TLy - ps_piece->i_OTy )  < p_sys->i_magnet_accuracy )
 658     {
 659         uint32_t i_group_ID = ps_piece->i_group_ID;
 660         p_sys->i_tmp_done_count++;
 661
 662         for ( uint32_t i = 0; i < p_sys->s_allocated.i_pieces_nbr; i++) {
 663             ps_piece = &p_sys->ps_pieces[i];
 664             if ( ( ps_piece->i_group_ID == i_group_ID ) && ( !ps_piece->b_finished ) ) {
 665                 ps_piece->ps_piece_in_plane[0].i_actual_x = ps_piece->i_OLx;
 666                 ps_piece->ps_piece_in_plane[0].i_actual_y = ps_piece->i_OTy;
 667                 ps_piece->i_actual_mirror = +1;
 668                 puzzle_calculate_corners( p_filter, i );
 669                 ps_piece->b_finished = true;
 670             }
 671         }
 672     }
 673 }
 674
 675 /*****************************************************************************
 676  * puzzle_sort_layers: sort pieces in order to see in foreground the
 677  *                     standalone ones and those are at the wrong place
 678  *****************************************************************************/
 679 int puzzle_sort_layers( filter_t *p_filter)
 680 {
 681     filter_sys_t *p_sys = p_filter->p_sys;
 682
 683     int32_t i_idx = 0;
 684     for (uint32_t i_qty = 1; i_qty <= p_sys->s_current_param.i_pieces_nbr; i_qty++) {
 685         /* pieces at the wrong place are in foreground */
 686         for (uint32_t i_pce_loop = 0; i_pce_loop < p_sys->s_current_param.i_pieces_nbr; i_pce_loop++) {
 687             uint32_t i_grp = p_sys->ps_pieces[i_pce_loop].i_group_ID;
 688             if ( p_sys->pi_group_qty[i_grp] == (int32_t)i_qty ) {
 689                 bool b_check_ok = true;
 690                 for (int32_t i_pce_check = 0; i_pce_check < i_idx; i_pce_check++)
 691                     if ( p_sys->ps_pieces_tmp[i_pce_check].i_group_ID == i_grp )
 692                         b_check_ok = false;
 693                 if ( b_check_ok )
 694                     for (uint32_t i_pce = i_pce_loop; i_pce < p_sys->s_current_param.i_pieces_nbr; i_pce++)
 695                         if (( p_sys->ps_pieces[i_pce].i_group_ID == i_grp ) && !p_sys->ps_pieces[i_pce].b_finished ) {
 696                             memcpy( &p_sys->ps_pieces_tmp[i_idx], &p_sys->ps_pieces[i_pce], sizeof(piece_t));
 697                             i_idx++;
 698                         }
 699             }
 700         }
 701         /* pieces at the final location are in background */
 702         for (uint32_t i_pce_loop = 0; i_pce_loop < p_sys->s_current_param.i_pieces_nbr; i_pce_loop++) {
 703             uint32_t i_grp = p_sys->ps_pieces[i_pce_loop].i_group_ID;
 704             if ( p_sys->pi_group_qty[i_grp] == (int32_t)i_qty ) {
 705                 bool b_check_ok = true;
 706                 for (int32_t i_pce_check = 0; i_pce_check < i_idx; i_pce_check++)
 707                     if ( p_sys->ps_pieces_tmp[i_pce_check].i_group_ID == i_grp && p_sys->ps_pieces_tmp[i_pce_check].b_finished )
 708                         b_check_ok = false;
 709                 if ( b_check_ok )
 710                     for (uint32_t i_pce = i_pce_loop; i_pce < p_sys->s_current_param.i_pieces_nbr; i_pce++)
 711                         if (( p_sys->ps_pieces[i_pce].i_group_ID == i_grp ) && p_sys->ps_pieces[i_pce].b_finished ) {
 712                             memcpy( &p_sys->ps_pieces_tmp[i_idx], &p_sys->ps_pieces[i_pce], sizeof(piece_t));
 713                             i_idx++;
 714                         }
 715             }
 716         }
 717     }
 718
 719     free( p_filter->p_sys->ps_pieces );
 720     p_filter->p_sys->ps_pieces = p_sys->ps_pieces_tmp;
 721     p_sys->ps_pieces_tmp = malloc( sizeof( piece_t) * p_sys->s_allocated.i_pieces_nbr );
 722     if (!p_sys->ps_pieces_tmp)
 723         return VLC_ENOMEM;
 724
 725     return VLC_SUCCESS;
 726 }
 727
 728 /*****************************************************************************
 729  * puzzle_auto_solve: solve the puzzle depending on auto_solve_speed parameter
 730  *                    = move one piece at the final location each time
 731  *                      auto_solve_countdown is < 0
 732  *****************************************************************************/
 733 void puzzle_auto_solve( filter_t *p_filter)
 734 {
 735     filter_sys_t *p_sys = p_filter->p_sys;
 736
 737     if ( p_sys->s_current_param.i_auto_solve_speed < 500 )
 738         return;
 739
 740     if ( --p_sys->i_auto_solve_countdown_val > 0 )
 741         return;
 742
 743     /* delay reached, preset next delay and proceed with puzzle_auto_solve */
 744     p_sys->i_auto_solve_countdown_val = init_countdown(p_sys->s_current_param.i_auto_solve_speed);
 745
 746     /* random piece to be moved */
 747     int32_t i_start = ((unsigned)vlc_mrand48()) % p_sys->s_allocated.i_pieces_nbr;
 748
 749     /* here the computer will help player by placing the piece at the final location */
 750     for (uint32_t i_l = 0; i_l < p_sys->s_allocated.i_pieces_nbr; i_l++) {
 751         int32_t i = ( i_l + i_start ) % p_sys->s_allocated.i_pieces_nbr;
 752         if ( !p_sys->ps_pieces[i].b_finished ) {
 753             for (uint32_t j = 0; j < p_sys->s_allocated.i_pieces_nbr; j++) {
 754                 if ( p_sys->ps_pieces[j].i_group_ID == p_sys->ps_pieces[i].i_group_ID ) {
 755                     p_sys->ps_pieces[j].i_actual_angle   = 0;
 756                     p_sys->ps_pieces[j].i_actual_mirror  = +1;
 757                     p_sys->ps_pieces[j].ps_piece_in_plane[0].i_actual_x = p_sys->ps_pieces[j].ps_piece_in_plane[0].i_original_x;
 758                     p_sys->ps_pieces[j].ps_piece_in_plane[0].i_actual_y = p_sys->ps_pieces[j].ps_piece_in_plane[0].i_original_y;
 759                     puzzle_calculate_corners( p_filter, j );
 760                 }
 761             }
 762             break;
 763         }
 764     }
 765 }
 766
 767 /*****************************************************************************
 768  * puzzle_auto_shuffle: shuffle the pieces on the desk depending on
 769  *                      auto_shuffle_speed parameter
 770  *                    = random move of one piece each time
 771  *                      auto_shuffle_countdown is < 0
 772  *****************************************************************************/
 773 void puzzle_auto_shuffle( filter_t *p_filter)
 774 {
 775     filter_sys_t *p_sys = p_filter->p_sys;
 776
 777     if ( p_sys->s_current_param.i_auto_shuffle_speed < 500 )
 778         return;
 779
 780     if ( --p_sys->i_auto_shuffle_countdown_val > 0 )
 781         return;
 782
 783     /* delay reached, preset next delay and proceed with puzzle_auto_shuffle */
 784     p_sys->i_auto_shuffle_countdown_val = init_countdown(p_sys->s_current_param.i_auto_shuffle_speed);
 785
 786     /* random piece to be moved */
 787     int32_t i_start = ((unsigned)vlc_mrand48()) % p_sys->s_allocated.i_pieces_nbr;
 788
 789     for (uint32_t i_l = 0; i_l < p_sys->s_allocated.i_pieces_nbr; i_l++){
 790         int32_t i = ( i_l + i_start ) % p_sys->s_allocated.i_pieces_nbr;
 791
 792         /* find one piece which is part of one group */
 793         if ( p_sys->pi_group_qty[p_sys->ps_pieces[i].i_group_ID] > 1 ) {
 794             /* find an empty group to be used by this dismantled piece */
 795             uint32_t i_new_group;
 796             for ( i_new_group = 0 ; i_new_group < p_sys->s_allocated.i_pieces_nbr ; i_new_group ++ )
 797                 if ( p_sys->pi_group_qty[i_new_group] == 0 )
 798                     break;
 799             p_sys->ps_pieces[i].i_group_ID = i_new_group;
 800             p_sys->ps_pieces[i].b_finished = false;
 801
 802             /* random rotate & mirror */
 803             switch ( p_sys->s_current_param.i_rotate )
 804             {
 805               case 1:
 806                     puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 2 ) ) * 2, p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 807                 break;
 808               case 2:
 809                     puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 4 ) ), p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 810                 break;
 811               case 3:
 812                     puzzle_rotate_pce( p_filter, i, (( (unsigned) vlc_mrand48()) % ( 8 ) ), p_sys->ps_pieces[i].i_center_x, p_sys->ps_pieces[i].i_center_y, false );
 813                 break;
 814             }
 815
 816             /* random mvt */
 817             p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_x =
 818                     p_sys->ps_desk_planes[0].i_border_width
 819                     + ( (unsigned) vlc_mrand48()) % ( p_sys->ps_desk_planes[0].i_width - 2*p_sys->ps_desk_planes[0].i_border_width - p_sys->ps_pieces[i].ps_piece_in_plane[0].i_width)
 820                     + p_sys->ps_pieces[i].ps_piece_in_plane[0].i_width / 2 * ( 1 - p_sys->ps_pieces[i].i_step_x_x )
 821                     - (p_sys->ps_pieces[i].ps_piece_in_plane[0].i_lines / 2) * p_sys->ps_pieces[i].i_step_y_x;
 822             p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_y =
 823                     p_sys->ps_desk_planes[0].i_border_lines
 824                     + ( (unsigned) vlc_mrand48()) % ( p_sys->ps_desk_planes[0].i_lines - 2*p_sys->ps_desk_planes[0].i_border_lines - p_sys->ps_pieces[i].ps_piece_in_plane[0].i_lines)
 825                     + p_sys->ps_pieces[i].ps_piece_in_plane[0].i_lines / 2 * ( 1 - p_sys->ps_pieces[i].i_step_y_y )
 826                     - (p_sys->ps_pieces[i].ps_piece_in_plane[0].i_width / 2) * p_sys->ps_pieces[i].i_step_x_y;
 827
 828             /* redefine shapes */
 829             uint32_t i_left_pce  = 0;
 830             uint32_t i_right_pce = 6;
 831             uint32_t i_top_pce   = 2;
 832             uint32_t i_btm_pce   = 4;
 833
 834             uint32_t i_pce = 0;
 835             for (int32_t i_row = 0; i_row < p_sys->s_allocated.i_rows; i_row++)
 836                 for (int32_t i_col = 0; i_col < p_sys->s_allocated.i_cols; i_col++) {
 837                     if (p_sys->ps_pieces[i].i_original_row == p_sys->ps_pieces[i_pce].i_original_row) {
 838                         if (p_sys->ps_pieces[i].i_original_col == p_sys->ps_pieces[i_pce].i_original_col - 1)
 839                             i_right_pce = i_pce;
 840                         else if (p_sys->ps_pieces[i].i_original_col == p_sys->ps_pieces[i_pce].i_original_col + 1)
 841                             i_left_pce = i_pce;
 842                     }
 843                     else if (p_sys->ps_pieces[i].i_original_col == p_sys->ps_pieces[i_pce].i_original_col) {
 844                         if (p_sys->ps_pieces[i].i_original_row == p_sys->ps_pieces[i_pce].i_original_row - 1)
 845                             i_btm_pce = i_pce;
 846                         else if (p_sys->ps_pieces[i].i_original_row == p_sys->ps_pieces[i_pce].i_original_row + 1)
 847                             i_top_pce = i_pce;
 848                     }
 849                     i_pce++;
 850                 }
 851
 852             if ((p_sys->ps_pieces[i].i_left_shape == 0) && (p_sys->ps_pieces[i].i_original_col != 0)) {
 853                 p_sys->ps_pieces[i_left_pce].i_right_shape = 6 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 854                 p_sys->ps_pieces[i].i_left_shape = (p_sys->ps_pieces[i_left_pce].i_right_shape - 6 ) ^ 0x01;
 855             }
 856
 857             if ((p_sys->ps_pieces[i].i_right_shape == 6) && (p_sys->ps_pieces[i].i_original_col != p_sys->s_allocated.i_cols-1)) {
 858                 p_sys->ps_pieces[i].i_right_shape = 6 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 859                 p_sys->ps_pieces[i_right_pce].i_left_shape = (p_sys->ps_pieces[i].i_right_shape - 6 ) ^ 0x01;
 860             }
 861
 862             if ((p_sys->ps_pieces[i].i_top_shape == 2) && (p_sys->ps_pieces[i].i_original_row != 0)) {
 863                 p_sys->ps_pieces[i_top_pce].i_btm_shape = 4 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 864                 p_sys->ps_pieces[i].i_top_shape = (p_sys->ps_pieces[i_top_pce].i_btm_shape - 2 ) ^ 0x01;
 865             }
 866
 867             if ((p_sys->ps_pieces[i].i_btm_shape == 4) && (p_sys->ps_pieces[i].i_original_row != p_sys->s_allocated.i_rows-1)) {
 868                 p_sys->ps_pieces[i].i_btm_shape = 4 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 869                 p_sys->ps_pieces[i_btm_pce].i_top_shape = (p_sys->ps_pieces[i].i_btm_shape - 2 ) ^ 0x01;
 870             }
 871
 872             puzzle_calculate_corners( p_filter, i );
 873             break;
 874         }
 875     }
 876 }
 877
 878 /*****************************************************************************
 879  * puzzle_save: save pieces location in memory
 880  *****************************************************************************/
 881 save_game_t* puzzle_save(filter_t *p_filter)
 882 {
 883     filter_sys_t *p_sys = p_filter->p_sys;
 884
 885     save_game_t *ps_save_game = calloc(1, sizeof(*ps_save_game));
 886     if (!ps_save_game)
 887         return NULL;
 888
 889     ps_save_game->i_cols   = p_sys->s_allocated.i_cols;
 890     ps_save_game->i_rows   = p_sys->s_allocated.i_rows;
 891     ps_save_game->i_rotate = p_sys->s_allocated.i_rotate;
 892
 893     ps_save_game->ps_pieces = calloc( ps_save_game->i_cols * ps_save_game->i_rows , sizeof(*ps_save_game->ps_pieces));
 894     if (!ps_save_game->ps_pieces) {
 895         free(ps_save_game);
 896         return NULL;
 897     }
 898
 899     int32_t i_border_width = p_sys->ps_desk_planes[0].i_border_width;
 900     int32_t i_border_lines = p_sys->ps_desk_planes[0].i_border_lines;
 901
 902     for (int32_t i_pce = 0; i_pce < ps_save_game->i_cols * ps_save_game->i_rows; i_pce++) {
 903         ps_save_game->ps_pieces[i_pce].i_original_row  = p_sys->ps_pieces[i_pce].i_original_row;
 904         ps_save_game->ps_pieces[i_pce].i_original_col  = p_sys->ps_pieces[i_pce].i_original_col;
 905         ps_save_game->ps_pieces[i_pce].i_top_shape     = p_sys->ps_pieces[i_pce].i_top_shape;
 906         ps_save_game->ps_pieces[i_pce].i_btm_shape     = p_sys->ps_pieces[i_pce].i_btm_shape;
 907         ps_save_game->ps_pieces[i_pce].i_right_shape   = p_sys->ps_pieces[i_pce].i_right_shape;
 908         ps_save_game->ps_pieces[i_pce].i_left_shape    = p_sys->ps_pieces[i_pce].i_left_shape;
 909         ps_save_game->ps_pieces[i_pce].f_pos_x         =(p_sys->ps_pieces[i_pce].ps_piece_in_plane[0].i_actual_x - i_border_width ) / ((float)p_sys->ps_desk_planes[0].i_width - 2*i_border_width);
 910         ps_save_game->ps_pieces[i_pce].f_pos_y         =(p_sys->ps_pieces[i_pce].ps_piece_in_plane[0].i_actual_y - i_border_lines ) / ((float)p_sys->ps_desk_planes[0].i_lines - 2*i_border_lines);
 911         ps_save_game->ps_pieces[i_pce].i_actual_angle  = p_sys->ps_pieces[i_pce].i_actual_angle;
 912         ps_save_game->ps_pieces[i_pce].i_actual_mirror = p_sys->ps_pieces[i_pce].i_actual_mirror;
 913     }
 914
 915     return ps_save_game;
 916 }
 917
 918 void puzzle_load( filter_t *p_filter, save_game_t *ps_save_game)
 919 {
 920     filter_sys_t *p_sys = p_filter->p_sys;
 921
 922     if (p_sys->s_current_param.i_cols  != ps_save_game->i_cols
 923         || p_sys->s_allocated.i_rows   != ps_save_game->i_rows
 924         || p_sys->s_allocated.i_rotate != ps_save_game->i_rotate)
 925         return;
 926
 927     int32_t i_border_width = p_sys->ps_desk_planes[0].i_border_width;
 928     int32_t i_border_lines = p_sys->ps_desk_planes[0].i_border_lines;
 929
 930     for (uint32_t i_pce=0; i_pce < p_sys->s_allocated.i_pieces_nbr; i_pce++) {
 931        for (uint32_t i=0; i < p_sys->s_allocated.i_pieces_nbr; i++)
 932             if   ( p_sys->ps_pieces[i].i_original_row == ps_save_game->ps_pieces[i_pce].i_original_row
 933                 && p_sys->ps_pieces[i].i_original_col == ps_save_game->ps_pieces[i_pce].i_original_col  )
 934             {
 935                 p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_x = i_border_width
 936                         + ((float)p_sys->ps_desk_planes[0].i_width - 2 * i_border_width)
 937                         * ps_save_game->ps_pieces[i_pce].f_pos_x;
 938                 p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_y = i_border_lines
 939                         + ((float)p_sys->ps_desk_planes[0].i_lines - 2 * i_border_lines)
 940                         * ps_save_game->ps_pieces[i_pce].f_pos_y;
 941
 942                 p_sys->ps_pieces[i].i_top_shape     =  ps_save_game->ps_pieces[i_pce].i_top_shape;
 943                 p_sys->ps_pieces[i].i_btm_shape     =  ps_save_game->ps_pieces[i_pce].i_btm_shape;
 944                 p_sys->ps_pieces[i].i_right_shape   =  ps_save_game->ps_pieces[i_pce].i_right_shape;
 945                 p_sys->ps_pieces[i].i_left_shape    =  ps_save_game->ps_pieces[i_pce].i_left_shape;
 946                 p_sys->ps_pieces[i].i_actual_angle  =  ps_save_game->ps_pieces[i_pce].i_actual_angle;
 947                 p_sys->ps_pieces[i].i_actual_mirror =  ps_save_game->ps_pieces[i_pce].i_actual_mirror;
 948                 p_sys->ps_pieces[i].i_group_ID     = i_pce;
 949                 p_sys->ps_pieces[i].b_finished     = false;
 950
 951                 p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_x = i_border_width + ((float)p_sys->ps_desk_planes[0].i_width
 952                                                                         - 2*i_border_width) * ps_save_game->ps_pieces[i_pce].f_pos_x;
 953                 p_sys->ps_pieces[i].ps_piece_in_plane[0].i_actual_y = i_border_lines + ((float)p_sys->ps_desk_planes[0].i_lines
 954                                                                         - 2*i_border_lines) * ps_save_game->ps_pieces[i_pce].f_pos_y;
 955                 puzzle_calculate_corners( p_filter, i );
 956
 957                 break;
 958             }
 959     }
 960
 961     for (uint32_t i_pce=0; i_pce < p_sys->s_allocated.i_pieces_nbr; i_pce++) {
 962         /* redefine shapes */
 963         uint32_t i_left_pce  = 0;
 964         uint32_t i_right_pce = 6;
 965         uint32_t i_top_pce   = 2;
 966         uint32_t i_btm_pce   = 4;
 967
 968         uint32_t i_pce_pair = 0;
 969         for (int32_t i_row = 0; i_row < p_sys->s_allocated.i_rows; i_row++)
 970             for (int32_t i_col = 0; i_col < p_sys->s_allocated.i_cols; i_col++) {
 971                 if (p_sys->ps_pieces[i_pce].i_original_row == p_sys->ps_pieces[i_pce_pair].i_original_row) {
 972                     if (p_sys->ps_pieces[i_pce].i_original_col == p_sys->ps_pieces[i_pce_pair].i_original_col - 1)
 973                         i_right_pce = i_pce_pair;
 974                     else if (p_sys->ps_pieces[i_pce].i_original_col == p_sys->ps_pieces[i_pce_pair].i_original_col + 1)
 975                         i_left_pce = i_pce_pair;
 976                 }
 977                 else if (p_sys->ps_pieces[i_pce].i_original_col == p_sys->ps_pieces[i_pce_pair].i_original_col) {
 978                     if (p_sys->ps_pieces[i_pce].i_original_row == p_sys->ps_pieces[i_pce_pair].i_original_row - 1)
 979                         i_btm_pce = i_pce_pair;
 980                     else if (p_sys->ps_pieces[i_pce].i_original_row == p_sys->ps_pieces[i_pce_pair].i_original_row + 1)
 981                         i_top_pce = i_pce_pair;
 982                 }
 983                 i_pce_pair++;
 984             }
 985
 986         if ((p_sys->ps_pieces[i_pce].i_left_shape == 0) && (p_sys->ps_pieces[i_pce].i_original_col != 0)) {
 987             p_sys->ps_pieces[i_left_pce].i_right_shape = 6 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 988             p_sys->ps_pieces[i_pce].i_left_shape = (p_sys->ps_pieces[i_left_pce].i_right_shape - 6 ) ^ 0x01;
 989         }
 990
 991         if ((p_sys->ps_pieces[i_pce].i_right_shape == 6) && (p_sys->ps_pieces[i_pce].i_original_col != p_sys->s_allocated.i_cols-1)) {
 992             p_sys->ps_pieces[i_pce].i_right_shape = 6 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 993             p_sys->ps_pieces[i_right_pce].i_left_shape = (p_sys->ps_pieces[i_pce].i_right_shape - 6 ) ^ 0x01;
 994         }
 995
 996         if ((p_sys->ps_pieces[i_pce].i_top_shape == 2) && (p_sys->ps_pieces[i_pce].i_original_row != 0)) {
 997             p_sys->ps_pieces[i_top_pce].i_btm_shape = 4 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
 998             p_sys->ps_pieces[i_pce].i_top_shape = (p_sys->ps_pieces[i_top_pce].i_btm_shape - 2 ) ^ 0x01;
 999         }
1000
1001         if ((p_sys->ps_pieces[i_pce].i_btm_shape == 4) && (p_sys->ps_pieces[i_pce].i_original_row != p_sys->s_allocated.i_rows-1)) {
1002             p_sys->ps_pieces[i_pce].i_btm_shape = 4 + 8 + 8*(( (unsigned) vlc_mrand48()) % ( SHAPES_QTY ) ) + (vlc_mrand48() & 0x01);
1003             p_sys->ps_pieces[i_btm_pce].i_top_shape = (p_sys->ps_pieces[i_pce].i_btm_shape - 2 ) ^ 0x01;
1004         }
1005
1006     }
1007 }