Draw a graph as a world map in UI?

Question

What's a good way to take a graph of nodes and draw it in your UI as a map?

I already have a graph and I'm happy with how it's generated. However, it doesn't have any positional data for the nodes -- just their connections. How can I use it to draw a map along the lines of Slay The Spire:

I've seen examples (Procedural Dungeon Generation #3, stsmapgen) that populate a space with nodes and connect those nodes, but I want to have more control over how often I branch so I would prefer if my generation wasn't based derived from random node positions.

So far most answers I've found were to use graphviz, but obviously that's not feasible at runtime.

My graph starts at an entrance node, terminates at an exit node, all transitions are unidirectional, and each node can have at most four connections (one in and three out). Paths through the tree can branch off and merge back in to a later path.

My naïve approach of giving an offset for each of the three out transitions, doing a breadth-first walk of the tree, and assigning node positions based on the source node and the offset produced overlapping nodes. It seems like I'd need to push nodes away that are overlapping, but I'm hoping there's a simpler solution and one that doesn't require physics.

Answer 1

I ended up storing some information at map generation time that guides map layout in UI.

I generate the map nodes into a grid (to help bound the total size of the map) and lay them out as follows:

• world map flows from left to right (unlike the above image)
• rooms are generated breadth first
• each room is assigned an index based on generation order
• each additional depth is in a new column
• each new room is put in the first available row in the column

This allows me to draw my UI as a transformation of this grid: vertically align each column and add some noise to offset them (I store this noise along with the generated map so presentation doesn't vary when the map's displayed).

In More Detail

I count the number of connected rooms in each column to determine a bucket count. This determines the starting height of the first node and the vertical offset for each subsequent node (max_height / bucket_count).

I horizontally space based on the bucket count too so that nodes with few connections can be placed closer together but nodes with many connections have more space to show their connections.

I have a circular list of random offsets. I select one based on the room index, scale it by column width, and added each node's position. This hides the regular grid and makes the map look more organic.