What's to figure out? I grow the tree by picking a star, adding lanes to all nearby systems that aren't yet connected to the tree, then adding all the stars that just got lanes made to them to the end of the list of connected systems. I then get the next system off the list, and repeat until the list is empty. This means that the first system has all of it's neighbours free, so makes as many starlanes as it has neighbours.
Judging by your screenshot that method produces a very interesting looking map, but it's not exactly a growing tree (in the maze generation sense of the word).
Growing tree maze generation:
1: Select a node (ie a star) at random
2: Add this first node to a list
do steps 3-6 until list size = 0:
2: Select node X from the list (randomly, or from the top/bottom of the list, depedant upon desired maze shape)
3: Select node Y from the unmade* nodes tangent* to node X
4: Connect nodes X to Y with a path (starlane)
5: Push node Y to the top of the list
6: If (unmade nodes tangent to node X)=0 then remove node X from the list
Your method is identical to a growing tree that always selected from the bottom of a list. Normally, a growing tree would select from the top or randomly, eliminating levitt situations.
* unmade nodes are those with no pathes connecting to other nodes.
* since our topology is not at all regular, the triangulation thingy is run first to determine which nodes are tangent
but I think the main problem is all the calls to ShortestPath
That's the problem.
You shouldn't need to call ShortestPath at all. My eyes are just glazing right now from working on Excel spreadsheets all day, going to think about this later.
The way to cut out the longer lanes will probly depend on what is decided for map stencil generation...
Easier method: before running triganulation, drop some "fake stars" in the empty spaces where no lanes should cross. before running maze generation, remove the "fake stars".