Des robots en goguette

Des robots en goguette

L'exemple de ce paragraphe illustre l'utilisation d'objets ainsi que la bibliothèque graphique. Nous verrons comment Objective CAML reprend les notions d'héritage simple, d'héritage multiple, de redéfinition de méthode et de liaison dynamique. Nous verrons également comment les classes paramétrées peuvent être mises à profit.

L'application comprend deux catégories principales d'objets : un monde et des robots. Le monde est un ensemble de cases sur lesquelles évoluent des robots. Nous aurons plusieures classes de robots. Chacune d'elles possédera sa propre stratégie de déplacement dans le monde. Le principe d'interaction du monde et des robots est ici extrêmement simple. Le monde est entièrement maître du jeu : il demande tour à tour à chacun des robots qu'il connaît quelle est sa prochaine position. Chaque robot détermine sa prochaine position à l'aveugle : il ne connaît ni la géométrie du monde, ni les autres robots présents. Si la position demandée par un robot est légale et libre alors le monde l'y déplace.

Le monde matérialisera l'évolution des robots par une interface. La complexité (toute relative) de la conception et du développement de cet exemple est dans la toujours nécessaire séparation entre un traitement (ici : l'évolution des robots) et son interface (ici : la trace de cette évolution).

Description générale.

L'application est développée en deux temps.

un ensemble de définitions donnant des classes de calcul pur pour le monde et pour divers robots envisagés.
un ensemble de définitions, utilisant les précédentes et ajoutant ce qui est nécessaire à la mise en place d'une interface. Nous donnerons deux exemples d'interfaces : une rudimentaire sous forme de texte ; une, plus élaborée, utilisant la bibliothèque graphique.

Robots << éthérés >>

Dans un premier temps, nous nous intéressons aux robots hors de toute considération sur l'environnement qui les entourent, c'est à dire de l'interface qui les affiche.

# class virtual robot (i0:int) (j0:int) = 
   object
     val mutable i = i0
     val mutable j = j0
     method get_pos = (i,j)
     method set_pos (i', j') = i <- i'; j <- j'
     method virtual next_pos : unit -> (int * int)
   end  ;;

En toute généralité, un robot est une entité connaissant, ou croyant connaître, sa position (i et j), capable de la donner à qui la lui demande (get_pos), susceptible de modifier cette connaissance si on la lui précise (set_pos) et sachant décider d'un éventuel mouvement vers une nouvelle position (next_pos).

Figure 17.9 : hiérarchie de classes des robots purs

Pour améliorer la lisibilité du programme, nous définissons les mouvements relatifs à une direction absolue :


# type dir = North | East | South | West | Nothing ;;
# let walk (x,y) = function 
     North -> (x,y+1) | South -> (x,y-1)
   | West  -> (x-1,y) | East  -> (x+1,y)
   | Nothing -> (x,y) ;;
val walk : int * int -> dir -> int * int = <fun>
# let turn_right = function 
   North -> East | East -> South | South -> West | West -> North | x -> x ;;
val turn_right : dir -> dir = <fun>

Du schéma induit par la classe virtuelle des robots, nous définissons quatre espèces de robots distinctes (voir la figure 17.9) en précisant leur manière de se déplacer :

les robots fixes qui ne bougent jamais :


# class fix_robot i0 j0 =
   object
     inherit robot i0 j0
     method next_pos() = (i,j)
   end  ;;

les robots fous qui se déplacent au hasard :


# class crazy_robot i0 j0 = 
   object
     inherit robot i0 j0
     method next_pos () = ( i+(Random.int 3)-1 , j+(Random.int 3)-1 ) 
   end ;;

les robots obstinés qui conservent la même direction tant qu'ils peuvent avancer,


# class obstinate_robot i0 j0 =
   object(self)
     inherit robot i0 j0
     val mutable wanted_pos = (i0,j0)
     val mutable dir = West 
 
     method private set_wanted_pos d = wanted_pos <- walk (i,j) d
     method private change_dir = dir <- turn_right dir 
     method next_pos () = if (i,j) = wanted_pos 
       then let np = walk (i,j) dir in ( wanted_pos <- np ; np )
       else ( self#change_dir ; wanted_pos <- (i,j) ; (i,j) )
  end ;;

les robots téléguidés qui obéissent à un opérateur extérieur :


# class virtual interactive_robot i0 j0 =
   object(self)
     inherit robot i0 j0
     method virtual private get_move : unit -> dir
     method next_pos () = walk (i,j) (self#get_move ()) 
    end ;;

Le cas du robot interactif est différent des autres car son comportement est lié à l'interface qui permettra de lui communiquer des ordres. En attendant, nous nous appuyons sur une méthode qui, virtuellement, communique cet ordre et en conséquence la classe interactive_robot demeure abstraite.

Remarquons que non seulement les quatre classes de robots spécialisés héritent de la classe robot mais que de surcroît elles en ont le type. En effet, les seules méthodes que nous ayons ajoutées sont des méthodes privées et donc n'apparaissent pas dans le type des instances de ces classes (voir page ??). Ce point nous est indispensable si nous souhaitons considérer tous les robots comme des objets de même type.

Monde pur

Un monde pur est un monde indépendant de l'interface. Il y est connu l'ensemble des positions qu'un robot est susceptible d'occuper. Cela prend la forme d'une grille de taille l×h, d'une méthode is_legal assurant qu'un couple d'entiers est bien une position dans le monde, et d'une méthode is_free indiquant si un robot occupe ou non une position donnée.

En outre, un monde dispose de la liste des robots présents sur sa surface robots ainsi que d'une méthode add permettant de faire rentrer de nouveaux robots.

Pour finir, un monde est pourvu de la méthode run lui permettant de prendre vie.

# class virtual ['robot_type] world (l0:int) (h0:int) =
   object(self)
     val l = l0
     val h = h0 
     val mutable robots =  ( [] : 'robot_type list )
     method add r = robots <- r::robots
     method is_free p = List.for_all (fun r -> r#get_pos <> p)  robots 
     method virtual is_legal : (int * int) -> bool
 
     method private run_robot r =
       let p = r#next_pos () 
       in if (self#is_legal p) & (self#is_free p) then r#set_pos p
 
     method run () = 
       while true do List.iter (function r -> self#run_robot r) robots done
  end ;;
class virtual ['a] world :
  int ->
  int ->
  object
    constraint 'a =
      < get_pos : int * int; next_pos : unit -> int * int;
        set_pos : int * int -> unit; .. >
    val h : int
    val l : int
    val mutable robots : 'a list
    method add : 'a -> unit
    method is_free : int * int -> bool
    method virtual is_legal : int * int -> bool
    method run : unit -> unit
    method private run_robot : 'a -> unit
  end

Le système de type d'Objective CAML ne permet pas de laisser le type des robots non déterminé (voir page ??). Pour résoudre ce problème, nous avions la possibilité de restreindre ce type à celui de la classe robot. Mais dans ce cas, nous nous interdisions de pouvoir peupler un monde d'autres objets que ceux ayant exactement le même type que robot. Donc, nous avons choisi de paramétrer la classe world par le type des robots qui le peuplent. Nous pourrons ensuite instancier ce paramètre de type par des robots textuels ou par des robots graphiques.

Robots textuels

Des objets texte

Pour obtenir des robots gérables par une interface texte, nous définissons la classe des objets textuels (txt_object).


# class txt_object (s0:string) =
   object
     val name = s0
      method get_name = name
   end  ;;

Une classe de spécification : les robots textuels abstraits

Par héritage double de robots et txt_object, nous obtenons la classe abstraite txt_robot des robots textuels.

# class virtual txt_robot i0 j0 =
   object
     inherit robot i0 j0
     inherit txt_object "Anonymous"
  end  ;;
class virtual txt_robot :
  int ->
  int ->
  object
    val mutable i : int
    val mutable j : int
    val name : string
    method get_name : string
    method get_pos : int * int
    method virtual next_pos : unit -> int * int
    method set_pos : int * int -> unit
  end

Cette classe nous sert pour définir un monde à interface texte (voir page ??). Les habitants de ce monde ne seront ni des objets de txt_robot (puisque cette classe est abstraite) ni des héritiers de cette classe. La classe txt_robots est en quelque sorte une classe de spécification permettant au compilateur d'identifier les types des méthodes (calcul et interface) des habitants du monde à interface texte. L'utilisation d'une telle classe de spécification vient de la séparation que nous voulons maintenir entre les calculs et l'interface.

Les robots concrets en mode texte

Ils s'obtiennent simplement par double héritage; la figure 17.10 donne leur hiérarchie de classes.

Figure 17.10 : hiérarchie de classes des robots en mode texte

# class fix_txt_robot i0 j0 =
   object
     inherit fix_robot i0 j0
     inherit txt_object "Fix robot"
   end  ;;

# class crazy_txt_robot i0 j0 =
   object
     inherit crazy_robot i0 j0
     inherit txt_object "Crazy robot"
   end  ;;

# class obstinate_txt_robot i0 j0 =
   object
     inherit obstinate_robot i0 j0
     inherit txt_object "Obstinate robot"
   end  ;;

Les robots interactifs doivent pour devenir concrets définir leur méthode d'interaction avec l'utilisateur.


# class interactive_txt_robot i0 j0 =
   object
     inherit interactive_robot i0 j0
     inherit txt_object "Interactive robot"
     method private get_move () =
       print_string "Which dir : (n)orth (e)ast (s)outh (w)est ? ";
       match read_line() with
           "n" -> North  | "s" -> South
         | "e" -> East   | "w" -> West
         |  _  -> Nothing
   end ;;

Monde textuel

Le monde à interface texte se dérive du monde pur par

héritage de la classe générique world en instanciant son paramètre de type par la classe de spécification txt_robot,
redéfinition de la méthode run pour y inclure les différents affichages textuels.


# class virtual txt_world (l0:int) (h0:int) =
   object(self)
     inherit [txt_robot] world l0 h0 as super
 
     method private display_robot_pos r = 
       let (i,j) = r#get_pos in Printf.printf "(%d,%d)" i j
 
     method private run_robot r =
      let p = r#next_pos () 
      in if (self#is_legal p) & (self#is_free p) 
         then
           begin
             Printf.printf "%s is moving from " r#get_name ;
             self#display_robot_pos r ;
             print_string " to " ; 
             r#set_pos p;
             self#display_robot_pos r ;
           end
         else
           begin
             Printf.printf "%s is staying at " r#get_name ;
             self#display_robot_pos r 
           end ;
        print_newline () ;
        print_string"next - ";
        ignore (read_line()) 
 
     method run () =
       let print_robot r =
         Printf.printf "%s is at " r#get_name ;
         self#display_robot_pos r ;
         print_newline ()
       in 
          print_string "Initial state :\n";
          List.iter print_robot robots;
          print_string "Running :\n";
          super#run()  (* 1 *)
   end  ;;

Nous attirons l'attention du lecteur sur l'appel à la méthode run de la classe ancêtre (marqué (* 1 *) dans le code) dans la redéfinition de cette même méthode. Nous avons là une illustration des deux types de liaison des méthodes possibles : statique ou dynamique (voir page ??). L'appel à super#run est statique; c'est l'intérêt de nommer la superclasse que de pouvoir appeler ses méthodes alors qu'elles ont été redéfinies. Par contre, dans cette méthode super#run se trouve un appel à self#run_robot. C'est ici une liaison dynamique qui a lieu; c'est la méthode définie dans la classe txt_world qui est exécutée et non celle de world, sans quoi nous n'obtiendrions aucun affichage.

Le monde plan rectangulaire textuel

s'obtient en implantant la dernière méthode encore abstraite : is_legal.


# class closed_txt_world l0 h0 =
   object(self)
     inherit txt_world l0 h0
     method is_legal (i,j) = (0<=i) & (i<l) & (0<=j) & (j<h)
   end  ;;

Figure 17.11 : hiérarchie de classes du monde plan rectangulaire en mode texte

On peut procéder à un petit essai en tapant :


let w = new closed_txt_world 5 5 
and r1 = new fix_txt_robot 3 3 
and r2 = new crazy_txt_robot 2 2 
and r3 = new obstinate_txt_robot 1 1
and r4 = new interactive_txt_robot 0 0
in w#add r1; w#add r2; w#add r3; w#add r4; w#run () ;;

Nous allons passer à présent à la réalisation de l'interface graphique pour notre monde de robots. En fin de course, nous obtiendrons une application ayant l'apparence de la figure 17.12.

Figure 17.12 : Le monde graphique des robots

Robots graphiques

Nous obtenons des robots en mode graphique en suivant le même schéma que le mode texte :

définition d'un objet graphique générique,
définition d'une classe abstraite de robots graphiques par double héritage des robots et des objets graphiques (analogue de la classe de spécification du paragraphe 17),
définition par double héritage des robots possédant un comportement particulier.

Objets graphiques génériques

Un objet graphique simple est un objet possédant une méthode display qui prend en argument les coordonnées d'un pixel et s'affiche.


# class virtual graph_object =
   object
     method virtual display : int -> int -> unit 
   end ;;

De cette spécification, il est possible de tirer des objets graphiques extrêmement complexes. Nous allons nous contenter ici d'une classe graph_item affichant le bitmap qui sert à la construire.

# class graph_item x y im = 
   object (self)
     val size_box_x = x
     val size_box_y = y
     val bitmap = im
     val mutable last = None
 
     method private erase = match last with 
         Some (x,y,img) -> Graphics.draw_image img x y 
       | None -> ()
 
     method private draw i j = Graphics.draw_image bitmap i j 
     method private keep i j =
       last <- Some (i,j,Graphics.get_image i j size_box_x size_box_y) ;
 
     method display i j = match last with 
         Some (x,y,img) -> if x<>i || y<>j 
                           then ( self#erase ; self#keep i j ; self#draw i j )
       | None -> ( self#keep i j ; self#draw i j )
   end ;;

Un objet graph_item conserve la portion d'image sur laquelle il est affiché pour la restaurer lors de l'affichage suivant. De plus, si l'image n'a pas bougé elle n'est pas réaffichée.

# let foo_bitmap =  [|[| Graphics.black |]|] ;;
# class square_item x col = 
   object
     inherit graph_item x x (Graphics.make_image foo_bitmap)
     method private draw i j = Graphics.set_color col ;
                               Graphics.fill_rect (i+1) (j+1) (x-2) (x-2)
   end ;;

# class disk_item r col = 
   object
     inherit graph_item (2*r) (2*r) (Graphics.make_image foo_bitmap)
     method private draw i j = Graphics.set_color col ; 
                               Graphics.fill_circle (i+r) (j+r) (r-2) 
   end ;;

# class file_bitmap_item name =
   let ch = open_in name 
   in let x = Marshal.from_channel ch 
   in let y = Marshal.from_channel ch 
   in let im = Marshal.from_channel ch 
   in let () = close_in ch
   in object 
         inherit graph_item x y (Graphics.make_image im)
      end ;;

Nous avons spécialisé les graph_item en carrés, disques et bitmaps lus depuis un fichier.

Le robot graphique abstrait

est à la fois un robot et un objet graphique.

# class virtual graph_robot i0 j0 =
   object
     inherit robot i0 j0
     inherit graph_object 
   end  ;;

Les robots graphiques fixes, fous et obstinés

sont des objets graphiques spécialisés.

# class fix_graph_robot i0 j0 =
   object
     inherit fix_robot i0 j0
     inherit disk_item 7 Graphics.green
   end ;;

# class crazy_graph_robot i0 j0 =
   object
     inherit crazy_robot i0 j0
     inherit file_bitmap_item "crazy_bitmap" 
    end ;;

# class obstinate_graph_robot i0 j0 =
   object
     inherit obstinate_robot i0 j0
     inherit square_item 15 Graphics.black
   end ;;

Le robot graphique interactif

utilise les primitives key_pressed et read_key du module Graphics pour l'acquisition du déplacement. On reconnaîtra les touches 8, 6, 2 et 4 du pavé numérique (touche NumLock active). De cette façon, l'utilisateur n'est pas obligé de donner une indication de déplacement à chaque interrogation du monde.

# class interactive_graph_robot i0 j0 =
   object
     inherit interactive_robot i0 j0
     inherit file_bitmap_item "interactive_bitmap" 
     method private get_move () = 
       if not (Graphics.key_pressed ()) then Nothing
       else match Graphics.read_key() with
         '8' -> North | '2' -> South | '4' -> West  | '6' -> East | _ -> Nothing
   end ;;

Monde graphique

On obtient un monde à interface graphique par héritage du monde pur en instanciant le paramètre 'a_robot avec la classe abstraite des robots graphiques graph_robot. Comme pour le monde en mode texte, le monde graphique redéfinit la méthode run_robot de traitement d'un robot et la méthode d'activation générale run.

# let delay x = let t = Sys.time () in while (Sys.time ()) -. t < x do () done ;;

# class virtual graph_world l0 h0 =
   object(self)
     inherit [graph_robot] world l0 h0 as super
     initializer 
       let gl = (l+2)*15 and  gh = (h+2)*15 and lw=7 and cw=7
       in Graphics.open_graph (" "^(string_of_int gl)^"x"^(string_of_int gh)) ;
          Graphics.set_color (Graphics.rgb 170 170 170) ;
          Graphics.fill_rect 0 lw gl lw ;
          Graphics.fill_rect (gl-2*lw) 0 lw gh ;
          Graphics.fill_rect 0 (gh-2*cw) gl cw ;
          Graphics.fill_rect lw 0 lw gh 
 
     method run_robot r = let p = r#next_pos () 
                          in delay 0.001 ; 
                             if (self#is_legal p) & (self#is_free p) 
                             then ( r#set_pos p ; self#display_robot r)
 
     method display_robot r = let (i,j) = r#get_pos
                              in r#display (i*15+15) (j*15+15) 
 
     method run() = List.iter self#display_robot robots ;
                    super#run()   
   end ;;

Notez que la fenêtre graphique est créée à l'initialisation d'un objet de cette classe.

Le monde plan rectangulaire et graphique

s'obtient de la même manière que pour le monde plan rectangulaire et textuel.

# class closed_graph_world l0 h0 =
   object(self)
     inherit graph_world l0 h0 
     method is_legal (i,j) = (0<=i) & (i<l) & (0<=j) & (j<h)
   end ;;
class closed_graph_world :
  int ->
  int ->
  object
    val h : int
    val l : int
    val mutable robots : graph_robot list
    method add : graph_robot -> unit
    method display_robot : graph_robot -> unit
    method is_free : int * int -> bool
    method is_legal : int * int -> bool
    method run : unit -> unit
    method run_robot : graph_robot -> unit
  end

On peut alors tester l'application graphique en tapant


let w = new closed_graph_world 10 10 ;;
w#add (new fix_graph_robot 3 3) ;;
w#add (new crazy_graph_robot 2 2) ;;
w#add (new obstinate_graph_robot 1 1) ;; 
w#add (new interactive_graph_robot 5 5) ;;
w#run () ;;

Pour en faire plus

L'implantation de la méthode run_robot des différents mondes sous-entend que les robots sont potentiellement capables de se rendre en tout point du monde du moment que celui-ci est libre et légal. De plus, rien n'interdit à un robot de modifier sa position sans en prévenir le monde. Une amélioration possible consiste à faire gérer l'ensemble des positions des robots par le monde; lors du déplacement d'un robot, le monde vérifie d'une part si la nouvelle position est légale mais aussi si elle constitue un déplacement autorisé. Dans ce cas, le robot devra être capable de demander au monde sa propre position; ce qui entraîne que la classe des robots devra être dépendante de la classe du monde. On pourra définir une classe robot prenant comme paramètre de type une classe de monde.

Cette modification permet alors de définir des robots capables d'interroger le monde qui les entoure et donc de se comporter en fonction de celui-ci. Nous pourrons réaliser des robots qui suivent ou qui fuient d'autres robots, qui tentent de les bloquer, etc. L'étape suivante est de permettre aux robots de communiquer entre eux pour s'échanger des informations et constituer ainsi des équipes de robots.

Les chapitres de la partie suivante de l'ouvrage permettent de libérer l'exécution des robots les unes des autres : soit en ayant recours aux Threads (voir page ??) pour que chacun s'exécute sur un processus distinct, soit en profitant des possibilités de l'informatique distribuée (voir page ??) pour que les robots soient des clients s'exécutant sur des machines distantes qui annoncent leur déplacement ou demandent des informations à un monde qui serait un serveur. Ce problème est traité à la page ??.