Creating a static "map" (graph)

I'm writing a toy pathfinder in Rust, using the Eve Online static data export as a "map".

It's been interesting downloading the export, streaming the zip files to memory, extracting the data needed and constructing enough to eventually do some pathfinding on (still todo).

My main current data-structure looks like this:

#[derive(Debug)]
pub struct SolarSystem {
    pub name: String,
    pub solar_system_id: SolarSystemId,
    pub constellation_id: u64,
    pub region_id: u64,
    neighbours: once_cell::unsync::OnceCell<Vec<Weak<SolarSystem>>>,
}

contained in a Vec.

I needed a once-cell/RefCell etc to do the linking of the solarsystems (trying to avoid just faking things with storing offset IDs). You can't link with references to other solarsystems that you might not have created yet, and you run into issues with mutating elements of the vec with a mutable borrow and immutable at the same time (advice here appreciated too).

At the moment, I have no particular need to make things parallel, but in principle, once it's created and done, this structure won't change and the systems in it won't go away unless the whole map does and should be able to be used simultaneously with the only requirement being that the whole map does not drop before you finish (ref-counting systems shouldn't really be needed).

It leaves me a little unsatisfied that if I try to solve this, I probably need to move over to Arc and a sync once-cell and pay some costs that don't feel strictly necessary, but I don't feel confident about other patterns for this.

There's a slight temptation to use something like bumpalo, and allocate an arena for the map to almost codify that this whole data-structure has a single lifetime.

Anyway, looking for suggestions / techniques / patterns that might work here, because I feel like those sorts of things are the tools that you put in your belt for solving other issues later.

Thanks in advance.

Posted Nov 13, 2022, 2:53 PM UTC

313

General graphs like this are fairly difficult to construct in Rust. They are (in essence) complex linked lists. However, I would recommend using Rc instead of the once cells here. Assuming you are constructing the graph in a single thread (which you should be doing), you can probably get away with the unsafe method on Rc get_mut_unchecked when adding on neighbors.

From there, the ergonomics of traversing the graph should be far better.

3
Redundancy_OP•

This uses Rc, with a strong reference from the vec, and a weak reference between the neighbours to avoid cycle issues keeping them alive.

get_mut_unchecked sounds like it might be helpful, thanks!

1

Ya, weak references might be good. However, I imagine you want to keep the whole graph around for the life of the program, so leaks are really a concern.

At any rate, the once cell is not needed because you can construct an empty Vec and populate it later.

1
Redundancy_OP•

So like: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=a0383aee1aab69739b479420ca209738

Downside, this requires nightly at the moment, and get_mut_unchecked doesn't at a glance look like it's getting stabilized any time soon due to challenges with it.

Interior mutability seems like a better way to avoid needing nightly and unsafe?

1

Ah, I didn't realize that was a nightly feature. What you have would work. To avoid using unsafe and nightly, you could use a RefCell. This would come at a (probably minor) performance hit, but would work well for what you're doing.

You will want to wrap the cells in an RC, still though.

2
PM_ME_UR_TOSTADAS•

I just started doing game engine dev and first thing I've worked on is rewriting memory managing for world data. What I ended up doing is putting all elements in an array and referencing other nodes via indices. Though this was in C++, I bet this is how you do it in Rust as well. It would look like this in Rust:

struct Graph<T> {
    nodes: Vec<GraphNode<t>>
}

struct GraphNode<T> where T: Sized {
    inner: T,
    neighbors: Vec<GraphNodeIndex>
}

struct GraphNodeIndex(usize);

impl Graph<T> {
    fn at(index: GraphNodeIndex) -> &T;
    fn at_mut(index: GraphNodeIndex) -> &mut T;
}

You then would provide necessary functions to implement the pathfinding algorithm on the Graph, as it is the owner of all nodes.

Also, you are right in your itch to use an arena allocator. Since all of the map data lives and dies together, arena allocator is very convenient for cleanup. I ended up using a scratch buffer as well which made world changing is as easy as

world.clean();
world.load(Worlds::MAP01);
3
Redundancy_OP•

I've made this work before with a scheme like that, but I'm trying to somewhat stretch myself by better learning / understanding Rust better, and part of that is to try and do a version that leans into Rc etc. You can actually somewhat see it in the use of a newtype for the SolarSystemID (there's also a SolarSystemIndex).

There's a temptation to break out unsafe, pointers and some other things and write a very C++y version of things that I'd probably never be able to prove is safe Rust, but I'm also interested in seeing if people point me to some other tools that I haven't come across yet or understood.

I'm not currently sure what I need to do to get to a point where I'm confident that I can do better following that path than the purely safe, panic free version.

3
PM_ME_UR_TOSTADAS•

I think this is understanding safe Rust. Rust tells you to have clear ownerships and to respect those ownerships. Trying to use indirections to get away from those recommendations feels to me like trying to fool the borrow checker. If I can never touch many pointer types and unsafe, and still write clean and performant Rust code, I'm a happy boy.

1
plutoniator•

What happens if you remove a node?

2
PM_ME_UR_TOSTADAS•

I honestly didn't need to because maps are static in my usecase, but in that case I'd use a T that is Option<U> to be able to denote a removed node (ie just make the node None) and then use the neighbors list to remove all references to the deleted node. You can add schemes to reclaim memory, too.

2
Redundancy_OP•

There are lots of use-cases where data can be thought of as essentially static, or where instead of modifying something you entirely replace it with a new one.

The "Index" approach is super convenient as it bypasses all Rust borrow semantics, but things like reordering the nodes, removing items etc can be tricky. You certainly don't want a GraphNodeIndex that ends up pointing beyond the end of the vec and panicing in at().

2
Redundancy_OP•

For the benefit of anyone looking for a Rc / Refcell version of this (simplified for the playground, hopefully correct)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f35de985fcec95d113a41fba580f2426

println!("{}", Rc::strong_count(&items[0]))

should (I believe) verify that this only has a single strong reference (Vec -> Item).

navigating the neighbours looks like:

println!("{}", items[0].neighbours.borrow()[0].upgrade().expect("uhoh").name);

The borrow to get your Refcell, the upgrade to get a strong reference.

The once_cell implementation would trade the borrow() for a get() that returns an option, and removes the possibility of a runtime panic.

1
Redundancy_OP•

Here's a simplified version using pointers and unsafe: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c2376fab94c54b1ce55162f26d255333

This definitely gets you to into "too many linked lists" territory: https://rust-unofficial.github.io/too-many-lists/index.html

I also cannot guarantee that this is safe / correct.

1