Vector of reference to struct

Hello,

I would like to have a structure with a reference vector inside.

I had already seen an example of this algorhythm but I can't find it anymore.

In my memory he used BOX

Thank you.

pub struct Cell{

row : usize,

column : usize,

links : Vec< &Cell>,

}

I am pretty confused. What do you want to do, and what does the code snippet have to do with it?

2 Likes

I don't have a code at the moment, I'm thinking about the structure of the data I would need.

What I want to do is that I have a grid, with cells and each cell must know its neighbour (open or closed passage). It's a maze generation algorithm.

Looks like that you're essentially trying to build a self-referential structure (or, strictly speaking, mutually-referential structures). This is not possible in safe Rust and generally not advisable. Probably you'd better store all the cells in the arena (i.e. Vec<Cell>) and make links field a vector of indices into this arena.

2 Likes

If we were "old school" about this:

  1. Given that you said "grid" that implies a simple two dimensional array.

  2. In order to know if each cell has an open passage to its neighbour in some direction only requires 1 bit. (0 closed, 1 open) So only four bits need to be saved in each cell to represent passages, north, south, east, west. Or you might need 8 bits if diagonal passages are allowed.

  3. So, each cell need only hold a u8, the bits of which are used to hold the open/closed passage of each direction out of the cell.

  4. Of course you are likely to want to store some other data in each cell, so better make each element of that array a struct with that "neighbours" byte in it and whatever other fields you need.

That is how I did a maze generation algorithm on a TRS-80 computer back in 1980 something. Worked a treat in the 4 kilo bytes of memory available on that machine.

Moving forward, I recently wanted to generate the mazes of the "Hunt The Wumpus" game in Rust: Hunt the Wumpus - Wikipedia

To that end I put all the caves of the game into elements of a vector of structures and created passages between them simply storing the índices of open passages in those elements.

As discussed here: When is a linked list not a linked list?. With code.

1 Like

Ok, I think I'll go back to your logic.

My primary goal was that when one cell opens a passage, the neighbouring cell should open a passage as well. By storing a reference of the cells I wanted my code to be more elegant, and to avoid making position calculations.

Sometimes the simplest method is the best

Thank you.

Well, if you have a reference to a neighbour and open that door, then you have to follow that reference to open the neighbours door in the opposite direction. (Assuming two way passages I guess)

If you have grid of cells in a 2D array then you have to visit the neighbour by incrementing/decrementing the array index in whatever direction.

It all amounts to the same thing does it not?