This is a basic example of how a slightly modified Prims Algorithm can be used to generate a grid or web of connections between points on a map.
In this case, I'm going to be using this for a game in the future - however this is a principle which could be useful for others.
You start with a set of "n" points. You then pick a starting one and connect up to the nearest "valid" point (I'll explain valid in a minute). Next loop, you find the nearest point to your starting one or the one you just chose (ie the shortest connection from either 'A' OR 'B') - making sure its a valid connection. Third time around, you use either 'A', 'B' OR 'C' as start points, finding the closest from those 3. Keep going until you can find no more shortest routes.
A Valid Connection is, in this case, one which does not cross the path of any existing paths. This is done using fairly simple variation on the "Y = MX + C" formula to figure out WHERE the intersection is between lines AB and CD. Once we know where that is, we can check of that intersection point lies between the X points of AB (we know that if it is between the two X points, it WILL be between the Y as its an INTERSECTION). If it is between the points, it intersects and therefore is NOT a valid line. If it doesn't, check against another connection.
Another criteria of a valid connection is that the connection doesn't already exist (in either direction... Connection AB is the same as BA).
I think that's about it!
NOTE: This example contains a line which requires Cloggy's Plugin... Its the line with "d3d_line3d" on it - this just joins up the lines.
Language:
Dark Basic Pro
Code:
`Initialise the system sync on sync rate 0 color backdrop 0 autocam off `Define some constants #constant TRUE 1 #constant FALSE 0 `Create a "floor" object, position it, point it upwards and colour it green make object plain 1000, 100, 100 position object 1000, 50, 0, 50 point object 1000, 50, 1, 50 color object 1000, 0x005500 `Position the camera above the map, looking down on it position camera 50, 100, 50 point camera 50, 0, 50 `Define a 2D vector for null = make vector2(1) `This is a Coord Type with 3 axis Type Coord x as float y as float z as float EndType `This is a "city" which is just a point on the map Type City p as Coord EndType `This is a connection definition, ` Basically a connection is just 2 city ID's and ` a gradient and constant for efficiency Type Connection `Cities ID's a as integer b as integer `Numbers for Line formula (y = mx + c) m as float c as float EndType `Create 20 cities/points InitializeCities(20) `Create connections between cities InitializeConnections() `This is just so we dont keep looking up the array size CityCount as integer : CityCount = array count( Cities() ) `Standard frame timer code frameTime as float : frameTime = 1.0 startTime as integer : startTime = timer() do frameTime = ( 0.5 * frameTime) + (0.5 * (timer() - startTime)) startTime = timer() `Print numbers next to city objects for i = 1 to CityCount : text object screen x(i)+10, object screen y(i)-10, str$(i) : next i `Loops over all connections, rendering a 3d line using Cloggy's DLL array index to top Connections() while array index valid( Connections() ) d3d_line3d Cities(Connections().a).p.x, 0.0, Cities(Connections().a).p.z, Cities(Connections().b).p.x, 0.0, Cities(Connections().b).p.z next array index Connections() endwhile sync loop function InitializeConnections() `tC is Temp Connection - this just gets generated as a template conection and passed for validation tc as Connection `This stores the best connection - at end of loop, this gets added if a connection is found. nextConnection as Connection `This is a list of CONNECTIONS (ie lines) and CONNECTED city ID's Dim Connections() as Connection Dim Connected() as integer `Create 1 connected city - assume city ID 1 is the start point. array insert at bottom Connected() Connected() = 1 `This is just an efficiency thing - no need to keep calculating the count, its static. CityCount as integer : CityCount = array count( Cities() ) `This while loops terminates if we've looped around and not found a closest city. `When we first loop, ClosestCity will be 0 while ClosestCity > -1 `This is just runtime debugging - slow PC's will appreciate this. text 0, 0, "Connected: " + str$(array count (Connected())) + ", Connections: " + str$(array count (Connections())) sync `Find Closest - initialise to variables ClosestDist as float : ClosestDist = 10000.0 ClosestCity as integer : ClosestCity = -1 `Loop over all CONNECTED cities (first loop will be city ID 1, for example) array index to top Connected() while array index valid( Connected() ) `For each city we have already connected, try connecting to every other city for i = 1 to CityCount `.. Except the one we're already looking at (ie, dont connection from point A to point A) if i <> Connected() `Use the 2D Vector to find the distance - faster than using Square Root for some reason! set vector2 1, Cities( Connected() ).p.x - Cities(i).p.x, Cities( Connected() ).p.z - Cities(i).p.z `If this potential connection is closer than the currently known closest valid connection, continue if length vector2(1) < ClosestDist `Check if connection exists ConnectionOK as boolean : ConnectionOK = TRUE `Loop over connections array index to top Connections() while array index valid( Connections() ) `Check connection both ways around if Connections().a = Connected() AND Connections().b = i then ConnectionOK = FALSE : exit if Connections().b = Connected() AND Connections().a = i then ConnectionOK = FALSE : exit next array index Connections() endwhile if ConnectionOK `Connection is not already done, create a template connection `This just makes sure the lowest ID is in A. Just for debugging sanity really... if Connected() > i tC.a = i tC.b = Connected() else tC.a = Connected() tC.b = i endif `Define Dx and Dx (Difference in X and Z coords - in this case, Y = MX + C is really Z = MX + C... Y = Z) dx as float : dx = 0.0 dz as float : dz = 0.0 `Find X difference dx = Cities( tC.a ).p.x - Cities( tC.b ).p.x if dx <> 0 `dX isn't vertical, so we can calculate gradient and constant dz = Cities( tC.a ).p.z - Cities( tC.b ).p.z tC.m = dz / dx tC.c = Cities( tC.a ).p.z - ( tC.m * Cities( tC.a ).p.x ) else `Odd case for vertical lines with infinite gradient - THIS NEEDS FIXING tC.m = 0.0 tC.c = 0.0 endif `Finally, confirm this is a valid connection (ie no overlaps) if ConnectionValid( tC ) `Closest City is the one we're looking at ClosestCity = i `Next Connection to add is THIS connection nextConnection = tC `Closest Distance is THIS distance ClosestDist = length vector2(1) endif endif endif endif next i `Ok - look at the next connected city.. next array index Connected() endwhile `After looping over all other cities, we should now have the closest most valid connection. If not, ClosestCity will be -1 if ClosestCity > -1 `Add this city to the "connected" list, if its not already in it inLoop as Boolean : inLoop = FALSE array index to top Connected() while array index valid( Connected() ) AND inLoop = FALSE if Connected = ClosestCity then inLoop = TRUE next array index Connected() endwhile if inLoop = FALSE then array insert at bottom Connected() : Connected() = ClosestCity `Add the connection array insert at bottom Connections() : Connections() = nextConnection endif endwhile endfunction function ConnectionValid( tC as Connection ) `Use cA and cB as shorthand references to the a/b links to the position for this connection cA as Coord : cA = Cities(tC.a).p cB as Coord : cB = Cities(tC.b).p `Loop over all connections array index to top Connections() while array index valid( Connections() ) `If this connection for comparison shares a point with the test connection (eg, comparing AB and BC), then skip the check - they WONT intersect in any bad way) if cA.x = Cities(Connections().a).p.x AND cA.z = Cities(Connections().a).p.z then goto SKIP if cA.x = Cities(Connections().b).p.x AND cA.z = Cities(Connections().b).p.z then goto SKIP if cB.x = Cities(Connections().a).p.x AND cB.z = Cities(Connections().a).p.z then goto SKIP if cB.x = Cities(Connections().b).p.x AND cB.z = Cities(Connections().b).p.z then goto SKIP `Work out the overlapping X Coords `y = Mx + C `Assume Y's are equal... `M1x + C1 = M2x + C2 `x(M1 - M2) = C2 - C1 `x = (C2 - C1) / (M1 - M2) x as float x = (tC.c - Connections().c) / (Connections().m - tC.m) y as float y = (tC.m * x) + tC.c `Now the "Does it cross INSIDE line AB rather than on the infinte line determined by AB's gradient and offset" test.. crossesTest as boolean : crossesTest = FALSE if cA.x < cB.x if x >= cA.x AND x <= cB.x then crossesTest = TRUE else if x >= cB.x AND x <= cA.x then crossesTest = TRUE endif `crossesTest will only be TRUE if the intersection point lies between the X values of the potential connection which is being tested by this funciton if crossesTest = TRUE `Now test it lies between the X coords of this connection we're comparing AGAINST. If it is - exit the function, we have an intersection so we dont need to check anything else. if Cities(Connections().a).p.x < Cities(Connections().b).p.x if x >= Cities(Connections().a).p.x AND x <= Cities(Connections().b).p.x then exitfunction FALSE else if x >= Cities(Connections().b).p.x AND x <= Cities(Connections().a).p.x then exitfunction FALSE endif endif `Skip point SKIP: `Assume no match, move onto the next Connection for comparison next array index Connections() endwhile endfunction TRUE `Simple function to generate some random cities which are at least 5 'units' away from each others function InitializeCities(cities) tooClose as boolean tPos as Coord Dim Cities(cities) as City for i = 1 to array count(Cities()) Check: Cities(i).p.x = FRnd() * 100.0 Cities(i).p.z = FRnd() * 100.0 tooClose = FALSE for j = 1 to i-1 set vector2 1, Cities(j).p.x - Cities(i).p.x, Cities(j).p.z - Cities(i).p.z if length vector2(1) < 5.0 then tooClose = TRUE : exit next j if tooClose then goto Check make object sphere i, 2 position object i, Cities(i).p.x, 0, Cities(i).p.z next i endfunction `Floating Point RND function - returns a number between 0.0 and 1.0. function FRnd() r as float r = rnd(33554432) / 33554432.0 endfunction r
(1 vote)