1 /* path.c - functions related to finding path between points
2 * on board
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 */
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <assert.h>
12
13 /* returns x coordinate of the node
14 number_of_cells: number of cells in the row */
__find_x_of_the_node(int node,int number_of_x_cells,int number_of_y_cells)15 int __find_x_of_the_node(int node, int number_of_x_cells, int number_of_y_cells) {
16 assert(number_of_x_cells > 0);
17 return node % number_of_x_cells;
18 }
19
20 /* returns y coordinate of the node
21 number_of_cells: number of cells in the row
22 */
__find_y_of_the_node(int node,int number_of_x_cells,int number_of_y_cells)23 int __find_y_of_the_node(int node, int number_of_x_cells, int number_of_y_cells) {
24 assert(number_of_x_cells > 0);
25 return node / number_of_x_cells;
26 }
27
28 /* returns x and y coordinates of the node */
find_x_y_of_the_node(int * x,int * y,int node,int number_of_x_cells,int number_of_y_cells)29 void find_x_y_of_the_node(int *x, int *y, int node, int number_of_x_cells, int number_of_y_cells) {
30 *x = __find_x_of_the_node(node, number_of_x_cells, number_of_y_cells);
31 *y = __find_y_of_the_node(node, number_of_x_cells, number_of_y_cells);
32 }
33
34 /* returns node at x and y coordinates */
find_node_of_x_y(int x,int y,int number_of_x_cells)35 int find_node_of_x_y(int x, int y, int number_of_x_cells) {
36 return y * number_of_x_cells + x;
37 }
38
39 /* find number of the node by its coordinates
40 number_of_cells: number of cells in the row */
find_node_by_coords(int x,int y,int number_of_x_cells,int number_of_y_cells)41 int find_node_by_coords(int x, int y, int number_of_x_cells, int number_of_y_cells) {
42 return y * number_of_x_cells + x;
43 }
44
45 /* mark all neighbouring nodes of the nodes
46 source_nodes: source nodes
47 neighbours: neighbouring nodes
48 mark: number to mark neighbours
49 number_of_cells: number of cells in the row
50 returns number of marked nodes */
mark_neighbours_of_the_nodes(int * nodes,int * source_nodes,int * neighbours,int mark,int number_of_x_cells,int number_of_y_cells)51 int mark_neighbours_of_the_nodes(int *nodes, int *source_nodes, int *neighbours, int mark,
52 int number_of_x_cells, int number_of_y_cells) {
53 int i, j, neighbours_count = 0;
54 int x, y, node;
55 int xses[4] = { 0, 0, 1, -1};
56 int yses[4] = {-1, 1, 0, 0};
57
58 for(i = 1; i <= source_nodes[0]; i++) {
59 find_x_y_of_the_node(&x, &y, source_nodes[i], number_of_x_cells, number_of_y_cells);
60 if(x != -1 && y != -1) {
61 for(j = 0; j < 4; j++) {
62 if(x + xses[j] >= 0 && x + xses[j] < number_of_x_cells &&
63 y + yses[j] >= 0 && y + yses[j] < number_of_y_cells) {
64 node = find_node_by_coords(x + xses[j], y + yses[j], number_of_x_cells, number_of_y_cells);
65 if((node != -1) && nodes[node] == 0) {
66 nodes[node] = mark;
67 neighbours[++neighbours_count] = node;
68 }
69 }
70 }
71 }
72 }
73 neighbours[0] = neighbours_count;
74 return neighbours_count;
75 }
76
77 /* check if nodes are neighbours */
is_neighbours(int node1,int node2,int xn,int yn)78 int is_neighbours(int node1, int node2, int xn, int yn) {
79 int x1, y1, x2, y2;
80
81 find_x_y_of_the_node(&x1, &y1, node1, xn, yn);
82 find_x_y_of_the_node(&x2, &y2, node2, xn, yn);
83
84 if((x1 == x2) && ((y1 == y2 + 1) || (y2 == y1 + 1))) {
85 return 1;
86 } else if((y1 == y2) && ((x1 == x2 + 1) || (x2 == x1 + 1))) {
87 return 1;
88 }
89 return 0;
90 }
91
92 /* find the path between source_node and the target_node
93 result stored in path
94 returns 0 on failure and 1 on success */
find_path(int * nodes,int source_node,int target_node,int * path,int number_of_x_cells,int number_of_y_cells)95 int find_path(int *nodes, int source_node, int target_node, int *path,
96 int number_of_x_cells, int number_of_y_cells) {
97 int waves[number_of_x_cells * number_of_y_cells][number_of_x_cells * number_of_y_cells];
98 int i, j, k = 1, finish = 0;
99
100 waves[0][0] = 1;
101 waves[0][1] = source_node;
102
103 nodes[source_node] = -1;
104 while(!finish) {
105 if(!mark_neighbours_of_the_nodes(nodes, waves[k - 1], waves[k], k,
106 number_of_x_cells, number_of_y_cells)) {
107 /* the destination can never be reached */
108 return 0;
109 }
110 for(i = 1; i <= waves[k][0]; i++) {
111 if(waves[k][i] == target_node) {
112 finish = 1;
113 break;
114 }
115 }
116 k++;
117 }
118
119 path[0] = k;
120 path[1] = waves[k - 1][i];
121 for(j = k - 2; j > 0; j--) {
122 finish = 0;
123 for(i = 1; i <= waves[j][0]; i++) {
124 if(is_neighbours(waves[j][i], path[k - j - 1],
125 number_of_x_cells, number_of_y_cells)) {
126 path[k - j] = waves[j][i];
127 break;
128 }
129 }
130 }
131
132 return 1;
133 }
134