home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 04 Pathfinding and Movement / 02 Surasmith / solution / solution.cpp next >
Encoding:
C/C++ Source or Header  |  2001-09-03  |  6.9 KB  |  378 lines
  1. /**
  2.     Smith Surasmith: Aug. 2001
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <limits.h>
  8. #include <time.h>
  9.  
  10. /**
  11.     Sample code for creating solution table
  12.  
  13.   - the solution table is 0 based.
  14.   - the example table in the book is 1 based.
  15.   - the values shown in soln.csv is one off from the book due
  16.     to the starting base difference.
  17. */
  18.  
  19. /**
  20.     Dijkstra:
  21.  
  22.     n - number of nodes
  23.     rbuf - the list for the result path, length n
  24.     tbl - connectivity table, lenght n-squared
  25.             2D array of weights,
  26.             <0 for no connections,
  27.             row major.
  28.     wbuf - buffer for scratch pad, length n
  29.             cost - SHRT_MAX for unchecked,
  30.                     >=0 for open,
  31.                     <0 for closed.
  32.             prev - the previous node index leading to current index
  33.     src - beginning index
  34.     dst - ending index
  35. */
  36. struct recDijkstra {
  37.     short cost;
  38.     short prev;
  39. };
  40.  
  41. bool Dijkstra(short n,short *rbuf,short *tbl,recDijkstra *wbuf,short src,short dst)
  42. {
  43.     short open,cur,min,cost,curCost;
  44.     int i,r;
  45.  
  46.     /* prep */
  47.     for(i=0;i<n;i++) {
  48.         wbuf[i].cost = SHRT_MAX;
  49.         wbuf[i].prev = -1;
  50.         rbuf[i] = -1;
  51.     }
  52.  
  53.     /* search */
  54.     cur=src;
  55.     open=1;
  56.     r=cur*n;
  57.     wbuf[cur].cost = -1;
  58.     curCost = tbl[r+cur];
  59.     while((cur!=dst)&&(0<open))
  60.     {
  61.         open--;
  62.  
  63.         /* look at all out going edges */
  64.         for(i=0;i<n;i++) 
  65.         {
  66.             if(i==cur) {
  67.                 continue;
  68.             }
  69.  
  70.             cost = tbl[r+i] + curCost;
  71.  
  72.             /* cost test */
  73.             if((curCost<=cost)&&(cost<wbuf[i].cost))
  74.             {
  75.                 wbuf[i].cost = cost;
  76.                 wbuf[i].prev = cur;
  77.                 open++;
  78.             }
  79.  
  80.         }
  81.  
  82.         if(0<open)
  83.         {
  84.             /* find lowest cost */
  85.             min=-1;
  86.             for(i=0;i<n;i++)
  87.             {
  88.                 if((-1!=wbuf[i].cost)&&(SHRT_MAX>wbuf[i].cost)&&((-1==min)||(wbuf[i].cost<wbuf[min].cost)))
  89.                 {
  90.                     curCost = wbuf[i].cost;
  91.                     min = i;
  92.                 }
  93.             }
  94.  
  95.             if(-1<min)
  96.             {
  97.                 rbuf[min] = wbuf[min].prev;
  98.                 cur = min;
  99.                 wbuf[cur].cost = -1;
  100.                 r=cur*n;
  101.             }
  102.         }
  103.     }
  104.  
  105.     /* end conditions */
  106.     if(cur==dst) {
  107.         return true;
  108.     } else {
  109.         return false;
  110.     }
  111. }
  112.  
  113. /**
  114.     LoadData
  115.  
  116.     file format:
  117.     - ascii file
  118.     - comma separated file
  119.     - each line contains: <number of entries>,<entry in format <number>[<cost>],...
  120.     - for and unconnected node, fill the first column with 0
  121.     - 
  122. */
  123. short *LoadData(short& n, short& start, const char *szFileName)
  124. {
  125.     /**
  126.         find how many lines, that's our n
  127.     */
  128.     short *data=0;
  129.     FILE *fp = fopen(szFileName,"r");
  130.     if(fp) {
  131.  
  132.         int i,c,res,nEntries,size;
  133.         short line,node,cost;
  134.  
  135.         /* header */
  136.         res = fscanf(fp,"%hd,%hd",&n,&start);
  137.         if((EOF == res)||(2!=res)) {
  138.             goto loadError;
  139.         }
  140.         c = fgetc(fp);
  141.         while((','==c) && (EOF!=c)) {
  142.             c = fgetc(fp);
  143.         }
  144.         if(EOF == c) {
  145.             goto loadError;
  146.         }
  147.  
  148.         /* new data */
  149.         n += start;
  150.         size = n*n;
  151.         data = new short [size];
  152.         if(!data) {
  153.             printf("unable to allocate memory for data table\n");
  154.             return 0;
  155.         }
  156.         for(i=0;i<size;i++) {
  157.             data[i] = -1;
  158.         }
  159.         for(i=0;i<n;i++) {
  160.             data[(i*n)+i] = 0;
  161.         }
  162.  
  163.         /* each line */
  164.         line=start;
  165.         for(line=start;line<n;line++) {
  166.             res = fscanf(fp,"%d",&nEntries);
  167.             if((EOF == res)||(1!=res)) {
  168.                 goto loadError;
  169.             }
  170.             for(i=0;i<nEntries;i++) {
  171.                 c = getc(fp); /* get rid of comma delimiter */
  172.                 if(','!=c) {
  173.                     goto loadError;
  174.                 }
  175.                 res = fscanf(fp,"%hd[%hd]",&node,&cost);
  176.                 if((EOF == res)||(2!=res)) {
  177.                     goto loadError;
  178.                 }
  179.                 data[(line*n)+node] = cost;
  180.             }
  181.  
  182.             /* get rid of trailing commas */
  183.             c = fgetc(fp);
  184.             while((','==c) && (EOF!=c)) {
  185.                 c = fgetc(fp);
  186.             }
  187.             if(EOF == c) {
  188.                 goto loadError;
  189.             }
  190.         }
  191.  
  192.         fclose(fp);
  193.  
  194.     } else {
  195.         printf("couldn't open file %s\n", szFileName);
  196.     }
  197.     return data;
  198.  
  199. loadError:
  200.     fclose(fp);
  201.     printf("reading error in file %s\n", szFileName);
  202.     if(data) {
  203.         delete [] data;
  204.     }
  205.     return 0;
  206. }
  207.  
  208.  
  209. /**
  210.     SaveIntermediateFile
  211. */
  212. void SaveIntermediateFile(short n, short start, short *data,const char *szFileName)
  213. {
  214.     int i,j,r,c,res;
  215.     static char sz[128];
  216.     char *p;
  217.     strcpy(sz,szFileName);
  218.     p = strchr(sz,'.');
  219.     sprintf(p,"i.csv");
  220.     FILE *fp = fopen(sz,"w");
  221.     if(fp) {
  222.         fprintf(fp,"%hd\n",n-start);
  223.         for(i=start;i<n;i++) {
  224.             r = i*n;
  225.             c = n-1;
  226.             for(j=start;j<c;j++) {
  227.                 res = fprintf(fp,"%hd,",data[r+j]);
  228.                 if(0 > res) {
  229.                     goto saveError;
  230.                 }
  231.             }
  232.             res = fprintf(fp,"%hd\n",data[r+c]);
  233.             if(0 > res) {
  234.                 goto saveError;
  235.             }
  236.         }
  237.         fclose(fp);
  238.     } else {
  239.         printf("unable to open intermediate file %s\n", sz);
  240.     }
  241.  
  242.     return;
  243.  
  244. saveError:
  245.     fclose(fp);
  246.     printf("error in writing to intermediate file.\n");
  247.     return;
  248. }
  249.  
  250. /**
  251.     GetFirstNode
  252. */
  253. short GetFirstNode(short *rbuf,short src,short dst) {
  254.     while(rbuf[dst]!=src) {
  255.         dst = rbuf[dst];
  256.     }
  257.     return dst;
  258. }
  259.  
  260. /**
  261.     SaveSolution
  262. */
  263. bool SaveSolution(short n,short start,short *soln,const char *szFileName)
  264. {
  265.     FILE *fp = fopen(szFileName,"w");
  266.     if(fp) {
  267.         int i,j,r;
  268.         fprintf(fp,"%hd,\n",n-start);
  269.         for(i=start;i<n;i++) {
  270.             r = i*n;
  271.             for(j=start;j<n;j++) {
  272.                 fprintf(fp,"%hd,",soln[r+j]);
  273.             }
  274.             fprintf(fp,"\n");
  275.         }
  276.         fclose(fp);
  277.         return true;
  278.     }
  279.     return false;
  280. }
  281.  
  282. /**
  283.     PrintUsage
  284. */
  285. void PrintUsage()
  286. {
  287.     printf("usage: -ih <source filename> <solution filename>\n");
  288.     printf("i : write out intermediate connectivity file.\n");
  289.     printf("h : help\n");
  290.     printf("<source filename> is the data source in csv format.\n");
  291.     printf("<solution filename> is the filename for data output.\n");
  292.     printf("default source filename is in.csv.\n");
  293.     printf("default solution filename is out.csv.\n"); 
  294. }
  295.  
  296. /**
  297.     MAIN
  298. */
  299. int main(int argc, char **argv)
  300. {
  301.     /* read params */
  302.     static char szIn[128] = "in.csv";
  303.     static char szOut[128] = "out.csv";
  304.     bool bIFile = false;
  305.     int param=1;
  306.     if(param < argc) {
  307.         if('-' == *argv[param]) {
  308.             if(0 != strchr(argv[param],'h')) {
  309.                 PrintUsage();
  310.                 return 0;
  311.             }
  312.             if(0 != strchr(argv[param],'i')) {
  313.                 bIFile = true;
  314.             }
  315.             param++;
  316.         }
  317.     }
  318.     if(param < argc) {
  319.         strcpy(szIn,argv[param]);
  320.         param++;
  321.     }
  322.     if(param < argc) {
  323.         strcpy(szOut,argv[param]);
  324.     }
  325.  
  326.  
  327.     /* load data */
  328.     short len,start;
  329.     short *tbl = LoadData(len,start,szIn);
  330.  
  331.     if(0==tbl) {
  332.         return 1;
  333.     }
  334.  
  335.     if(true == bIFile) {
  336.         SaveIntermediateFile(len,start,tbl,szIn);
  337.     }
  338.  
  339.     short *rbuf = new short [len];
  340.     recDijkstra *wbuf = new recDijkstra [len];
  341.     short *soln = new short [len*len];
  342.     int i,j,r;
  343.  
  344.     /* create solution table */
  345.     time_t t0,t1;
  346.     t0 = time(0);
  347.  
  348.     for(i=0;i<len;i++) {
  349.         r = len * i;
  350.         for(j=0;j<len;j++) {
  351.             if(i==j) {
  352.                 soln[r+j] = j;
  353.             } else {
  354.                 if(Dijkstra(len,rbuf,tbl,wbuf,i,j)) {
  355.                     soln[r+j] = GetFirstNode(rbuf,i,j);
  356.                 } else {
  357.                     soln[r+j] = -1;
  358.                 }
  359.             }
  360.         }
  361.     }
  362.  
  363.     t1 = time(0);
  364.  
  365.     printf("profile: soln table creation took %d seconds.\n", difftime(t1,t0));
  366.  
  367.     /* write out the soln */
  368.     if(false == SaveSolution(len,start,soln,szOut)) {
  369.         printf("error saving to file %s.\n",szOut);
  370.     }
  371.  
  372.     delete [] rbuf;
  373.     delete [] wbuf;
  374.     delete [] tbl;
  375.     delete [] soln;
  376.     return 0;
  377. }
  378.