Chương 10: Grid World, phần 2

Trở về Mục lục bài viết

Phần 2 của nghiên cứu cụ thể GridWorld có sử dụng một số đặc điểm mà ta chưa từng gặp, vì vậy bạn sẽ xem qua bây giờ và seau này sẽ xem xét kĩ hơn. Hãy nhớ lại rằng, bạn có thể tìm tài liệu cho các lớp GridWorld ở http://www.greenteapress.com/thinkapjava/javadoc/gridworld/.

Khi cài đặt GridWorld, bạn sẽ có một thư mục mang tên projects/boxBug, trong đó chứa BoxBug.javaBoxBugRunner.java và BoxBug.gif.

Hãy sao chép những file này vào thư mục hiện thời của bạn rồi nhập chúng vào môi trường phát triển. Có những chỉ dẫn trong tài liệu sau mà bạn có thể tham khảo: http://www.collegeboard.com/prod_downloads/student/testing/ap/compsci_a/ap07_gridworld_installation_guide.pdf.

Sau đây là mã lệnh lấy từ BoxBugRunner.java:

import info.gridworld.actor.ActorWorld; 
import info.gridworld.grid.Location; 
import java.awt.Color; 
public class BoxBugRunner { 
  public static void main(String[] args) { 
    ActorWorld world = new ActorWorld(); 
    BoxBug alice = new BoxBug(6); 
    alice.setColor(Color.ORANGE); 
    BoxBug bob = new BoxBug(3); 
    world.add(new Location(7, 8), alice); 
    world.add(new Location(5, 5), bob); 
    world.show(); 
  } 
}

Ở đây mọi thứ có lẽ đều quen thuộc, ngoại trừ Location, thuộc về GridWorld, và đối tượng này tương đương với java.awt.Point.

BoxBug.java chứa lời định nghĩa lớp cho BoxBug.

public class BoxBug extends Bug { 
  private int steps; 
  private int sideLength; 
  public BoxBug(int length) { steps = 0; sideLength = length; } 
}

Dòng đầu tiên nói rằng lớp này mở rộng Bug, nghĩa là BoxBug là một dạng của Bug.

Hai dòng kế tiếp là những biến thực thể. Từng con Bug có một biến tên là sideLength, để quy định kích thước ô mà nó vẽ nên, và steps, để theo dõi xem con Bug này đi bao nhiêu bước rồi.

Dòng tiếp theo định nghĩa một constructor; đây là một phương thức đặc biệt để khởi tạo biến thực thể. Khi bạn tạo nên một Bug bằng cách kích hoạt new, Java sẽ kích hoạt constructor này.

Tham số cho constructor này là chiều dài cạnh.

Hành vi của Bug được điều khiển bởi phương thức act. Sau đây là phương thức act của BoxBug:

  public void act() { 
    if (steps < sideLength && canMove()) { 
      move(); 
      steps++; 
    } else { 
      turn(); 
      turn(); 
      steps = 0; 
    } 
  }

Nếu BoxBug có thể di chuyển, và chưa thực hiện đủ số bước đi theo yêu cầu, thì nó sẽ di chuyển và đồng thời tăng biến steps.

Nếu nó đụng phải tường hoặc đi hết một cạnh của hộp, thì con bọ sẽ quay 90 độ sang phải đồng thời chỉnh biến steps về 0.

Hãy chạy chương trình và xem nó làm gì. Bạn có thấy được con bọ có hành vi như dự kiến không?

10.1  Con mối

Tôi đã viết ra một lớp có tên Termite để mở rộng Bug và bổ sung khả năng tương tác với những bông hoa. Để chạy được lớp này, bạn hãy tải về những file sau rồi nhập chúng vào môi trường phát triển đang dùng:

http://thinkapjava.com/code/Termite.java
http://thinkapjava.com/code/Termite.gif
http://thinkapjava.com/code/TermiteRunner.java
http://thinkapjava.com/code/EternalFlower.java

Vì Termite mở rộng Bug, tất cả những phương thức của Bug đều hoạt động được với các Termite. Nhưng Termite có thêm những phương thức khác mà Bug không có.

/** 
 * Trả lại true nếu con mối có mang bông hoa.
 */ 
  public boolean hasFlower(); 
/** 
 * Trả lại true nếu con mối quay mặt về phía bông hoa.
 */ 
  public boolean seeFlower(); 
/** 
 * Tạo nên bông hoa trừ khi con mối đã có sẵn một bông.
 */ 
  public void createFlower(); 
/**
 * Bỏ lại bông hoa tại vị trí con mối đang đứng.
 *
 * Lưu ý: trên mỗi ô chỉ có được một vật, bởi vậy hiệu ứng
 * của việc đánh rơi bông hoa sẽ được hoãn lại đến khi con mối di chuyển.
 */ 
  public void dropFlower(); 
/**
 * Ném bông hoa vào chỗ mà con mối đang hướng tới.
 */ 
  public void throwFlower(); 
/**
 * Nhặt bông hoa tại vị trí con mối hướng tới, nếu có,
 * và nếu con mối chưa mang theo hoa.
 */ 
  public void pickUpFlower();

Có những phương thức mà Bug cung cấp một lời định nghĩa này và Termite lại cung cấp cái khác. Trong trường hợp như vậy, phương thức Termite sẽ ghi đè lên phương thức Bug.

Chẳng hạn, Bug.canMove trả lại true nếu có một bông hoa ở vị trí kế tiếp, bởi vậy các có thể Bug có thể giẫm lên Flower. Còn Termite.canMove sẽ trả lại false nếu có bất kì đối tượng nào khác ở vị trí kế tiếp, nên biểu hiện của Termite sẽ khác đi.

Một ví dụ khác, các đối tượng con mối có một phiên bản turn trong đó nhận tham số là số nguyên chỉ độ góc. Sau cùng, đối tượng con mối có randomTurn, với tác dụng quay ngẫu nhiên qua trái hoặc phải với góc quay 45 độ.

Sau đây là mã lệnh từ file TermiteRunner.java:

public class TermiteRunner {
  public static void main(String[] args) {
    ActorWorld world = new ActorWorld();
    makeFlowers(world, 20);
    Termite alice = new Termite();
    world.add(alice);
    Termite bob = new Termite();
    bob.setColor(Color.blue);
    world.add(bob);
    world.show();
  } 
  public static void makeFlowers(ActorWorld world, int n) { 
    for (int i = 0; i<n; i++) { 
      world.add(new EternalFlower());
    }
  }
}

Ở đây mọi thức có lẽ đều quen thuộc. TermiteRunner tạo nên một ActorWorld với 20 EternalFlowers và hai Termite.

Mỗi EternalFlower là một Flower ghi đè lên act sao cho các bông hoa không được tô thẫm đi.

public class EternalFlower extends Flower { 
  public void act() {
  } 
}

Nếu bạn chạy TermiteRunner.java, bạn sẽ thấy hai con mối di chuyển ngẫu nhiên quanh những bông hoa.

MyTermite.java giới thiệu những phương thức tương tác với các bông hoa. Sau đây là lời khai báo lớp này:

public class MyTermite extends Termite { 
  public void act() {
    if (getGrid() == null) 
      return; 
    if (seeFlower()) { 
      pickUpFlower(); 
    } 
    if (hasFlower()) { 
      dropFlower();
    } 
    if (canMove()) {
      move();
    }
    randomTurn();
  }
}

MyTermite mở rộng Termite và ghi đè lên act. Nếu MyTermite thấy một bông hoa, nó sẽ nhặt lên. Nếu có bông hoa rồi, thì nó sẽ bỏ lại bông hoa này.

10.2  Con mối của Langton

Con kiến của Langton là một mô hình đơn giản về biểu hiện của kiến nhưng hiển thị những biểu hiện phức tạp đáng ngạc nhiên. Con kiến sống trong một lưới ô như GridWorld trong đó từng ô có màu trắng hoặc đen. Kiến di chuyển theo những quy tắc sau:

  • Nếu con kiến đứng trên ô trắng; nó quay sang phải, tô màu ô thành đen, rồi tiến bước.
  • Nếu con kiến đứng trên ô đen; nó quay sang trái, tô màu ô thành trắng, rồi tiến bước.

Vì những quy luật này rất đơn giản nên bạn sẽ trông đợi rằng con kiến này sẽ làm những điều đơn giản như chạy vòng quanh hoặc lặp lại một mẫu hình đơn giản. Song nếu kiến ta bắt đầu trên lưới ô toàn màu trắng thì nó sẽ đi hơn 10000 bước theo một dạng mẫu tưởng như ngẫu nhiên trước khi vào một vòng lặp gồm 104 bước.

Bạn có thể đọc thêm về con kiến Langton tại http://en.wikipedia.org/wiki/Langton_ant.

Thật không dễ lập nên con kiến Langton trong GridWorld vì ta không thể đặt màu của các ô. Song thay vào đó, ta có thể dùng những bông hoa để đánh dấu ô. Có điều là ta không thể có đồng thời cả kiến lẫn hoa trên cùng một ô, nên ta không hoàn toàn thực hiện đúng được những quy luật với con kiến.

Thay vào đó ta sẽ tạo nên một con mối có tên LangtonTermite, trong đó dùng seeFlower để kiểm tra xem ô trước mặt có bông hoa không, và nếu ô trước mặt có bông hoa, thì dùng pickUpFlower để hái nó, và throwFlower để đặt hoa xuống ô kế tiếp. Bạn có thể sẽ muốn đọc mã lệnh của những phương thức này để chắc rằng chúng làm gì.

10.3  Bài tập

Bài tập 1   Bây giờ bạn đã biết đủ kiến thức để làm bài tập trong cuốn Sách bài tập (Student Manual), Phần 2. Hãy làm những bài này, rồi xem tiếp những bài lý thú dưới đây.
Bài tập 2   Mục đích của bài tập này là khám phá biểu hiện của các con mối khi tương tác với những bông hoa. Hãy sửa chữa TermiteRunner.java để tạo nên những MyTermite thay vì các Termite. Sau đó chạy lại. MyTermite sẽ chạy vòng quanh  một cách ngẫu nhiên, làm dịch chuyển những bông hoa. Tổng số bông hoa phải không đổi (kể cả những mông mà MyTermite đang giữ). Trong cuốn “Termites, Turtles and Traffic Jams”, Mitchell Resnick đã mô tả một mô hình đơn giản cho biểu hiện của con mối:

  • Nếu bạn thấy bông hoa, hãy nhặt nó lên. Trừ khi bạn đã có hoa rồi; trong trường hợp này thì vứt bỏ bông hoa hiện có.
  • Tiến bước, nếu có thể.
  • Quay sang trái hoặc phải một cách ngẫu nhiên.

Hãy sửa chữa MyTermite.java để thực hiện mô hình này. Theo bạn thì thay đổi trên sẽ có hiệu ứng gì đối với biểu hiện của các MyTermite?

Hãy thử chạy chương trình. Một lần nữa, tổng số bông hoa không đổi, nhưng dần dần hoa sẽ tụ lại thành một số ít các đống, nhiều khi chỉ là một đống.

Biểu hiện này là một thuộc tính nổi, mà bạn có thể tham khảo ở http://en.wikipedia.org/wiki/Emergence. Các con MyTermite tuân theo những quy tắc đơn giản chỉ bằng thông tin quy mô nhỏ, song kết quả sẽ là sự tổ chức có quy mô lớn.

Hãy thử nghiệm với những quy tắc khác nhau và xem chúng có tác động gì lên hệ thống. Những thay đổi nhỏ có thể gây nên kết quả không lường trước!

Bài tập 3

  1. Sao chép lại file Termite.java rồi đặt tên thành LangtonTermite và sao chép TermiteRunner.java thành LangtonRunner.java. Hãy sửa chữa sao cho những định nghĩa lớp có tên trùng với tên file, và do đó LangtonRunner tạo nên một LangtonTermite.
  2. Nếu bạn tạo một file tên là LangtonTermite.gif, GridWorld sẽ dùng nó để biểu diễn cho Termite của bạn. Bạn có thể tải về những ảnh côn trùng đẹp từ http://www.cksinfo.com/animals/insects/realisticdrawings/index.html. Để chuyển chúng về dạng GIF, bạn có thể dùng một ứng dụng như ImageMagick.
  3. Sửa chữa act để thực hiện những quy tắc tương tự cho kiến Langton. Hãy thử những quy tắc khác nhau, và với cả hai góc quay 45 và 90 độ. Hãy tìm những quy tắc để chạy được nhiều ô nhất trước khi con mối bắt đầu chạy vòng.
  4. Để cho mối có đủ chỗ chạy, bạn có thể nới rộng lưới ô hay chuyển sang dùng một UnboundedGrid.
  5. Tạo nên nhiều con LangtonTermite rồi xem chúng tương tác như thế nào.

1 Phản hồi

Filed under Think Java

One response to “Chương 10: Grid World, phần 2

  1. Pingback: Think Java: Cách suy nghĩ như nhà khoa học máy tính | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s