Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
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.
Posted 31 October 2012 - 04:01 AM
Posted 03 November 2012 - 07:13 AM
Edited by Tournicoti, 03 November 2012 - 07:45 AM.
Posted 03 November 2012 - 10:07 PM
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.
No it is not.Out of curiosity, is that your master thesis that you linked to?
Edited by Tournicoti, 04 November 2012 - 03:12 AM.
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.
#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; }
Edited by prushik, 04 November 2012 - 08:51 PM.
Posted 11 November 2012 - 08:09 AM
#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 && 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 && 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 && 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) && 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 && 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,&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; }
//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; }
Edited by prushik, 13 November 2012 - 05:08 AM.
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.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.