• Create Account

Need scary sound effects or creepy audio loops for your next horror-themed game? Check out Highscore Vol.3 - The Horror Edition in our marketplace. 50 sounds and 10 loops for only \$9.99!

### #Actualprushik

Posted 13 November 2012 - 05:08 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?

### #2prushik

Posted 13 November 2012 - 05:08 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?

### #1prushik

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: