searchroad.java

基于J2ME的手机游戏软件。可以控制游戏人物在地图上上下左右行走；可以在地图上放置一颗炸弹

public final class SearchRoad
{
  private static int[][] map;//障碍表
  private static int[][] search_array = new int[200][];//创建一个探索树
  private static int[] id = {-1,1,0,0};
  private static int[] jd = {0,0,-1,1};
  private static int step = 0;//当前深度
//  private static int index = 0;//当前数组的索引值
  private SearchRoad()
  {
  }
  private static int[][] initMap(int[][] smap)
  {
    int[][] buf_map = new int[smap.length][];
    for(int i = 0;i < smap.length;i++)
    {
      buf_map[i] = new int[smap[i].length];
      for(int j = 0;j < smap[i].length;j++)
      {
        if(smap[i][j] == 1 || smap[i][j] == 2)
        {
          buf_map[i][j] = smap[i][j];
        }
        else
        {
          buf_map[i][j] = 0;
        }
      }
    }
    return buf_map;
  }
  private static int[] createNode(int ci,int cj,int si,int sj,int root)//SI和SJ表示从哪一点到达的这一点
  {
    int[] node = new int[7];
    node[0] = root;
    node[1] = ci;
    node[2] = cj;
    for(int i = 0;i < 4;i++)
    {
      if(ci + id[i] == si && cj + jd[i] == sj)
      {
        node[i + 3] = 2;
      }
      else if(map[ci+id[i]][cj+jd[i]] == 0)
      {
        node[i + 3] = 1;
      }
      else
      {
        node[i + 3] = 0;
      }
    }
    return node;
  }
  private static void initSearchArray(int[][] array,int offset,int length)
  {//用给定值填充数组
    if(offset + length > array.length)
    {
      System.out.println("return");
      return;
    }
    for(int i = 0;i < length;i++)
    {
      array[offset + i] = null;
    }
  }
  public static int[][] search(int[][] smap,int si,int sj,int di,int dj)
  {
    map = initMap(smap);//初始化障碍表
    initSearchArray(search_array,0,search_array.length);//清空探索表
    search_array[0] = createNode(si,sj,-100,-100,-1);//创建起点
    if(buildTree(search_array[0],di,dj,0) == false)
    {
      System.out.println("no way!");
      return null;
    }
    int length = 0;
    for(int i = 0;i < search_array.length;i++)
    {
      if(search_array[i] == null)
      {
        break;
      }
      length++;
    }
    int[][] road = new int[length][2];
    for(int i = 0;i < road.length;i++)
    {
      road[i][0] = search_array[i][1];
      road[i][1] = search_array[i][2];
    }
    return road;
  }
  private static boolean buildTree(int[] root,int di,int dj,int index)
  {
    if(root[1] == di && root[2] == dj)
    {
      return true;
    }
    map[root[1]][root[2]] = -1;
    for(int i = 0;i < 4;i++)//四方向遍历
    {
      if(root[i + 3] == 1)//若可以通行
      {
        int ni = root[1] + id[i];
        int nj = root[2] + jd[i];
        search_array[index+1] = createNode(ni,nj,root[1],root[2],index);
        if(buildTree(search_array[index + 1],di,dj,index+1) == false)
        {
          root[i+3] = 2;
          search_array[index+1] = null;
        }
        else
        {
          return true;
        }
      }
    }
    return false;
  }
}