movepath.java

MegaMek is a networked Java clone of BattleTech, a turn-based sci-fi boardgame for 2+ players. Fight

     * Changes turn-forwards-opposite-turn sequences into quad lateral shifts.
     * <p/>
     * Finds the sequence of three steps that can be transformed, then removes
     * all three and replaces them with the lateral shift step.
     */
    private void transformLateralShift() {
        if (steps.size() < 3) {
            return;
        }
        int index = steps.size() - 3;
        MoveStep step1 = getStep(index);
        MoveStep step2 = getStep(index + 1);
        MoveStep step3 = getStep(index + 2);

        if (step1.oppositeTurn(step3)
            && (step2.getType() == MovePath.STEP_BACKWARDS || step2.getType() == MovePath.STEP_FORWARDS)) {
            int stepType = step1.getType();
            int direction = step2.getType();
            // remove all old steps
            steps.removeElementAt(index);
            steps.removeElementAt(index);
            steps.removeElementAt(index);
            // add new step
            MoveStep shift = new MoveStep(this, lateralShiftForTurn(stepType, direction));
            addStep(shift);
        }
    }

    /**
     * Returns the lateral shift that corresponds to the turn direction
     */
    public static int lateralShiftForTurn(int turn, int direction) {
        if (direction == MovePath.STEP_FORWARDS) {
            switch (turn) {
                case MovePath.STEP_TURN_LEFT :
                    return MovePath.STEP_LATERAL_LEFT;
                case MovePath.STEP_TURN_RIGHT :
                    return MovePath.STEP_LATERAL_RIGHT;
                default :
                    return turn;
            }
        }
		switch (turn) {
		    case MovePath.STEP_TURN_LEFT :
		        return MovePath.STEP_LATERAL_LEFT_BACKWARDS;
		    case MovePath.STEP_TURN_RIGHT :
		        return MovePath.STEP_LATERAL_RIGHT_BACKWARDS;
		    default :
		        return turn;
		}
    }

    /**
     * Returns the turn direction that corresponds to the lateral shift
     */
    static int turnForLateralShift(int shift) {
        switch (shift) {
            case MovePath.STEP_LATERAL_LEFT :
                return MovePath.STEP_TURN_LEFT;
            case MovePath.STEP_LATERAL_RIGHT :
                return MovePath.STEP_TURN_RIGHT;
            case MovePath.STEP_LATERAL_LEFT_BACKWARDS :
                return MovePath.STEP_TURN_LEFT;
            case MovePath.STEP_LATERAL_RIGHT_BACKWARDS :
                return MovePath.STEP_TURN_RIGHT;
            default :
                return shift;
        }
    }

    /**
     * Returns the direction (either MovePath.STEP_TURN_LEFT or
     * STEP_TURN_RIGHT) that the destination facing lies in.
     */
    public static int getDirection(int facing, int destFacing) {
        final int rotate = (destFacing + (6 - facing)) % 6;
        return rotate >= 3 ? STEP_TURN_LEFT : STEP_TURN_RIGHT;
    }

    /**
     * Returns the adjusted facing, given the start facing.
     */
    public static int getAdjustedFacing(int facing, int movement) {
        if (movement == STEP_TURN_RIGHT) {
            return (facing + 1) % 6;
        } else if (movement == STEP_TURN_LEFT) {
            return (facing + 5) % 6;
        }
        return facing;
    }

    /**
     * Returns the number of MPs used in the path
     */
    public int getMpUsed() {
        if (getLastStep() != null) {
            return getLastStep().getMpUsed();
        }
        return 0;
    }

    /**
     * Returns the logical number of hexes moved
     * the path (does not count turns, etc).
     */
    public int getHexesMoved() {
        if (getLastStep() == null) {
            return 0;
        }
        return getLastStep().getDistance();
    }

    public boolean isJumping() {
        if (steps.size() > 0) {
            return getStep(0).getType() == MovePath.STEP_START_JUMP;
        }
        return false;
    }

    /**
     * Extend the current path to the destination <code>Coords</code>.
     *
     * @param   dest the destination <code>Coords</code> of the move.
     * @param   type the type of movment step required.
     */
    public void findPathTo(Coords dest, int type) {
        int timeLimit = PreferenceManager.getClientPreferences().getMaxPathfinderTime();

        if (timeLimit >= 5000) {
            System.out.print("WARNING!!!  Settings allow up to ");
            System.out.print(timeLimit);
            System.out.println(" milliseconds to find the optimum path!");
        }
        this.notSoLazyPathfinder(dest, type, timeLimit);
    }

    public boolean isMoveLegal() {
        // Moves which end up off of the board are not legal.
        if (!game.getBoard().contains(getFinalCoords())) {
            return false;
        }

        if (getLastStep() == null) {
            return true;
        }
        if (getLastStep().getMovementType()==STEP_CHARGE) {
            return getSecondLastStep().isLegal();
        }
        return getLastStep().isLegal();
    }

    /**
     * An A* pathfinder to get from the end of the current path
     * (or entity's position if empty) to the destination.
     *
     * @param dest The goal hex
     * @param type The type of move we want to do
     * @param timeLimit the maximum <code>int</code> number of
     *          milliseconds to take hunting for an ideal path.
     */
    private void notSoLazyPathfinder(final Coords dest, final int type, final int timeLimit) {
        long endTime = System.currentTimeMillis() + timeLimit;

        int step = type;
        if (step != MovePath.STEP_BACKWARDS) {
            step = MovePath.STEP_FORWARDS;
        }

        MovePathComparator mpc = new MovePathComparator(dest, step == MovePath.STEP_BACKWARDS);

        MovePath bestPath = (MovePath) this.clone();

        HashMap discovered = new HashMap();
        discovered.put(bestPath.getKey(), bestPath);

        ArrayList candidates = new ArrayList();
        candidates.add(bestPath);

        boolean keepLooping = this.getFinalCoords().distance(dest) > 1;
        int loopcount = 0;

        while (candidates.size() > 0 && keepLooping) {
            MovePath candidatePath = (MovePath) candidates.remove(0);
            Coords startingPos = candidatePath.getFinalCoords();
            int startingElev = candidatePath.getFinalElevation();
            
            if (candidatePath.getFinalCoords().distance(dest) == 1) {
                bestPath = candidatePath;
                keepLooping = false;
                break;
            }

            Iterator adjacent = candidatePath.getNextMoves(step == STEP_BACKWARDS, step == STEP_FORWARDS).iterator();
            while (adjacent.hasNext()) {
                MovePath expandedPath = (MovePath) adjacent.next();

                if (expandedPath.getLastStep().isMovementPossible(this.game, startingPos, startingElev)) {
                    MovePath found = (MovePath) discovered.get(expandedPath.getKey());
                    if (found != null && mpc.compare(found, expandedPath) <= 0) {
                        continue;
                    }
                    int index = Collections.binarySearch(candidates, expandedPath, mpc);
                    if (index < 0) {
                        index = -index - 1;
                    }
                    candidates.add(index, expandedPath);
                    discovered.put(expandedPath.getKey(), expandedPath);
                    if (candidates.size() > 100) {
                        candidates.remove(candidates.size() - 1);
                    }
                }
            }
            loopcount++;
            if (loopcount % 256 == 0 && keepLooping && candidates.size() > 0) {
                MovePath front = (MovePath)candidates.get(0);
                if (front.getFinalCoords().distance(dest) < bestPath.getFinalCoords().distance(dest)) {
                    bestPath = front;
                    keepLooping = System.currentTimeMillis() < endTime;
                } else {
                    keepLooping = false;
                }
            }
        } //end while

        if (getFinalCoords().distance(dest) > bestPath.getFinalCoords().distance(dest)) {
            //Make the path we found, this path.
            this.steps = bestPath.steps;
        }
        if (!getFinalCoords().equals(dest)) {
            lazyPathfinder(dest, type);
        }
    }
    
    /**
     * Find the shortest path to the destination <code>Coords</code> by
     * hex count.  This right choice <em>only</em> when making a simple
     * move like a straight line or one with a single turn.
     *
     * @param   dest the destination <code>Coords</code> of the move.
     * @param   type the type of movment step required.
     */
    private void lazyPathfinder(Coords dest, int type) {
        int step = STEP_FORWARDS;
        if (type == STEP_BACKWARDS) {
            step = STEP_BACKWARDS;
        }
        Coords subDest = dest;
        if (!dest.equals(getFinalCoords())) {
            subDest = dest.translated(dest.direction(getFinalCoords()));
        }

        while (!getFinalCoords().equals(subDest)) {
            // adjust facing
            rotatePathfinder((getFinalCoords().direction(subDest)
                              + (step == STEP_BACKWARDS ? 3 : 0)) % 6);
            // step forwards
            addStep(step);
        }
        rotatePathfinder((getFinalCoords().direction(dest)
                          + (step == STEP_BACKWARDS ? 3 : 0)) % 6);
        if (!dest.equals(getFinalCoords())) {
            addStep(type);
        }
    }

    /**
     * Returns a list of possible moves that result in a
     * facing/position/(jumping|prone) change, special steps (mine clearing and
     * such) must be handled elsewhere.
     */
    public List getNextMoves(boolean backward, boolean forward) {
        ArrayList result = new ArrayList();
        MoveStep last = getLastStep();
        if (isJumping()) {
            MovePath left = (MovePath) this.clone();
            MovePath right = (MovePath) this.clone();

            // From here, we can move F, LF, RF, LLF, RRF, and RRRF.
            result.add( ((MovePath) this.clone())
                        .addStep(MovePath.STEP_FORWARDS) );
            for ( int turn = 0; turn < 2; turn++ ) {
                left.addStep(MovePath.STEP_TURN_LEFT);
                right.addStep(MovePath.STEP_TURN_RIGHT);
                result.add( ((MovePath) left.clone())
                            .addStep(MovePath.STEP_FORWARDS) );
                result.add( ((MovePath) right.clone())
                            .addStep(MovePath.STEP_FORWARDS) );
            }
            right.addStep(MovePath.STEP_TURN_RIGHT);
            result.add( right.addStep(MovePath.STEP_FORWARDS) );

            // We've got all our next steps.            
            return result;
        }
        if (getFinalProne() || getFinalHullDown()) {
            if (last != null && last.getType() != STEP_TURN_RIGHT) {
                result.add(((MovePath) this.clone()).addStep(MovePath.STEP_TURN_LEFT));
            }
            if (last != null && last.getType() != STEP_TURN_LEFT) {
                result.add(((MovePath) this.clone()).addStep(MovePath.STEP_TURN_RIGHT));
            }
            result.add(((MovePath) this.clone()).addStep(MovePath.STEP_GET_UP));
            return result;
        }
        if (canShift()) {
            if (forward && (!backward || (last == null || last.getType() != MovePath.STEP_LATERAL_LEFT))) {
                result.add(((MovePath) this.clone()).addStep(STEP_LATERAL_RIGHT));
            }
            if (forward && (!backward || (last == null || last.getType() != MovePath.STEP_LATERAL_RIGHT))) {
                result.add(((MovePath) this.clone()).addStep(MovePath.STEP_LATERAL_LEFT));
            }
            if (backward && (!forward || (last == null || last.getType() != MovePath.STEP_LATERAL_LEFT_BACKWARDS))) {
                result.add(((MovePath) this.clone()).addStep(MovePath.STEP_LATERAL_RIGHT_BACKWARDS));
            }
            if (backward && (!forward || (last == null || last.getType() != MovePath.STEP_LATERAL_RIGHT_BACKWARDS))) {
                result.add(((MovePath) this.clone()).addStep(MovePath.STEP_LATERAL_LEFT_BACKWARDS));
            }
        }
        if (forward && (!backward || (last == null || last.getType() != MovePath.STEP_BACKWARDS))) {
            result.add(((MovePath) this.clone()).addStep(MovePath.STEP_FORWARDS));
        }
        if (last == null || last.getType() != MovePath.STEP_TURN_LEFT) {
            result.add(((MovePath) this.clone()).addStep(MovePath.STEP_TURN_RIGHT));
        }
        if (last == null || last.getType() != MovePath.STEP_TURN_RIGHT) {
            result.add(((MovePath) this.clone()).addStep(MovePath.STEP_TURN_LEFT));
        }
        if (backward && (!forward || (last == null || last.getType() != MovePath.STEP_FORWARDS))) {
            result.add(((MovePath) this.clone()).addStep(MovePath.STEP_BACKWARDS));
        }
        return result;
    }

    /**
     * Clones this path, will contain a new clone of the steps
     * so that the clone is independent from the original.
     *
     * @return the cloned MovePath
     */
    public Object clone() {
        MovePath copy = new MovePath(this.game, this.entity);
        copy.steps = (Vector) steps.clone();
        return copy;
    }

    /**
     * Rotate from the current facing to the destination facing.
     */
    public void rotatePathfinder(int destFacing) {
        while (getFinalFacing() != destFacing) {
            int stepType = getDirection(getFinalFacing(), destFacing);
            addStep(stepType);
        }
    }

    protected static class MovePathComparator implements Comparator {
        private Coords destination;
        boolean backward;

        public MovePathComparator(Coords destination, boolean backward) {
            this.destination = destination;
            this.backward = backward;
        }

        public int compare(Object o1, Object o2) {
            MovePath first = (MovePath) o1;
            MovePath second = (MovePath) o2;

            int firstDist = first.getMpUsed() + first.getFinalCoords().distance(destination) + getFacingDiff(first);
            int secondDist = second.getMpUsed() + second.getFinalCoords().distance(destination) + getFacingDiff(second);
            return firstDist - secondDist;
        }

        private int getFacingDiff(MovePath first) {
            if (first.isJumping()) {
                return 0;
            }
            int firstFacing = Math.abs((first.getFinalCoords().direction(destination) + (backward?3:0))%6 - first.getFinalFacing());
            if (firstFacing > 3) {
                firstFacing = 6 - firstFacing;
            }
            if (first.canShift()) {
                firstFacing = Math.max(0, firstFacing - 1);
            }
            return firstFacing;
        }
    }
}