Helping out with External Code

[keith.lamothe]

That does look like a much clearer way to do the sun-to-sun pattern Reminds me of the X pattern in terms of strategic implications, but I think I like this more than X.

[BadgerBadger]

Thanks! I'm glad to see people seem to like it so far. There are still some tweaks left, so I'll be posting more pictures later (for example, my code doesn't scale up nicely to 120 planets).

I'm having some cool ideas for things that could be done with gameplay mods that are based on Map Types. A few brainstorming ideas:  "As soon as you leave an outer solar system and get to a planet in the inner ring, the Nemesis is unleashed from its home planet, which is at the very middle of the map. The Nemesis will attack anything that comes into the inner ring, but doesn't ever really go into the outer solar systems. However, if you go to the Nemesis' home planet and destroy a Magic Structure there, it will die permanently."

Another cool sort of thing would be "Each outer solar system has different types of guardians/defenses; one is heavy on MLRS, another uses Gravity, another uses lightning".

I'm not sure how possible this will be with the tools Keith can provide for us though, but a badger can dream!

[BadgerBadger]

Quick question: Are there any bad side effects of calling "using System.Threading" in MapGeneration.cs? I'm considering trying an interesting map that might be computationally expensive, and want to make sure a threading implementation would work if I can't make the algorithm < O((n/2)!)

[keith.lamothe]

Quick question: Are there any bad side effects of calling "using System.Threading" in MapGeneration.cs? I'm considering trying an interesting map that might be computationally expensive, and want to make sure a threading implementation would work if I can't make the algorithm < O((n/2)!)

The "Travelling Salesman" map type, eh? Or using a force-driven untangling algorithm?

There's no inherent problem with multithreading the mapgen, but you'll need to make sure that the result is 100% deterministic based on the seed or it will break multiplayer (as well as violating the customary semantics of having a map seed). That generally means that either each thread gets its own random generator or only one thread does random generations. And of course you need to avoid more mundane race-conditions and non-determinacies.

Bear in mind that mapgen already happens on its own thread, so you don't have to worry about the screen freezing during the generation or whatever.

[BadgerBadger]

So I dug out my old Graph Theory notes, because I thought that implementing a few graph theory algorithms might lead to interesting maps. Here's a map style constructed by scattering points at random across a circle centered on GalaxyCenter, then using Prim's algorithm to construct a minimum spanning tree. I think this looks pretty cool!

[z99-_]

So I dug out my old Graph Theory notes, because I thought that implementing a few graph theory algorithms might lead to interesting maps. Here's a map style constructed by scattering points at random across a circle centered on GalaxyCenter, then using Prim's algorithm to construct a minimum spanning tree. I think this looks pretty cool!

If I ever had any doubt that modding was worth the amount of time Chris and Keith have been putting into it, I can say they are now gone. Just glancing at it, I wouldn't be surprised if this ends up becoming my new favorite map type. I'm curious, how long did it take you to make this?

And do you have other awesome map types planned?

[Draco18s]

So I dug out my old Graph Theory notes, because I thought that implementing a few graph theory algorithms might lead to interesting maps. Here's a map style constructed by scattering points at random across a circle centered on GalaxyCenter, then using Prim's algorithm to construct a minimum spanning tree. I think this looks pretty cool!

Looks cool, but it would be hell to play. It's basically an X map.

Now, if you added in extra linkages at random, you'd get some good connectivity.

[BadgerBadger]

Yeah, it is pretty similar to an X, though it's got a more organic feel to it. I'll look into adding some extra linkages though.

[z99-_]

Looks cool, but it would be hell to play. It's basically an X map.

That depends on your playstyle. For a conquer-the-galaxy player (like myself) the many chokepoints and branching paths are a huge advantage.

It would be really interesting if some nomad planets were added to this map. That would certainly spicen things up  >D

[keith.lamothe]

Don't some of the maze types use prim?

[BadgerBadger]

@Keith, The Maze code uses an interesting set of backtrackings which seemed a bit daunting, so I never put much effort into grokking that code. It might use Prim's, though Prim's requires you to check distances, and I don't see obviously where you are doing so.  I found Concentric and Wheel to be a better source of coding inspiration, so I mostly taught myself using those.

@z99, coding this one wasn't too hard; think "First coding project for a 200 level graph theory course/comp sci course". The single hardest part of creating maps was making my very first one (it was 10 planets in a line), because I just wasn't sure how all the pieces worked yet.  Once the MapGen code has totally stabilized I will post my notes and write up a toy map generator with lots of comments (on the wiki, probably) so that it will be easier for anyone else. I also have more cool ideas for map types, just wait and see!

@Keith, I can see a number of useful ways someone could want to tune a map to their playstyle. For example, the Spanning tree one I just posted immediately had two opinions as to whether it was good as is, or whether it should have more random linkages. Since I don't expect most people will want to futz about in the C#, my thought is I could have a "Spanning" and a "Spanning with links" map type, but it might be easier if a given map type would expose some tunables for it that could be set by the user in the Map Selection Screen.

[Draco18s]

So the way I added extra links in a project I was working on was to generate the MST and then randomly pick a node, from its list of neighbors* remove the ones its already connected to, then from the rest remove any that are already connected to any neighbor we already removed.  This results in loops that are at least 4 nodes in size (because we removed all 3-node hops by excluding any neighbor connected to a connected neighbor).

And you only need around 5-10% of the tree to gain an extra link for it to have sufficient alternate routes.

*Presumably you did a Delaney triangulation prior to MST-ing.

[BadgerBadger]

@Draco, I tried out adding connections to the MST "randomly" but it did not give good results. Then I tried your idea (tracking nearest X neighbors, and only linking points that are sufficiently distant) and I really like it. My code now has flags for "How many random connections to add to the MST" and "How many jumps away must two planets be to consider linking them".

Opinions?

[keith.lamothe]

Nice

I suggest only linking planets where the resulting connection does not overlap another connection (you can call GetWouldLinkCrossOverOtherPlanets( Planet First, Planet Second ) to check for that). Much more visually pleasing and understandable, though of course certain map types benefit from the extra flexibility.

[BadgerBadger]

I have done so, but it doesn't seem to work (maybe I'm misusing it?); observe that the connection between Lehman and Orillia on the right overlaps with another connection.

Here is a map, and here is a code snippet that is used when generating the map.
I know there won't be overlaps from just the spanning tree, so these overlaps have to come
from the random connections code, but the random connections code uses your GetWouldLinkCrossOverOtherPlanets function.

            //Two potential planets are selected for random connections (neither has                                                                                                                                                                                                                                          
            //a random connection yet)                                                                                                                                                                                                                                                                                        
            //Lets make sure a link there does not cause any overlap in lines                                                                                                                                                                                                                                                 
            Planet firstPlanet = planetsForMap[firstPlanetIdx];                                                                                                                                                                                                                                                               
            Planet secondPlanet = planetsForMap[secondPlanetIdx];                                                                                                                                                                                                                                                             
            bool wouldLinkCrossOtherPlanets = UtilityMethods.GetWouldLinkCrossOverOtherPlanets(firstPlanet, secondPlanet);                                                                                                                                                                                                    
            if(wouldLinkCrossOtherPlanets)                                                                                                                                                                                                                                                                                    
              {                                                                                                                                                                                                                                                                                                               
                i--; //discard this pair, since there's an overlap                                                                                                                                                                                                                                                            
              }                                                                                                                                                                                                                                                                                                               
            else                                                                                                                                                                                                                                                                                                              
              {                                                                                                                                                                                                                                                                                                               
                firstPlanet.AddLinkTo(secondPlanet);                                                                                                                                                                                                                                                                          
                usedPlanetsForConnections.Add(firstPlanetIdx);                                                                                                                                                                                                                                                                
                usedPlanetsForConnections.Add(secondPlanetIdx);                                                                                                                                                                                                                                                               
              }                                                                                                                                                                                                                                                                                                               

When I look at your code, I see

                if ( Mat.LineIntersectsRectangleContainingCircle( First.GalaxyLocation, Second.GalaxyLocation, 
                                                                                         planetToNotHit.GalaxyLocation, 
                                                                                         planetToNotHit.TypeData.IntraStellarRadius ) )                                                                                                                                  

It looks like this says "Make sure the ensuing line does not intersect a planet body, not a connection", but I could easily be misreading this (I can't see the Mat class to check).