Сначала создайте Черную доску (здесь должна быть ссылка на сайт), которая является объектом, в который кто угодно может записывать информацию. Эта обычная черная доска рисует лабиринт и используется в качестве информации о структуре лабиринта, приходящей обратно от крыс, которые исследуют его.
Теперь создайте сам лабиринт. Как и в реальном лабиринте, этот объект показывает очень мало информации о себе - получая координаты, он может сказать вам в каком месте стена или проход по четырем направлениям в ближайшем окружении этой координаты, и не более того. Для начинающих, прочтите лабиринт из текстового файла, но сначала найдите в Интернете алгоритм генерации лабиринта. В любом случае, в результате должен получится объект, которому передаются координаты лабиринта, и который сообщает о стенах и проходах вокруг этой координаты. Также вы должны быть способны спросить его относительно точки входа в лабиринт.
И, наконец, создайте класс Крысы исследующей лабиринт. Каждая крыса может общаться с черной доской, получая текущую информацию о координатах, и с лабиринтом, запрашивая новую информацию, основываясь на текущем положении крысы. Однако, каждый раз, когда крыса достигает разветвления, она создает новую крысу, чтобы каждая из них шла по своей ветке. Каждая крыса ограничена своей собственной ниткой (процессом). Когда крыса достигает тупика, она умирает, сообщив результат своего исследования черной доске.
Цель работы - получить полную карту лабиринта, но вы сначала должны также определить будет ли условием окончания реальное прохождение лабиринта или черная доска должна быть ответственна за решение.
Вот вам пример реализации от Джереми Майера (Jeremy Meyer):
//: projects:Maze.java
package projects;
import java.util.*;
import java.io.*;
import java.awt.*;
public class Maze extends Canvas {
private Vector lines; // a line is a char array
private int width = -1;
private int height = -1;
public static void main(String[] args) throws IOException {
if (args.length < 1) {
System.out.println("Enter filename");
System.exit(0);
}
Maze m = new Maze();
m.load(args[0]);
Frame f = new Frame();
f.setSize(m.width * 20, m.height * 20);
f.add(m);
Rat r = new Rat(m, 0, 0);
f.setVisible(true);
}
public Maze() {
lines = new Vector();
setBackground(Color.lightGray);
}
synchronized public boolean isEmptyXY(int x, int y) {
if (x < 0)
x += width;
if (y < 0)
y += height;
// Use mod arithmetic to bring rat in line:
byte[] by = (byte[]) (lines.elementAt(y % height));
return by[x % width] == ' ';
}
synchronized public void setXY(int x, int y, byte newByte) {
if (x < 0)
x += width;
if (y < 0)
y += height;
byte[] by = (byte[]) (lines.elementAt(y % height));
by[x % width] = newByte;
repaint();
}
public void load(String filename) throws IOException {
String currentLine = null;
BufferedReader br = new BufferedReader(new FileReader(filename));
for (currentLine = br.readLine(); currentLine != null; currentLine = br
.readLine()) {
lines.addElement(currentLine.getBytes());
if (width < 0 || currentLine.getBytes().length > width)
width = currentLine.getBytes().length;
}
height = lines.size();
br.close();
}
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
int canvasHeight = this.getBounds().height;
int canvasWidth = this.getBounds().width;
if (height < 1 || width < 1)
return; // nothing to do
int width = ((byte[]) (lines.elementAt(0))).length;
for (int y = 0; y < lines.size(); y++) {
byte[] b;
b = (byte[]) (lines.elementAt(y));
for (int x = 0; x < width; x++) {
switch (b[x]) {
case ' ': // empty part of maze
g.setColor(Color.lightGray);
g.fillRect(x * (canvasWidth / width), y
* (canvasHeight / height), canvasWidth / width,
canvasHeight / height);
break;
case '*': // a wall
g.setColor(Color.darkGray);
g.fillRect(x * (canvasWidth / width), y
* (canvasHeight / height),
(canvasWidth / width) - 1,
(canvasHeight / height) - 1);
break;
default: // must be rat
g.setColor(Color.red);
g.fillOval(x * (canvasWidth / width), y
* (canvasHeight / height), canvasWidth / width,
canvasHeight / height);
break;
}
}
}
}
} // /:~//: projects:Rat.java
package projects;
public class Rat {
static int ratCount = 0;
private Maze prison;
private int vertDir = 0;
private int horizDir = 0;
private int x, y;
private int myRatNo = 0;
public Rat(Maze maze, int xStart, int yStart) {
myRatNo = ratCount++;
System.out.println("Rat no." + myRatNo + " ready to scurry.");
prison = maze;
x = xStart;
y = yStart;
prison.setXY(x, y, (byte) 'R');
new Thread() {
public void run() {
scurry();
}
}.start();
}
public void scurry() {
// Try and maintain direction if possible.
// Horizontal backward
boolean ratCanMove = true;
while (ratCanMove) {
ratCanMove = false;
// South
if (prison.isEmptyXY(x, y + 1)) {
vertDir = 1;
horizDir = 0;
ratCanMove = true;
}
// North
if (prison.isEmptyXY(x, y - 1))
if (ratCanMove)
new Rat(prison, x, y - 1);
// Rat can move already, so give
// this choice to the next rat.
else {
vertDir = -1;
horizDir = 0;
ratCanMove = true;
}
// West
if (prison.isEmptyXY(x - 1, y))
if (ratCanMove)
new Rat(prison, x - 1, y);
// Rat can move already, so give
// this choice to the next rat.
else {
vertDir = 0;
horizDir = -1;
ratCanMove = true;
}
// East
if (prison.isEmptyXY(x + 1, y))
if (ratCanMove)
new Rat(prison, x + 1, y);
// Rat can move already, so give
// this choice to the next rat.
else {
vertDir = 0;
horizDir = 1;
ratCanMove = true;
}
if (ratCanMove) { // Move original rat.
x += horizDir;
y += vertDir;
prison.setXY(x, y, (byte) 'R');
} // If not then the rat will die.
try {
Thread.sleep(2000);
}
catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
System.out.println("Rat no." + myRatNo
+ " can't move..dying..aarrgggh.");
}
} // /:~Файл инициализации лабиринта:
//:! projects:Amaze.txt
* ** * * ** *
*** * ******* * ****
*** ***
***** ********** *****
* * * * ** ** * * * ** *
* * * * ** * * * * **
* ** * **
* ** * ** * ** * **
*** * *** ***** * *** **
* * * * * *
* ** * * * ** * *
///:~Другие ресурсы относительно лабиринтов
Обсуждение алгоритмов создания лабиринтов и их реализации на Java (с исходниками):
http://www.mazeworks.com/mazegen/mazegen.htm
Обсуждение алгоритмов обнаружения коллизий и других индивидуальных/групповых перемещений для автономных физических объектов:
http://www.red3d.com/cwr/steer/
| ← | Проекты | XML Декоратор | → |