cgame.java

A*算法

import java.io.DataInputStream;
import javax.microedition.lcdui.Canvas;
import javax.microedition.lcdui.Graphics;
import javax.microedition.lcdui.Image;
import java.util.*;

/**
 * <p>Title: CGame</p>
 * <p>Description: Game Loop</p>
 * <p>Copyright: CoCoMo Copyright (c) 8/15/2006</p>
 * <p>Company: In-fusio</p>
 * @author CoCoMo(郭昉)
 * @version 1.0
 */

public final class CGame extends Canvas implements Runnable {
  // Control----------------------------------------------------------------------
  static boolean b_running;
  // Screen -------------------------------------------------------------------
  public final static int SCREEN_WIDTH = 240;
  public final static int SCREEN_HEIGHT = 309;
  // State -------------------------------------------------------------------
  public final static int ST_FIRST = 1;
  public final static int ST_INIT = 2;
  public final static int ST_RUN = 3;
  public final static int ST_END = 4;
  public final static int ST_QUIT = 5;

  static byte s_curGameState;
  // Frame -------------------------------------------------------------------
  static long s_curFrameTime;
  // Random -------------------------------------------------------------------
  static Random s_rm;
  // Map -------------------------------------------------------------------
  static int s_mapWidth;
  static int s_mapHeight;
  static int s_tileWidth;
  static int s_tileHeight;
  static int[][] s_mapData;
  Vector s_openList;
  Vector s_closeList;
  Vector s_pathList;

  static int s_startSpot; //x, y
  static int s_endSpot; //x, y

  public CGame() {
    setFullScreenMode(true);
    s_rm = new Random(System.currentTimeMillis());
    b_running = true;
    s_curGameState = ST_FIRST;
  }


  //  -------------------------------------------------------------------
  /** @todo                      Game Part                            */
  //  -------------------------------------------------------------------
  /**
   * paint
   *
   * @param graphics Graphics
   */
  protected void paint(Graphics g) {
    try {
      switch(s_curGameState) {
        case ST_FIRST:
          s_curGameState = ST_INIT;
          break;
        case ST_INIT:
          g.setColor(0);
          g.fillRect(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);
          break;
        case ST_RUN:
          drawMap(g);
          break;
      }
    }
    catch (Exception e) {
      e.printStackTrace();
    }
  }

  /**
   * run
   */
  public void run() {
    try {
      s_curFrameTime = System.currentTimeMillis();

      while(b_running) {
        long d = System.currentTimeMillis() - s_curFrameTime;
        if (d < 60) Thread.sleep(60 - d);
        s_curFrameTime = System.currentTimeMillis();

        updateState();
        repaint();
        serviceRepaints();
      }

      destroyApp();
    }
    catch (Exception e) {
      e.printStackTrace();
    }
  }

  void destroyApp() {
    CMIDlet.App.notifyDestroyed();
    CMIDlet.App.destroyApp(true);
  }

  void quit() {
    b_running = false;
  }

  void updateState() {
    try {
      switch(s_curGameState) {
        case ST_INIT:
          initGame();
          searchPath();
          s_curGameState = ST_RUN;
          break;
      }
    }
    catch (Exception e) {
    }
  }

  void initGame() {
    s_tileWidth = 16;
    s_tileHeight = 16;
    s_mapWidth = SCREEN_WIDTH / s_tileWidth - 1;
    s_mapHeight = SCREEN_HEIGHT / s_tileHeight - 1;

    //map data
    s_mapData = new int[s_mapWidth][s_mapHeight];

    for(int i = 0; i < s_mapData.length; i++) {
      for(int j = 0; j < s_mapData[i].length; j++) {
        if(rand(3) == 0)
          s_mapData[i][j] = -1;
        else
          s_mapData[i][j] = 1;
      }
    }

    //start Spot
    int x = rand(s_mapWidth + 1);
    int y = rand(s_mapHeight + 1);
    while(s_mapData[x][y] < 0) {
      x = rand(s_mapWidth + 1);
      y = rand(s_mapHeight + 1);
    }
    s_startSpot = y * s_mapWidth + x;

    //end Spot
    x = rand(s_mapWidth + 1);
    y = rand(s_mapHeight + 1);
    while(s_mapData[x][y] < 0) {
      x = rand(s_mapWidth + 1);
      y = rand(s_mapHeight + 1);
    }
    s_endSpot = y * s_mapWidth + x;

    s_openList = new Vector();
    s_closeList = new Vector();
    s_pathList = new Vector();
  }

  void drawMap(Graphics g) {
    g.setClip(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);
    g.setColor(0);
    g.fillRect(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);

    g.setColor(0x00ff00);

    int width = s_tileWidth * s_mapWidth;
    int height = s_tileHeight * s_mapHeight;
    //包括边框
    for (int i = 0; i <= s_mapHeight; i++) {
      g.drawLine(0, i * s_tileHeight, width, i * s_tileHeight);
    }

    for (int i = 0; i <= s_mapWidth; i++) {
      g.drawLine(i * s_tileWidth, 0, i * s_tileWidth, height);
    }

    //obstacle
    g.setColor(0x0000ff);
    for (int i = 0; i < s_mapData.length; i++) {
      for (int j = 0; j < s_mapData[i].length; j++) {
        if (s_mapData[i][j] < 0) {
          g.fillRect(i * s_tileWidth + 1, j * s_tileHeight + 1, s_tileWidth - 1,
                     s_tileHeight - 1);
        }
      }
    }

    g.setColor(0x00ff00);
    g.fillRect( (s_startSpot % s_mapWidth) * s_tileWidth + 1,
               (s_startSpot / s_mapWidth) * s_tileHeight + 1, s_tileWidth - 1,
               s_tileHeight - 1);

    g.setColor(0xff0000);
    g.fillRect( (s_endSpot % s_mapWidth) * s_tileWidth + 1,
               (s_endSpot / s_mapWidth) * s_tileHeight + 1,
               s_tileWidth - 1, s_tileHeight - 1);

    g.setColor(0x00ffff);
    //reverse seq
    int size = s_pathList.size();
    for (int i = 1; i < size; i++) {
      CNode node = (CNode) s_pathList.elementAt(i);
      g.fillRect( (node.index % s_mapWidth) * s_tileWidth + 1,
                 (node.index / s_mapWidth) * s_tileHeight + 1,
                 s_tileWidth - 1, s_tileHeight - 1);
    }
  }

  void searchPath() {
    CNode node = new CNode(s_startSpot, 0, 0);
    s_openList.addElement(node);

    boolean endFlag = false;
    while (! (endFlag || s_openList.size() == 0)) {
      node = searchMinF();
      s_openList.removeElement(node);
      s_closeList.addElement(node);

      if(node.index == s_endSpot) {
        endFlag = true;
        break;
      }

      for(int i = 1; i <= 9; i++) {
        int dirX = (i - 1) % 3 - 1;
        int dirY = (i - 1) / 3 - 1;

        int index = node.index + s_mapWidth * dirY +  dirX;
        if (index > 0 && index < s_mapWidth * s_mapHeight) {
          if (! (s_mapData[index % s_mapWidth][index / s_mapWidth] < 0 ||
                 searchCloseList(index) != null)) {
            CNode checkedNode = searchOpenList(index);
            if(checkedNode == null) {
              int curX = index % s_mapWidth;
              int curY = index / s_mapWidth;
              int endX = s_endSpot % s_mapWidth;
              int endY = s_endSpot / s_mapWidth;
              int H = (Math.abs(endX - curX) + Math.abs(endY - curY)) * 10;
              if (Math.abs(dirX) == Math.abs(dirY))
                checkedNode = new CNode(index, node.G + 14, H);
              else
                checkedNode = new CNode(index, node.G + 10, H);
              checkedNode.parent = node;
              s_openList.addElement(checkedNode);
            }
            else {
              int d = checkedNode.index - node.index;
              int g = 0;
              if (d == node.index - s_mapWidth - 1 ||
                  d == node.index - s_mapWidth + 1 ||
                  d == node.index + s_mapWidth - 1 ||
                  d == node.index + s_mapWidth + 1)
                g = node.G + 14;
              else
                g = node.G + 10;

              if(checkedNode.G > g) {
                checkedNode.parent = node;
                checkedNode.G = g;
                checkedNode.F = checkedNode.G + checkedNode.H;
              }
            }
          }
        }
      }
    }

    if(endFlag) {
      node = (CNode) s_closeList.elementAt(s_closeList.size() - 1);
      s_pathList.addElement(node);
      node = node.parent;
      while(node.index != s_startSpot) {
        s_pathList.addElement(node);
        node = node.parent;
      }
    }
  }

  CNode searchMinF() {
    CNode minNode = (CNode) s_openList.elementAt(0);
    int size = s_openList.size();
    for(int i = 0; i < size; i++) {
      CNode node = (CNode) s_openList.elementAt(i);
      if(node.F < minNode.F)
        minNode = node;
    }

    return minNode;
  }

  CNode searchCloseList(int index) {
    CNode node = null;
    int size = s_closeList.size();
    for(int i = 0; i < size; i++) {
      node = (CNode) s_closeList.elementAt(i);
      if(node.index == index)
        return node;
    }
    return null;
  }

  CNode searchOpenList(int index) {
    CNode node = null;
    int size = s_openList.size();
    for(int i = 0; i < size; i++) {
      node = (CNode) s_openList.elementAt(i);
      if(node.index == index)
        return node;
    }
    return null;
  }

  int rand(int num) {
    return Math.abs(s_rm.nextInt()) % num;
  }

  protected void keyPressed(int keyCode) {
  }

  protected void keyReleased(int keyCode) {
  }
}