Hey guys, hows it going?
Essentially, what I am trying to do is generate a grid. (done)
Populate the grid randomly with some number of nodes. (done)
Iterate through all the nodes, generate a random number between 1 and 4 and link to that many nearby nodes. (ehh..)
Dissolve the grid leaving only the array of connected nodes behind.

So, creating and populating the grid are no problem. Linking the nodes is the issue I am struggling with. Yes, I know it should be easy to do, however, I discovered that my code becomes way too complicated really quickly. There must be some kind of existing algorithm for this kind of thing, right?
For the grid, I just made a 2D array called grid (I am using C), the nodes are also an array. I just randomly place a node in the grid, generating a new random if that grid space is already occupied.
After that, I iterate through the nodes, this is where the trouble starts. I want to find the closest node in the array (that isn't already linked to the current node) to the current node, and then create a link by adding the node's index to an array in the node structure, and the links should go both ways (doubly linked).
I also want to favor nodes in opposite directions of existing links if there are any, and also favor nodes which can be connected with horizontal or vertical lines (avoid diagonal lines somewhat) - These rules are not 100% necessary.

Is there some existing algorithm for this? how would you accomplish this task? thanks for the help, I love you

Hello

Yes there is an algorithm for this exactly !
Have a look on Growing Neural Gas


Basically, an edge is inserted between the 2 winning nodes ( ie the 2 closest nodes from the input vector ), but ...
Here 's a detailed explanation

Hope it helps !

Hmm... an algoritm for neural networks. That's not exactly my application, and from the looks of it it will need to be greatly simplified for my program, but maybe I can use it. I need to take a closer look at it, and I can't do that on my phone.
If it does what I want and I can implement it then I will be very happy, thank you.
Out of curiosity, is that your master thesis that you linked to?

Hmm... an algoritm for neural networks. That's not exactly my application, and from the looks of it it will need to be greatly simplified for my program, but maybe I can use it.

It's a competitive neural network model, nothing to do with multi-layered perceptrons. Your application can be seen as a self organizing map,
and is very close to a Kohonen Map. The difference is that you try to build the topology during the learning process, the topology isn't static, that's why I suggested to have a look on Growing Neural Gas. It will explain : how to link/unlink nodes and how to create/destroy nodes.

Out of curiosity, is that your master thesis that you linked to?

No it is not.

Bye

It's a competitive neural network model, nothing to do with multi-layered perceptrons. Your application can be seen as a self organizing map,
and is very close to a Kohonen Map. The difference is that you try to build the topology during the learning process, the topology isn't static, that's why I suggested to have a look on Growing Neural Gas. It will explain : how to link/unlink nodes and how to create/destroy nodes.

I do think my topology will be static, I am only creating these nodes and then linking them, once that is finished, the connections and nodes will never change again, I won't create or destroy nodes or unlink them. The map will just be created once in the beginning and then used 'as is' afterwards.
Essentially, traversing the map will be the user's responsibility, if that makes a difference.

Will it be helpful if I post some of my code?


#define MAX_NODES 100
#define GRID_W 50
#define GRID_H 50

struct node
{
int x,y;
int links;
int link[4];
};

struct node node[MAX_NODES];

void genMap()
{
//create grid
int grid[GRID_W][GRID_H];

int i,j;

//zero grid
for (i=0;i<GRID_W;i++)
for (j=0;j<GRID_H;j++)
grid[j]=0;


//fill grid
for (i=0;i<MAX_NODES;i++)
{
//variable for guesses
int gx,gy;
do
{
gx=rand()%GRID_W;
gy=rand()%GRID_H;
} while (grid[gx][gy]!=0);

grid[gx][gy]=i+1;
node.x=gx;
node.y=gy;
}

//link nodes....
for (i=0;i<MAX_NODES;)
{
//........
}

return;
}



Something like that....

I got something that does pretty much everything I want. It's not perfect, but its pretty close to perfect. The code is a little complicated and spread out, messy in some places.
Here is what it looks like:
[source]
#include "global.h"
#include "random.h"

#define MAX_NODES 26
#define GRID_W 8
#define GRID_H 8
#define NULLNODE (MAX_NODES+1)

struct node
{
int x, y;
int links;
int link[4];
};

struct candidates
{
int closest[4];
};

static struct node node[MAX_NODES];
//static struct node overflow; //This is for debugging so I can check it for overflows from the node array
static int grid[GRID_W][GRID_H];

//Get the distance between two nodes
double nodeDistance(int a, int b)
{
double dx,dy;

dx=fabs(node[a].x-node.x);
dy=fabs(node[a].y-node.y);
return sqrt((dx*dx)+(dy*dy));
}

//Get the direction from one node to another
int nodeDirection(int a, int b)
{
double dir;
double dx,dy;

dx=node[a].x-node.x;
dy=node[a].y-node.y;

// if ((int)(atan2(dy,dx)*(180.0/PI))>90)
// printf("direction from %c to %c: %d\n",a+'a',b+'a',(int)(atan2(dy,dx)*(180.0/PI)));

return (int)(atan2(dy,dx)*(180.0/PI));
}

//Sort intager arrays by the distance from the corresponding node to another specific node
void insertionSortNodeDistance(int *list, int n, int baseNode)
{
int i;
for (i=1;i<n;i++)
{
int item=list;
int hole=i;
while (hole>0 &amp;&amp; nodeDistance(list[hole-1],baseNode)>nodeDistance(item,baseNode))
{
list[hole]=list[hole-1];
hole=hole-1;
}
list[hole]=item;
}
}

//This function does an insertion sort on intager arrays. Fairly useless
void insertionSortInt(int *list, int n)
{
int i;
for (i=1;i<n;i++)
{
int item=list;
int hole=i;
while (hole>0 &amp;&amp; list[hole-1]>item)
{
list[hole]=list[hole-1];
hole=hole-1;
}
list[hole]=item;
}
}

//examine a node pair for backward links
int backlinkCheck(int a, int b)
{
int i;

//return true if a backward link already exists
for (i=0;i<node.links;i++)
if (node.link==a)
return 1;

return 0;
}

//examine nodes to find candidates for linking
//clobbers w, returns number of link candidates
int findCandidateNodes(int baseNode, struct candidates *w)
{
int i,j,linkc=0;
int table[MAX_NODES];

for (i=0;i<4;i++)
w->closest=NULLNODE;

//fill the table with some node numbers
for (i=0;i<MAX_NODES;i++)
table=i;

//sort node table by distance to base node
insertionSortNodeDistance(table,MAX_NODES,baseNode);

//Pass1: Backlinks
for (i=0;i<MAX_NODES;i++)
{
int p=backlinkCheck(baseNode,table);

if (p &amp;&amp; linkc<4)
w->closest[linkc++]=table;
}

int k;
//Pass2-n: Remove similar nodes from table
for (k=linkc;k<4;k++)
{
//Remove node is similar directions
for (i=0;i<linkc;i++)
for (j=0;j<MAX_NODES;j++)
if (nodeDirection(w->closest,baseNode)+360>=((nodeDirection(table[j],baseNode)-45)+360) &amp;&amp; nodeDirection(w->closest,baseNode)<=((nodeDirection(table[j],baseNode)+45)%360))
table[j]=NULLNODE;

//select closest remaining node as next candidate
for (i=0;i<MAX_NODES;i++)
if (table!=NULLNODE &amp;&amp; table!=baseNode)
if (linkc<4)
{
w->closest[linkc++]=table;
break;
}
}

#ifdef DEBUG_GRID
//print candidates
printf("%c: ",baseNode+'a');
for (i = 0; i < 4; i++)
{
printf("%c|",w->closest+'a');
}
printf("\n");
//print table
printf("%c: ",baseNode+'a');
for (i = 0; i < MAX_NODES; i++)
{
printf("%c|",table+'a');
}
printf("\n");
#endif

return linkc;
}

int main(int argc, unsigned char **argv)
{
int i, j;

//zero grid
for (i=0;i<GRID_W;i++)
for (j=0;j<GRID_H;j++)
{
grid[j]=NULLNODE;
}

//Seed the PRNG
sxor128(14);

//fill grid
for (i=0;i<MAX_NODES;i++)
{
int gx,gy;

do
{
gx=xor128()%GRID_W;
gy=xor128()%GRID_H;
} while (grid[gx][gy]!=NULLNODE);

grid[gx][gy]=i;
node.x=gx;
node.y=gy;
}

//link nodes
for (i=0;i<MAX_NODES;i++)
{
struct candidates candidates;

int n=findCandidateNodes(i,&amp;candidates);

node.links=n;
for (j=0;j<n;j++)
{
node.link[j]=candidates.closest[j];
}
}

#ifdef DEBUG_GRID
//print grid
for (i=0;i<GRID_W;i++)
{
printf("|");
for (j=0;j<GRID_H;j++)
{
if (grid[j]!=NULLNODE)
printf("-%c-",grid[j]+'a');
else
printf(" ");
}
printf("|\n");
}
#endif

return 0;
}[/source]

xor128() is the xorshift PRNG copied from wikipedia. I wanted something that was simple, fast, and predictable across platforms, true randomness is not important.
it looks like this:

[source]//This is essentially the Wikipedia xorshift PRNG algorithm
//WARNING: This function may fall under the creative commons license
unsigned int xor128()
{
static unsigned int x = 123456789;
static unsigned int y = 362436069;
static unsigned int z = 521288629;
static unsigned int w = 88675123;
unsigned int t;

t = x ^ (x << 11);
x = y; y = z; z = w;

return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

//This kinda pseudo-seeds the xor128 PRNG by running it a bunch of times
//It't not a true seed since it doesnt reset the values
void sxor128(unsigned int s)
{
for (;s>0;s--)
xor128();

return;
}[/source]
The main issue with the code is that it is possible in some cases (although somewhat rare) for a node to have more than 4 nodes linking to it, which means that it will only link back to 4 of them, leaving one or more 1-way links. This can be observed by compiling the code as is (with my random seed of 14) with -DDEBUG_GRID and observing node 25 ('z').

Any ideas?