/*                                                                        bai.c
          Using very basic AI techniques                                     */

#include "utilities.h"
#include "data.h"
#include "aiutils.h"
#include "ai.h"

void basic_ai_find_route(city_record *from, city_record *to, int target)
{ float best_solution_length=-1.0;
  int numops=1, numadded;
  state *init_state=new_state(from,to);
  set_of_states *open_set=empty_set();
  add_to_set(open_set,init_state);
  while (!(is_empty_set(open_set)))
  { state *current_state;
    list_of_roads *current_route;
    road_record *last_road_in_route, *this_exit;
    city_record *last_city_reached;
    float length_of_route;
    printf("After %d operations",numops);
    if (best_solution_length>-0.1)
      printf(", shortest route so far %.1f",best_solution_length);
    if (target>=0) printf(", target %d",target);
    printf("\n");
    printf("Size of open set is %d; considering this route:\n",
           size_of_set(open_set));
    current_state=remove_random_member_from_set(open_set);
    current_route=current_state->route;
    print_list_of_roads(current_route);
    length_of_route=current_route->total_length;
    last_road_in_route=last_road_in_list(current_route);
    if (last_road_in_route==NULL)
      last_city_reached=current_state->from;
    else
      last_city_reached=last_road_in_route->end2;
    printf("    length of path to %s is %.1f\n",
           last_city_reached->name,length_of_route);
    this_exit=last_city_reached->roads;
    numadded=0;
    printf("    Adding for later consideration:\n");
    while (this_exit!=NULL)
    { state *newstate;
      float totlen;
      numops+=1;
      newstate=duplicate_state(current_state);
      add_road_to_end_of_list(newstate->route,this_exit);
      totlen=newstate->route->total_length;
      printf("      %s to %s, total %.1f miles\n",
             this_exit->name, this_exit->end2->name, totlen);
      if (this_exit->end2==to)
      { printf("\n*****VIABLE SOLUTION FOUND AFTER %d OPERATIONS, length = %.1f\n", 
               numops, totlen);
        print_list_of_roads(newstate->route);
        if (totlen<best_solution_length || best_solution_length<0)
        { best_solution=newstate;
          best_solution_length=totlen;
          best_solution_time=numops; }
        if (totlen<=target)
        { printf("\n*****TARGET SOLUTION FOUND*****\n");
          return; } }
      add_to_set(open_set, newstate);
      numadded+=1;
      this_exit=this_exit->next; }
    if (numadded==0)
      printf("      <nothing>\n");
    printf("\n");
    press_enter_to_continue(); }
  printf("\nAll Finished.\n"); }