Battleship Game - Random Ship Placement

user_12724216 0
Viewed 467

I have to do a Battleship game. The game should have some kind of AI. The AI CAN place ships with a hard coded pattern, but i want to take things a step further and make the ship placement random.

I have implemented a "trial and error" method, where ships get randomly placed on the field with a random rotation, until the algorithm runs out of either ships to be placed or fields to place the ships in. In the second case the recursive implementation allows to try out other ship/field/rotation combos, until the first condition is reached. So to speak: try all possible ship/rotation/field combo's (picked randomly) until you find one valid one, where all ships are placed.

As you can imagine, this is a terrible effort, when it comes to runtime. The size of the "board" can be 5x5 up to 30x30 with exactly 30% of the fields beeing occupied by a ship.

Now, Runtime isn't my concern for sizes up to 14x14, but then runtime increases so badly, that i have to think of a way to reduce runtime.

Any suggestions? (I would like to get general thinking advice/idea's, not code)

In case, my explenation wasn't enough: Here's the class that tries to place the ships on the field:

public class RandomShipFactory {

    private int size;
    private Game game;
    private ArrayList<Ship> toBeCheckedShips = new ArrayList<Ship>();
    private ArrayList<Position> toBeCheckedPositions = new ArrayList<Position>();
    
    public RandomShipFactory(int size, Game game) {
        this.size = size;
        this.game = game;
        this.toBeCheckedShips.addAll(game.ownBoard.getShips());
        
        for(int i = 0; i < this.size; i++) {
            for(int j = 0; j < this.size; j++) {
                this.toBeCheckedPositions.add(new Position(i,j));
            }
        }
    }
    
    public void makeRandomShipPlacements() {
        this.makeRandomShipPlacements(this.toBeCheckedPositions, this.toBeCheckedShips);
        game.ownBoard.printBoard();
    }
    
    private boolean makeRandomShipPlacements(ArrayList<Position> currentPositions, ArrayList<Ship> currentShips) {
        if(currentPositions.isEmpty()) {
            return false;
        }
        
        ArrayList<Position> checkedPositionsInThisRun = new ArrayList<Position>();

        Random r = new Random();
        boolean success = false;
        
        while(!success && !currentShips.isEmpty() && !currentPositions.isEmpty()) {
            int randomPositionIndex = r.nextInt(currentPositions.size());
            Position randomPosition = currentPositions.remove(randomPositionIndex);
            checkedPositionsInThisRun.add(randomPosition);
            
            ArrayList<Ship> currentShipQueue = new ArrayList<Ship>();
            currentShipQueue.addAll(currentShips);
            while(!success && !currentShipQueue.isEmpty()) {
                Ship currentShip = currentShipQueue.remove(0);
                
                boolean shouldRotate = r.nextBoolean();
                if(shouldRotate) {
                    currentShip.rotate();
                }
                
                boolean canPlaceShip = this.game.placeShipOnOwnBoard(currentShip, randomPosition.x, randomPosition.y);
                if(canPlaceShip) {
                    currentShips.remove(currentShip);
                    ArrayList<Position> boxPositions = removeBoxSquarePositions(currentPositions, currentShip, randomPosition);
                    
                    if(currentShips.isEmpty()) {
                        success = true;
                    }else {
                        boolean recursiveSuccess = this.makeRandomShipPlacements(currentPositions, currentShips);
                        if(!recursiveSuccess) {
                            this.game.removeShipFromOwnBoard(currentShip);
                            currentPositions.addAll(boxPositions);
                            currentShips.add(currentShip);
                        }else {
                            success = true;
                        }
                    }
                }else {
                    currentShip.rotate();
                    
                    canPlaceShip = this.game.placeShipOnOwnBoard(currentShip, randomPosition.x, randomPosition.y);
                    if(canPlaceShip) {
                        currentShips.remove(currentShip);
                        ArrayList<Position> boxPositions = removeBoxSquarePositions(currentPositions, currentShip, randomPosition);
                        
                        if(currentShips.isEmpty()) {
                            success = true;
                        }else {
                            boolean recursiveSuccess = this.makeRandomShipPlacements(currentPositions, currentShips);
                            if(!recursiveSuccess) {
                                this.game.removeShipFromOwnBoard(currentShip);
                                currentPositions.addAll(boxPositions);
                                currentShips.add(currentShip);
                            }else {
                                success = true;
                            }
                        }
                    }
                }
            }
        }
        
        currentPositions.addAll(checkedPositionsInThisRun);
        return success;
    }
    
    private ArrayList<Position> removeBoxSquarePositions(ArrayList<Position> positionList, Ship ship, Position pos) {
        ArrayList<Position> boxPositions = new ArrayList<Position>();
        for(int i = 0; i < ship.length + 2; i++) {
            for(int j = 0; j < 3; j++) {
                int nextX, nextY;
                
                switch(ship.getRotation()) {
                case HORIZONTAL:
                    nextX = pos.x - 1 + i;
                    nextY = pos.y - 1 + j;
                    break;
                case VERTICAL:
                    nextX = pos.x - 1 + j;
                    nextY = pos.y - 1 + i;
                    break;
                default:
                    nextX = pos.x - 1 + j;
                    nextY = pos.y - 1 + i;
                    break;
                }
                
                if(nextX >= 0 && nextX < this.size && nextY >= 0 && nextY < this.size) {
                    Position currentPosition = Position.findPosInList(positionList, nextX, nextY);
                    if(currentPosition != null) {
                        positionList.remove(currentPosition);
                        boxPositions.add(currentPosition);
                    }
                }
            }
        }
        return boxPositions;
    }
}
java
1 Answers

Multiple things to consider here, where improvement can take place:

  1. This point is INVALID, because the OP has actually accounted for that. But this is still a basic thing to keep in mind: NEVER try to hit positions with random addresses. As soon as the field has a few ships, this will decrease speed drastically. In addition, 'random' functions can be really really slow, depending on their implementation

  2. a) Your code is also slow because you search items in linear lists, so in average your additional effort will be (list size) / 2. Use HashMaps or TreeMaps or HeapMaps, or their Set version.

  3. b) Your code uses remove(anyIndex). In ArrayLists, this will start to copy (on average) half of the array data to another position on every call.

  • And it does not play a role, whether you 'pop' from the very top (index 0) or not.
  • Worst of all, you use this remove() in loops, exploding your runtime.
  • Use an unstable removal (order will not be maintained), or LinkedLists, or some Map.
  1. a) instead of targeting random positions, build a map of ALL available spaces (on a 30x30 board, this will add 900 entries to the hashmap). The advantage of this approach is that build-up is slow, but all other operations are linear or minimized.
  • have a parameter for the size of a ship
  • create the HashMap (should be its own method, because we might need this at different locations in the code):
    • iterate over all positions, add the free ones (where you could validly place a ship of required length and rotation) to a hashmap, use coordinates as key
    • alternatively, if you expect coverage to be less than 85%, add ALL positions, then iterate over already placed ships and remove their positions from the HashMap
    • placement collisions for future placements would be possible at this point, but get removed once we hit (y)
  • place the ships:
    • x) selecting a random 'index' from a hashmap is a little challenge here, but you'll figure that out
    • y) once you start placing ships, remove all affected positions from the hashmap (include the ship's length and orientation in your calculations)
    • resume at (x)
  1. b) extension of that algorithm - improvement for differing sizes
  • if you run this algorithm for ships with differing sizes, calculate the available positions for the longest ships first, then you can also re-use the created hashmap for shorter ones. if the hashmap is empty but there are still ships remaining: when you run the 'create hashmap of valid positions' algorithm again, adjust/reduce the searched ship length to the currently required one. (This then will not be 'truly random' anymore, but random enough that no player will ever realize it. But in cryptography for example, this here would break the algorithm)
    • this will greatly increase speed while coverage is below ~80%
  1. A little hint on switches: use fall-through for combined code blocks:

Your code is

        switch(ship.getRotation()) {
            case HORIZONTAL:
                nextX = pos.x - 1 + i;
                nextY = pos.y - 1 + j;
                break;
            case VERTICAL:
                nextX = pos.x - 1 + j;
                nextY = pos.y - 1 + i;
                break;
            default:
                nextX = pos.x - 1 + j;
                nextY = pos.y - 1 + i;
                break;
        }

it can easily be reduced to

        switch(ship.getRotation()) {
            case HORIZONTAL:
                nextX = pos.x - 1 + i;
                nextY = pos.y - 1 + j;
                break;
            case VERTICAL: // fall-through to default, as VERTICAL seems to be the default^^
            default:
                nextX = pos.x - 1 + j;
                nextY = pos.y - 1 + i;
                break;
        }
user_19320110
Related