Previous Contents Next

Fancy Robots

The example in this section illustrates the use of objects from the graphics library. We will revisit the concepts of simple inheritance, overriding methods and dynamic dispatch. We also see how parametric classes may be profitably used.

The application recognizes two principal categories of objects: a world and robots. The world represents a state space within which the robots evolve. We will have various classes of robots, each possessing its own strategy to move around in the world.

The principle of interaction between robots and the world here is extremely simple. The world is completely in control of the game: it asks, turn by turn, each of the robots if they know their next position. Each robot determines its next position fairly blindly. They do not know the geometry of the world, nor what other robots may be present. If the position requested by a robot is legal and open, the world will place the robot at that position.

The world displays the evolution of the robots via an interface. The (relative) complexity of the conception and development of this example is in the always-necessary separation between a behavior (here the evolution of the robots) and its interface (here the tracking of this evolution).

General Description
The application is developed in two stages.
  1. A group of definitions providing pure calculation classes for the world and for the diverse set of envisaged robots.

  2. A group of definitions using the preceding set, adding whatever is necessary to add in an interface.

    We provide two examples of such interfaces: a rudimentary text-based interface, and a more elaborate one using a graphical library.
In the first section, we provide the abstract definitions for the robots. Then (page ??), we provide the pure abstract definition for the world. In the next section (page ??), we introduce the text interface for the robots, and in the fourth section (page ??), the interface for the world. On page ?? we introduce a graphical interface for the robots and finally (page ??) we define a world for the graphical interface.

``Abstract'' Robots

The first thing to do is to examine robots abstractly, independent of any consideration of the environment in which they will move, that is to say, the interface that displays them.


# 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 ;;


A robot is an entity which knows, or believes it knows, its position (i and j), is capable of communicating that position to a requester (get_pos), is able to modify this knowledge if it knows precisely where it should be (set_pos) and may decide to move towards a new position (next_pos).



Figure 17.9: Hierarchy of pure robot classes

To improve the readability of the program, we define relative movements based on absolute directions:


# 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>


The schema is shown by the virtual class robots from which we define four distinct species of robots (see figure 17.9) to more precisely see their manner of motion:

The case of the interactive robot is different from the others in that its behavior is controlled by an interface that permits communicating orders to it. To deal with this, we provide a virtual method to communicate this order. As a consequence, the class interactive_robot remains abstract.

Note that not only do the four specialized robot classes inherit from class robot, but also any others that have the same type. In effect, the only methods that we have added are the private methods that therefore do not appear in the type signatures of the instances of these classes (see page ??). This property is indispensable if we wish to consider all the robots to be objects of the same type.

Pure World

A pure world is a world that is independent of an interface. It is understood as the state space of positions which a robot may occupy. It takes the form of a grid of size l × h, with a method is_legal to assure that a coordinate is a valid position in the world, and a method is_free indicates whether or not a robot occupies a given position.

In practice, a world manages the list of robots present on its surface while a method, add, allows new robots to enter the world.

Finally, a world is made visible by the method run, allowing the world to come to life.


# 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


The Objective CAML type system does not permit leaving the types of robots undetermined (see page ??). To resolve this problem, we might consider restraining the type to those of the class robot. But that would forbid populating a world with objects other than those having exactly the same type as robot. As a result, we have instead decided to parameterize world with the type of the robots that populate it. We may thereby instantiate this type parameter with textual robots or graphical robots.

Textual Robots

Text Objects
To obtain robots controllable via a textual interface, we define a class of text objects (txt_object).


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


An Interface Class: Abstract Textual Robots
By double inheritance from robots and txt_object, we obtain the abstract class txt_robot of textual robots.


# 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


This class defines a world with a textual interface (see page ??). The inhabitants of this world will not be objects of txt_robot (since this class is abstract) nor inheritors of this class. The class txt_robot is, in a way, an interface classe permitting the compiler to identify the method types (calculations and interfaces) of the inhabitants of the text interface world. The use of such a specification class provides the separation we wish to maintain between calculations and interface.

Concrete Text Robots
These are simply obtained via double inheritance; figure 17.10 shows the hierarchy of classes.



Figure 17.10: Hierarchy of classes for text mode robots


# 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 ;;


The interactive robots require, for a workable implementation, defining their method of interacting with the user.


# 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 ;;


Textual World

The text interface world is derived from the pure world by:
  1. Inheritance from the generic class world by instantiating its type parameter with the class specified by txt_robot, and

  2. Redefinition of the method run to include the different textual methods.

# 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 ;;


We direct the reader's attention to the call to run of the ancestor class (this method call is marked (* 1 *) in the code) in the redefinition of the same method. There we have an illustration of the two possible types of method dispatch: static or dynamic (see page ??). The call to super#run is static. This is why we name the superclass: to be able to call the methods when they are redefined. On the other hand, in super#run we find a call to self#run_robot. This is a dynamic dispatch; the method defined in class txt_world is executed, not that of world. Were the method from world executed, nothing would be displayed, and the method in txt_world would remain useless.

The planar rectangular text world
is obtained by implementing the final method that still remains abstract: 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: Hierarchy of classes in the textual planar rectangular world

We may proceed with a small essay in typing: 

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 () ;;


We may skip, for the moment, the implementation of a graphical interface for our world of robots. In due course, we will obtain an application having an appearance like figure 17.12.



Figure 17.12: The graphical world of robots

Graphical Robots

We may implement robots in a graphical mode by following the same approach as with the text mode:
  1. define a generic graphical object,
  2. define an abstract class of graphical robots by double inheritance from robots and graphical objects (analogous to the interface class of page ??),
  3. define, through double inheritance, the particular behavior of robots.

Generic Graphical Objects

A simple graphical object is an object possessing a display method which takes, as arguments, the coordinates of a pixel and displays it.


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


From this specification, it would be possible to implement graphical objects with extremely complex behavior. We will content ourselves for now with a class graph_item, displaying a bitmap that serves to represent the object.


# 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 ;;


An object of graph_item stores the portion of the image upon which it is drawn in order to restore it in subsequent redraws. In addition, if the image has not been moved, it will not be redrawn.


# 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 ;;


We specialize the graph_item with instances of crosses, disks, and other bitmaps, read from a file.

The abstract graphical robot
is both a robot and a graphical object. 


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


Graphical robots that are fixed, crazy, and obstinate
are specialized graphical objects.


# 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 ;;


The interactive graphical robot
uses the primitives key_pressed and read_key of module Graphics to determine its next move. We again see the key presses 8, 6, 2 and 4 on the numeric keypad (NumLock button active). In this manner, the user is not obliged to provide direction at each step in the simulation. 


# 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 ;;


Graphical World

We obtain a world with a graphical interface by inheriting from the pure world, instantiating the parameter 'a_robot with the graphical robot abstract class graph_robot. As with the text mode world, the graphical world provides its own method, run_robot, to implement the robot's behavior as well as the general activation method 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 ;;


Note that the graphical window is created at the time that an object of this class is initialized.

The rectangular planar graphical world
is obtained in much the same manner as with the rectangular planar textual world.


# 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


We may then test the graphical application by typing in:


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 () ;;


To Learn More

The implementation of the method run_robot in different worlds suggests that the robots are potentially able to move to any point on the world the moment it is empty and legal. Unfortunately, nothing prevents a robot from modifying its position arbitrarily; the world cannot prevent it. One remedy would consist of having robot positions being controlled by the world; when a robot attempts to move, the world verifies not only that the new position is legal, but also that it constitutes an authorized move. In that case, the robot must be capable of asking the world its actual position, with the result that the robot class must become dependent on the world's class. The robot class would take, as a type parameter, the world class.

This modification permits defining robots capable of querying the world in which they run, thus behaving as dependents of the world. We may then implement robots which follow or avoid other robots, try to block them, and so forth.

Another extension would be to permit robots to communicate with one another, exchanging information, perhaps constituting themselves into teams of robots.

The chapters of the next section allow making execution of robots independent from one another: by making use of Threads (see page ??), each may execute as a distinct process. They may profit from the possibilities of distributed computing (see ??) where the robots become clients executing on remote machines that announce their movements or request other information from a world that behaves as a server. This problem is dealt with on page ??.





Previous Contents Next