Author Topic: A star control 1 remake that may actually get finished  (Read 70387 times)

0 Members and 1 Guest are viewing this topic.

Offline Angelfish

  • *Happy Camper*
  • ***
  • Posts: 235
  • Karma: 7
  • Fear Boop. Run away and hide. Quickly!
    • View Profile
    • VandeDonk.nl - InsaniBlog
Re: A star control 1 remake that may actually get finished
« Reply #165 on: September 22, 2009, 01:06:23 am »
Hehe, who knows, this board might come alive yet ;).
As to the starmap.. maybe it's possible to realign the starmap by starting with the 2d starmap with Z=0, and then displace a few stars or clusters on the Z-axis and then realign the other stars to keep these distances.
What would you give to know the truth?

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #166 on: December 14, 2009, 05:59:23 am »
In matlab one can sort of do that by saying something like
Code: [Select]
if variable==2
    StructureType='gaussian'
end
----
if StructureType=='gaussian'
    insert stuff here
end

Anyway, I wrote some MST code* and it seems to do the job. I implemented Jarnik/Prim's algorithm.


The code and that image . . . actually, all the goodies I've posted in this thread, will disappear between christmas and new year because of a server migration.

The numerical result of the code is the array ``branches". Each row of this array corresponds to an MST branch, containing the length of the branch, the index of the first endpoint, and the index of the second endpoint. These indices are assigned to each of the points contained in the starting list ``inputpositions". It essentially says that the 4th point is connected to the 67th point, et cetera.

Some kind of optimisation might be possible for how it selects positions to test for possible branches, but I'm not sure. Maybe also seeding the MST from one of the corners would speed it up a bit.

So, that would guarantee that all stars are connected. To get the loops, I'm thinking there is probably an easier way than the delaunay tessellation, which seems tricky in three dimensions. A procedure for adding additional links, once one has the MST. For each node of the starmap, calculate the distances to neighbouring stars within some radius - possibly the length of the longest MST link already there. These are the stars that might get linked.

Modify each distance by multiplying it by a sum. There is a contribution to this sum corresponding to each point which is closer (and the corresponding potential links P). Each of these contributions is arbitrary factor*(pi/(angle)). Angle is the angle between two lines. One of these is a potential link, the other is the link to the point whose distance is being modified. This modified distance will be greatly increased if there are lots of stars that are closer and along the path where the link would be.

Using the modified distances, create links to stars within some radius. Basically a way of linking points such that connections get ``broken" by intervening stars.

Time for me to go to sleep, and time for you to stumble through my retarded explanation ;D Nice avatar Dragon, are we getting a spectacular remake for christmas?

EDITS
Optimisation is both necessary and possible via a number of ways. I'm on the case, but who knows when I'll get around to it.

*Also posted on ultronomicon.

Added comments to the code.
« Last Edit: February 14, 2010, 05:27:05 am by Zeracles »
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #167 on: December 18, 2009, 02:30:04 am »
Firefox sucks - it just disappeared midway through typing this.  Anyway, here we go again.

I got your code thanks, although I see you've *just* also added it to the Ultronomicon.

On reflection it's all good that my original post got lost.  I had little misunderstanding on how I was going to detect links 'broken' by stars added to form loops.  I'll have to have a think about it again.

I still have a technical backlog before I get to working on Star Control specifics.  If you look at my last post (somewhere) - I mentioned I was working on the UI.  While doing that I realised I didn't have a good input library and while writing an input library I discovered a huge omission in my image editing routines (they both use the same code for bit fiddling).  I'm slowly pushing the stack back to Star Control but it'll be a long haul.

Once I get back to SC I still need to add your star generation routines and Gaussian blur for nebulae and then I can get to actually implementing an MST.  Phew.

Eventually I'll get to it but it'll take a while and, as luck would have it, life's been utterly chaotic here - every time I think things are calming down something else happens.  So, yes, eventually, eventually.  And now I must get back to working because - wait for it - there's been a stuff up.

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #168 on: December 18, 2009, 05:14:39 am »
This thread is now the number one result in google for annigilate me!

With any luck, there'll be a flood of people registering to downvote me 8)

Firefox sucks - it just disappeared midway through typing this.  Anyway, here we go again.
IE sucks - whenever my X server hangs (which it did a few hours ago) I have to close it to start up cygwin again (and reopen all my terminals, remote logins and any other linux-y stuff I had up).

On reflection it's all good that my original post got lost.  I had little misunderstanding on how I was going to detect links 'broken' by stars added to form loops.  I'll have to have a think about it again.
Yeah, my explanation didn't cut it.

See here 3 stars
1      2      3

Do we make a link between 1 and 3? Looking at it from position 1's perspective, my suggestion is to consider all stars that are closer than 3. In this case, 2 is closer. Will it prevent the link between 1 and 3?

If 2 is the only star that's closer, it's the only one to consider. We compare the angle a 1->2 link would make with the 1->3 link in prospect. This angle is zero. This is the angle that goes into the little formula I mentioned involving pi/angle. Since it's zero, the result is infinity, which we then multiply with the distance between 1 and 3. No matter what distance has been set for two stars to be linked within, it'll be less than this modified distance, so 1 will not be linked to 3. Which is the sort of the linking behaviour we're after. Hope that makes it clearer.

I don't think it's necessarily better than the delaunay tessellation, but it should be really easy, hopefully meaning there's nothing difficult left with the starmap.

I need to get back to work too. Must be a conspiracy ;)
« Last Edit: December 18, 2009, 05:20:14 am by Zeracles »
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #169 on: December 18, 2009, 05:32:55 am »
This thread is now the number one result in google for annigilate me!
With any luck, there'll be a flood of people registering to downvote me
Oh shit, I completely forgot about karma.  Here, let me annigilate you ;D.  Also another annigilation reference for the old Goo'g.  Ooo, and another...

IE sucks - whenever my X server hangs (which it did a few hours ago) I have to close it to start up cygwin again (and reopen all my terminals, remote logins and any other linux-y stuff I had up).
Wha...?  I don't even want to think about what IE's locked to stop cygwin starting.

I don't think it's necessarily better than the delaunay tessellation, but it should be really easy, hopefully meaning there's nothing difficult left with the starmap.
I think that sounds good, I haven't hit it with an example yet but I'll probably be internet'less until next year so prolly my last post 'til then.

Hmm... a spectacular christmas remake.  I'll see what I can ...  8) ... shine up.
« Last Edit: December 18, 2009, 05:34:58 am by Dragon »

Offline mminasi

  • Hunam
  • *
  • Posts: 3
  • Karma: 0
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #170 on: January 02, 2010, 03:02:50 pm »
Just wanted to say that this looks better and better. Can NOT wait.  Thanks for the efforts!

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #171 on: February 14, 2010, 08:48:33 am »
Gave my (45 minute) seminar and it all turned out pretty well :) It had some similarities with this thread (slides), I used one of the stellar backgrounds from earlier in this thread as the slide background, talked about smoothing, MSTs and Delaunay Tessellation as part of the intro, the subject of the talk was an algorithm I developed and abortively tried to generate nebulae earlier and also used the 3D visualisation stuff (developed from the background code) a bit (slides 1 and 17).

That's an aside. Down to business -

I've found a use for MSTs in my work, so that's pushed this up my list which is also my excuse to Cedric for doing this instead of working on his mod.

Before, the MST code would take minutes to generate the MST over 50 input points. Now that I've done the necessary optimisation, thousands of points can be linked in minutes. This involved coming up with a new algorithm for generating the MST. At the time, I was working at an internetless computer and couldn't find out if I was reinventing any wheels, but it turns out someone beat me to it >:(

If you follow the logic in this code rather than the one I posted before, it should go a lot faster. Actually, if you wait long enough I'll do the C conversion, but that could be a weighty wait indeed.

So now I can post some more impressive demos

MST on 1000 random points in 2 dimensions.


MST on 1000 random points in 3 dimensions. It takes a bit longer (something like 1.25 times as long) to do this in 3D.


It may not have a use in this project, but there's an option I added to do a thing called ``separation" - remove all branches above some arbitrary length to leave behind islands. Uh, in case there's a race that can make long-distance travel difficult, or something.


Again, this may not have a use, but this is the result of ``pruning", removing long thin branches (after separation). For this purpose, branches are defined as the lines comprising nodes that only have 2 links at most coming from them. It's supposed to make the structure in the input points easier to see at a glance. As you can see there isn't much structure in a random field ;D It might have a use for displaying the starmap along with zoom and rotate tools, or something.

So next I need to test the procedure for adding links to get the closed loops. Should be easy compared with this, and if not, I guess there's always Death's idea to fall back on . . .
« Last Edit: February 14, 2010, 09:48:47 am by Zeracles »
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #172 on: February 15, 2010, 11:03:58 am »
As luck would have it I got into the office all bright and shiny eyed to do a massive post here.  Then Zeracles beat me too it.  I haven't had a chance to understand it yet but it looks cool.

I don't have anything pretty to show but I came across an interesting problem this weekend so I thought I'd share.  Or maybe I should say the solution was interesting, the problem has been around for *ages*.

Basically something happens - a user presses a key, resizes the window or even blows up the enemy - and there are a number of other objects that want to know about it.  Yep.  It's eventing.  Now it's been solved time and time again and in probably every language ever invented.  So how can I possibly have anything to say about it?

Well, I hadn't yet found a solution that I was entirely happy with - certainly I've implemented any number of eventing systems but I've never liked any of them.  Mostly they've felt to complicated and that lead me to believe I didn't really understand what the problem space was.  So this weekend I had a long think about what it is I really wanted from an eventing system.  The solution - when I finally found it - proved to be ridiculously simple.

Something happens to an object and that object wants to tell any other interested objects: "Hey! This thing happened to me".  I could start using words like queues and stacks and guaranteed delivery at this point but, really, all I want to do is send those objects a message.  And a message - to the purists - is just a function call.  My problem is reduced to: how do I call a method on several objects at the same time.  Normally when sending a message (ie: calling a function) the object receiving the message most be known at compile time.  However I couldn't assume that I would know about every object that could ever possibly be interested in my message.  Someone else will - very likely - want to know about it after I'm done with my code.

The solution is - obvious to c++ programmers - a bit of virtual function magic.  But that's not enough I wanted the usage to be simple as well.  When I post my message (or send my event or whater you'd call it) I want to type one line saying: "This happened" - all those who wanted to know about it must magically hear me.  But even that's not enough.  If I'm listening for any message I want to type only one line to say I'm interested and only one more line to say I hear it.

The solution is in the blue block below (view the image to get a readable size).


The class CEvent, it's a potential message; it isn't an actual message that is being sent right now.  It knows who's interested in it has a collection of listeners.  The function AddListener is all that's required to tell the event you're interested in it.  Actually that's not strictly true, the object that's interested has to inherit from CListener to force the compiler to provide the largest possible function pointers (multiple virtual inheritance) but CListener is an empty class so it's not too painful.

The function CallListeners actually sends the message.  It's the heart of the solution, everything else is just engineering to make it work.  And how it works is what makes this all so elegant - it's why I've posted this.  For instance let's say there is a missile object and an asteroid object.  The missile wants to know if the asteroid is destroyed so it can stop tracking it*.  When the asteroid is destroyed it runs this line of code (previously the missile must have added itself to the asteroids Event as a listener Asteroid.Event.AddListener but that's trivial).  Line of code:

Code: [Select]
Asteroid.Event.CallListeners(AsteroidListener::Destroyed, Asteroid);

C++ can deduce the template parameter - in this case AsteroidListener - automatically.  One doesn't have to specify the template parameter with <> like: CallListeners<AsteroidListener>(AsteroidListener::Destroyed, Asteroid).  But that's still not the real magic, that's just saving a bit of redundant typing.  No, if you look at the CallListeners function you will see a rather strange local variable declared as:

Code: [Select]
M cTemp
Where M is the template parameter: AsteroidListener.  It creates an actual instance of AsteroidListener on the stack.  We need this instance so that we have the virtual function table for AsteroidListener**.  We need the virtual function table so that we can call GetClassName on it.  Wait! what?  It looks like there's no such method but deeper in the system some preprocessor madness means that certain classes (including all CListeners and sub-classes) do have that method.  How that works is a tale for another time.  For the sake of this post just assume that GetClassName on AsteroidListener has been implemented and returns "AsteroidListener".

Given the name of our Listener we can now look through all the Listeners in the Event that are AsteroidListeners.  This guarantees that the function we are calling on the listeners exists: AsteroidListener::Destroyed.  The function is called using the rather strange and nasty ->* operator in

Code: [Select]
(pcListener->*ListenerFunc)(pcSource, pvContext)
ListenerFunc is the AsteroidListener::Destroyed parameter passed to CallListeners originally.  The brackets around "(pcListener->*ListenerFunc)" are necessary because of some retardation in the C++ spec regarding precedence of operators. 

And that, is how you call a method on any number of objects in one line.

Neat huh?

*Why?  I don't know.  It's a contrived example.  Deal with it.
**Only instances have virtual function tables, we can't call virtual functions statically.  Bugger.


@Zeracles: Expect another post shortly  ;)

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #173 on: February 19, 2010, 10:07:09 am »
So that's how an asteroid will know to explode (and everything that follows) when I shoot it? What a beautiful story!

I was thinking about writing simulation code for things ranging from projectiles to galaxy clusters. Something like what you posted could be handy for handling events like, uh, asteroids blowing up.

Another Massive Post coming soon 8)
« Last Edit: February 19, 2010, 10:12:30 am by Zeracles »
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #174 on: February 19, 2010, 11:27:07 am »
Another Massive Post coming soon 8)
Oh god no!!!  I'm still trying to understand the last one  ;D

I was thinking about writing simulation code for things ranging from projectiles to galaxy clusters. Something like what you posted could be handy for handling events like, uh, asteroids blowing up.
Well mostly I use it for mundane stuff like reading keystrokes etc... but, yeah, telling things to blow up is fun.
« Last Edit: February 19, 2010, 11:33:50 am by Dragon »

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #175 on: February 22, 2010, 11:45:03 pm »
I've implemented my earlier idea about the addition of links to get the closed loops, and I think it does the job. I'm calling it the Minimally Connected Opaque Friend Graph feel free to call it a Zeracles graph if you prefer. I've posted the definition and code for it on the ultronomicon. Anyone interested in the details should read that page.


This is the same two-dimensional MST as before, with links added to produce an MCOFG. There are two numbers that vary the connectedness of the graph. This has friendliness = locality factor = 1. The original MST had 999 links, this has 1078.


Here I've increased the friendliness to 1000, which increases the number of links to 1402. There are links going through points here, which we don't really want. Friendliness increases the number of links each point makes to its neighbours, but doesn't change the length scale that defines its ``neighbourhood." This is what the locality factor is for.


Here I've reduced the friendliness back to 1 but increased the locality factor to 2, which gives 3195 links. This is reminiscent of the delaunay tessellation, which we considered earlier, but perhaps better for our purposes, since this doesn't necessarily make a convex hull, and is adaptable with the two parameters here. I think this is what we want, so annigilate it!


This is the same, but on the three-dimensional MST - 8585 links. Bit hard to tell what's going on, but this stuff should generalise very simply to any number of dimensions.

The one caveat with this is that all these examples are done with random point distributions, and trying this out with structured fields is an important test. Apart from that, the remaining (optional?) step is removal of links weighted by length, as mentioned earlier, which is trivial. Reducing the locality factor might give a similar result but not random. I'd also like to implement Death 999's idea in some way. I'll be leaving this stuff alone until I've done a few things for Cedric though.

Well mostly I use it for mundane stuff like reading keystrokes etc... but, yeah, telling things to blow up is fun.
I was thinking about the sort of event this might be good for in the simulation, and imagined a change to the laws of physics. Adding ``God" as a Listener should be pretty amusing ;)
« Last Edit: February 22, 2010, 11:54:14 pm by Zeracles »
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #176 on: February 23, 2010, 02:36:55 am »

Here I've reduced the friendliness back to 1 but increased the locality factor to 2, which gives 3195 links. This is reminiscent of the delaunay tessellation, which we considered earlier, but perhaps better for our purposes, since this doesn't necessarily make a convex hull, and is adaptable with the two parameters here. I think this is what we want, so annigilate it!
Sweet!  This one looks like WinnarTM.  I wouldn't worry about increasing the friendliness and getting lines passing through points because in 3D is unlikely a line will pass *exactly* through a point.

And now all that's left is for me to actually implement it - you know: the Zeracles graph.   I think that this weekend, I should stop mucking around with UI code and write something interesting.  :)

Offline Angelfish

  • *Happy Camper*
  • ***
  • Posts: 235
  • Karma: 7
  • Fear Boop. Run away and hide. Quickly!
    • View Profile
    • VandeDonk.nl - InsaniBlog
Re: A star control 1 remake that may actually get finished
« Reply #177 on: February 23, 2010, 10:56:43 am »
Good idea dragon :). Go get this thing on the road!
What would you give to know the truth?

Offline Zeracles

  • Talking Pet
  • ****
  • Posts: 421
  • Karma: -69
  • Icon of X
    • View Profile
    • Me
Re: A star control 1 remake that may actually get finished
« Reply #178 on: February 24, 2010, 05:04:04 pm »
Page 12 and we're still on the bike track? ;D

Thanks Dragon, if you're doing a conversion based on the code I posted, let me know if anything is confusing.

I wouldn't worry about increasing the friendliness and getting lines passing through points because in 3D is unlikely a line will pass *exactly* through a point.
Normally yes, but if one of the structures in the starmap is a thin ``wall" (like in an example I posted on the previous page), it becomes much more likely as then it's locally reduced to the planar case.
Fear not the Arch Viles and Spectres of the Deepest Reaches, for the X is strong in this place.

In my next life I would like to be a pootworm. ANNIGILATE ME!

Offline Dragon

  • Talking Pet
  • ****
  • Posts: 364
  • Karma: 16
    • View Profile
Re: A star control 1 remake that may actually get finished
« Reply #179 on: February 25, 2010, 03:08:03 am »
Page 12 and we're still on the bike track? ;D
Well, more of an animal path but...

Go get this thing on the road!
Yep! Time to get some actual Star Controlling done.

Which reminds me, I must take your code home on Friday or I'm going to be sitting there looking lost for the next four days (Yay for 2 days off!).  Should probably take a few PDFs on DTs and MSTs also...