data/qcsrc/server/pathlib/expandnode.qc

   1 vector plib_points2[8];\r
   2 vector plib_points[8];\r
   3 float  plib_fvals[8];\r
   4 \r
   5 float pathlib_expandnode_starf(entity node, vector start, vector goal)\r
   6 {\r
   7     vector where,f,r,t;\r
   8     float i,fc,fc2,c;\r
   9     entity nap;\r
  10 \r
  11     where = node.origin;\r
  12 \r
  13     f = PLIB_FORWARD * pathlib_gridsize;\r
  14     r = PLIB_RIGHT   * pathlib_gridsize;\r
  15 \r
  16     // Forward\r
  17     plib_points[0] = where + f;\r
  18 \r
  19     // Back\r
  20     plib_points[1] = where - f;\r
  21 \r
  22     // Right\r
  23     plib_points[2] = where + r;\r
  24 \r
  25     // Left\r
  26     plib_points[3] = where - r;\r
  27 \r
  28     // Forward-right\r
  29     plib_points[4] = where + f + r;\r
  30 \r
  31     // Forward-left\r
  32     plib_points[5] = where + f - r;\r
  33 \r
  34     // Back-right\r
  35     plib_points[6] = where - f + r;\r
  36 \r
  37     // Back-left\r
  38     plib_points[7] = where - f - r;\r
  39 \r
  40     for(i=0;i < 8; ++i)\r
  41     {\r
  42         t = plib_points[i];\r
  43         fc  = pathlib_heuristic(t,goal) + pathlib_cost(node,t,pathlib_gridsize);\r
  44         plib_fvals[i] = fc;\r
  45 \r
  46     }\r
  47 \r
  48     fc = plib_fvals[0];\r
  49     plib_points2[0] = plib_points[0];\r
  50     vector bp;\r
  51     bp = plib_points[0];\r
  52     for(i = 0; i < 8; ++i)\r
  53     {\r
  54         c = 0;\r
  55         nap = pathlib_nodeatpoint(plib_points[i]);\r
  56         if(nap)\r
  57             if(nap.owner == openlist)\r
  58                 c = 1;\r
  59         else\r
  60             c = 1;\r
  61 \r
  62         if(c)\r
  63         if(plib_fvals[i] < fc)\r
  64         {\r
  65             bp = plib_points[i];\r
  66             fc = plib_fvals[i];\r
  67             plib_points2[fc2] = plib_points[i];\r
  68             ++fc2;\r
  69         }\r
  70 \r
  71         /*\r
  72         nap = pathlib_nodeatpoint(plib_points[i]);\r
  73         if(nap)\r
  74         if not nap.owner == closedlist)\r
  75         {\r
  76         }\r
  77         */\r
  78     }\r
  79 \r
  80     pathlib_makenode(node,start,bp,goal,pathlib_gridsize);\r
  81 \r
  82     for(i = 0; i < 3; ++i)\r
  83     {\r
  84         pathlib_makenode(node,start,plib_points2[i],goal,pathlib_gridsize);\r
  85     }\r
  86 \r
  87     return pathlib_open_cnt;\r
  88 }\r
  89 \r
  90 float pathlib_expandnode_star(entity node, vector start, vector goal)\r
  91 {\r
  92     vector point,where,f,r;\r
  93 \r
  94     where = node.origin;\r
  95 \r
  96     f = PLIB_FORWARD * pathlib_gridsize;\r
  97     r = PLIB_RIGHT   * pathlib_gridsize;\r
  98 \r
  99     // Forward\r
 100     point = where + f;\r
 101     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 102 \r
 103     // Back\r
 104     point = where - f;\r
 105     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 106 \r
 107     // Right\r
 108     point = where + r;\r
 109     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 110 \r
 111     // Left\r
 112     point = where - r;\r
 113     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 114 \r
 115     // Forward-right\r
 116     point = where + f + r;\r
 117     pathlib_makenode(node,start,point,goal,pathlib_movecost_diag);\r
 118 \r
 119     // Forward-left\r
 120     point = where + f - r;\r
 121     pathlib_makenode(node,start,point,goal,pathlib_movecost_diag);\r
 122 \r
 123     // Back-right\r
 124     point = where - f + r;\r
 125     pathlib_makenode(node,start,point,goal,pathlib_movecost_diag);\r
 126 \r
 127     // Back-left\r
 128     point = where - f - r;\r
 129     pathlib_makenode(node,start,point,goal,pathlib_movecost_diag);\r
 130 \r
 131     return pathlib_open_cnt;\r
 132 }\r
 133 \r
 134 float pathlib_expandnode_octagon(entity node, vector start, vector goal)\r
 135 {\r
 136     vector point,where,f,r;\r
 137 \r
 138     where = node.origin;\r
 139 \r
 140     f = PLIB_FORWARD * pathlib_gridsize;\r
 141     r = PLIB_RIGHT   * pathlib_gridsize;\r
 142 \r
 143     // Forward\r
 144     point = where + f;\r
 145     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 146 \r
 147     // Back\r
 148     point = where - f;\r
 149     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 150 \r
 151     // Right\r
 152     point = where + r;\r
 153     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 154 \r
 155     // Left\r
 156     point = where - r;\r
 157     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 158 \r
 159     f = PLIB_FORWARD * pathlib_gridsize * 0.5;\r
 160     r = PLIB_RIGHT   * pathlib_gridsize * 0.5;\r
 161 \r
 162     // Forward-right\r
 163     point = where + f + r;\r
 164     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 165 \r
 166 \r
 167     // Forward-left\r
 168     point = where + f - r;\r
 169     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 170 \r
 171 \r
 172     // Back-right\r
 173     point = where - f + r;\r
 174     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 175 \r
 176     // Back-left\r
 177     point = where - f - r;\r
 178     pathlib_makenode(node,start,point,goal,pathlib_movecost);\r
 179 \r
 180     return pathlib_open_cnt;\r
 181 }\r
 182 \r
 183 float pathlib_expandnode_box(entity node, vector start, vector goal)\r
 184 {\r
 185     vector v;\r
 186 \r
 187     for(v_z = node.origin_z - pathlib_gridsize; v_z <= node.origin_z + pathlib_gridsize; v_z += pathlib_gridsize)\r
 188     for(v_y = node.origin_y - pathlib_gridsize; v_y <= node.origin_y + pathlib_gridsize; v_y += pathlib_gridsize)\r
 189     for(v_x = node.origin_x - pathlib_gridsize; v_x <= node.origin_x + pathlib_gridsize; v_x += pathlib_gridsize)\r
 190     {\r
 191         //if(vlen(v - node.origin))\r
 192             pathlib_makenode(node,start,v,goal,pathlib_movecost);\r
 193     }\r
 194 \r
 195     return pathlib_open_cnt;\r
 196 }\r