A star control 1 remake that may actually get finished

[Death 999]

Not that it really changes much, but one of those stars has 5 neighbors.

[Zeracles]

There were loops in SC1, so a minimal spanning tree method is definitely not the way.

Which is why I said its main utility would be to ensure we don't get isolated clusters, with loops achieved by other means. MST is not the only way to do this of course, I'm going to mention another later in this post.

As for sensitivity of parameters... I don't see that as a problem.

It becomes a problem if a large fraction of one's parameter space gives undesirable results, such that it's just a narrow band one is aiming for. This was just my first impression, though, maybe the ``undesirables" I was thinking of are actually ``interesting".

Here's a map with the connections drawn in (and that was a tedious task of note)

Thanks for posting those linked stars, they are illuminating!

Hmm, that dead end with two stars near the plus sign is interesting, or maybe not if it's actually not so close in 3D to that other arm of stars.

Nah, really I was being facetious.  That's what directX and friends are for  

I really need to branch out beyond my numerical box . . .

At least to generate gameplay interesting maps higher level structures would be needed to create it.  eg:  LineOfStars could contain stars and the end points of other lines of stars.  Unfortunately we're wondering into realms I haven't thought about so I don't have anything valuable to add yet.  What I would like to do is keep the clusteryness of Zeracles' stars but I don't think that should be a problem if one generates fractal regions/volumes and then places lines of stars (etc..) within them.

Ah, now this is interesting, fractal. A fractal set of points might be connected by a graph that isn't fractal. An MST should preserve the fractal nature of it but if that's followed up by connecting all points separated by less than some arbitrary distance, the self-similarity is broken.

I thought of a graph that should preserve the self-similarity, called the Delaunay Tesselation. It's related to the Voronoi Tesselation and I think it has some nice properties. It makes closed loops on all scales, connects all the points and doesn't do crazy interconnectedness. It also removes any arbitrary choices in the assignment of links, leaving that choice to the structure in the distribution . . . which is where I would choose to put it; there should be a reasonable intuition between the distribution of points and the links in the end result, in my opinion.

The problem with DT is that it doesn't do dead ends - there are way too many triangles to emulate what was in SC1. Looking at the image Dragon posted, perhaps this problem could be solved by removing all links above some arbitrary length (retaining all MST links to ensure all stars remain linked). The user could then choose how much to reduce the interconnectedness - effectively, how many dead ends to substitute for the triangles, without fear of creating isolated clusters. Just another possibility thrown out there.

EDITed many times for clarity.

[Dragon]

Not that it really changes much, but one of those stars has 5 neighbors.

Oops, that was my fault.  The central line in the quad shouldn't be there.  When I screenshotted that image the two stars connected by that line were almost ontop of each other so I moved the one and then got confused.  But as you said, it makes no real difference.

Hmm, that dead end with two stars near the plus sign is interesting, or maybe not if it's actually not so close in 3D to that other arm of stars.

No, they're not close in 3D so unfortunately not very interesting.  I've update the map with oranges stars which are significantly behind other stars in the local set.

... called the Delaunay Tesselation. It's related to the Voronoi Tesselation ...

Aaaagh, both of those two did my head in when in 3D.  But, I think that Delaunay Triangulation could be a winner if links are removed randomly weighted to length.  Also a slightly more interesting graph would be created if the 4 connection maximum is enforced.

I have one question though: (in 2d) what does the Delaunay Triangulation of two separate clusters look like?  Does one end up with one convex hull around both clusters or does it create connections between the closest points in the clusters too each other and a dumbbell shape?

I dug up this link for it's examples but they always have spares points around the edges.

[EDIT] Bugger!  It'll produce the convex hull right?

[Zeracles]

... called the Delaunay Tesselation. It's related to the Voronoi Tesselation ...

Aaaagh, both of those two did my head in when in 3D.

Yeah, I always think of the Voronoi construction as bubbles expanding from each point, spreading along surfaces where they meet to create the edges of the cells. Then join any two points that share a cell surface for the Delaunay links (I don't even know how to define Delaunay independently of Voronoi ).

As an aside, this is an interesting application of it. Chapter 6 does the full nerd treatment and there's a picture on page 32 of 3D voronoi, also a 3D DT on page 41. Not sure if they really help though.

But, I think that Delaunay Triangulation could be a winner if links are removed randomly weighted to length.

I agree, this is probably better than removing all links above some length . . . actually, randomly removing without the weighting could retain self-similarity such that clusters are connected in the same way as points within clusters.

I have one question though: (in 2d) what does the Delaunay Triangulation of two separate clusters look like?  Does one end up with one convex hull around both clusters or does it create connections between the closest points in the clusters too each other and a dumbbell shape?

I dug up this link for it's examples but they always have spares points around the edges.

[EDIT] Bugger!  It'll produce the convex hull right?

I think it depends a bit on how close together they are and how spherical they are. If they're sort of parallel lines one would get a convex hull. Maybe I should try plotting this up, I think matlab has inbuilt functions for these except I have work to do right now

[Zeracles]

[EDIT] Bugger!  It'll produce the convex hull right?

I haven't plotted this, just thought about it and I'm pretty sure you're right.

I agree, this is probably better than removing all links above some length . . . actually, randomly removing without the weighting could retain self-similarity such that clusters are connected in the same way as points within clusters.

I was also wrong when I said this, because clusters are likely to be connected by several links . . . if one wants the self-similarity, random removal weighted by length is looking good again, sorry.

I'm thinking MST is the minimal graph we'd have, and DT would give the max. The random removal weighted by length could be used to leave a graph that is somewhere in between. Haven't looked at how to actually do any of this though

[spinsane]

Wait a sec (haven't read thread), is there a reason why you want your mapping algorithm to work in three dimensions? I know that SC1 used a pseudo-3D map, but honestly, that thing was annoying. You'd be doing a world of good just making it in 2D: simpler and more user-friendly, as well as slightly less troublesome to program.

[Lukipela]

It's a remake, so it needs to contain all the stuff the original contained. It might contain more than one mode or some other sort of clarification though.

[Dragon]

As an aside, this is an interesting application of it. Chapter 6 does the full nerd treatment and there's a picture on page 32 of 3D voronoi, also a 3D DT on page 41. Not sure if they really help though.

Oh, dear... that sent me off on another mad tangent (until my PC packed up).  I've always enjoyed generating surfaces for whatever strange and in-explicable reason.

I think it depends a bit on how close together they are and how spherical they are. If they're sort of parallel lines one would get a convex hull. Maybe I should try plotting this up, I think matlab has inbuilt functions for these except I have work to do right now
...
I haven't plotted this, just thought about it and I'm pretty sure you're right.

Looking at a few more examples I don't know if the shape will always be convex (which is good).  I also really have to try this but - likewise - I have a biggish deadline on Monday so free time this weekend looks absent.

I was also wrong when I said this, because clusters are likely to be connected by several links . . . if one wants the self-similarity, random removal weighted by length is looking good again, sorry.

No worries, I haven't had a chance to try and produce anything yet.  Although I'm really itching to.  See stupid deadline above.

I'm thinking MST is the minimal graph we'd have, and DT would give the max. The random removal weighted by length could be used to leave a graph that is somewhere in between. Haven't looked at how to actually do any of this though

Hmm, if one generated the DT and then the MST from the DT and then removed - say - 80% of the edges but not touching any in the MST it should generate a pretty reasonable map with a few loops but mostly long paths.  Hope that made sense.

Is there a reason why you want your mapping algorithm to work in three dimensions?

Part of SC1 was trying to find (and protect) the best paths in 3D so (as Lukipela mentioned) that in itself is enough reason for me to keep it.  However the actual, unrationalised reason is that I think the 3D starmap looks pretty. 

It no longer does the continuous rotation thing - unless you leave the controls alone.  That was annoying and difficult to see.  Now it's possibe to rotate with the mouse or the gamepad and it'll only start rotating in a 'screensaver' mode.

[spinsane]

Right, I mean, in SC1 you still need to discover which astronomical bodies you can travel in between to determine chokes/find mining platforms/precursor stuff etc- but doing it in 2D doesn't necessarily detract from that- but I agree with the desire to keep things pure.

What is your storage/generation method for the maps? Or rather, do you have a prefered method of data storage/what lingual limitations are you operating under? It would be easy to work on an algorithm abstractly (all you need is position and pointers/references to the connecting stars, the rest is just your generation algorithm) and it may be fun for the rest of us to think about based upon what you've got already... *hint hint*

Also, the possibility of having random map scripts for particular types of maps would be very neat. One that situates Starbases close to each other, one that has a big loop, but all still randomized around a base algorithm for that type of map.

[Death 999]

One very simple way for fixing the starmaps would be to specify a random seed. You wouldn't get to PICK it except through the time-consuming method of trying seed candidates, but it would fix the result.

[Dragon]

Seeing spinsanes post I was just thinking that a general import routine might be perfect for Death999.  I already import Zeracles starmaps, adding the connections between them and the types of stars/planets would not be difficult.  Neither would be adding ships/starbases/artifacts.

I like the idea of importing maps because I'm quite likely to try and implement the DT/MST first.  I already have most of the basis for it from when I generated convex hulls for collision.  I'd rather get something out sooner than implement different types of generation routines.  I don't dislike Deaths idea but it's different from anything I have already so I'm hoping if I provided the tools...

I think random seeded with parameters (eg: from the original map editor) shouldn't be too hard.

and vaguely related here's....

... an old convex hull generation piccy which got lost at some point.

[spinsane]

Consider implementing concavity in your collision detection? IMO- it would be mighty cool to see a blazer get stuck in a Broodhome's grill...

[Dragon]

Consider implementing concavity in your collision detection? IMO- it would be mighty cool to see a blazer get stuck in a Broodhome's grill...

It's already in .  Unfortunately doing concave (ie: per per-triangle) collision is orders of magnitude slower than using hulls.

However I'm not doing rigid body simulation (that's a huge project all on it's own).  Instead I'm approximating the ships with particles so even if I did use concave collision detection they'd just bounce apart again anyways.

[spinsane]

It's already in .  Unfortunately doing concave (ie: per per-triangle) collision is orders of magnitude slower than using hulls.

With trimeshes in 3d, yes. Not in true 2d, especially since the ships are simple enough to hand draw your hit box to minimize the number of triangles... I mean, if you're into that .

[Angelfish]

Just use whichever collision detection algorithm works best for you, I don't really mind . Even rectangular hitboxes could easily work for almost all the ships, except the round ones (Melnorme and Mycon)