• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
prushik

Linking nodes in a grid

5 posts in this topic

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
0

Share this post


Link to post
Share on other sites
Hello

Yes there is an algorithm for this [i]exactly [/i]!
Have a look on [url="http://en.wikipedia.org/wiki/Neural_gas"]Growing Neural Gas[/url] [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]


Basically, an edge is inserted between the 2 winning nodes ( ie the 2 closest nodes from the input vector ), but ...
[url="http://booru.net/download/MasterThesisProj.pdf"]Here 's a detailed explanation[/url]

Hope it helps ! [img]http://public.gamedev.net//public/style_emoticons/default/rolleyes.gif[/img] Edited by Tournicoti
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
[quote name='prushik' timestamp='1352002067' post='4997076']
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.[/quote]

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 [url="http://en.wikipedia.org/wiki/Self-organizing_map"]Kohonen Map[/url]. 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.

[quote name='prushik' timestamp='1352002067' post='4997076']
Out of curiosity, is that your master thesis that you linked to?
[/quote]
No it is not.

Bye [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by Tournicoti
0

Share this post


Link to post
Share on other sites
[quote name='Tournicoti' timestamp='1352020135' post='4997114']
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 [url="http://en.wikipedia.org/wiki/Self-organizing_map"]Kohonen Map[/url]. 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.
[/quote]

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

[/code]

Something like that.... Edited by prushik
0

Share this post


Link to post
Share on other sites
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[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;
}[/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? Edited by prushik
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0