• Create Account

## Linking nodes in a grid

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1prushik  Members

164
Like
0Likes
Like

Posted 31 October 2012 - 04:01 AM

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

### #2Tournicoti  Prime Members

704
Like
0Likes
Like

Posted 03 November 2012 - 07:13 AM

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 !

Edited by Tournicoti, 03 November 2012 - 07:45 AM.

### #3prushik  Members

164
Like
0Likes
Like

Posted 03 November 2012 - 10:07 PM

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?

### #4Tournicoti  Prime Members

704
Like
0Likes
Like

Posted 04 November 2012 - 03:08 AM

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

Edited by Tournicoti, 04 November 2012 - 03:12 AM.

### #5prushik  Members

164
Like
0Likes
Like

Posted 04 November 2012 - 08:45 PM

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;
};

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[i][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[i].x=gx;
node[i].y=gy;
}

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

return;
}



Something like that....

Edited by prushik, 04 November 2012 - 08:51 PM.

### #6prushik  Members

164
Like
0Likes
Like

Posted 11 November 2012 - 08:09 AM

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:
#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;
};

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[b].x);
dy=fabs(node[a].y-node[b].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[b].x;
dy=node[a].y-node[b].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[i];
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[i];
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 i;

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 table[MAX_NODES];

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

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

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

for (i=0;i<MAX_NODES;i++)
{

}

int k;
//Pass2-n: Remove similar nodes from table
{
//Remove node is similar directions
for (j=0;j<MAX_NODES;j++)
if (nodeDirection(w->closest[i],baseNode)+360>=((nodeDirection(table[j],baseNode)-45)+360) &amp;&amp; nodeDirection(w->closest[i],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[i]!=NULLNODE &amp;&amp; table[i]!=baseNode)
{
break;
}
}

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

}

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[i][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[i].x=gx;
node[i].y=gy;
}

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

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

for (j=0;j<n;j++)
{
}
}

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

return 0;
}

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:

//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;
}

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?

Edited by prushik, 13 November 2012 - 05:08 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.