Interlinked mutable items

Hi,
I’ve toyed around with Rust for a while and to apply it to a “real” problem (eg: pass the “hello world” stage) I wanted to implement this simple old-school game http://www.rosettacode.org/wiki/Hunt_The_Wumpus that I’ve already implemented in other languages so far.

The first stage is to create the map. The map is a serie of 20 interconnected rooms, each linked to three other rooms (imagine a room with 3 corridors that lead to 3 other rooms), for instance:

Room(1, [Room 2, Room3, Room4])
Room(2, [Room 1, Room3, Room4])
Room(3, [Room 1, Room2, Room4])
Room(4, [Room 1, Room2, Room3])
Room(5, [Room 6, Room7, Room8])

When I implemented this in other languages, I used a pretty trivial algorithm:

  1. Generate an array of 20 Room objects
  2. Each Room object (class, struct…) has an id and an (initially) empty list of other rooms
  3. I loop each room
  4. For each room I check how many items there are in the list of connected rooms and if there are less than 3, and till there are exacly 3, I scan all the other rooms looking for the first one that:
    4.a. is not the current room
    4.b. has less than 3 connected rooms
    4.c. has not yet been linked to the current one
  5. I then link the found room to the current one (push it into the current room’s list of connected rooms)
  6. I link back the current room to the found room (push the current room into the found room’s list of connected rooms)

I finally have a list of 20 interconnected rooms each having a list of 3 other rooms.

In python of javascript or c, this is simple. In rust I’ve found out that having a mutable list of mutable items with mutable lists that point to mutable items of the same list that i need to mutate while also mutating each item is close to impossibile.

How would you approach this problem? Thanks!

Check out interior mutability and reference cycle

Reference cycles are not easy in rust, because there is no garbage collector.

You say your rooms have an id. Just store the id in the list of other rooms.

1 Like
  • Here is a version using shared references and interior mutability; as you can see the code involves plenty of lifetimes annotation and is cumbersome;

  • Here is a version using indices only: much simpler.


The algorithm described does not connect all the rooms together, it creates isolated 4-room “squares”:

You could explore with some randomization, to hopefully get more interesting “dungeons”:

2 Likes

Wow, thank you for your time, I’m going to study your code :slight_smile: