Das Programmierspiel von der Gulasch-Programmier-Nacht 11

(Latest mirror + merged latest fork by qr4 on Lua 5.3)

Entropia info page https://entropia.de/GPN11:Programmierspiel (dead links)
Origin Gitlab
https://code.nerd2nerd.org/n2n/WeltraumProgrammierNacht

route.c 11KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455
  1. #include <math.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "route.h"
  5. #include "globals.h"
  6. // Quadrierter Abstand
  7. // Mit Vorzeichen
  8. double quaddist(vector_t* A, vector_t* B) {
  9. vector_t t;
  10. t.v = B->v - A->v;
  11. t.v *= t.v;
  12. return t.x + t.y;
  13. }
  14. // Abstand zwischen zwei Punkten
  15. double dist(vector_t* A, vector_t* B) {
  16. return sqrt(quaddist(A, B));
  17. }
  18. double left_of(const vector_t *A, const vector_t *B, const vector_t *C) {
  19. vector_t t1, t2;
  20. double t3;
  21. t1.v = B->v - A->v;
  22. t2.v = C->v - A->v;
  23. t3 = t2.x;
  24. t2.x = t2.y;
  25. t2.y = t3;
  26. t1.v *= t2.v;
  27. t3 = t1.x - t1.y;
  28. return t3;
  29. }
  30. // Wo auf der Linie zwischen A und B sitzt der Fußpunkt des Lots von C auf AB?
  31. // Werte kleiner Null bedeuten vor A entlang AB
  32. // Werte zwischen 0 und 1 geben an nach welchem Bruchteil von AB der Fußpunkt kommt
  33. // Werte größer 1 bedeuten daß der Fußpunkt auf der Verlängerung von AB hinter B liegt
  34. // Wert den Code mit A=B aufruf ist doof und verdient daß alles platzt
  35. double dividing_ratio(vector_t* A, vector_t* B, vector_t* C) {
  36. return ((C->x - A->x)*(B->x - A->x) + (C->y - A->y)*(B->y - A->y))/quaddist(A, B);
  37. }
  38. // Was ist der Minimal-Abstand von C zum Linien AB?
  39. // Achtung dies liefert den vorzeichenbehafteten Abstand
  40. // Werte kleiner Null bedeuten das C "links" der Verbindungslinie liegt wenn man von A Richtung B schaut
  41. // Werte größer Null dementsprechend recht, exakt null auf der Verbindungslinie
  42. double dist_to_line(vector_t* A, vector_t* B, vector_t* C) {
  43. return ((A->y - B->y)*C->x - (A->x - B->x)* C->y + ((B->y - A->y)* A->x + (A->x - B->x)* A->y))/dist(A,B);
  44. }
  45. // Was ist der Minimal-Abstand von C zum Liniensegment AB?
  46. // Die ist der Abstand zwischen C und dem Fußpunkt des Lots auf AB fall dieser zwischen A und B fällt
  47. // Ansonsten der Abstand zu A btw B
  48. double dist_to_seg(vector_t* A, vector_t* B, vector_t* C) {
  49. double r = dividing_ratio(A, B, C);
  50. if(r <= 0) {
  51. return dist(A, C);
  52. } else if (r >= 1) {
  53. return dist(B, C);
  54. } else {
  55. return fabs(dist_to_line(A, B, C));
  56. }
  57. }
  58. waypoint_t* go_around(vector_t* A, vector_t* B, cluster_t* C, double r) {
  59. vector_t X;
  60. X.v = A->v + (v2d) {r, r} * (B->v - A->v);;
  61. double d = dist(&X, &(C->center));
  62. vector_t W;// = {{C->center.x + C->safety_radius*sqrt(2)*(X.x - C->center.x) / d, C->center.y + C->safety_radius*sqrt(2)*(X.y - C->center.y) / d}};
  63. W.v = C->center.v + (X.v - C->center.v) * (v2d) {M_SQRT2, M_SQRT2} * (v2d) {C->safety_radius, C->safety_radius} / (v2d) {d, d};
  64. waypoint_t* wp = malloc(sizeof(waypoint_t));
  65. wp->next = NULL;
  66. wp->point = W;
  67. return wp;
  68. }
  69. void get_surrounding_points(cluster_t **surrounding_points, cluster_t* clusters, int n, int face_x, int face_y) {
  70. surrounding_points[0] = &(clusters[(face_y - 1) * n + (face_x - 1)]);
  71. surrounding_points[1] = &(clusters[(face_y) * n + (face_x - 1)]);
  72. surrounding_points[2] = &(clusters[(face_y) * n + (face_x)]);
  73. surrounding_points[3] = &(clusters[(face_y - 1) * n + (face_x)]);
  74. }
  75. int get_line_intersection(vector_t *P0, vector_t *P1, vector_t *P2, vector_t *P3, vector_t *result)
  76. {
  77. vector_t s1, s2;
  78. s1.v = P1->v - P0->v;
  79. s2.v = P3->v - P2->v;
  80. double s, t;
  81. t = s1.x * s2.y - s2.x * s1.y;
  82. s = (-s1.y * (P0->x - P2->x) + s1.x * (P0->y - P2->y)) / t;
  83. t = ( s2.x * (P0->y - P2->y) - s2.y * (P0->x - P2->x)) / t;
  84. if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
  85. {
  86. if (result) {
  87. result->v = P0->v + ((v2d) {t, t} * s1.v);
  88. }
  89. return 1;
  90. }
  91. return 0;
  92. }
  93. void find_face(vector_t *p, cluster_t *clusters, int n, int *x, int *y) {
  94. int face_x = p->x / (GLOBALS.WIDTH / (n + 1));
  95. int face_y = p->y / (GLOBALS.HEIGHT / (n + 1));
  96. int edge;
  97. int retry = 1;
  98. int count = 0;
  99. cluster_t *surrounding[4];
  100. while (retry && count < 4) {
  101. retry = 0;
  102. get_surrounding_points(surrounding, clusters, n, face_x, face_y);
  103. for (edge = 0; edge < 4; edge++) {
  104. double r = left_of(&(surrounding[edge]->center), &(surrounding[(edge + 1) % 4]->center), p);
  105. if (r > 0) {
  106. //fprintf(stderr, "edge: %d, r %f, x %d, y %d\n", edge, r, face_x, face_y);
  107. retry = 1;
  108. count++;
  109. switch (edge) {
  110. case 0 :
  111. face_x--;
  112. break;
  113. case 1 :
  114. face_y++;
  115. break;
  116. case 2 :
  117. face_x++;
  118. break;
  119. case 3 :
  120. face_y--;
  121. break;
  122. }
  123. break;
  124. }
  125. }
  126. }
  127. *x = face_x;
  128. *y = face_y;
  129. }
  130. waypoint_t* route_scanline_gridbased(vector_t* start, vector_t* stop,
  131. int face_start_x, int face_start_y, int face_stop_x, int face_stop_y,
  132. cluster_t* clusters, int n) {
  133. static int called = 0;
  134. int i = -1;
  135. int last_edge = -1;
  136. int face_x = face_start_x;
  137. int face_y = face_start_y;
  138. cluster_t *min = NULL;
  139. double r_min = 1;
  140. called++;
  141. //fprintf(stderr, "going from (%d, %d) to (%d, %d)\n", face_start_x, face_start_y, face_stop_x, face_stop_y);
  142. //fprintf(stderr, "going from (%.1f, %.1f) to (%.1f, %.1f)\n", start->x, start->y, stop->x, stop->y);
  143. while (min == NULL && (face_x != face_stop_x || face_y != face_stop_y)) {
  144. //printf("x %d y %d sx %d sy %d called: %d i: %d\n", face_x, face_y, face_stop_x, face_stop_y, called, i);
  145. //getchar();
  146. cluster_t *surrounding[4];
  147. get_surrounding_points(surrounding, clusters, n, face_x, face_y);
  148. for (i = 0; i < 4; i++) {
  149. double r = dividing_ratio(start, stop, &(surrounding[i]->center));
  150. if (r > 0 && r < 1) {
  151. double d = dist_to_line(start, stop, &(surrounding[i]->center));
  152. if (fabs(d) < surrounding[i]->safety_radius) {
  153. min = surrounding[i];
  154. r_min = r;
  155. break;
  156. }
  157. }
  158. }
  159. if (min == NULL) {
  160. for (i = 0; i < 4; i++) {
  161. if (i == last_edge) {
  162. continue;
  163. }
  164. if (get_line_intersection(&(surrounding[i]->center), &(surrounding[(i + 1)%4]->center), start, stop, NULL)) {
  165. break;
  166. }
  167. }
  168. switch (i) {
  169. case 0 :
  170. face_x--;
  171. break;
  172. case 1 :
  173. face_y++;
  174. break;
  175. case 2 :
  176. face_x++;
  177. break;
  178. case 3 :
  179. face_y--;
  180. break;
  181. default:
  182. break;
  183. }
  184. last_edge = (i + 2) % 4;
  185. }
  186. }
  187. if(min != NULL) {
  188. waypoint_t* wp = go_around(start, stop, min, r_min);
  189. find_face(&(wp->point), clusters, n, &face_x, &face_y);
  190. waypoint_t* part1 = NULL;
  191. if (face_start_x != face_x || face_start_y != face_y ) {
  192. part1 = route_scanline_gridbased(start, &(wp->point), face_start_x, face_start_y, face_x, face_y, clusters, n);
  193. }
  194. if(part1 == NULL) {
  195. part1 = wp;
  196. } else {
  197. waypoint_t* t = part1;
  198. while(t->next != NULL) {
  199. t = t->next;
  200. }
  201. t->next = wp;
  202. }
  203. waypoint_t* part2 = NULL;
  204. if (face_stop_x != face_x || face_stop_y != face_y ) {
  205. part2 = route_scanline_gridbased(&(wp->point), stop, face_x, face_y, face_stop_x, face_stop_y, clusters, n);
  206. }
  207. if(part2 != NULL) {
  208. waypoint_t* t = part1;
  209. while(t->next != NULL) {
  210. t = t->next;
  211. }
  212. t->next = part2;
  213. }
  214. return part1;
  215. } else {
  216. return NULL;
  217. }
  218. }
  219. waypoint_t* route(vector_t* start, vector_t* stop, cluster_t* clusters, int n_points) {
  220. int i;
  221. int i_min = -1;
  222. double r_min = 1;
  223. for(i = 0; i < n_points; i++) {
  224. double r = dividing_ratio(start, stop, &(clusters[i].center));
  225. if (r > 0 && r < 1) {
  226. double d = dist_to_line(start, stop, &(clusters[i].center));
  227. if (fabs(d) < clusters[i].safety_radius) {
  228. if(fabs(r-0.5) < fabs(r_min-0.5)) {
  229. i_min = i;
  230. r_min = r;
  231. }
  232. }
  233. }
  234. }
  235. if(i_min >= 0) {
  236. waypoint_t* wp = go_around(start, stop, &(clusters[i_min]), r_min);
  237. waypoint_t* part1 = route(start, &(wp->point), clusters, n_points);
  238. if(part1 == NULL) {
  239. part1 = wp;
  240. } else {
  241. waypoint_t* t = part1;
  242. while(t->next != NULL) {
  243. t = t->next;
  244. }
  245. t->next = wp;
  246. }
  247. waypoint_t* part2 = route(&(wp->point), stop, clusters, n_points);
  248. if(part2 != 0) {
  249. waypoint_t* t = part1;
  250. while(t->next != NULL) {
  251. t = t->next;
  252. }
  253. t->next = part2;
  254. }
  255. return part1;
  256. } else {
  257. return NULL;
  258. }
  259. }
  260. waypoint_t* plotCourse_scanline_gridbased(vector_t* start, vector_t* stop, cluster_t* clusters, int n) {
  261. //int n_points = n*n;
  262. int face_start_x, face_start_y, face_stop_x, face_stop_y;
  263. find_face(start, clusters, n, &face_start_x, &face_start_y);
  264. find_face(stop, clusters, n, &face_stop_x, &face_stop_y);
  265. waypoint_t* wp_start = malloc(sizeof(waypoint_t));
  266. waypoint_t* wp_stop = malloc(sizeof(waypoint_t));
  267. wp_start->point = *start;
  268. wp_stop->point = *stop;
  269. wp_start->next = route_scanline_gridbased(start, stop, face_start_x, face_start_y, face_stop_x, face_stop_y, clusters, n);
  270. wp_stop->next = NULL;
  271. waypoint_t* t = wp_start;
  272. while (t->next != NULL) {
  273. t = t->next;
  274. }
  275. t->next = wp_stop;
  276. return wp_start;
  277. }
  278. waypoint_t* plotCourse(vector_t* start, vector_t* stop, cluster_t* clusters, int n) {
  279. waypoint_t* wp_start = malloc(sizeof(waypoint_t));
  280. waypoint_t* wp_stop = malloc(sizeof(waypoint_t));
  281. wp_start->point = *start;
  282. wp_stop->point = *stop;
  283. wp_start->next = route(start, stop, clusters, n * n);
  284. wp_stop->next = NULL;
  285. waypoint_t* t = wp_start;
  286. while (t->next != NULL) {
  287. t = t->next;
  288. }
  289. t->next = wp_stop;
  290. return wp_start;
  291. }
  292. waypoint_t *smooth(waypoint_t *way, int res) {
  293. waypoint_t *end = way;
  294. waypoint_t *working_start;
  295. waypoint_t *working;
  296. vector_t startp;
  297. vector_t midp;
  298. vector_t endp;
  299. vector_t t1, t2;
  300. vector_t v1, v2;
  301. vector_t s;
  302. int i;
  303. working_start = malloc(sizeof(waypoint_t));
  304. *working_start = *way;
  305. working = working_start;
  306. if (end) {
  307. midp = end->point;
  308. end = end->next;
  309. } else return way;
  310. if (end) {
  311. endp = end->point;
  312. end = end->next;
  313. } else return way;
  314. while (end != NULL) {
  315. startp = midp;
  316. midp = endp;
  317. endp = end->point;
  318. t1.v = (startp.v + midp.v) * (v2d) {0.5, 0.5};
  319. t2 = midp;
  320. v1.v = (midp.v - startp.v) * (v2d) {0.5, 0.5} / (v2d) {res, res};
  321. v2.v = (endp.v - midp.v) * (v2d) {0.5, 0.5} / (v2d) {res, res};
  322. for (i = 0; i < res; i++) {
  323. s.v = t1.v + ((t2.v - t1.v) * (v2d) {i, i}) / (v2d) {res, res};
  324. t1.v += v1.v;
  325. t2.v += v2.v;
  326. working->next = malloc (sizeof(waypoint_t));
  327. working = working->next;
  328. working->point = s;
  329. }
  330. working->next = end;
  331. end = end->next;
  332. }
  333. return working_start;
  334. }
  335. waypoint_t* plotCourse_gridbased(vector_t *start, vector_t *stop, cluster_t *clusters, int n) {
  336. int face_x, face_y, face_s_x, face_s_y;
  337. int edge;
  338. int last_edge = -1;
  339. find_face(start, clusters, n, &face_x, &face_y);
  340. find_face(stop, clusters, n, &face_s_x, &face_s_y);
  341. cluster_t *surrounding[4];
  342. waypoint_t *wp_start = malloc (sizeof(waypoint_t));
  343. wp_start->point = *start;
  344. wp_start->next = NULL;
  345. waypoint_t *working = wp_start;
  346. while (face_x != face_s_x || face_y != face_s_y) {
  347. vector_t c;
  348. get_surrounding_points(surrounding, clusters, n, face_x, face_y);
  349. for (edge = 0; edge < 4; edge++) {
  350. if (edge == last_edge) continue;
  351. c = working->point;
  352. if (get_line_intersection(&(surrounding[edge]->center), &(surrounding[(edge + 1)%4]->center), &c, stop, NULL)) {
  353. c.v = (surrounding[edge]->center.v + surrounding[(edge + 1) % 4]->center.v) / (v2d){2, 2};
  354. break;
  355. }
  356. }
  357. working->next = malloc(sizeof(waypoint_t));
  358. working = working->next;
  359. working->point = c;
  360. working->next = NULL;
  361. switch (edge) {
  362. case 0 :
  363. face_x--;
  364. break;
  365. case 1 :
  366. face_y++;
  367. break;
  368. case 2 :
  369. face_x++;
  370. break;
  371. case 3 :
  372. face_y--;
  373. break;
  374. default:
  375. return wp_start;
  376. }
  377. last_edge = (edge + 2) % 4;
  378. }
  379. working->next = malloc(sizeof(waypoint_t));
  380. working = working->next;
  381. working->point = *stop;
  382. working->next = NULL;
  383. return wp_start;
  384. }