More efficient iteration through cells in a grid

I have a struct as follows:

struct Cell {
    x: usize,
    y: usize,
    contents: MyEnum
}

These cells are stored in a vec that is max x * max y size. I need to compare the contents of the adjacent cells in the same row, column, or diagonal line. Currently I’m doing this by nested for loops:

let iter = my_vec_of_cells.iter();
        for cell in iter.clone() {
            if cell.contents == MyEnum::Variant1 {
                // do nothing to the cell //
                continue;
            }
            let mut s = cell.clone();
            for adjac in iter.clone() {
                s = match s.x as i32 - adjac.x as i32 {
                    1 | 0 | -1 => { match s.y as i32 - adjac.y as i32 {
                        1 | 0 | -1 => Cell { x: s.x, y: s.y, occ: processed_contents(s,adjac) },
                        _ => s
                    }
                    },

                    _ => s,
                };
            }
        }

This loops through every Cell in the vec rather than just the adjacent cells. Is there a more efficient way to accomplish this?

Can you represent the grid as a Vec<Vec<MyEnum>>? The adjacent cells can then be computed based on the (x,y) position of a given cell.

Alternatively, represent the grid as a graph and store adjacency info at construction time.

Yeah, I thought about changing the whole structure but was hoping to avoid that. Can you elaborate on “represent the grid as a graph”?

A simple approach would be to have an adjacency list. This can be modeled as, eg, a HashMap<MyEnum, Vec<MyEnum>>; each key has a vec of neighboring enums across all the paths (x,y and diag).

If you decide on trying to model as a graph, look at the petgraph crate.

Is your scenario going to mostly involve walking the adjacency list of all cells? What would you like/need to optimize for?

1 Like

I was just doing an exercise implementing a Minesweeper board, but I’m trying to come up with the pros and cons of the approach I used vs alternatives.

Not using the custom struct and just using Vec<Vec<Enum>> is the most appropriate approach for this particular case. I thought about potentially having the ability to flag cells by adding a field to the Cell struct as one reason for going the route I did.

I will read up on graph implementations and see if that makes sense.

Are you familiar with integer division and modulus? There is a very simple trick for converting between flat indices into your Vec and (row, col) pairs.

Assuming data is ordered so that values of equal row are contiguous:

  • index = width * row + col
  • col = index % width
  • row = index / width

With this, you do not need a Cell type, because you can easily recover row and col from an index. Here is a wrapper type which makes use of these relationships. Try working with a Grid<Enum>:

struct Grid<T> {
    dim: (usize, usize),
    data: Vec<T>,
}

type Pos = (usize, usize); // written as (row, column)

impl<T> Grid<T> {
    pub fn new(dim: (usize, usize), data: Vec<T>) -> Self {
        assert_eq!(dim.0 * dim.1, data.len());
        Grid { dim, data }
    }
    fn flat_index(&self, pos: Pos) -> usize {
        assert!(pos.0 < self.dim.0);
        assert!(pos.1 < self.dim.1);

        let strides = (self.dim.1, 1);

        pos.0 * strides.0 + pos.1 * strides.1
    }

    // inverse of flat_index
    fn pos(&self, index: usize) -> Pos {
        (index / self.dim.1, index % self.dim.1)
    }

    pub fn at_pos(&self, pos: Pos) -> &T {
        &self.data[self.flat_index(pos)]
    }
}

Such a helper type could expose methods for viewing neighbors as follows:

impl<T> Grid<T> {
    pub fn neighbors(&self, pos: Pos) -> Vec<&T> {
        let mut out = Vec::with_capacity(4);
        self.each_neighbor_pos(pos, |neighbor| {
            out.push(self.at_pos(neighbor));
        });
        out
    }

    // helper, written in the form of an "internal iterator" to make it
    // easier to add other things (like e.g. a `neighbors_mut` function)
    fn each_neighbor_pos(&self, pos: Pos, mut func: impl FnMut(Pos)) {
        if pos.0 != 0 {
            func((pos.0 - 1, pos.1));
        }
        if pos.1 != 0 {
            func((pos.0, pos.1 - 1));
        }

        if pos.0 + 1 != self.dim.0 {
            func((pos.0 + 1, pos.1));
        }
        if pos.1 + 1 != self.dim.1 {
            func((pos.0, pos.1 + 1));
        }
    }
}

Note that several popular third-party implementations of my Grid type already exist if you are interested. See:

  • ndarray, a generalization to n dimensions which also works with discontiguous data. (this is on the “complicated but powerful” end!)
  • imgref, which despite the name is not just for images! I’ve never used it but I know it provides a 2D type much like my Grid (as well as “grid views” for viewing a region of the grid), and is probably easier to learn than ndarray.

Ok, for a Minesweeper board, a flat vec is fine since the geometry of the board is uniform (ie fixed rows x cols). The example @ExpHP gave is good, although I’d probably use an iterator to allow the caller to walk the neighbors rather than allocating a Vec (but this is a minor thing in the grand scheme).

For minesweeper having x/y in the Cell seems redundant. You can use iter.enumerate() to get the coordinates without storing them.

Alright, so technically this particular case can be done with impl Iterator.

impl<T> Grid<T> {
    // hmm. Maybe "pos" was not the best choice of abbreviation...
    fn neighbor_poses(&self, pos: Pos) -> impl Iterator<Item=Pos> {
        let a = match pos.0 == 0 {
            true => None,
            false => Some((pos.0 - 1, pos.1)),
        };
        let b = match pos.1 == 0 {
            true => None,
            false => Some((pos.0, pos.1 - 1)),
        };
        let c = match pos.0 + 1 == self.dim.0 {
            true => None,
            false => Some((pos.0 + 1, pos.1)),
        };
        let d = match pos.1 + 1 == self.dim.1 {
            true => None,
            false => Some((pos.0, pos.1 + 1)),
        };
        a.into_iter().chain(b).chain(c).chain(d)
    }
}

although unfortunately, long chains of Iterator::chain are known to cause compile time issues, and it also doesn't implement ExactSizeIterator. If I wanted to dodge allocation I'd rather just make my each_neighbor_pos public (and maybe add a try_ variant), as internal iterators have a variety of advantages over iterators for small things like this.

In the grand scheme of things, for very hot computations on very large grids, I wouldn't use anything like this, because I doubt it vectorizes well. I would instead write an optimized function for the entire fold I care about.... But I don't think Minesweeper is quite that demanding. :stuck_out_tongue:

This would look nicer with generators but alas they’re not available on stable. But yeah, exposing each_neighbor_pos is fine too.

I think the number of chain() calls here is pretty small - I’d be shocked if compile time gets noticeably longer from just this place (if this pattern repeats tens/hundreds of times, however, then it could add up).

One can also impl a custom iterator that tracks the neighbor state it’s visiting. Or return an array of 4 Option wrapped values.

I appreciate all the input on solving the minesweeper exercise in a better way, but that was not the question I was really interested in. I am happy to continue experimenting and iterating my solution the problem, but I am actually interested in specifically how one might iterate in a “look around” manner. If the changing the data structure to something better is not an option, would there be a better way to implement the look around than what I did?

In practice this requires consideration of cache structures and varies depending on the required pattern of inspection of adjacent cells and retention of results. Most real modern hardware has multi-level caches, so the actual performance will improve when the access patterns are matched to the cache structure. In other words, rather than scanning by rows or columns across the entire array, it may be better to work in two-dimensional patches sized to the cache structure, essentially covering the array with slightly-overlapping tiles. Game developers commonly employ such approaches.

If the cells are not stored in any particular order, then your code offers a way to map from a Cell to its coordinates, but no way to map coordinates to a Cell (other than iterating through every Cell). In this case, solving the problem fundamentally requires changing or adding data structures.

If the cells are stored in order, then you can use ExpHP’s solution above to find a Cell given its coordinates. And as ExpHP points out, this means you no longer need to store the coordinates inside the Cell.

1 Like