API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
129
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.99 KB | None | 0 0
raw download clone embed print report
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define pragma optimize GCC ("03")
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <string.h>
  6. int map_w = 10;
  7. int map_h = 10;
  8. int dragon_position[2];
  9. int princess_position[3][2];
  10. /*char map[20][40] = {
  11. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  12. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  13. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  14. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  15. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  16. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  17. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'p', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  18. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  19. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'd', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  20. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  21. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  22. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  23. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'p', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  24. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  25. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'p', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  26. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  27. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  28. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  29. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  30. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' }
  31. };*/
  32. char map[10][10] = {
  33. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  34. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  35. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  36. { 'c', 'c', 'd', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  37. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'p', 'c', 'c' },
  38. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  39. { 'c', 'c', 'c', 'c', 'c', 'p', 'c', 'c', 'c', 'c' },
  40. { 'c', 'c', 'p', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  41. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  42. { 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c' },
  43. };
  44. typedef struct uzol{
  45. int value;
  46. int g_value;
  47. int f_value;
  48. int h_value;
  49. int x, y;
  50. char type;
  51. bool checked;
  52. struct uzol *parent;
  53. }UZOL;
  54.  
  55. typedef struct graf{
  56. UZOL ***uzol;
  57. int vyska;
  58. int sirka;
  59. }GRAF;
  60.  
  61. typedef struct front{
  62. UZOL **uzly;
  63. int pocet;
  64. }FRONT;
  65.  
  66. FRONT* create_front(FRONT* front){
  67. front = (FRONT*)malloc(sizeof(FRONT));
  68. front->uzly = (UZOL**)malloc(map_h*map_w*sizeof(UZOL*));
  69. front->pocet = 0;
  70. return front;
  71. }
  72.  
  73. void front_write(FRONT* front){
  74. int i;
  75. if (front != NULL && front->pocet >= 1)
  76. for (i = 0; i < front->pocet; i++){
  77. //printf("H_value = %d, index uzla = %d, suradnice: [%d,%d]\n", front->uzly[i]->h_value, front->uzly[i]->value,front->uzly[i]->x,front->uzly[i]->y);
  78. printf("suradnice: [%d,%d], F_value = %d, index uzla = %d\n", front->uzly[i]->x, front->uzly[i]->y, front->uzly[i]->f_value, front->uzly[i]->value);
  79. }
  80. else
  81. printf("Empty front\n");
  82.  
  83. }
  84.  
  85. FRONT* front_sort(FRONT* front){
  86. UZOL* par;
  87. UZOL* pom;
  88. int pocet = front->pocet;
  89. while (pocet != 0){
  90. par = front->uzly[(pocet - 1) / 2];
  91. if (par->f_value > front->uzly[pocet]->f_value){
  92. pom = front->uzly[(pocet - 1) / 2];
  93. front->uzly[(pocet - 1) / 2] = front->uzly[pocet];
  94. front->uzly[pocet] = par;
  95. pocet = (pocet - 1) / 2;
  96. }
  97. else
  98. break;
  99. }
  100. return front;
  101. }
  102.  
  103. FRONT *front_insert(FRONT *front, UZOL *u){
  104. int velkost;
  105.  
  106. if (front == NULL)
  107. front = create_front(front);
  108. u->checked = true;
  109. velkost = front->pocet;
  110. front->uzly[velkost] = u;
  111. front = front_sort(front);
  112. front->pocet++;
  113.  
  114. return front;
  115. }
  116.  
  117. FRONT* front_Heap(FRONT *front, int i){
  118. int left, right;
  119. int min;
  120. UZOL *pom;
  121.  
  122. left = (i * 2);
  123. right = (i * 2) + 1;
  124. do{
  125. if ((front->uzly[i]->f_value > front->uzly[left]->f_value) && (left <= (front->pocet - 1)) ){
  126. min = left;
  127. }
  128. else
  129. min = i;
  130. if ((front->uzly[min]->f_value > front->uzly[right]->f_value) && (right <= (front->pocet - 1)) ){
  131. min = right;
  132. }
  133. pom = front->uzly[i];
  134. front->uzly[i] = front->uzly[min];
  135. front->uzly[min] = pom;
  136. } while (min != i);
  137. return front;
  138. }
  139.  
  140. FRONT *front_remove_min(FRONT *front){
  141. if (front != NULL){
  142. UZOL *min, *posledny;
  143. int velkost;
  144. velkost = front->pocet;
  145. posledny = front->uzly[velkost - 1];
  146. front->pocet--;
  147. min = front->uzly[0];
  148. front->uzly[0] = posledny;
  149.  
  150. //front = front_Heap(front, 0);
  151. front = front_Heap(front, 0);
  152. return front;
  153. }
  154. else{
  155. printf("FRONT je prazdny!\n");
  156. return NULL;
  157. }
  158.  
  159. }
  160.  
  161. GRAF* create_graph(GRAF* graf){
  162. graf = (GRAF*)malloc(sizeof(GRAF));
  163. return graf;
  164. }
  165.  
  166. GRAF* init_graph(GRAF* graf, int vyska, int sirka){
  167. int i, j, found_princess = 0, index = 0;
  168. graf->vyska = vyska;
  169. graf->sirka = sirka;
  170.  
  171. graf->uzol = (UZOL***)malloc(vyska*sizeof(UZOL**));
  172.  
  173. for (i = 0; i < vyska; i++){
  174.  
  175. graf->uzol[i] = (UZOL**)malloc(sirka*sizeof(UZOL*));
  176.  
  177. for (j = 0; j < sirka; j++){
  178. graf->uzol[i][j] = (UZOL*)malloc(sizeof(UZOL));
  179. graf->uzol[i][j]->value = index;
  180. index++;
  181. graf->uzol[i][j]->x = j;
  182. graf->uzol[i][j]->y = i;
  183. graf->uzol[i][j]->type = map[i][j];
  184. //printf("%c\n", graf->uzol[i][j]->type);
  185. graf->uzol[i][j]->parent = NULL;
  186. graf->uzol[i][j]->checked = false;
  187. graf->uzol[i][j]->g_value = 0;
  188. graf->uzol[i][j]->f_value = 0;
  189.  
  190. if (map[i][j] == 'p'){
  191. princess_position[found_princess][0] = j;
  192. princess_position[found_princess][1] = i;
  193. found_princess++;
  194. }
  195. if (map[i][j] == 'd'){
  196. dragon_position[0] = j;
  197. dragon_position[1] = i;
  198. }
  199. }
  200. }
  201. /*for (i = 0; i < found_princess; i++){
  202. int x = princess_position[i][0];
  203. int y = princess_position[i][1];
  204. printf("PRINCEZNA NAJDENA NA SURADNICIACH [%d,%d] %c\n", x, y, graf->uzol[y][x]->type);
  205. }
  206. printf("DRAK NAJDENY NA SURADNICIACH [%d,%d] %c\n", dragon_position[0], dragon_position[1], graf->uzol[dragon_position[1]][dragon_position[0]]->type);*/
  207. return graf;
  208.  
  209. }
  210.  
  211. GRAF* set_h_value(GRAF* graf, char znak){
  212. int i, j, xdif, ydif;
  213. for (i = 0; i < graf->vyska; i++){
  214. for (j = 0; j < graf->sirka; j++){
  215. if (graf->uzol[i][j]->type == znak){
  216. //printf("ZHODA!! GRAF: %c ZNAK %c\n", graf->uzol[i][j]->type, znak);
  217. // printf("INDEXY: %d %d\n", i, j);
  218. graf->uzol[i][j]->h_value = 0;
  219. //printf("H_VALUE: %d\n", graf->uzol[i][j]->h_value);
  220. }
  221. else if (znak == 'd'){
  222. xdif = abs(j - dragon_position[0]);
  223. ydif = abs(i - dragon_position[1]);
  224. graf->uzol[i][j]->h_value = xdif + ydif;
  225. }
  226. else if (znak == 'p'){
  227. xdif = abs(j - princess_position[0][0]);
  228. ydif = abs(i - princess_position[0][1]);
  229. graf->uzol[i][j]->h_value = xdif + ydif;
  230. }
  231. }
  232. }
  233. return graf;
  234. }
  235.  
  236. void graph_write(GRAF* graf){
  237. int i, j;
  238. printf("VYSKA: %d\n", graf->vyska);
  239. printf("SIRKA: %d\n", graf->sirka);
  240. getchar();
  241. for (i = 0; i < graf->vyska; i++){
  242. for (j = 0; j < graf->sirka; j++){
  243. printf("UZOL %d ZNAK: %c INDEXY: [%d,%d] VZDIALENOST: %d \n ", graf->uzol[i][j]->value, graf->uzol[i][j]->type, graf->uzol[i][j]->x, graf->uzol[i][j]->y, graf->uzol[i][j]->h_value);
  244. getchar();
  245. }
  246. }
  247. }
  248.  
  249. UZOL* front_return(FRONT* front){
  250. return front->uzly[0];
  251. }
  252.  
  253. int front_exist(FRONT* front, UZOL* u){
  254. if (front == NULL){
  255. return 0;
  256. }
  257. else{
  258. int j;
  259. for (j = 0; j < front->pocet; j++){
  260. if (front->uzly[j]->value == u->value)
  261. return 1;
  262. }
  263. }
  264. return 0;
  265. }
  266. void graph_checked(FRONT **openlist, FRONT **closedlist, UZOL* sus, UZOL* akt){
  267. if (front_exist(*closedlist, sus) == 0 && front_exist(*openlist, sus) == 0){
  268. printf("%d nie je v OL ani CL\n", sus->value);
  269. sus->g_value = 1; //akt->g_value + 1;
  270. printf("nastavil som g_value: %d\n", sus->g_value);
  271. }
  272. sus->f_value = sus->g_value + sus->h_value;
  273. printf("nastavil som f_value: %d\n", sus->f_value);
  274. sus->parent = akt;
  275. if (sus->checked == false)
  276. *openlist = front_insert(*openlist, sus);
  277. }
  278. void graph_search(GRAF* graf, int x, int y){
  279. FRONT* closed_list = NULL;
  280. FRONT* open_list = NULL;
  281. UZOL *akt, *ls = NULL, *ps = NULL, *hs = NULL, *ds = NULL, *pom = NULL;
  282. int index_draka = graf->uzol[dragon_position[1]][dragon_position[0]]->value;
  283. int index_z = graf->uzol[x][y]->value;
  284. int road[200];
  285. int i = 0;
  286. akt = graf->uzol[x][y];
  287. closed_list = front_insert(closed_list, akt);
  288. while (akt->value != index_draka){
  289. if (akt->x - 1 >= 0){ //lavy sused
  290.  
  291. ls = graf->uzol[akt->y][akt->x - 1];
  292. if (ls->value == index_draka){
  293. ls->parent = akt;
  294. akt = ls;
  295. break;
  296. }
  297.  
  298. graph_checked(&open_list, &closed_list, ls, akt);
  299. }
  300. if (akt->x + 1 <= graf->sirka){ //pravy sused
  301.  
  302. ps = graf->uzol[akt->y][akt->x + 1];
  303. if (ps->value == index_draka){
  304. ps->parent = akt;
  305. akt = ps;
  306. break;
  307. }
  308.  
  309. graph_checked(&open_list, &closed_list, ps, akt);
  310. }
  311. if (akt->y- 1 >= 0){ //horny sused
  312.  
  313. hs = graf->uzol[akt->y - 1][akt->x];
  314. if (hs->value == index_draka){
  315. hs->parent = akt;
  316. akt = hs;
  317. break;
  318. }
  319.  
  320. graph_checked(&open_list, &closed_list, hs, akt);
  321. }
  322. if (akt->y + 1 >= 0){ //dolny sused
  323.  
  324. ds = graf->uzol[akt->y + 1][akt->x];
  325. if (ds->value == index_draka){
  326. ds->parent = akt;
  327. akt = ds;
  328. break;
  329. }
  330.  
  331. graph_checked(&open_list, &closed_list, ds, akt);
  332. }
  333. printf("OPEN LIST\n");
  334. front_write(open_list);
  335. printf("CLOSED LIST\n");
  336. front_write(closed_list);
  337.  
  338. akt = front_return(open_list);
  339. open_list = front_remove_min(open_list);
  340. closed_list = front_insert(closed_list, akt);
  341. printf("OPEN LIST\n");
  342. front_write(open_list);
  343. printf("CLOSED LIST\n");
  344. front_write(closed_list);
  345. printf("---------------------------------------------------\n");
  346. // getchar();
  347. }
  348. printf("Nasiel som %d!\nCesta: \n", index_draka);
  349.  
  350. printf("%d %d\n", akt->x, akt->y);
  351. while (akt->value != index_z){
  352. road[i++] = akt->parent->x;
  353. road[i++] = akt->parent->y;
  354. printf("%d %d\n", akt->parent->x, akt->parent->y);
  355. akt = akt->parent;
  356. }
  357. }
  358. int main(){
  359. GRAF* graf = NULL;
  360. graf = create_graph(graf);
  361. graf = init_graph(graf, map_h, map_w);
  362. graf = set_h_value(graf, 'd');
  363. //graph_write(graf);
  364. graph_search(graf, 0, 0);
  365. getchar();
  366. return 0;
  367. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!