A star control 1 remake that may actually get finished

[Lukipela]

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...

Oooh, that sounds promising.

[Zeracles]

It might be worth noting that my approach to the MST is different to most others out there. Normally, one has a whole lot of ``weights" which in this context are the interpoint distances. There is a weight for every pair of points. So if one has 1000 points, the first step is often to calculate about half a million distances, and leave that array in memory while generating the MST.

I don't calculate all the weights first up because it isn't necessary, instead I search around each tree within a small radius for the closest points, and incrementally increase the search radius until it's sufficient to link all the points. I can't be sure it's faster than precomputing the weights to begin with, but the 1000 points in 3 dimensions takes about a minute on my computer, the way I've done it. Adding the links for the Zeracles graph is really cheap, possibly less than a second.

[Dragon]

@Zeracles, a couple of questions about your code:

Code:

index=transpose(linspace(1,lengthinputpositions,lengthinputpositions));

Does linspace create an integer array of 1..lengthinputpositions of length lengthinputpositions?  And if so, what does transposing it do?  I'm assuming it's changing it from a vector A_i1 to A_1i but I don't understand why.

Code:

remainingpositionxs=inputpositionxs(find(maskvector==0));

What does this code do?  I gues the == is a check for equality but does that 'find' then filter out all the zeros from inputpositions?  I couldn't make head or tail of it.

Code:

numbertrees=length(unique(treenumber));

Does unique imply that the array it returns is sorted in anyway or does it give the unique elements in the order that they're found?  Also does 'length' return the same result as numel?

K.  Gotta run.

[Zeracles]

Sorry

Does linspace create an integer array of 1..lengthinputpositions of length lengthinputpositions?

I think that's all I use it for here, but linspace is more general; linspace(a,b,n) creates a 1-by-n vector which contains values (not necessarily integers) linearly spaced between and including a and b. I think in the code I posted, I mostly do linspace(1,n,n), which just counts integers from 1 to n.

>> linspace(1,10,10)
ans =
     1     2     3     4     5     6     7     8     9    10

>> linspace(1,pi,4)
ans =
    1.0000    1.7139    2.4277    3.1416

In the instance you quote, I'm just numbering the trees, which to begin with are the input points themselves.

what does transposing it do?  I'm assuming it's changing it from a vector A_i1 to A_1i but I don't understand why.

Yep, that's exactly what it does. Here, it's from an earlier version of the code in which it was necessary, but now it isn't so I've removed it. I think I transposed it to get a column vector I could attach as a column to one of the other arrays.

EDIT*: But I transpose elsewhere in the code, because to feed elements of a vector into a for loop,

for i=somevector
   ...
end

the vector needs to be a row vector. Otherwise, there will only be one i, and it'll be a column vector. So I only transpose to put a vector in the right shape for iterating. Partly because of this, I like the way C does loops, but anyway - I don't think you'll have to tranpose at all.

Code:

remainingpositionxs=inputpositionxs(find(maskvector==0));

What does this code do?  I gues the == is a check for equality

Yes. == < <= > >= all return 1 if the relational condition is satisfied (and zero otherwise).

>> [-2,-1,0,1,2]==1
ans =
     0     0     0     1     0

>> [-2,-1,0,1,2]>=1
ans =
     0     0     0     1     1
     

does that 'find' then filter out all the zeros from inputpositions?

Right again - find returns the indices of all nonzero elements of a vector. If the vector was row or column, find(vector) will be row or column respectively.

>> find([-1,0,1])
ans =
     1     3

because only the second element is zero.

So find is handy for retrieving indices of elements that satisfy some condition.

Does unique imply that the array it returns is sorted in anyway or does it give the unique elements in the order that they're found?

It gives unique elements in ascending order.

>> unique([1,1,4,3])
ans =
     1     3     4

But as with the transpose thing, it's a redundant operation from an earlier version of the code, and I've removed this too.

Also does 'length' return the same result as numel?

For a vector (which is all I use it on here), yes.

Okay, now I'll see if I can spot anything else . . .

In a few places I manipulate arrays
[a,b,c] makes a row vector
[a;b;c] makes a column vector
[] is nothing - like declaring a 0-by-0 array that can have other arrays appended to it
array(:,2) returns the second column from the left of array (not the third like in C)
array(2,:) returns the second row from the top of array

Code:

xextent=eps;

eps is just a small number, 2.2204e-16, so that the area or volume (measure) can't be zero, which causes problems.

.* is element-wise multiplication, rather than matrix multiplication.

size(array) returns a vector which measures array (in numbers of rows and columns) - it's {number of rows, number of columns}, if array is only two-dimensional.

Sorry abut those (especially the bits that were redundant leftovers ), hassle me about anything else I haven't made clear, by post or PM.

*EDIT: above, about the transpose.

[Dragon]

I think that's all I use it for here, but linspace is more general; linspace(a,b,n) creates a 1-by-n vector

Just to be sure to be sure.  This creates a row right, not a column?  Would linspace(a;b,n) have create a column or am I trying to be clever?

Find returns the indices of all nonzero elements of a vector. If the vector was row or column, find(vector) will be row or column respectively.

Ah ha!  That makes a lot more sense knowing it returns the indices.  I really was stumped by what find was returning.

hassle me about anything else I haven't made clear, by post or PM.

Well... seeing as you asked...   

Code:

maskvector=treenumber==tree;
treeindices=find(maskvector);
lengthtreepositions=sum(maskvector);

remainingpositionxs=inputpositionxs(find(maskvector==0));
remainingpositionys=inputpositionys(find(maskvector==0));

Taking a look at this code here (and let's assume 5 points/trees to start with and that the tree we're dealing with is number 2).  Does this mean that:
maskvector equals [0,0,1,0,0].
treeindices equals 3 (the only non-zero in the vector
lengthtreepositions equals... wait a minute?  Does maskvector become something like:

Code:

0,0,1,0,0
0,0,1,  0
0,  1,  0

or is does it become an m by n matrix where all the rows and columns are the same length (with a bunch of ones down the center).
So first time around lenghtreepositions will equal 1 and later on more elements are added to the columns?
and finally remainingpositionxs and remainingpositionys both become [1,2,4,5]?

I'm sort of rubber ducking here/thinking aloud/whatever but I'm slowly starting to understand.  Please be patient, there's going to be a lot more questions yet...

Lasty, a general matlab question: Can an element in a matrix be a matrix itself?  I haven't worked out whether branches is using something like that or not.

[Zeracles]

No-one should get the wrong idea here, Dragon is a much better coder than me. Matlab is a language that allows people like me with no real computing background (I haven't done any computer courses) to avoid a lot of low-level stuff.

I think that's all I use it for here, but linspace is more general; linspace(a,b,n) creates a 1-by-n vector

Just to be sure to be sure.  This creates a row right, not a column?

Yep, a row.

Would linspace(a;b,n) have create a column or am I trying to be clever?

That's a brilliant inference, but semicolons don't mean anything in matlab function arguments as far as I know, unless they're being used within [] to construct arrays.

Code:

maskvector=treenumber==tree;
treeindices=find(maskvector);
lengthtreepositions=sum(maskvector);

remainingpositionxs=inputpositionxs(find(maskvector==0));
remainingpositionys=inputpositionys(find(maskvector==0));

I'll start by explaining what this does - I think you've got it, but just to be sure.

It all works by joining together trees. Each tree grows and is joined to nearby ones. This involves looking around each tree for nodes from other trees that are nearby. The first step here is to isolate the nodes of one tree. treeindices does this. lengthtreepositions is the number of nodes in this one tree, and the for loop a few lines later is where the searching is done, it visits each node of the tree, so i counts to lengthtreepositions.

Taking a look at this code here (and let's assume 5 points/trees to start with and that the tree we're dealing with is number 2).  Does this mean that:
maskvector equals [0,0,1,0,0].
treeindices equals 3 (the only non-zero in the vector

That's right, assuming you meant tree number 3.

lengthtreepositions equals... wait a minute?  Does maskvector become something like:

Code:

0,0,1,0,0
0,0,1,  0
0,  1,  0

*kicks self* I should have explained - the sum function arithmetically adds together all the elements of a vector (I don't think I use it on a matrix anywhere here). maskvector remains a vector, and lengthtreepositions is a scalar equal to the number of nodes contained in the current tree.

So first time around lenghtreepositions will equal 1 and later on more elements are added to the columns?

lenghtreepositions starts at one and increases as the number of ones in maskvector grows.

and finally remainingpositionxs and remainingpositionys both become [1,2,4,5]?

They'll become the xs and ys corresponding to the indices [1,2,4,5], yes.

Lasty, a general matlab question: Can an element in a matrix be a matrix itself?  I haven't worked out whether branches is using something like that or not.

No, but I can totally see what you're thinking. Matrices can be put together in the same way as scalars to form larger matrices. The individual elements of the ``ingredient" matrices then become individual elements of the resultant matrix. If I make a 4-by-4 matrix a, and another 4-by-4 matrix b, c=[a,b] would be a 4-by-8 matrix.

I'll go through exactly how branches evolves. It does indeed do the sort of thing I just described.

Code:

branches=[];

At the beginning, initialised as a 0-by-0 array.

Code:

mindistancecandidates=[mindistancecandidates;mindistancecandidate];
mindistancecandidateindices=[mindistancecandidateindices;branchcandidateindex];

When searching around the nodes of a particular tree to find potential linkees, many distances are stored so they can be compared later (we want the minimum distance). These distances are mindistancecandidates, and their indices are mindistancecandidateindices. We get this pair for each node of the current tree.

Code:

mindistance=[min(mindistancecandidates),treeindex,mindistancecandidateindices(find(mindistancecandidates==min(mindistancecandidates)))]; % minimum distances carry the indices of the prospective link destination
mindistances=[mindistances;mindistance];

Once we have all the neighbouring distances, we find the minimum, which is mindistance. It's a row vector, at this point I get it to carry the 2 indices of the potential link nodes, treeindex and . . . the other one. mindistance is the minimum distance for a single node of the tree. mindistances stores the minimum distances for all nodes of the current tree.

Code:

branchdistance=min(mindistances(:,1));
branchindex=find(branchdistance==mindistances(:,1));

These are the precursors to branch. For the current tree, we want the minimum distance from any node of that tree to any node outside that tree. This means we want the minimum (branchdistance) of the minima (mindistances) found at each node.

Code:

branch=mindistances(branchindex,:);

Here, the appropriate row of mindistances is selected and then -

Code:

branches=[branches;branch];

This is where branch is added as a row to branches. The final result of the code is a matrix with as many rows as there are MST links, and 3 columns. Each row has the length of the link and the indices of the two endpoints.

I'm sort of rubber ducking here/thinking aloud/whatever but I'm slowly starting to understand.  Please be patient, there's going to be a lot more questions yet...

No worries , I don't visit this place every day though, so I won't always be able to reply straight away.

In other news, this thread has broken into the forum's top 10!

[Lukipela]

This is probably the most complicated top 10 thread as well.

[Sage]

Really? I'm not having too much trouble following it myself!

[Zeracles]

Digital art, 3D models, graph theory, Dragon's awesomeness, a dash of cricket, sand dun The thread gets longer, Dragon's karma goes up, and mine goes down. Simple

[Dragon]

Still digesting this, just got a bit distracted by The Real World^TM

Matlab is a language that allows people like me with no real computing background (I haven't done any computer courses) to avoid a lot of low-level stuff.

In my not-so-humble opinion computer courses don't teach you how to program so it's no great loss if you haven't done any.  'Varsity courses tend to be theoretical and teach how compilers work or why network protocols are designed as they are; you should be a competent programmer before attending.  Technicon courses teach how to fill in the right check boxes in job interviews; they're mostly money spinners for whoever runs them.   Anyway, before I start ranting; I began with BASIC which is similar to Matlab in a number of aspects and goes to show that you don't need typed and compiled languages to achieve things.

I'll start by explaining what this does ... Matrices can be put together in the same way as scalars to form larger matrices.

Thanks, I think I understand this now.

I'll go through exactly how branches evolves. It does indeed do the sort of thing I just described ...

I still need to read this with understanding (as opposed to just skimming it).  I should have some time this weekend to go over it in detail.  Actually as the branch stuff was what I was really stuck on (I had no concept of what it was doing or even what was stored in the branches) I should make some good headway now.

And have an annigilation for your efforts .