Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
5 replies to this topic

#1 prushik   Members   -  Reputation: 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

Sponsor:

#2 Tournicoti   Prime Members   -  Reputation: 684

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 Posted Image


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 ! Posted Image

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


#3 prushik   Members   -  Reputation: 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?

#4 Tournicoti   Prime Members   -  Reputation: 684

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 Posted Image

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


#5 prushik   Members   -  Reputation: 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;
     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[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;
     }

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

     return;
}


Something like that....

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


#6 prushik   Members   -  Reputation: 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;
	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[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 backlinkCheck(int a, int b)
{
	int i;

	//return true if a backward link already exists
	for (i=0;i<node[b].links;i++)
		if (node[b].link[i]==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[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);

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

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

	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[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)
				if (linkc<4)
				{
					w->closest[linkc++]=table[i];
					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

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

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

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

		node[i].links=n;
		for (j=0;j<n;j++)
		{
			node[i].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[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.



PARTNERS