1.原因
前面写过一篇有关贪吃蛇实现的小文《
完全用链表实现的贪吃蛇》,其实现得很统一,几乎完全用链表实现了所有的元素,然而其效率不甚高。该实现虽然津津乐道于没有使用二维数组,然而却大量使用链表,实际上是将二维数组的双for循环换成了大量链表的遍历,虽然由于受到游戏面板长度宽度的限制,算法时间复杂度不会到O(N),但效率仍不敢恭维。
经由验证考研,网上朋友的指点,加之自己的思考,今天重新实现了一版,去除了上一版的“抽象但无用”的“统一于链表”的思想,更多的融入了OO的思想以及一些优化,通篇没有一次遍历整个链表。
2.保留的链表以及更改的数据结构
虽然这一版声明不再使用链表,然而做事不能太极端,我还是保留了freelist链表,因为这在生成食物以及随机障碍物的时候十分有用,否则就要通过下面的算法进行了:
do {
随机生成一个位置
}while (该位置和蛇体冲突);
在长蛇阵的情况下,循环次数将增加。另外保留了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不是我所长,设计加分/计分/排名逻辑也非我所好,就此打住了,不过我深深知道,这种性格是一个人生致命的缺陷
原文链接: https://blog.csdn.net/dog250/article/details/6819996
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/409306
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!