OpenTTD AI which builds a road network between all towns it can reach.

delaunay.nut 7.0KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226
  1. /*--------------------------------------------------------------------
  2. | |
  3. | Delaunay Triangulation |
  4. | Source from https://github.com/ironwallaby/delaunay |
  5. --------------------------------------------------------------------*/
  6. class Delaunay
  7. {
  8. constructor() {
  9. }
  10. }
  11. class DelaunayTriangle
  12. {
  13. a = null;
  14. b = null;
  15. c = null;
  16. x = null;
  17. y = null;
  18. r = null;
  19. constructor( a, b, c ) {
  20. this.a = a;
  21. this.b = b;
  22. this.c = c;
  23. local A = b.x - a.x,
  24. B = b.y - a.y,
  25. C = c.x - a.x,
  26. D = c.y - a.y,
  27. E = A * (a.x + b.x) + B * (a.y + b.y),
  28. F = C * (a.x + c.x) + D * (a.y + c.y),
  29. G = 2 * (A * (c.y - b.y) - B * (c.x - b.x)),
  30. minx, miny, dx, dy;
  31. /* If the points of the triangle are collinear, then just find the
  32. * extremes and use the midpoint as the center of the circumcircle. */
  33. if(abs(G) < 1e-12) {
  34. minx = min(a.x, b.x, c.x);
  35. miny = min(a.y, b.y, c.y);
  36. dx = (max(a.x, b.x, c.x) - minx) * 0.5;
  37. dy = (max(a.y, b.y, c.y) - miny) * 0.5;
  38. this.x = minx + dx;
  39. this.y = miny + dy;
  40. this.r = dx * dx + dy * dy;
  41. }
  42. else {
  43. this.x = (D*E - B*F) / G;
  44. this.y = (A*F - C*E) / G;
  45. dx = this.x - a.x;
  46. dy = this.y - a.y;
  47. this.r = dx * dx + dy * dy;
  48. }
  49. }
  50. }
  51. function byX(first, second) {
  52. local r = second.x - first.x;
  53. if (r > 0) return 1;
  54. if (r < 0) return -1;
  55. return 0;
  56. }
  57. function dedup(edges) {
  58. local j = edges.len();
  59. local a, b, i, m, n;
  60. while(j) {
  61. b = edges[--j];
  62. a = edges[--j];
  63. i = j;
  64. while(i) {
  65. n = edges[--i];
  66. m = edges[--i];
  67. if((a == m && b == n) || (a == n && b == m)) {
  68. edges.remove(j);
  69. edges.remove(j);
  70. edges.remove(i);
  71. edges.remove(i);
  72. j = j-2;
  73. i = 0;
  74. }
  75. }
  76. }
  77. }
  78. function Delaunay::triangulate(vertices)
  79. {
  80. /* Bail if there aren't enough vertices to form any triangles. */
  81. if(vertices.len() < 3)
  82. return [];
  83. /* Ensure the vertex array is in order of descending X coordinate
  84. * (which is needed to ensure a subquadratic runtime), and then find
  85. * the bounding box around the points. */
  86. vertices.sort(byX);
  87. local i = vertices.len() - 1,
  88. xmin = vertices[i].x,
  89. xmax = vertices[0].x,
  90. ymin = vertices[i].y,
  91. ymax = ymin;
  92. while(i--) {
  93. if(vertices[i].y < ymin) ymin = vertices[i].y;
  94. if(vertices[i].y > ymax) ymax = vertices[i].y;
  95. }
  96. /* Find a supertriangle, which is a triangle that surrounds all the
  97. * vertices. This is used like something of a sentinel value to remove
  98. * cases in the main algorithm, and is removed before we return any
  99. * results.
  100. *
  101. * Once found, put it in the "open" list. (The "open" list is for
  102. * triangles who may still need to be considered; the "closed" list is
  103. * for triangles which do not.) */
  104. local dx = xmax - xmin,
  105. dy = ymax - ymin,
  106. dmax = (dx > dy) ? dx : dy,
  107. xmid = (xmax + xmin) * 0.5,
  108. ymid = (ymax + ymin) * 0.5,
  109. open = [
  110. DelaunayTriangle(
  111. {x= xmid - 20 * dmax, y= ymid - dmax, sentinel= true},
  112. {x= xmid , y= ymid + 20 * dmax, sentinel= true},
  113. {x= xmid + 20 * dmax, y= ymid - dmax, sentinel= true}
  114. )
  115. ],
  116. closed = [],
  117. edges = [],
  118. j, a, b;
  119. /* Incrementally add each vertex to the mesh. */
  120. i = vertices.len();
  121. while(i--)
  122. {
  123. /* For each open triangle, check to see if the current point is
  124. * inside it's circumcircle. If it is, remove the triangle and add
  125. * it's edges to an edge list. */
  126. edges.clear();
  127. j = open.len();
  128. while(j--) {
  129. /* If this point is to the right of this triangle's circumcircle,
  130. * then this triangle should never get checked again. Remove it
  131. * from the open list, add it to the closed list, and skip. */
  132. dx = vertices[i].x - open[j].x;
  133. if(dx > 0 && dx * dx > open[j].r) {
  134. closed.append(open[j]);
  135. open.remove(j);
  136. continue;
  137. }
  138. /* If not, skip this triangle. */
  139. dy = vertices[i].y - open[j].y;
  140. if(dx * dx + dy * dy > open[j].r)
  141. continue;
  142. /* Remove the triangle and add it's edges to the edge list. */
  143. edges.append(open[j].a);
  144. edges.append(open[j].b);
  145. edges.append(open[j].b);
  146. edges.append(open[j].c);
  147. edges.append(open[j].c);
  148. edges.append(open[j].a);
  149. open.remove(j);
  150. }
  151. /* Remove any doubled edges. */
  152. dedup(edges);
  153. /* Add a new triangle for each edge. */
  154. j = edges.len();
  155. while(j) {
  156. b = edges[--j]
  157. a = edges[--j]
  158. open.append(DelaunayTriangle(a, b, vertices[i]));
  159. }
  160. }
  161. /* Copy any remaining open triangles to the closed list, and then
  162. * remove any triangles that share a vertex with the supertriangle. */
  163. closed.extend(open);
  164. i = closed.len();
  165. while(i--)
  166. if(closed[i].a.sentinel ||
  167. closed[i].b.sentinel ||
  168. closed[i].c.sentinel)
  169. closed.remove(i);
  170. closed.sort(bySize);
  171. /* Yay, we're done! */
  172. return closed;
  173. }
  174. function bySize(first,second) {
  175. local dist1 = AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(first.a.x,first.a.y), AIMap.GetTileIndex(first.b.x,first.b.y))
  176. + AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(first.b.x,first.b.y), AIMap.GetTileIndex(first.c.x,first.c.y))
  177. + AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(first.c.x,first.c.y), AIMap.GetTileIndex(first.a.x,first.a.y));
  178. local dist2 = AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(second.a.x,second.a.y), AIMap.GetTileIndex(second.b.x,second.b.y))
  179. + AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(second.b.x,second.b.y), AIMap.GetTileIndex(second.c.x,second.c.y))
  180. + AITile.GetDistanceManhattanToTile(AIMap.GetTileIndex(second.c.x,second.c.y), AIMap.GetTileIndex(second.a.x,second.a.y));
  181. if (dist1 < dist2)
  182. return 1;
  183. if (dist1 > dist2)
  184. return -1;
  185. return 0;
  186. }
  187. function byDist(first,second)
  188. {
  189. local dist1 = AITown.GetDistanceManhattanToTile(first[0], AITown.GetLocation(first[1]));
  190. local dist2 = AITown.GetDistanceManhattanToTile(second[0], AITown.GetLocation(second[1]));
  191. if (dist1 > dist2) return 1;
  192. if (dist1 < dist2) return -1;
  193. return 0;
  194. }