4
\$\begingroup\$

Summary

I have been playing with Rust for a couple of days, so I thought I would implement something rather simple. This code generates a random variation of board for well-known game of Battleship. In this variation, there are one 4-cell ship, two 3-cell ships, three 2-cell ships and four 1-cell ships.

There's definitely a room for improvement both algorithm- and style-wise. Much appreciate the help!

use itertools::Itertools;
use rand::rngs::SmallRng;
use rand::seq::SliceRandom;
use rand::{Rng, SeedableRng};

const FIELD_SIZE: isize = 10;
#[rustfmt::skip]
const DIRECTIONS: [(isize, isize); 9 as usize] = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0), (-1, 1), (1, -1), (-1, -1), (1, 1)];

#[derive(Clone, PartialEq, Copy)]
enum CellType {
    EMPTY,
    UNAVAILABLE,
    OCCUPIED,
}

struct Field {
    field: [CellType; (FIELD_SIZE * FIELD_SIZE) as usize],
}

impl std::fmt::Display for Field {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        Ok(for (index, element) in self.field.iter().enumerate() {
            #[rustfmt::skip]
            let char_repr = match element {
                CellType::EMPTY       => '.',
                CellType::UNAVAILABLE => 'o',
                CellType::OCCUPIED    => 'X',
            };
            if index % FIELD_SIZE as usize == 0 {
                writeln!(f)?;
            }
            write!(f, "{}", char_repr)?;
        })
    }
}

fn is_valid_formation(
    field: &Field,
    mut x: isize,
    mut y: isize,
    dx: isize,
    dy: isize,
    ship_size: usize,
) -> bool {
    // I. Construct a bounding box for the placed ship.
    let bounds = 0..FIELD_SIZE;
    for ship_size in 0..ship_size {
        let x = x + (dx * ship_size as isize);
        let y = y + (dy * ship_size as isize);
        // Move in every box direction.
        for direction in DIRECTIONS.iter() {
            // Indices cannot be negative or >= FIELD_SIZE.
            if !bounds.contains(&(x + direction.0)) || !bounds.contains(&(y + direction.1)) {
                continue;
            }
            let bounding_box_cell =
                field.field[((x + direction.0) + ((y + direction.1) * FIELD_SIZE)) as usize];
            // If there's a ship within a bounding box, halt the loop -- we cannot place the ship here.
            if bounding_box_cell == CellType::OCCUPIED {
                return false;
            }
        }
    }
    // II. Check whether the cells that are being used to place the ship onto are occupied.
    for _ in 0..ship_size {
        if !bounds.contains(&x) || !bounds.contains(&y) {
            return false;
        }
        let current_cell = field.field[(y * FIELD_SIZE + x) as usize];
        if let CellType::OCCUPIED | CellType::UNAVAILABLE = current_cell {
            return false;
        }
        x += dx;
        y += dy;
    }
    true
}

fn get_available_cells(
    field: &Field,
    dx: isize,
    dy: isize,
    ship_size: usize,
) -> Vec<(isize, isize)> {
    (0..FIELD_SIZE)
        .cartesian_product(0..FIELD_SIZE)
        .filter(|(x, y)| is_valid_formation(&field, *x, *y, dx, dy, ship_size))
        .collect()
}

fn emplace_ships(field: &mut Field, ship_size: usize, rng: &mut SmallRng) {
    // Flip a coin to determine an alignment (horizontal / vertical).
    let (dx, dy) = if rng.gen() { (1, 0) } else { (0, 1) };
    // Get the vector of appropriate cells.
    let cell_coordinates = get_available_cells(&field, dx, dy, ship_size);
    let (mut x, mut y) = cell_coordinates.choose(rng).unwrap();
    // Place a ship!
    for _ in 0..ship_size {
        field.field[(x + y * FIELD_SIZE) as usize] = CellType::OCCUPIED;
        x += dx;
        y += dy;
    }
}

impl Field {
    fn generate() -> Self {
        /* Generating the field. */
        let mut f = Field { field: [CellType::EMPTY; (FIELD_SIZE * FIELD_SIZE) as usize] };
        let mut rng: SmallRng = SmallRng::from_entropy();
        for ship_size in [4, 3, 3, 2, 2, 2, 1, 1, 1, 1].iter() {
            emplace_ships(&mut f, *ship_size, &mut rng);
        }
        f
    }
}
fn main() {
    let field = Field::generate();
    println!("{}", field);
}

\$\endgroup\$
4
\$\begingroup\$

Looks good overall! For example, good job using enums, and writing helpful comments. A few additional possible improvements, implemented below:

  • In the declaration for DIRECTIONS, you don't need to cast 9 to usize; it can do so implicitly.
  • Move the code for char_repr to an implementation of Display for CellType.
  • Consider making more things usize instead of isize.
  • A few minor things suggested by clippy, such as using for x in &[...] instead of for x in [...].iter()
  • Comment what index % FIELD_SIZE as usize == 0 does.
  • Implement Index(Mut) for Field.
  • Make things methods on Field.
  • Rename is_valid_formation to can_place_ship.
  • Create a Ship struct that implements Iterator or IntoIterator.
  • Use impl Rng instead of SmallRng for code that doesn't care what kind of RNG is used.

Other things to consider, not implemented below:

  • Unit tests
  • Creating a Coordinate struct (may or may not be an improvement)

Final code:

#![warn(clippy::all)]
#![warn(clippy::pedantic)]
#![warn(clippy::nursery)]
#![allow(clippy::cast_possible_wrap)]
#![allow(clippy::cast_sign_loss)]

use itertools::Itertools;
use rand::rngs::SmallRng;
use rand::seq::SliceRandom;
use rand::{Rng, SeedableRng};
use std::fmt;
use std::ops::{Index, IndexMut};

const FIELD_SIZE: usize = 10;
#[rustfmt::skip]
const DIRECTIONS: [(isize, isize); 9] = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0), (-1, 1), (1, -1), (-1, -1), (1, 1)];

#[derive(Clone, PartialEq, Copy)]
enum CellType {
    EMPTY,
    UNAVAILABLE,
    OCCUPIED,
}

impl fmt::Display for CellType {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Self::EMPTY => '.',
                Self::UNAVAILABLE => 'o',
                Self::OCCUPIED => 'X',
            }
        )
    }
}

#[derive(Copy, Clone)]
struct ShipShape {
    dx: usize,
    dy: usize,
    size: usize,
}

#[derive(Copy, Clone)]
struct Ship {
    x: usize,
    y: usize,
    shape: ShipShape,
}

// If you prefer, you can use `IntoIterator` here instead.
#[allow(clippy::copy_iterator)]
impl Iterator for Ship {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<(usize, usize)> {
        if self.shape.size > 0 {
            let result = (self.x, self.y);
            self.x += self.shape.dx;
            self.y += self.shape.dy;
            self.shape.size -= 1;
            Some(result)
        } else {
            None
        }
    }
}

struct Field {
    field: [CellType; (FIELD_SIZE * FIELD_SIZE) as usize],
}

impl fmt::Display for Field {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for (index, element) in self.field.iter().enumerate() {
            // Start of line
            if index % FIELD_SIZE as usize == 0 {
                writeln!(f)?;
            }
            write!(f, "{}", element)?;
        }
        Ok(())
    }
}

impl Index<(usize, usize)> for Field {
    type Output = CellType;

    fn index(&self, (x, y): (usize, usize)) -> &CellType {
        &self.field[x + y * FIELD_SIZE]
    }
}

impl IndexMut<(usize, usize)> for Field {
    fn index_mut(&mut self, (x, y): (usize, usize)) -> &mut CellType {
        &mut self.field[x + y * FIELD_SIZE]
    }
}

impl Field {
    fn can_place_ship(&self, ship: Ship) -> bool {
        // I. Construct a bounding box for the placed ship.
        let bounds = 0..(FIELD_SIZE as isize);
        for (x, y) in ship {
            // Move in every box direction.
            for direction in &DIRECTIONS {
                // Indices cannot be negative or >= FIELD_SIZE.
                if !bounds.contains(&(x as isize + direction.0))
                    || !bounds.contains(&(y as isize + direction.1))
                {
                    continue;
                }
                let bounding_box_cell = self[(
                    (x as isize + direction.0) as usize,
                    (y as isize + direction.1) as usize,
                )];
                // If there's a ship within a bounding box, halt the loop -- we cannot place the ship here.
                if bounding_box_cell == CellType::OCCUPIED {
                    return false;
                }
            }
        }

        // II. Check whether the cells that are being used to place the ship onto are occupied.
        let bounds = 0..FIELD_SIZE;
        for (x, y) in ship {
            if !bounds.contains(&x) || !bounds.contains(&y) {
                return false;
            }
            let current_cell = self[(x, y)];
            if let CellType::OCCUPIED | CellType::UNAVAILABLE = current_cell {
                return false;
            }
        }
        true
    }

    fn get_available_cells(&self, shape: ShipShape) -> Vec<(usize, usize)> {
        (0..FIELD_SIZE)
            .cartesian_product(0..FIELD_SIZE)
            .filter(|&(x, y)| self.can_place_ship(Ship { x, y, shape }))
            .collect()
    }

    fn emplace_ships(&mut self, size: usize, rng: &mut impl Rng) {
        // Flip a coin to determine an alignment (horizontal / vertical).
        let (dx, dy) = if rng.gen() { (1, 0) } else { (0, 1) };
        let shape = ShipShape { dx, dy, size };
        // Get the vector of appropriate cells.
        let cell_coordinates = self.get_available_cells(shape);
        let (x, y) = *cell_coordinates.choose(rng).unwrap();
        let ship = Ship { x, y, shape };
        // Place a ship!
        for (x, y) in ship {
            self[(x, y)] = CellType::OCCUPIED;
        }
    }

    fn generate() -> Self {
        /* Generating the field. */
        let mut result = Self {
            field: [CellType::EMPTY; FIELD_SIZE * FIELD_SIZE],
        };
        let mut rng: SmallRng = SmallRng::from_entropy();
        for ship_size in &[4, 3, 3, 2, 2, 2, 1, 1, 1, 1] {
            result.emplace_ships(*ship_size, &mut rng);
        }
        result
    }
}
fn main() {
    let field = Field::generate();
    println!("{}", field);
}

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=da8fca6fff5803ad9fe26957c3e70afa

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks! Besides; I think there is a way to get rid of unnecessary allocations by declaring an instance of StaticVec to pass into generating function. This significantly speeds things up. \$\endgroup\$ – Inter Veridium Jun 25 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.