gen_solve.java

这是一个可自动生成迷宫、自动或人工寻找迷宫路径的java程序

package maze;

import java.awt.*;
import java.awt.event.*;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2003</p>
 * <p>Company: </p>
 * @author unascribed
 * @version 1.0
 */

public class Gen_Solve {

    public static final int NORTH = 0x01;
    public static final int WEST = 0x02;
    public static final int SOUTH = 0x04;
    public static final int EAST = 0x08;

    public static final int S_NORTH = 0x10;
    public static final int S_WEST = 0x20;
    public static final int S_SOUTH = 0x40;
    public static final int S_EAST = 0x80;

    public static final int W_NORTH = 0x0100;
    public static final int W_WEST = 0x0200;
    public static final int W_SOUTH = 0x0400;
    public static final int W_EAST = 0x0800;

    public static final int WALL = 0x0F;
    public static final int WRONG = 0x0F00;
    public static final int SOLVE = 0xF0;

    public static int istrack = 0;
    public static int isauto = 0;
    public static int nowstart = 1;
    public static int total = 0;

    private Drawer drawer;
    private ControlPanel controlPane;
    private ConDialog mydialog = new ConDialog();
    private int width;
    private int height;
    private int[] data;
    private int[] stack;
    private int [] manstack;
    private int start = -1, end = -1;
    private int stackPointer = -1;
    private int manstackPointer = -1;
    private int delayTime = 100;
    private boolean stop = false;
    private int isover = 0;
    private int lastdirect = -1;
    private int isfirst = 0;

    public Gen_Solve(ControlPanel controlPane, Drawer drawer) {
        this(controlPane.getMazeWidth(), controlPane.getMazeHeight());
        setControlPane(controlPane);
        setDrawer(drawer);
    }

    public Gen_Solve(int width, int height) {
        this.width = width;
        this.height = height;
        data = new int[width * height];
        stack = new int[data.length];
        manstack = new int[data.length];
        manstack[++manstackPointer] = start;
        isfirst = 1;
    }

    private void Setstack(int width, int height) {
        this.width = width;
        this.height = height;
        data = new int[width * height];
        stack = new int[data.length];
        manstack = new int[data.length];
        manstack[++manstackPointer] = start;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }

    public int getData(int x, int y) {
        return data[y * width + x];
    }

    public void setStartEnd() {
        int size = width * height;
        int[] pos = {0, size - width, size - 1, width - 1};
        int i = (int) (Math.random() * 4);
        start = pos[i];
        i += 2;
        if (i > 3) i -= 4;
        end = pos[i];
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    private int getDirection(int pos) {
        int i = 0;
        int[] directions = new int[4];
        int x = pos % width;
        int y = pos / width;
        if (y > 0 && (data[pos - width] & 0x0F) == 0) {
            directions[i++] = NORTH;
        }
        if (x > 0 && (data[pos - 1] & 0x0F) == 0) {
            directions[i++] = WEST;
        }
        if (y < height - 1 && (data[pos + width] & 0x0F) == 0) {
            directions[i++] = SOUTH;
        }
        if (x < width - 1 && (data[pos + 1] & 0x0F) == 0) {
            directions[i++] = EAST;
        }
        if (i == 0) {
            return -1;
        }
        return directions[(int) (Math.random() * i)];
    }

    private int gen_next_step( int pos, int direction) {
        int next;
        switch (direction) {
        case NORTH:
            next = pos - width;
            data[pos] |= NORTH;
            data[next] |= SOUTH;
            break;
        case WEST:
            next = pos - 1;
            data[pos] |= WEST;
            data[next] |= EAST;
            break;
        case SOUTH:
            next = pos + width;
            data[pos] |= SOUTH;
            data[next] |= NORTH;
            break;
        case EAST:
            next = pos + 1;
            data[pos] |= EAST;
            data[next] |= WEST;
            break;
        default:
            throw new RuntimeException("Unknow Error when go (pos = " + pos
                                       + ", direction is " + direction + ")");
        }
        return next;
    }

    public void generate() {
        start = -1;
        end = -1;
        stackPointer = -1;
        manstackPointer = -1;
        stop = false;
        isover = 0;
        lastdirect = -1;
        isauto = 0;
        total = 0;
        width = controlPane.getMazeWidth();
        height =  controlPane.getMazeHeight();
        if(isfirst == 1)
          Setstack(width,height);

        int left = data.length - 1;
        int pos = (int) (Math.random() * left);
        while (left > 0) {
          if (stop) return;
          int direction;
          while ((direction = getDirection(pos)) < 0) {
            pos = stack[stackPointer--];
            if (stackPointer < 0) {
              throw new RuntimeException("Unknowen Error: statck null");
            }
          }
          stack[++stackPointer] = pos;
          pos = gen_next_step(pos, direction);
          left--;
       }
       setStartEnd();
       draw();
    }

    public void solve() {
        istrack = controlPane.isTrack();
        if (start < 0) {
            return;
        }
        stackPointer = -1;
        for(int i=0;i<manstackPointer;i++)
        {
          stack[++stackPointer] = manstack[i];
        }
        new Thread() {
            public void run() {
                int pos = nowstart;
                while (true) {
                    if (stop) return;
                    if (pos == end) {
                       isover = 1;
                       break;
                      }
                      pos = Solve_next_step(pos);

                    if (controlPane != null) {
                        delayTime = controlPane.getSolveDelay();
                    }
                    if (delayTime <= 0) {
                        continue;
                    }

                    draw();
                    try {
                        Thread.sleep(delayTime);
                    } catch (Exception exception) {
                        // Ignore
                    }
                }
                draw();
               if(isover==1) mydialog.show();
            }
        }.start();
    }

    private int solveWrong(int wrongPos) {
        int pos = stack[stackPointer--];
        if (stackPointer < -1) {
            throw new RuntimeException("Unknown Error: statck null");
        }

        data[wrongPos] &= ~SOLVE;
        if (wrongPos == pos - width) {
            data[pos] |= W_NORTH;
            data[pos] &= ~S_NORTH;
            data[wrongPos] |= W_SOUTH;
        } else if (wrongPos == pos - 1) {
            data[pos] |= W_WEST;
            data[pos] &= ~S_WEST;
            data[wrongPos] |= W_EAST;
        } else if (wrongPos == pos + width) {
            data[pos] |= W_SOUTH;
            data[pos] &= ~S_SOUTH;
            data[wrongPos] |= W_NORTH;
        } else if (wrongPos == pos + 1) {
            data[pos] |= W_EAST;
            data[pos] &= ~S_EAST;
            data[wrongPos] |= W_WEST;
        } else {
            throw new RuntimeException("Unkonwn Error: no way!");
        }
        return pos;
    }

    private int Solve_next_step(int pos) {
        int x = pos % width;
        int y = pos / width;
        int next;

        if (y > 0 && (data[pos] & NORTH) > 0){
          next = pos - width;
          if(next == end)
            return next;
        }
        if (x > 0 && (data[pos] & WEST) > 0){
          next = pos - 1;
          if(next == end)
            return next;
        }
        if (y < height - 1 && (data[pos] & SOUTH) > 0){
          next = pos + width;
          if(next == end)
            return next;
        }
        if (x < width - 1 && (data[pos] & EAST) > 0){
          next = pos + 1;
          if(next == end)
            return next;
        }

        if (y > 0 && (data[pos] & NORTH) > 0
            && (data[pos] & W_NORTH) == 0 && (data[pos] & S_NORTH) == 0) {
            next = pos - width;
            data[pos] |= S_NORTH;
            data[next] |= S_SOUTH;
        } else if (x > 0 && (data[pos] & WEST) > 0
                   && (data[pos] & W_WEST) == 0 && (data[pos] & S_WEST) == 0) {
            next = pos - 1;
            data[pos] |= S_WEST;
            data[next] |= S_EAST;
        } else if (y < height - 1 && (data[pos] & SOUTH) > 0
                   && (data[pos] & W_SOUTH) == 0 && (data[pos] & S_SOUTH) == 0) {
            next = pos + width;
            data[pos] |= S_SOUTH;
            data[next] |= S_NORTH;
        } else if (x < width - 1 && (data[pos] & EAST) > 0
                   && (data[pos] & W_EAST) == 0 && (data[pos] & S_EAST) == 0) {
            next = pos + 1;
            data[pos] |= S_EAST;
            data[next] |= S_WEST;
        } else {
            next = solveWrong(pos);
            return next;
        }
        stack[++stackPointer] = pos;
        return next;
    }

    private int man_Solve_next_step(int pos,KeyEvent e) {
      int x = pos % width;
      int y = pos / width;
      int next =-1;
      lastdirect = -1;

      if (y > 0 && (data[pos] & NORTH) > 0 &&(e.getKeyCode()==KeyEvent.VK_W)){
          next = pos - width;
          data[pos] |= S_NORTH;
          data[next] |= S_SOUTH;
          lastdirect = 1;
        }
     else if (x > 0 && (data[pos] & WEST) > 0 &&(e.getKeyCode()==KeyEvent.VK_A)){
          next = pos - 1;
          data[pos] |= S_WEST;
          data[next] |= S_EAST;
          lastdirect = 2;
         }
      else if (y < height - 1 && (data[pos] & SOUTH) > 0 &&(e.getKeyCode()== KeyEvent.VK_S)){
          next = pos + width;
          data[pos] |= S_SOUTH;
          data[next] |= S_NORTH;
          lastdirect = 3;
         }
      else if (x < width - 1 && (data[pos] & EAST) > 0 &&(e.getKeyCode()== KeyEvent.VK_D)){
          next = pos + 1;
          data[pos] |= S_EAST;
          data[next] |= S_WEST;
          lastdirect = 4;
       }
      else
        return -1;
      if(total == 0){
        manstack[++manstackPointer] = pos;
      }
      return next;
    }

    public int man_solve(KeyEvent e,int pos) {
            int nowpos;
            istrack = controlPane.isTrack();
            if (start < 0) {
                return -1;
            }
           if (stop) return -1;
           if (pos == end) {
              mydialog.show();
              return -1;
            }
            nowpos = pos;
            pos = man_Solve_next_step(pos,e);
            total++;
            if(pos == -1) return -1;
            if((manstackPointer > 0) && (pos == manstack[manstackPointer-1])){
             switch(lastdirect){
             case 1://north
               data[pos] &= ~S_SOUTH;
               data[pos] |= W_SOUTH;
               data[nowpos] &= ~S_NORTH;
               data[nowpos] |= W_NORTH;
               draw();
               data[pos] &= ~W_SOUTH;
               data[nowpos] &= ~W_NORTH;
             break;
             case 2:
               data[pos] &= ~S_EAST;
               data[pos] |= W_EAST;
               data[nowpos] &= ~S_WEST;
               data[nowpos] |= W_WEST;
               draw();
               data[pos] &= ~W_EAST;
               data[nowpos] &= ~W_WEST;
             break;
             case 3:
               data[pos] &= ~S_NORTH;
               data[pos] |= W_NORTH;
               data[nowpos] &= ~S_SOUTH;
               data[nowpos] |= W_SOUTH;
               draw();
               data[pos] &= ~W_NORTH;
               data[nowpos] &= ~W_SOUTH;
             break;
             case 4:
               data[pos] &= ~S_WEST;
               data[pos] |= W_WEST;
               data[nowpos] &= ~S_EAST;
               data[nowpos] |= W_EAST;
               draw();
               data[pos] &= ~W_WEST;
               data[nowpos] &= ~W_EAST;
             break;
             }
             manstackPointer--;
            }
            else{
              manstack[++manstackPointer] = pos;
              draw();
            }
            nowstart = pos;
            return pos;
    }

    public void setControlPane(ControlPanel controlPane) {
        this.controlPane = controlPane;
        controlPane.setGenerator(this);
    }

    public void setDrawer(Drawer drawer) {
        this.drawer = drawer;
        drawer.setGenerator(this);
    }

    private void draw() {
        if (drawer == null) return;
        drawer.refreshMaze();
    }

    public void stop() {
        stop = true;
    }

}