Implementing 2D vector syntax for accessing a 1D vector?

Question

I'm making a toy roguelike and have a Level structure for storing the game map, for which the most naive implementation is a 2D vector.

I'm following this tutorial which uses a Vector of Vectors, but states that for performance gains it's also possible to use a single Vector of size MAP_HEIGHT * MAP_WIDTH, and to access a tile at (x, y) one can simply access map[y * MAP_WIDTH + x].

I'm trying to implement this faster method but using getters and setters is clunky, and public fields aren't that great either. I'd much prefer it to feel like a 2D vector.

In order to do that I need to implement the Index trait for my class, but I'm not sure how to get the result I want. Maybe by nesting the impls? I really no idea.

Here is my code with a terrible attempt at implementing Index for my structure, which obviously won't work for my purposes because it's one dimensional:

const MAP_WIDTH: i32 = 80;
const MAP_HEIGHT: i32 = 45;

pub struct Level {
    map: Vec<Tile>,
}

impl Level {
    pub fn new() -> Self {
        Level { map: vec![Tile::empty(); (MAP_HEIGHT * MAP_WIDTH) as usize] }
    }
}

impl std::ops::Index<i32> for Level {
    type Output = Tile;
    fn index(&self, x: i32) -> &Self::Output {
        self[MAP_WIDTH + x]; // We have x and y values; how do we make this work?
    }
}

Answer 1

Make your struct indexible over objects of type (i32, i32).

type Pos = (i32, i32);

impl std::ops::Index<Pos> for Level {
    type Output = Tile;
    fn index(&self, (x, y): Pos) -> &Self::Output {
        &self.map[(y * MAP_WIDTH + x) as usize]
    }
}

Which you can then access with, for example:

let tile = level[(3, 4)];

Since you are using i32, you need to make sure that the values are within range, and can be coerced to usize, which is what Vecs are indexed over. Probably you should just stick with u32 or usize values from the start. Otherwise, you'll need to keep track of the minimum x and y values, and subtract them, to keep the position in range. It's definitely simpler to deal with positive coordinates and make the assumption that the corner of your map is (0, 0).

Answer 2

It is possible, though not obvious.

First of all, I suggest having the MAP_WIDTH and MAP_HEIGHT in usize, as they are positive integers:

const MAP_WIDTH: usize = 80;
const MAP_HEIGHT: usize = 45;

Then you need to implement Index (and possibly IndexMut) to return a slice; in this case I'm assuming that you want the first coordinate to be the row:

impl std::ops::Index<usize> for Level {
    type Output = [Tile];

    fn index(&self, row: usize) -> &[Tile] {
        let start = MAP_WIDTH * row;
        &self.map[start .. start + MAP_WIDTH]
    }
}

impl std::ops::IndexMut<usize> for Level {
    fn index_mut(&mut self, row: usize) -> &mut [Tile] {
        let start = MAP_WIDTH * row;
        &mut self.map[start .. start + MAP_WIDTH]
    }
}

Then, when you index a Level, it first returns a slice with the applicable row; then you can index that slice with the column number.

Below is an example implementation with a substitute Tile:

const MAP_WIDTH: usize = 80;
const MAP_HEIGHT: usize = 45;

#[derive(Clone, Debug)]
pub struct Tile {
    x: u32,
    y: u32
}

pub struct Level {
    map: Vec<Tile>,
}

impl Level {
    pub fn new() -> Self {
        Level { map: vec![Tile { x: 0, y: 0 }; (MAP_HEIGHT * MAP_WIDTH) as usize] }
    }
}

impl std::ops::Index<usize> for Level {
    type Output = [Tile];

    fn index(&self, row: usize) -> &[Tile] {
        let start = MAP_WIDTH * row;
        &self.map[start .. start + MAP_WIDTH]
    }
}

impl std::ops::IndexMut<usize> for Level {
    fn index_mut(&mut self, row: usize) -> &mut [Tile] {
        let start = MAP_WIDTH * row;
        &mut self.map[start .. start + MAP_WIDTH]
    }
}

fn main() {
    let mut lvl = Level::new(); 

    lvl[5][2] = Tile { x: 5, y: 2 };

    println!("{:?}", lvl[5][2]); // Tile { x: 5, y: 2 }
}