Java

动手实现一个迷宫机器人

Posted by maybelence on 2021-09-23

很久没有产出，回过头来看看这些日子，好像又没有什么有趣的技术积累。突然想起来之前帮朋友做了个小作业做的一个迷宫机器人。虽然不高级但是还是挺好玩的。下面就给大家分享一下过程。

地图绘制

首先定义出地图的宽和高，利用一个二维数组来保存地图的地形。 spawnMarker 用于存储机器人出生点位置。 robots 用于存放迷宫中机器人的当前状态。 controller 用于接收键盘/鼠标事件并传给 World。 Renderer 用于将 2D 字符地图渲染成图形。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class World {

    private int width, height;
    private char[][] terrain;
    private final char FIRST_TERRAIN = ' ', LAST_TERRAIN = '~'; //地图上能展示的ASCII 方便用于机器人说话
    private Position[] spawnMarker = new Position[10]; //from digits 0 to 9

    private List<Robot> robots = new ArrayList<>();
    private Controller controller = new Controller(this);
    private Renderer renderer;

    private int targetFrametime = 16;
    private boolean pause = true;
    private long currentFrame = 0;
    private long pauseAtFrame = -1; //will pause if current frame equals this, set to <0 to not use

    private Method work, memoryToString;
}

上述工作做完之后，我们就来看一下如何将下面的 2D 字符渲染成图案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
String mazeMap =

        "###################\n" +
        "#  0H  #   ##    #  $\n" +
        "#  #a ##   ## ## #  #\n" +
        "####p  # #     #   ##\n" +
        "#  yp  #    ## ##   #\n" +
        "#  #  Mid # ##Automn#\n" +
        "#####################";

World world = new World(mazeMap);
Robot robot = makeMazeRunner();
robot.spawnInWorld(world, '0');
world.run();

首先通过 World 的构造函数将地图数据构建出来，并放置机器人出生点，并默认渲染地图数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//constructs the world from the "2D" String
public World(String mapData) {
    this(mapData, true);
}

//you should probably leave shouldRender to true, otherwise you will not see anything
public World(String mapData, boolean shouldRender) {
    if (shouldRender)
        renderer = new Renderer();

    width = mapData.lines().mapToInt(String::length).max().orElseThrow();
    height = (int) mapData.lines().count();

    terrain = new char[width][height];
    String[] rows = mapData.lines().map(s -> s + " ".repeat(width - s.length())).toArray(String[]::new);
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            char c = rows[y].charAt(x);
            if ('0' <= c && c <= '9')
                spawnMarker[c - '0'] = new Position(x + 0.5, y + 0.5);
            terrain[x][y] = c;
        }
    }

    try {
        work = Robot.class.getMethod("work");
        memoryToString = Robot.class.getMethod("memoryToString");
    } catch (NoSuchMethodException e) {
        /* student has not implemented these methods yet */
    }
}

接着通过 World 的 run() 方法来渲染地图数据。具体的 Renderer 类细节就不描述了，整体的源码链接我会贴在文章结尾。渲染后地图大致是这个样子：

image.png

俯视图是这样的：

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void run() {
    if(renderer != null)
        renderer.setup();

    try {
        while (true) {
            if(renderer != null) {
                // wait until unpaused
                while (pause || currentFrame == pauseAtFrame)
                    Thread.sleep(50);

                long before = System.currentTimeMillis();

                simulateFrame();
                renderer.render();

                long frametime = System.currentTimeMillis() - before;
                long sleepTime = targetFrametime - frametime;
                if (sleepTime > 0)
                    Thread.sleep(sleepTime);
            } else
                simulateFrame();
        }
    } catch (InterruptedException e) {
        /* Intentionally left blank */
    }
}

迷宫机器人

接着我们来看 Robot 类。机器人的变量相对而言就变得比较简单，name 和 size 用于描述机器人的姓名大小。 position ，direction ，world 描述机器人当前状态。memory 和 sensors 用于存储机器人的记忆和感知。 todo 和 program 用于存储机器人要做的一系列指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Robot {
 
    private final String name;
    private final double size;

    private Position position = new Position();
    private double direction;
    private World world;

    // memory expand
    private List<Memory<?>> memory = new ArrayList<>();

    // sensor expand
    private List<Sensor<?>> sensors = new ArrayList<>();
    
    private Queue<Command> todo = new ArrayDeque<>();
    private Function<Robot, List<Command>> program = new Function<Robot, List<Command>>() {
        @Override
        public List<Command> apply(Robot robot) {
            List<Command> commands = new ArrayList<>();
            commands.addAll(todo);
            return commands;
        }
    };

}

既然机器人要走迷宫，那走和调整方向的方法肯定是必不可少的。这里 turnBy 表示在当前方向上面顺延多少角度，turnTo 表示直接转向新的方向。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// Pre-programmed Commands
public boolean go(double distance) {
    //step can be negative if the penguin walks backwards
    double sign = Math.signum(distance);
    distance = Math.abs(distance);
    //penguin walks, each step being 0.2m
    while (distance > 0) {
        position.moveBy(sign * Math.min(distance, 0.2), direction);
        world.resolveCollision(this, position);
        distance -= 0.2;
    }
    return true;
}

public boolean turnBy(double deltaDirection) {
    direction += deltaDirection;
    return true;
}

public boolean turnTo(double newDirection) {
    direction = newDirection;
    return true;
}

这里还给机器人加了一个 say 的方法，因为之前 World 中定义了有一些字符在地图中是可以直接打印并且不被渲染的。当机器人走到这个字符上，我希望能够让机器人说出这个字符。因为最后是一个 gui 的打印所以还是调用了 World 中的 say方法来渲染这个字符。

1
2
3
4
public boolean say(String text) {
    world.say(this, text);
    return true;
}

我调整了一下 ASCII 的打印范围，让地图能够顺利渲染出中秋快乐的文字，让我们来看一下这个机器人是如何说出中秋快乐的吧：

中秋2.gif

接下来就开始我们最重要的走迷宫环节啦。在不知道迷宫复杂度的情况，又不能人为预设路线。所以需要我们对于未知路线，如何让机器人做出正确指令有一些思考。

我当时应该是参考了这个图片，但是具体的算法应该还是与这个有些出入的。奈何自己没有做注释，现在都看不懂当时是怎么想的了。所以作为一名 coder，注释真的很重要！
image.png

这是我当时的代码，比较好玩的是，只要地图是可以通向终点的，哪怕地图内部不通，但是多一个口从外部也能连接终点。机器人也是可以找到终点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public static Robot makeMazeRunner() {

    Robot panicPenguin = new Robot("Maze!", 0, 0.5);

    // create memory
    Memory<Character> terrain = panicPenguin.createMemory(new Memory<>("terrain", '0'));
    Memory<Character> end = panicPenguin.createMemory(new Memory<>("end", '$'));
    // create and attach sensors
    panicPenguin.attachSensor(new TerrainSensor().setProcessor(terrain::setData));
    panicPenguin.attachSensor(new TerrainSensor().setProcessor(end::setData));

    // program the robot
    panicPenguin.setProgram(robot -> {
        Position position = robot.getPosition();
        List<Command> commands = new ArrayList<>();

        if (Objects.equals(end.getData().toString(), "$")) {
            return commands;
        }
        switch (dir) {
            case 0:
                if ('#' != robot.getWorld().getTerrain(position.x + 1, position.y)) {
                    commands.add(r -> r.turnTo(0));
                    commands.add(r -> r.say(terrain.getData().toString()));
                    commands.add(r -> r.go(1));
                    dir = 1;
                    return commands;
                } else {
                    if ('#' != robot.getWorld().getTerrain(position.x, position.y - 1)) {
                        commands.add(r -> r.turnTo(1.5 * Math.PI));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        return commands;
                    } else {
                        commands.add(r -> r.turnTo(Math.PI));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        dir = 3;
                        return commands;
                    }
                }
            case 1:
                if ('#' != robot.getWorld().getTerrain(position.x, position.y + 1)) {
                    commands.add(r -> r.turnTo(Math.PI * 0.5));
                    commands.add(r -> r.say(terrain.getData().toString()));
                    commands.add(r -> r.go(1));
                    dir = 2;
                    return commands;
                } else {
                    if ('#' != robot.getWorld().getTerrain(position.x + 1, position.y)) {
                        commands.add(r -> r.turnTo(0));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        return commands;
                    } else {
                        commands.add(r -> r.turnTo(1.5 * Math.PI));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        dir = 0;
                        return commands;
                    }
                }
            case 2:
                if ('#' != robot.getWorld().getTerrain(position.x - 1, position.y)) {
                    commands.add(r -> r.turnTo(Math.PI));
                    commands.add(r -> r.say(terrain.getData().toString()));
                    commands.add(r -> r.go(1));
                    dir = 3;
                    return commands;
                } else {
                    if ('#' != robot.getWorld().getTerrain(position.x, position.y + 1)) {
                        commands.add(r -> r.turnTo(Math.PI * 0.5));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        return commands;
                    } else {
                        commands.add(r -> r.turnTo(0));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        dir = 1;
                        return commands;
                    }
                }
            case 3:
                if ('#' != robot.getWorld().getTerrain(position.x, position.y - 1)) {
                    commands.add(r -> r.turnTo(1.5 * Math.PI));
                    commands.add(r -> r.say(terrain.getData().toString()));
                    commands.add(r -> r.go(1));
                    dir = 0;
                    return commands;
                } else {
                    if ('#' != robot.getWorld().getTerrain(position.x - 1, position.y)) {
                        commands.add(r -> r.turnTo(Math.PI));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        return commands;
                    } else {
                        commands.add(r -> r.turnTo(Math.PI * 0.5));
                        commands.add(r -> r.say(terrain.getData().toString()));
                        commands.add(r -> r.go(1));
                        dir = 2;
                        return commands;
                    }
                }
        }
        return commands;
    });
    return panicPenguin;
}

下面来一起看一下各种好玩的效果图吧。

中秋.gif

中秋3.gif

源码链接

源码链接，祝大家🥮节快乐~

Copyright by @maybelence.

...

...

00:00
00:00
标签
Java
其他常用