totoxian

浏览: 1034753 次
性别:
来自: 西安

最近访客更多访客>>

u012363178

chen6485

jingyixiushen

wms763660840

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1502)

社区版块

存档分类

高效率的贪吃蛇-Java实现

1.原因

前面写过一篇有关贪吃蛇实现的小文《完全用链表实现的贪吃蛇》，其实现得很统一，几乎完全用链表实现了所有的元素，然而其效率不甚高。该实现虽然津津乐道于没有使用二维数组，然而却大量使用链表，实际上是将二维数组的双for循环换成了大量链表的遍历，虽然由于受到游戏面板长度宽度的限制，算法时间复杂度不会到O(N)，但效率仍不敢恭维。
经由验证考研，网上朋友的指点，加之自己的思考，今天重新实现了一版，去除了上一版的“抽象但无用”的“统一于链表”的思想，更多的融入了OO的思想以及一些优化，通篇没有一次遍历整个链表。

2.保留的链表以及更改的数据结构

虽然这一版声明不再使用链表，然而做事不能太极端，我还是保留了freelist链表，因为这在生成食物以及随机障碍物的时候十分有用，否则就要通过下面的算法进行了：

在长蛇阵的情况下，循环次数将增加。另外保留了deltalist，该链表指示了“哪些位置需要重画”，具体怎么重画和该位置的type属性有关，这就需要更改数据结构。该版贪吃蛇对数据结构进行了大量的封装，访问数据必须通过get/set方法进行，对position类进行了扩充，增加了type位属性，对snake进行了整体封装，不再将蛇链表导入Game_pad中，对于蛇的移动，取消了拐点链表，而是直接将蛇尾删除加入蛇头。

3.代码

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;
class position {
    int x;
    int y;
    int type;
    body belong;
    public static int NOTHING = 0;
    public static int FREE = 0x01;
    public static int SNAKE = 0x02;
    public static int BARRIER = 0x04;
    public static int FOOD = 0x08;
    public static int MASK = 0x0F;
    public position(){}
    public position(int x, int y) {
        this.x = x;
        this.y = y;
        this.type = position.NOTHING;
    }
    public position(int x, int y, int type) {
        this.x = x;
        this.y = y;
        this.type = type;
    }
    public int getType(){
        return this.type;
    }
    public void setType(int type){
        this.type = type;
    }
    public int getX(){
        return this.x;
    }
    public int getY(){
        return this.y;
    }
    public void setBelong(body b){
        this.belong = b;
    }
    public body getBelong(){
        return this.belong;
    }
}
/**
 * 静态数据，保存所有的位置和方向信息
 * 这原本是可以定义到各个使用类内部以内部类实现的
 * @author marywangran
 */
class static_pos {
    public static position LEFT = new position(-1, 0);
    public static position RIGHT = new position(1, 0);
    public static position UP = new position(0, -1);
    public static position DOWN = new position(0, 1);
    public static position HALT = new position(0, 0);

public static position pos[][];
    public static void setpos (int width, int height) {
        int i = 0, j = 0;
        int num = width*height;
        pos = new position[width][height];
        for (i = 0; i < width; i++) {
            for (j = 0; j < height; j++) {
            pos[i][j] = new position(i, j);
            pos[i][j].setType(position.NOTHING);
            }
        }
    }
    public static position go_on(position curr, position direct) {
        return pos[curr.x + direct.x][curr.y + direct.y];
    }
}
/**
 * 游戏中有些元素是链表，定义为body类
 * @author marywangran
 */
class body extends Object{
    position pos;
    position direct;
    public body(){}
    public body (position pos, position direct){
        this.pos = pos;
        this.direct = direct;
    }
    public void setPosition(position pos){
        this.pos = pos;
    }
    public position getPosition(){
        return this.pos;
    }
    public void setDirect(position direct){
        this.direct = direct;
    }
    public position getDirect(){
        return this.direct;
    }
}
/**
 * 将Snake进行了封装，定义其该有的方法
 * @author marywangran
 */
class Snake {
    LinkedList<body> snake_body;
    LinkedList<position> delta_pos;
    body eat = null;
    public static int NOTHING = 0;
    public Snake(int x, int y, int length, position init_dir, int hv) {
        this.delta_pos = new LinkedList();
        this.snake_body = new LinkedList();
        for (int i = 0; i < length; i++){
            position pos = static_pos.pos[x+i][y];
            pos.setType((i == length-1)?position.SNAKE:(position.BARRIER|position.SNAKE));
            body sb = new body(pos, init_dir);
            snake_body.add(0, sb);
            delta_pos.add(sb.getPosition());
        }
    }
    public LinkedList<position> getDeltaList(){
        return this.delta_pos;
    }
    public void removeDeltaList(){
        delta_pos.clear();
    }
    public void snakeGoingOn(){
        int nx = 0, ny = 0, nType;
        position opos, npos;    
        body bf = snake_body.get(0); //得到蛇头
        bf.getPosition().setType(position.BARRIER);
        nx = bf.getPosition().getX() + bf.getDirect().getX();
        ny = bf.getPosition().getY() + bf.getDirect().getY();
        npos = static_pos.pos[nx][ny]; //得到新的蛇头位置
        //得到新位置的Type，看看蛇到底碰到了什么
        nType = (npos.getType()& position.MASK);//&~position.SNAKE;
        if(nType == position.BARRIER){
            System.out.println("over"); //死了，TODO
        } else if ((nType & position.FOOD) != 0) { //吃了食物
            System.out.println("foodx:"+npos.x+":"+npos.y);
            npos.setType(position.FREE|position.SNAKE);
            npos.getBelong().setDirect(bf.getDirect());
            this.snake_body.add(0, npos.getBelong());
            this.eat = npos.getBelong();
        } else { //前行
           body bl = snake_body.remove(snake_body.size()-1);
            opos = bl.getPosition();
            opos.setType(position.FREE);
            static_pos.pos[nx][ny].setType(position.FREE|position.SNAKE);
            bl.setDirect(bf.getDirect());
            bl.setPosition(npos);
            snake_body.add(0, bl);
            delta_pos.add(opos);
        }    
        delta_pos.add(npos);
    }
    public body getEatPending(){
        return this.eat;
    }
    public void clearEat(){
        this.eat = null;
    }
    public void changeDirect(position direct) {
        snake_body.get(0).setDirect(direct);
    }
}
class Snake_Game_Pad {

int curr_status;
    int curr_level;
    int curr_score;
    int width, height;
    Snake snake;
    boolean repaintFood = false;
    LinkedList<position> freelist;
    LinkedList<position> foodlist;
    /**
     * 贪吃蛇游戏初始化
     * @param width            横向元素数量
     * @param height        纵向元素数量
     * @param init_length    初始蛇长度
     */
    public void init(int width, int height, int init_length) {
        this.width = width;
        this.height = height;
        static_pos.setpos(this.width, this.height);
        this.snake = new Snake(10, 10, 1, static_pos.RIGHT, 0);
        this.foodlist = new LinkedList();
        freelist = new LinkedList();
        //初始化障碍position的Type
        for (int i = 0; i < this.width; i++){
            static_pos.pos[i][0].setType(position.BARRIER);
            static_pos.pos[i][this.height-1].setType(position.BARRIER);
        }
        for (int i = 0; i < this.height; i++){
            static_pos.pos[0][i].setType(position.BARRIER);
            static_pos.pos[this.width -1][i].setType(position.BARRIER);
        }
        //初始化freelist
        for (int i = 0; i < this.width; i++){
            for (int j = 0; j < this.height; j++){
                if (static_pos.pos[i][j].getType() == position.NOTHING)
                    freelist.add(static_pos.pos[i][j]);
            }
        }
        random_gen_food ();    
        this.repaintFood = true;
    }
    public void reset() {
        freelist.clear();
        foodlist.clear();
    }
    /**
     * 贪吃蛇主处理函数
     * @return 需要重绘的free_body元素的链表
     */
    LinkedList<position> game_handler() {
        LinkedList<position> delta;
        snake.snakeGoingOn();

//需要将delta中的新蛇体从freelist删除，将新free加入freelist，此处没有做，为一bug
        delta = snake.getDeltaList();
        if (snake.getEatPending() != null){
            position foodeat = snake.getEatPending().getPosition();
            foodlist.remove(foodeat);
            delta.add(foodeat);
            snake.clearEat();
            this.repaintFood = true;
            this.random_gen_food();
        }
        return delta;
    }
    public void afterGoon(){
        snake.removeDeltaList();
    }
    public boolean getEatPending(){
        return this.repaintFood;
    }
    public void clearEatPending(){
        this.repaintFood = false;
    }
    void key_handler (position direct) {
        this.snake.changeDirect(direct);
    }
    /**
     * 该方法没有完全实现，现有的实现很丑陋。TODO
     * 1.将分值设定参数化，策略化，和当前级别联动
     * 2.将超时时间和当前级别以及最近距离联动
     */
    void random_gen_food () {
        Random rand = new Random();
        int rx = rand.nextInt(this.freelist.size()-1);
        position food = this.freelist.get(rx);
        body fb = new body(food, static_pos.HALT);
        fb.getPosition().setType(position.FOOD);
        fb.getPosition().setBelong(fb);
        foodlist.add(fb.getPosition());
    }
    void clearFood(position food){
        foodlist.clear();
    }
}
/**
 * 简单的一个UI，测试用的，十分不完善，什么功能都没有
 * @author marywangran
 */
class GameThread extends JFrame implements KeyListener ,Runnable {
    Snake_Game_Pad game;
    position pos;
    JPanel mainp;
    public GameThread() {
        static_pos.setpos(200,200);
        game = new Snake_Game_Pad();
        game.init(200, 200, 20);    
        mainp=new JPanel();
        mainp.addKeyListener(this);
        mainp.setFocusable(true);
        getContentPane().setLayout(null);
        getContentPane().add(mainp);
        mainp.setBounds(0,0,650,650);
        setSize(650,650);
        setResizable(false);
        setVisible(true);
        new Thread(this).start();
    }
    public void prepaint(){
        Graphics g = mainp.getGraphics();
        this.setBackground(Color.white);
        int i ,j;
        for(i=0;i<600;i+=3)
            for(j=0;j<600;j+=3) {
                g.setColor(Color.green);
                g.fillRect(i,j,3,3);
            }
        g.setColor(Color.blue);
    }
    public void paint(Graphics g) {
        g = mainp.getGraphics();
        
        Iterator<position> pos_iter = game.game_handler().iterator();
        //取得delta链表，仅重画改变了的部分
        while (pos_iter.hasNext()){
            position pos = pos_iter.next();
            if ((pos.getType()&position.SNAKE) != 0){
                g.setColor(Color.blue);
            } else if ((pos.getType()&position.FREE) != 0){
                g.setColor(Color.green);
            }
            g.fillRect(pos.x*3, pos.y*3,3,3);    
        }
        //仅在食物位置发生改变的时候才重画食物，一下子重画所有食物
        if (game.getEatPending()){
            Iterator<position> food_iter = game.foodlist.iterator();    
            while (food_iter.hasNext()){
                position pos = food_iter.next();
                g.setColor(Color.red);
                g.fillRect(pos.x*3, pos.y*3,3,3);    
            }//打印引起的悲哀
            game.clearEatPending();
        }
        game.afterGoon();
    }
    public void run () {
        LinkedList<position> clist = null;
        while (true) {
            try {
                repaint();
                Thread.sleep(100);
            }catch (Exception e) {
                e.printStackTrace();//System.exit(1);
            }
        }
    }
    public void keyPressed(KeyEvent ke) {
    }
    public void keyReleased(KeyEvent ke) {
    }
    public void keyTyped(KeyEvent key) {
        String kv = ""+key.getKeyChar();
        if (kv.equals("w"))
            game.key_handler(static_pos.UP);
        else if (kv.equals("s"))
            game.key_handler(static_pos.DOWN);
        else if(kv.equals("a"))
            game.key_handler(static_pos.LEFT);
        else if(kv.equals("d"))
            game.key_handler(static_pos.RIGHT);
    }
}
public class Main {
    public static void main(String[] args) {
        new GameThread();    
    }
}

这个版本的蛇跑起来的话，CPU利用率大大降低，比完全链表版的提高不少，比完全二维数组版的效率提高更多，虽然完全链表版的理解起来更直观，然而此版本的程序CPU执行起来更轻松，孰重孰轻，还是自己权衡。

这是一个真正可玩的版本，然而到此我就再也做不下去了，GUI不是我所长，设计加分/计分/排名逻辑也非我所好，就此打住了，不过我深深知道，这种性格是一个人生致命的缺陷

分享到：

对于macbook，软件不重要！ | 你需要持续的时间来做事

2011-09-25 16:34
浏览 710
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

高效率的贪吃蛇-Java实现

1.原因

2.保留的链表以及更改的数据结构

3.代码

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

高效率的贪吃蛇-Java实现

1.原因

2.保留的链表以及更改的数据结构

3.代码

评论

发表评论

相关推荐

最近访客更多访客>>