Minimun Spannig Tree

Blitz3D Forums/Blitz3D Programming/Minimun Spannig Tree

limdorn (Posted 2011) [#1]

Hi , I´m working a game like Master of Orion and I need help to connect all stars to create the starlines. Exist a algorithm named "minimun spanning tree" to create this effect but I don´t understand it. Somebody can help me? Thanks

Ginger Tea (Posted 2011) [#2]

I had a quick look at the wiki page before my eyes crossed, do you really want all dot's (stars) connected in this fassion? I ask for a few reasons 1> going from star to star should just be a straight line trip, where as this might take you "round the houses" so to speak depending on it's out come 2> more stars/dot's the more work it has to do to plot the route where each star is visited once only (atleast I think thats the plan). I'm not familiar with Masters of Orion or how the star lines work and I'm assuming you are not looking for something like constelations as this is not the droid you are looking for, although the image does look like one. If its a road map between stars and it has to go via near by stars, why I don't know, then you wont need to plot the entire star map, just a local event between those two points and A* might be more suited. edit: eg you want to go from the top right point to the bottom right, which has a weight of 18 acording to the diagram, if you went via the other stars the total would be far greater, if that was read as distance, then going round the houses is not quicker (obviously) and would only benefit the ship if it had to make solar boosts inbetween and the single point trip would cause the ship to run out of juice. Last edited 2011

Krischan (Posted 2011) [#3]

In the german community, "FirstDeathMaker" created a solution for this - if you don't understand german I put it all together in two single files ready to run. It creates 100 Stars, connects them and calculates / displays the shortest path between two random stars. But it is *very* complex, I don't understand exactly how it works so don't ask me :-D You can move with mouse/arrows and Enter creates a new random route. demo.bb Include "spanningtree.bb" Global movespeed#=0.5 ms=MilliSecs() TNode_InitAll() TConnection_InitAll() Graphics3D 800,600,32,2 ; Entities cam=CreateCamera() MoveEntity cam,0,0,100 wiref_piv = CreatePivot() solid_piv = CreatePivot() star=CreateSphere(8) ; Create Random Stars For n.TNode = Each TNode n\entity=CopyEntity(star,solid_piv) PositionEntity n\entity,n\pos[0],n\pos[1],n\pos[2] ScaleEntity n\entity,1,1,1 Next PointEntity cam,star FreeEntity star ; calculate the shortest way TConnection_CreateSpanningTree(First TNode) TConnections_Show() ende=MilliSecs()-ms MoveMouse 400,300 While Not KeyHit(1) FPS_C=FPS_C+1 : If ms<MilliSecs() Then ms=MilliSecs()+1000 : FPS=FPS_C : FPS_C=0 mxs#=MouseXSpeed() : mys#=MouseYSpeed() : pitch#=EntityPitch(cam)+(mys#/5) If pitch>89 Then pitch=89 Else If pitch<-89 Then pitch=-89 RotateEntity cam,pitch,EntityYaw(cam)-(mxs#/5),0 MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 If KeyDown(200) Then MoveEntity cam,0,0,movespeed If KeyDown(208) Then MoveEntity cam,0,0,-movespeed If KeyDown(205) Then MoveEntity cam,movespeed,0,0 If KeyDown(203) Then MoveEntity cam,-movespeed,0,0 If KeyHit(57) Then wf=1-wf If KeyHit(28) For n.TNode = Each TNode EntityColor n\entity,255,255,255 Next ; calculate path from star1 -> star2 Local offset# = 0.4 Local star1.TNode = NODE_ARRAY(Rand(0,NODES-1)) Local star2.TNode = NODE_ARRAY(Rand(0,NODES-1)) ; find path from star1 to star2 Local path.TPathNode = AStar_getPath(star1,star2) ; draw path, start=green, target=red EntityColor star1\entity,255,0,0 EntityColor star2\entity,0,255,0 TConnections_Show() If path<>Null TPath_Show(path) Else DebugLog "No Path found (should be impossible)" EndIf EndIf ; Render wireframe objects. WireFrame 1 : ShowEntity wiref_piv : HideEntity solid_piv CameraClsMode cam,1,1 : RenderWorld ; Render solid objects. WireFrame wf : HideEntity wiref_piv : ShowEntity solid_piv CameraClsMode cam,0,0 : RenderWorld ; Text Text 0, 0,"FPS...............: "+FPS Text 0,15,"Tree created in...: "+ende+"ms" Text 0,30,"Press Enter to calculate a new path" RenderWorld Flip 1 Wend End ; Draw 3D Line Function Line3D(mesh,x0#,y0#,z0#,x1#,y1#,z1#,r%=255,g%=255,b%=255) Local surf%,last_surf%,v1%,v2% If mesh = 0 mesh = CreateMesh() surf = CreateSurface(mesh) EntityFX mesh,1+2+16 Else last_surf = CountSurfaces(mesh) surf = GetSurface(mesh,last_surf) If CountVertices(surf) > 30000 Then surf = CreateSurface(mesh) End If v1 = AddVertex(surf,x1,y1,z1) v2 = AddVertex(surf,x0,y0,z0) AddTriangle surf,v1,v1,v2 VertexColor surf,v1,r,g,b,1 VertexColor surf,v2,r,g,b,1 Return mesh End Function Function TConnections_Show() Local i% For i = 0 To NODES-1 c.TConnection = CurrentConnectionsArray(i) If c<>Null If c\entity FreeEntity c\entity c\entity = Line3D(mesh,c\node[0]\pos[0],c\node[0]\pos[1],c\node[0]\pos[2],c\node[1]\pos[0],c\node[1]\pos[1],c\node[1]\pos[2],0,128,255) EndIf Next End Function Function TPath_Show(path.TPathNode) If path = Null Return Local pn.TPathNode = path While pn<>Null If pn\nextPathNode<>Null c.TConnection = TConnection_getConnection.TConnection(pn\node\id,pn\nextPathNode\node\id) If c\entity FreeEntity c\entity c\entity = Line3D(mesh,c\node[0]\pos[0],c\node[0]\pos[1],c\node[0]\pos[2],c\node[1]\pos[0],c\node[1]\pos[1],c\node[1]\pos[2],255,128,0) EndIf pn = pn\nextPathNode Wend End Function spanningtree.bb ;by Christian Geißler ;24.1.2009 Const NODES%=100 Global NODES_XDIST# = 100 / 2 Global NODES_YDIST# = 100 / 2 Global NODES_ZDIST# = 100 / 2 Global CurrentConnections_counter% = 0 Global CONNECTIONS% = TConnection_calcConnCount%() Dim CurrentConnectionsArray.TConnection(NODES-1) Dim NODE_ARRAY.TNode(NODES) Dim CONNECTION_ARRAY.TConnection(CONNECTIONS) Type TQuicksortLink Field value# Field objHandle% End Type Type TNode Field id% Field entity% Field pos#[3] Field connected% End Type Type TConnection Field node.TNode[2] Field dist# Field valid% Field entity% End Type ;STRUCT TList Type TList Field f.TLink ;first link Field l.TLink ;last link Field count% End Type ;STRUCT TLink Type TLink Field n.TLink ;next link Field p.TLink ;previous link Field list.TList Field value% End Type Type TPathNode Field node.TNode Field nextPathNode.TPathNode Field value# Field travelDist# ;left over travel distance to target point End Type Type TPriorityQueue Field list.TList End Type Type TPriorityLink Field value# Field objHandle% End Type Function TQuicksortLink_create.TQuicksortLink(value#,objectHandle%) Local pl.TQuicksortLink = New TQuicksortLink pl\value = value pl\objHandle = objectHandle Return pl End Function Function TQuicksortLink_removeFirst%() Local l.TQuicksortLink = First TQuicksortLink If l<>Null Local h% = l\objHandle Delete l Return h EndIf End Function Function TQuicksortLink_removeLast%() Local l.TQuicksortLink = Last TQuicksortLink If l<>Null Local h% = l\objHandle Delete l Return h EndIf End Function Function TQuicksort_clear() For ql.TQuicksortLink = Each TQuicksortLink Delete ql Next End Function Function TQuicksort_sort() TQuicksort_sortPart(First TQuicksortLink,Last TQuicksortLink) End Function Function TQuicksort_sortPart(f.TQuicksortLink,l.TQuicksortLink) If f = l Return If l = Null Return If f = Null Return p.TQuicksortLink = f e.TQuicksortLink = l ;p = pivot element this.TQuicksortLink = f enum.TQuicksortLink = After this While this<>e And enum<>Null this = enum enum = After enum If this\value < p\value Insert this Before f f = this Else Insert this After l l = this EndIf Wend TQuicksort_sortPart(f,p) TQuicksort_sortPart(After p,l) End Function Function TNode_getDistanceBetween(n1.TNode,n2.TNode) Return Sqr(n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2]) End Function Function TConnection_calcConnCount%() ; See <a href="http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F" target="_blank">http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F</a> Return (NODES*(NODES+1)/2) - NODES End Function Function minInt(c1%,c2%) If c1<=c2 Then Return c1 Return c2 End Function Function maxInt(c1%,c2%) If c1>=c2 Then Return c1 Return c2 End Function Function TConnection_getConnection.TConnection(n1%,n2%) If n1=n2 Then Return Null Return CONNECTION_ARRAY(TConnection_getArrayPos(n1,n2)) End Function Function TConnection_getArrayPos%(n1%,n2%) Local na% = minInt(n1,n2) Local nb% = maxInt(n1,n2) Local pos% = 0 Local i% For i = 1 To na pos = pos + Sgn((na-i)) * (NODES - i) Next pos = pos + (nb-na) - 1 Return pos End Function Function TConnection_getConnectionTest() Local i% For i = 5000 To 5005 Local c2.TConnection = TConnection_getConnection((i/1000)+1,(i Mod 1000)+1) If c2<>Null Print ((i/1000)+1)+"/"+((i Mod 1000)+1) + " = "+c2\node[0]\id + "/"+c2\node[1]\id EndIf Next End Function Function TNode_InitAll() Local i% DebugLog "Init Nodes" For i% = 1 To NODES Local n.TNode = New TNode n\id = i n\pos[0] = Rnd(-NODES_XDIST,NODES_XDIST) n\pos[1] = Rnd(-NODES_YDIST,NODES_YDIST) n\pos[2] = Rnd(-NODES_ZDIST,NODES_ZDIST) NODE_ARRAY(i-1) = n Next End Function Function TConnection_Create.TConnection(n1.TNode,n2.TNode) Local c.TConnection = New TConnection c\node[0] = n1 c\node[1] = n2 c\dist = (n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2]) Return c End Function Function TConnection_InitAll() DebugLog "Init Connections" Local stmp% = NODES-1 Local c% = 0 TQuicksort_clear() For i1% = 0 To stmp For i2% = i1 To stmp If i1<>i2 CONNECTION_ARRAY(c) = TConnection_Create(NODE_ARRAY(i1),NODE_ARRAY(i2)) TQuicksortLink_create.TQuicksortLink(CONNECTION_ARRAY(c)\dist,Handle(CONNECTION_ARRAY(c))) c = c + 1 EndIf Next Next DebugLog "sorting connections: ..." Local time% = MilliSecs() TQuicksort_sort() DebugLog "sorting connections: finished within "+(MilliSecs()-time)+" ms" End Function Function TConnection_CreateSpanningTree(startNode.TNode) Local i% DebugLog "Reset" CurrentConnections_counter = 0 For n.TNode = Each TNode n\connected = False Next For c.TConnection = Each TConnection c\valid = False Next DebugLog "calculating min spanning tree" startNode\connected = True For i = 1 To NODES TConnection_CreateSpanningTree_Sub() Next DebugLog "cleaning up" ;For qsl.TQuicksortLink = Each TQuicksortLink ; Local c.TConnection = Object.TConnection(qsl\objHandle) ; If c\node[0]\connected And c\node[1]\connected ; Local pos% = TConnection_getArrayPos%(c\node[0]\id,c\node[1]\id) ; If CONNECTION_ARRAY(pos)<>Null Delete CONNECTION_ARRAY(pos) ; CONNECTION_ARRAY(pos) = Null ; EndIf ;Next TQuicksort_clear() DebugLog "finished calc spanning tree" For i% = 0 To NODES-1 c.TConnection = CurrentConnectionsArray(i) If c<>Null Then DebugLog "c "+c\node[0]\id+" <--> "+c\node[1]\id+" dist:"+c\dist Next End Function Function TConnection_CreateSpanningTree_Sub() ; choose smallest edge which connects the graph with unconnected nodes For qsl.TQuicksortLink = Each TQuicksortLink Local c.TConnection = Object.TConnection(qsl\objHandle) If c\node[0]\connected Xor c\node[1]\connected c\node[0]\connected = True c\node[1]\connected = True c\valid = True CurrentConnectionsArray(CurrentConnections_counter) = c CurrentConnections_counter = CurrentConnections_counter + 1 Delete qsl Return EndIf Next End Function Function TList_first%(l.TList) Return TLink_value(l\f) End Function Function TList_last%(l.TList) Return TLink_value(l\l) End Function Function TList_firstLink.TLink(l.TList) Return l\f End Function Function TList_lastLink.TLink(l.TList) Return l\l End Function Function TList_addLast.TLink(list.TList,value%) Local newLink.TLink = TLink_create(list,list\l,Null,value) Return newLink End Function Function TList_insertBeforeLink(link.TLink,value%) TLink_insertBefore(link,value) End Function Function TList_insertAfterLink(link.TLink,value%) TLink_insertAfter(link,value) End Function Function TList_addFirst.TLink(list.TList,value%) Local newLink.TLink = TLink_create(list,Null,list\f,value) Return newLink End Function ;removes last link and returns its value Function TList_removeLast%(l.TList) Return TLink_remove(l\l) End Function ;removes first link and returns its value Function TList_removeFirst%(l.TList) Return TLink_remove(l\f) End Function ;returns count of elements in this list Function TList_count%(l.TList) Return l\count End Function ;clears all values from list Function TList_clear(l.TList) While l\f<>Null TList_removeFirst(l.TList) Wend End Function Function TLink_create.TLink(list.TList,pL.TLink,nL.TLink,val%) If list = Null Return Null Local l.TLink = New TLink l\p = pL l\n = nL If pL<>Null If pL\n = nL pL\n = l Else DebugLog "ERROR" EndIf Else ;then this should be the first one list\f = l EndIf If nL<>Null If nL\p = pL nL\p = l Else DebugLog "ERROR" EndIf Else ;then this should be the last one list\l = l EndIf l\list = list list\count = list\count + 1 l\value = val Return l End Function Function TLink_insertBefore(link.TLink,value%) TLink_create(link\list,link\p,link,value) End Function Function TLink_insertAfter(link.TLink,value%) TLink_create(link\list,link,link\n,value) End Function Function TLink_value%(link.TLink) If link<>Null Return link\value End Function Function TLink_nextLink.TLink(link.TLink) Return link\n End Function Function TLink_prevLink.TLink(link.TLink) Return link\p End Function Function TLink_remove%(l.TLink) If l = Null Return If l\p<>Null l\p\n = l\n EndIf If l\n<>Null l\n\p = l\p EndIf If l=l\list\f l\list\f = l\n EndIf If l=l\list\l l\list\l = l\p EndIf l\list\count = l\list\count - 1 l\p = Null l\n = Null l\list = Null Local val% = l\value Delete l Return val End Function Function TPriorityQueue_create.TPriorityQueue() Local pq.TPriorityQueue = New TPriorityQueue pq\list = New TList Return pq End Function Function TPriorityQueue_delete(pq.TPriorityQueue) TList_clear(pq\list) pq\list = Null Delete pq End Function Function TPriorityQueue_clear(pq.TPriorityQueue) TList_clear(pq\list) End Function ;Adds an objectHandle whitch might be a very low one ;meaning it starts testing from the lower end of the list Function TPriorityQueue_addLowest(pq.TPriorityQueue,objectHandle%,value#) Local newPL.TPriorityLink = TPriorityLink_create(value,objectHandle) Local oldPL.TPriorityLink = Null Local link.TLink = TList_firstLink(pq\list) While link<>Null oldPL = Object.TPriorityLink(TLink_value(link)) If newPL\value<=oldPL\value TList_insertBeforeLink(link,Handle(newPL)) Return EndIf link = TLink_nextLink(link) Wend TList_addLast(pq\list,Handle(newPL)) End Function ;Adds an objectHandle whitch might be a very high one ;meaning it starts testing from the higher end of the list Function TPriorityQueue_addHighest(pq.TPriorityQueue,objectHandle%,value#) Local newPL.TPriorityLink = TPriorityLink_create(value,objectHandle) Local oldPL.TPriorityLink = Null Local link.TLink = TList_lastLink(pq\list) While link<>Null oldPL = Object.TPriorityLink(TLink_value(link)) If newPL\value>=oldPL\value TList_insertAfterLink(link,Handle(newPL)) Return EndIf link = TLink_prevLink(link) Wend TList_addFirst(pq\list,Handle(newPL)) End Function ;Adds an objectHandle to either the end or the beginning of the list (takes that one that seems better) Function TPriorityQueue_add(pq.TPriorityQueue,objectHandle%,value#) Local pl.TPriorityLink = Object.TPriorityLink(TList_first(pq\list)) If pl<>Null If pl\value > value ;insert at the beginning TPriorityQueue_addLowest(pq,objectHandle%,value#) Else TPriorityQueue_addHighest(pq,objectHandle%,value#) EndIf Else TPriorityQueue_addLowest(pq,objectHandle%,value#) EndIf End Function ;returns: Handle of object with lowest value Function TPriorityQueue_getLowest%(pq.TPriorityQueue) Local pl.TPriorityLink = Object.TPriorityLink(TList_first(pq\list)) If pl<>Null Return pl\objHandle End Function ;returns: Handle of object with highest value Function TPriorityQueue_getHighest%(pq.TPriorityQueue) Local pl.TPriorityLink = Object.TPriorityLink(TList_last(pq\list)) If pl<>Null Return pl\objHandle End Function ;returns: Handle of object with lowest value Function TPriorityQueue_removeLowest%(pq.TPriorityQueue) Local pl.TPriorityLink = Object.TPriorityLink(TList_removeFirst(pq\list)) If pl<>Null Return pl\objHandle End Function ;returns: Handle of object with highest value Function TPriorityQueue_removeHighest%(pq.TPriorityQueue) Local pl.TPriorityLink = Object.TPriorityLink(TList_removeLast(pq\list)) If pl<>Null Return pl\objHandle End Function Function TPriorityQueue_count%(pq.TPriorityQueue) Return TList_count(pq\list) End Function Function TPriorityLink_create.TPriorityLink(value#,objectHandle%) Local pl.TPriorityLink = New TPriorityLink pl\value = value pl\objHandle = objectHandle Return pl End Function ;finds a minimal path between start and finish Function AStar_getPath.TPathNode(start.TNode,finish.TNode) Local visited%[NODES] Local n.TPathNode = Null Local nn.TPathNode = Null Local whitelist.TPriorityQueue = TPriorityQueue_create() n = TPathNode_create(finish,Null) TPriorityQueue_addLowest(whitelist,Handle(n),TPathNode_CalcValue(n,start)) visited[n\node\id] = True While n\node <> start n = Object.TPathNode(TPriorityQueue_removeLowest%(whitelist)) If n = Null Exit If n\node = start Exit For i% = 0 To NODES-1 Local c.TConnection = CurrentConnectionsArray(i) If c<>Null If c\node[0] = n\node Or c\node[1] = n\node If Not visited[c\node[1]\id] visited[c\node[1]\id] = True nn = TPathNode_create(c\node[1],n) TPriorityQueue_addLowest(whitelist,Handle(nn),TPathNode_CalcValue(nn,start)) ElseIf Not visited[c\node[0]\id] visited[c\node[0]\id] = True nn = TPathNode_create(c\node[0],n) TPriorityQueue_addLowest(whitelist,Handle(nn),TPathNode_CalcValue(nn,start)) EndIf EndIf EndIf Next Wend TPriorityQueue_delete(whitelist) Return n End Function Function TPathNode_create.TPathNode(node.TNode,nextNode.TPathNode) Local pn.TPathNode = New TPathNode pn\node = node pn\nextPathNode = nextNode If nextNode<>Null pn\travelDist = nextNode\travelDist + TNode_getDistanceBetween(node,nextNode\node) EndIf Return pn End Function ;calculates node value ;this is the heuristic of AStar Function TPathNode_CalcValue#(current.TPathNode,start.TNode) Return TNode_getDistanceBetween(current\node,start) + current\travelDist End Function Function TPathNode_deletePath(path.TPathNode) While path<>Null Local n.TPathNode = path\nextPathNode Delete path path = n Wend End Function Last edited 2011

limdorn (Posted 2011) [#4]

Thanks. You help a lot.

Warpy (Posted 2011) [#5]

Aaar! I've just spent an hour or so writing a proper explanation of the algorithm in BlitzMax, and I've just noticed this is in the b3d forum! Eugh! Anyway, here's the code, and here's an EXE file of the demo. It walks through the algorithm step by step, explaining what's going on.