423 |
424 |
424 m->Box[move.box] = newpos; |
425 m->Box[move.box] = newpos; |
425 } |
426 } |
426 |
427 |
427 |
428 |
428 |
429 static void update_depth_counters(const int depth) |
429 static int search_depth(struct Map maps[], int depth, |
430 { |
430 struct BoxMove movements[], |
|
431 int num_movements, float percent, float total_percent) |
|
432 { |
|
433 struct BoxMove new_movements[MAX_MOVES]; |
|
434 int num_new_movements; |
|
435 struct Map *m; |
|
436 int i; |
|
437 float next_percent; |
|
438 |
|
439 next_percent = percent / num_movements; |
|
440 |
|
441 m = &maps[depth+1]; |
|
442 if (depth > max_depth) |
431 if (depth > max_depth) |
443 max_depth = depth; |
432 max_depth = depth; |
444 if (depth > max_depth_period) |
433 if (depth > max_depth_period) |
445 max_depth_period = depth; |
434 max_depth_period = depth; |
446 if (depth < min_depth_period) |
435 if (depth < min_depth_period) |
447 min_depth_period = depth; |
436 min_depth_period = depth; |
448 |
437 } |
449 for (i=0; i < num_movements; i++) |
438 |
450 { |
439 struct Map *all_maps; |
451 CopyMap(m, &maps[depth]); |
440 struct BoxMove *all_movements; /* DEPTH movements of MAX_MOVES */ |
452 force_move_box(m, movements[i]); |
441 int *all_mov_tries; /* The actual step in movements for every depth */ |
453 if (m->NumPlatforms == m->NumBoxesInPlatform) |
442 int *all_mov_max; /* Maximum of movements per all_movement element */ |
454 { |
443 float *percent; |
455 PrintMove(movements[i]); |
444 float *percent_part; |
456 actual_map = &maps[depth+1]; |
445 int depth; |
|
446 |
|
447 int search_loop(const struct Map *origin) |
|
448 { |
|
449 int found; /* bool */ |
|
450 |
|
451 all_maps = malloc(sizeof(*all_maps) * (MAX_STEPS+1)); |
|
452 all_movements = malloc(sizeof(*all_movements)*MAX_MOVES*(MAX_STEPS+1)); |
|
453 all_mov_tries = malloc(sizeof(*all_mov_tries)*(MAX_STEPS+1)); |
|
454 all_mov_max = malloc(sizeof(*all_mov_max)*(MAX_STEPS+1)); |
|
455 percent = malloc(sizeof(*percent)*(MAX_STEPS+1)); |
|
456 percent_part = malloc(sizeof(*percent)*(MAX_STEPS+1)); |
|
457 |
|
458 |
|
459 if (load_state()) |
|
460 { |
|
461 --depth; |
|
462 if (all_mov_tries[depth] != 0) |
|
463 all_mov_tries[depth] = 0; |
|
464 } else |
|
465 { |
|
466 depth = 0; |
|
467 CopyMap(&all_maps[0], origin); |
|
468 all_mov_max[0] = get_box_movements(&all_maps[0], &all_movements[0]); |
|
469 assert(all_mov_max[0] < MAX_MOVES); |
|
470 assert(all_mov_max[0] > 0); |
|
471 percent[0] = 0.; |
|
472 percent_part[0] = 100.; |
|
473 all_mov_tries[0] = 0; |
|
474 } |
|
475 |
|
476 |
|
477 found = 0; |
|
478 do |
|
479 { |
|
480 struct BoxMove *new_movements = &all_movements[(depth+1)*MAX_MOVES]; |
|
481 struct BoxMove *movements = &all_movements[depth*MAX_MOVES]; |
|
482 int num_movements = all_mov_max[depth]; |
|
483 int *num_new_movements = &all_mov_max[depth+1]; |
|
484 int *step = &all_mov_tries[depth]; |
|
485 struct Map *new_map = &all_maps[depth+1]; |
|
486 |
|
487 update_depth_counters(depth); |
|
488 |
|
489 percent_part[depth+1] = percent_part[depth] / num_movements; |
|
490 |
|
491 CopyMap(new_map, &all_maps[depth]); |
|
492 |
|
493 /* DEBUG */ |
|
494 #if DEBUG |
|
495 ShowMap(new_map); |
|
496 show_tries(depth); |
|
497 printf("Nummovs[%i]: %i\n", depth, num_movements); |
|
498 printf("Step[%i]: %i\n", depth, *step); |
|
499 #endif |
|
500 |
|
501 /* Now four things can happen: |
|
502 * - look for depth + 1 |
|
503 * - keep looking for movements in depth |
|
504 * - go one depth back. |
|
505 * - solve the puzle */ |
|
506 |
|
507 /* Go one depth back */ |
|
508 if (*step >= num_movements) |
|
509 { |
|
510 --depth; |
|
511 continue; |
|
512 } |
|
513 |
|
514 force_move_box(new_map, movements[(*step)]); |
|
515 |
|
516 ++(*step); |
|
517 |
|
518 /* Solve the puzzle */ |
|
519 if (new_map->NumPlatforms == new_map->NumBoxesInPlatform) |
|
520 { |
|
521 PrintMoves(all_movements, all_mov_tries, depth+1); |
|
522 actual_map = &all_maps[depth+1]; |
457 show_percent_and_map(); |
523 show_percent_and_map(); |
458 return 0; |
524 save_state(); |
459 } |
525 found = 1; |
460 |
526 } |
461 if (is_new_map(maps, depth+1)) |
527 |
462 { |
528 if (is_new_map(all_maps, depth+1)) |
463 num_new_movements = get_box_movements(m, new_movements); |
529 { |
464 assert(num_new_movements < MAX_MOVES); |
530 *num_new_movements = |
|
531 get_box_movements(new_map, new_movements); |
|
532 assert(*num_new_movements < MAX_MOVES); |
465 } |
533 } |
466 else |
534 else |
467 num_new_movements = 0; |
535 *num_new_movements = 0; |
468 |
536 |
469 if (num_new_movements == 0) |
537 percent[depth] = percent[depth] + percent_part[depth+1]; |
470 { |
538 percent_to_show = percent[depth]; |
471 percent_to_show = total_percent + next_percent*i; |
539 |
|
540 /* Keep looking for movements in depth */ |
|
541 if (*num_new_movements == 0) |
|
542 { |
472 depth_to_show = depth; |
543 depth_to_show = depth; |
473 actual_map = &maps[depth]; |
544 actual_map = &all_maps[depth]; |
474 #ifdef DEBUG /* to be out */ |
545 continue; |
475 show_percent_and_map(); |
546 } |
476 #endif |
547 |
477 |
548 /* Look for depth + 1*/ |
478 } |
549 if (depth+1 < MAX_STEPS) |
479 else |
550 { |
480 { |
551 percent[depth+1] = percent[depth]; |
481 if (depth+1 < MAX_STEPS) |
552 all_mov_tries[depth+1] = 0; |
482 { |
553 ++depth; |
483 if(search_depth(maps, depth+1, new_movements, |
554 } |
484 num_new_movements, next_percent, |
555 } while(!found && depth >= 0); |
485 total_percent + next_percent*i) == 0) |
556 free(all_maps); |
486 { |
557 free(all_movements); |
487 PrintMove(movements[i]); |
558 free(all_mov_tries); |
488 actual_map = &maps[depth+1]; |
559 free(all_mov_max); |
489 show_percent_and_map(); |
560 |
490 return 0; |
561 return found; |
491 } |
|
492 } |
|
493 } |
|
494 } |
|
495 return 1; |
|
496 } |
562 } |
497 |
563 |
498 |
564 |
499 int solve_map(const struct Map *origin) |
565 int solve_map(const struct Map *origin) |
500 { |
566 { |
501 struct Map *maps; |
|
502 struct BoxMove new_movements[MAX_MOVES]; |
567 struct BoxMove new_movements[MAX_MOVES]; |
503 int num_new_movements; |
568 int num_new_movements; |
504 int ret; |
569 int ret; |
505 |
570 |
506 maps = malloc(sizeof(*maps) * (MAX_STEPS+1)); |
|
507 |
|
508 CopyMap(&maps[0], origin); |
|
509 |
|
510 num_new_movements = get_box_movements(&maps[0], new_movements); |
|
511 assert(num_new_movements < MAX_MOVES); |
|
512 assert(num_new_movements > 0); |
|
513 |
|
514 init_os(); |
571 init_os(); |
515 |
572 |
516 ret = search_depth(maps, 0, new_movements, |
573 ret = search_loop(origin); |
517 num_new_movements, 100. / num_new_movements, |
574 |
518 0); |
|
519 free(maps); |
|
520 return ret; |
575 return ret; |
521 } |
576 } |