贪吃蛇简单AI

随笔,算法 2016-04-19

简单实现了贪吃蛇AI,效果大概能吃90%的食物。先占个坑,后面有兴致再研究下人工智能或者深度学习的实现。

效果

sdf.gif

数据结构

使用双端队列存储蛇体,移动的时候只需要弹出队尾,根据蛇头方向添加新头部。

避免碰撞 

根据游戏经验,后期基本上是首尾相接进行游走。显然,如果每次移动都保证头部和尾部存在一条路径,那么最坏的结果就是一直循环,也就避免了碰撞。

自主游走

蛇的每次移动有三种选择,在保证首尾存在路径的情况下,选择曼哈顿距离减小的方向游走,这样可以尽快吃到食物。如果在曼哈顿距离减小的情况下不存在首尾路径,则尽可能保持原方向(这样可以避免一直拐弯,根据实际运行效果,如果拐弯太多,容易生成一些不可走区域,走进去会走不出来),否则则往存在首尾路径的方向走。

避免死循环

当蛇长占大半部分的空间时,蛇可选择的路线减少,造成蛇头始终跟着蛇尾走,进了死循环。假设首尾相邻,且临近的两个位置有空格,可以尝试判断是否可以将空格移动靠近食物位置。

控制器代码

    private void control() {
        if (food == null)
            return;
        ArrayList<Node> list = new ArrayList<Node>();
        for (Iterator<Node> it = snaker.getDequeIterator(); it.hasNext();) {
            list.add(it.next());
        }
        Node first = list.get(0);
        Node last = list.get(list.size() - 1);
        if (!hadEatFood) {
            list.remove(list.size() - 1);
        }
        boolean vis[][] = new boolean[row][col];
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j) {
                vis[i][j] = false;
            }
        for (int i = 0; i < list.size(); ++i) {
            Node p = list.get(i);
            vis[p.x][p.y] = true;
        }
        if (hadEatFood) {
            for (int i = 0; i < 4; ++i) {
                int nx = last.x + dir[i].getDx();
                int ny = last.y + dir[i].getDy();
                if (isOutOfRange(nx, ny))
                    continue;
                if (vis[nx][ny])
                    continue;
                vis[first.x][first.y] = false;
                if (!hasPath(first.x, first.y, nx, ny, vis)) {
                    vis[first.x][first.y] = true;
                    continue;
                }
                print("Old Last " + vis[last.x][last.y]);
                vis[first.x][first.y] = true;
                last = new Node(nx, ny);
                print("New Last = " + last.toString());
                break;
            }
        }
        // try eat last food
        if (list.size() + 1 == row * col) {
            print("Left Only One Food.");
            for (int i = 0; i < 4; ++i) {
                int nx = first.x + dir[i].getDx();
                int ny = first.y + dir[i].getDy();
                if (nx == food.x && ny == food.y) {
                    snaker.setDirection(dir[i]);
                    return;
                }
            }
        }
        // move empty to food
        double radio = 1.0 * list.size() / (1.0 * row * col);
        if (radio > 0.3
                && Math.abs(first.x - last.x) + Math.abs(first.y - last.y) == 1) {
            if (first.x == last.x) {
                int x = first.x;
                if (food.x < x) {
                    if (x + 1 < row && !vis[x + 1][first.y]
                            && !vis[x + 1][last.y]) {
                        print("Move Right");
                        snaker.setDirection(Direction.RIGHT);
                        return;
                    }
                }
                if (food.x > x) {
                    if (0 < x && !vis[x - 1][first.y] && !vis[x - 1][last.y]) {
                        print("Move Left");
                        snaker.setDirection(Direction.LEFT);
                        return;
                    }
                }
            } else {
                int y = first.y;
                if (food.y < y) {
                    if (y + 1 < col && !vis[first.x][y + 1]
                            && !vis[last.x][y + 1]) {
                        print("Move Down");
                        snaker.setDirection(Direction.DOWN);
                        return;
                    }
                }
                if (food.y > y) {
                    if (0 < y && !vis[first.x][y - 1] && !vis[last.x][y - 1]) {
                        print("Move UP");
                        snaker.setDirection(Direction.UP);
                        return;
                    }
                }
            }
        }
        // random direction
        List<Integer> ind = Arrays.asList(0, 1, 2, 3);
        Collections.shuffle(ind);
        // keep
        for (int i = 0; i < 4; ++i) {
            int d = ind.get(i);
            if (dir[d] != snaker.getDirection())
                continue;
            int nx = first.x + dir[d].getDx();
            int ny = first.y + dir[d].getDy();
            if (isOutOfRange(nx, ny)) {
                continue;
            }
            if (vis[nx][ny]
                    || !(Math.abs(nx - food.x) < Math.abs(first.x - food.x) || Math
                            .abs(ny - food.y) < Math.abs(first.y - food.y))
                    || makeHole(nx, ny, vis)) {
                continue;
            }
            if (hasPath(nx, ny, last.x, last.y, vis)) {
                print("Keep, " + dir[d] + ", " + new Node(nx, ny).toString()
                        + ", " + last.toString());
                snaker.setDirection(dir[d]);
                return;
            }
        }
        // closer
        for (int i = 0; i < 4; ++i) {
            int d = ind.get(i);
            int b = (dir[d].toBinary() << 2) | (dir[d].toBinary() >> 2);
            if ((b & snaker.getDirection().toBinary()) != 0)
                continue;
            int nx = first.x + dir[d].getDx();
            int ny = first.y + dir[d].getDy();
            if (isOutOfRange(nx, ny)) {
                continue;
            }
            if (vis[nx][ny]
                    || !(Math.abs(nx - food.x) < Math.abs(first.x - food.x) || Math
                            .abs(ny - food.y) < Math.abs(first.y - food.y))
                    || makeHole(nx, ny, vis)) {
                continue;
            }
            if (hasPath(nx, ny, last.x, last.y, vis)) {
                print("Closer, " + dir[d] + ", " + new Node(nx, ny).toString()
                        + ", " + last.toString());
                snaker.setDirection(dir[d]);
                return;
            }
        }
        // keep
        for (int i = 0; i < 4; ++i) {
            int d = ind.get(i);
            if (dir[d] != snaker.getDirection())
                continue;
            int nx = first.x + dir[d].getDx();
            int ny = first.y + dir[d].getDy();
            if (isOutOfRange(nx, ny) || vis[nx][ny] || makeHole(nx, ny, vis)) {
                continue;
            }
            if (hasPath(nx, ny, last.x, last.y, vis)) {
                print("Keep, " + dir[d] + ", " + new Node(nx, ny).toString()
                        + ", " + last.toString());
                snaker.setDirection(dir[d]);
                return;
            }
        }
        // away
        for (int i = 0; i < 4; ++i) {
            int d = ind.get(i);
            int b = (dir[d].toBinary() << 2) | (dir[d].toBinary() >> 2);
            if ((b & snaker.getDirection().toBinary()) != 0)
                continue;
            int nx = first.x + dir[d].getDx();
            int ny = first.y + dir[d].getDy();
            if (isOutOfRange(nx, ny) || vis[nx][ny] || makeHole(nx, ny, vis)) {
                continue;
            }
            if (hasPath(nx, ny, last.x, last.y, vis)) {
                print("Away, " + dir[d] + ", " + new Node(nx, ny).toString()
                        + ", " + last.toString());
                snaker.setDirection(dir[d]);
                return;
            }
        }
        // away with blank
        for (int i = 0; i < 4; ++i) {
            int d = ind.get(i);
            int b = (dir[d].toBinary() << 2) | (dir[d].toBinary() >> 2);
            if ((b & snaker.getDirection().toBinary()) != 0)
                continue;
            int nx = first.x + dir[d].getDx();
            int ny = first.y + dir[d].getDy();
            if (isOutOfRange(nx, ny) || vis[nx][ny]) {
                continue;
            }
            if (hasPath(nx, ny, last.x, last.y, vis)) {
                print("Away with blank, " + dir[d] + ", "
                        + new Node(nx, ny).toString() + ", " + last.toString());
                snaker.setDirection(dir[d]);
                return;
            }
        }
        System.out.println("Wrong Step");
    }

本文由 mcginn 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!