I think it makes sense to use a mapped adjacency list since most of the operations we do with edges are iterating through lists/sets rather than existence lookups.
unordered map: (source) -> Set or List of (dest, weight)
In general, finding or testing adjacency is fast if we use an 8-connected graph. O(1) although vector operations are slow.
Vertices are represented by binned coordinates (Vector2i or similar; hashable), and thus can have negative values. Weights are floating points. We can probably store sqrt(2) as a constexpr since it'll be used frequently for 8-connected graphs.
Discretization
We can do something similar to the continuous-to-discrete bin conversion in the 2D and 3D lookup tables from the SLAM assignment. The slides have a suggested resolution of 0.25 meters.
Graph Generation
I think it makes sense to lazily generate the graph, since we generally won't be exploring the entire map.
Obstacle Representation
We can store a set of bins containing obstacles or walls from the vector map. It probably makes the most sense to generate this set at instantiation, since lookup in the VectorMap is expensive (I think). This isn't optimal, as we're storing a bunch of vertices we'll never explore, but in general it should be pretty sparse.
Missing Vertex Detection
When adding a vertex to the adjacency list, naturally we want to enumerate all of its valid neighbors. However, for this procedure we don't need to check whether the neighbors themselves are in the adjacency list. Instead, we can lazily detect vertex existence and generate missing entries when querying edge lists.
ctor:
initialize graph structure
add source vertex and its enumerate edges
create obstacle vertex set
query(V) -> Collection[E]
if V not in graph keys:
add V and enumerate edges
return edge list for V
Slides
Graph Representation
I think it makes sense to use a mapped adjacency list since most of the operations we do with edges are iterating through lists/sets rather than existence lookups.
In general, finding or testing adjacency is fast if we use an 8-connected graph. O(1) although vector operations are slow.
Vertices are represented by binned coordinates (Vector2i or similar; hashable), and thus can have negative values. Weights are floating points. We can probably store sqrt(2) as a constexpr since it'll be used frequently for 8-connected graphs.
Discretization
We can do something similar to the continuous-to-discrete bin conversion in the 2D and 3D lookup tables from the SLAM assignment. The slides have a suggested resolution of 0.25 meters.
Graph Generation
I think it makes sense to lazily generate the graph, since we generally won't be exploring the entire map.
Obstacle Representation
We can store a set of bins containing obstacles or walls from the vector map. It probably makes the most sense to generate this set at instantiation, since lookup in the VectorMap is expensive (I think). This isn't optimal, as we're storing a bunch of vertices we'll never explore, but in general it should be pretty sparse.
Missing Vertex Detection
When adding a vertex to the adjacency list, naturally we want to enumerate all of its valid neighbors. However, for this procedure we don't need to check whether the neighbors themselves are in the adjacency list. Instead, we can lazily detect vertex existence and generate missing entries when querying edge lists.