2 Copyright (C) 2016 Stephen M. Cameron
3 Author: Stephen M. Cameron
5 This file is part of Spacenerds In Space.
7 Spacenerds in Space is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 Spacenerds in Space is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with Spacenerds in Space; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 #include <ccan/a_star/a_star.h>
28 #include <ccan/a_star/a_star.c>
30 /* Here is the maze we want to solve with A* algorithm */
32 "##########@################x#################\n"
35 "# ########### ################### #\n"
38 "# # # ######## # #\n"
39 "# # ######### # # # #\n"
42 "# # ##### ##################\n"
45 "# ######################### #\n"
47 "############ # # # #\n"
49 "#############################################\n";
51 static const char solution[] =
52 "##########@################x#################\n"
54 "# . # ............ #\n"
55 "# ###########. ###################. #\n"
57 "#### .......#.. # ............ #. #\n"
58 "# .# ... # .######## .. #. #\n"
59 "# .# ######### .# # . #. #\n"
60 "# .# # ..... # ..... #\n"
62 "# .# ##### .##################\n"
63 "# .########## # .. #\n"
64 "# .# # # .............. #\n"
65 "# ..........#########################. #\n"
66 "# # .........#......... #..... #\n"
67 "############ .#. # ...#. #\n"
69 "#############################################\n";
72 /* Return the width of the maze */
73 static int maze_width(char *maze)
77 n = strchr(maze, '\n');
81 /* offsets for 4 points north, east south, west */
82 static int xoff[] = { 0, 1, 0, -1 };
83 static int yoff[] = { 1, 0, -1, 0 };
85 /* Convert x,y coords into a pointer to an element in the maze */
86 static char *maze_node(char *maze, int x, int y)
88 return maze + y * maze_width(maze) + x;
91 /* Return ptr to nth traversable neighbor of a node p, where 0 <= n <= 3, NULL if n out of range */
92 static void *nth_neighbor(void *context, void *p, int n)
96 int i, x, y, offset = c - maze;
98 /* convert ptr to x,y coords */
99 x = offset % maze_width(maze);
100 y = offset / maze_width(maze);
102 for (i = n; i < 4; i++) {
103 int tx = x + xoff[i];
104 int ty = y + yoff[i];
105 if (tx < 0 || ty < 0) /* x,y out of range? */
107 if (ty * maze_width(maze) + tx > strlen(maze)) /* out of range? */
109 c = maze_node(maze, x + xoff[i], y + yoff[i]);
110 if (*c != '#') /* traversable? */
116 static float maze_cost(void *context, void *first, void *second)
118 char *maze = context;
127 sx = sp % maze_width(maze);
128 sy = sp / maze_width(maze);
129 fx = fp % maze_width(maze);
130 fy = fp / maze_width(maze);
132 dx = (float) sx - fx;
133 dy = (float) sy - fy;
134 d = (float) (abs(dx) + abs(dy)); /* manhattan distance */
138 int main(int argc, char *argv[])
140 static int maxnodes, i;
142 struct a_star_path *path;
144 start = strchr(maze, '@');
145 goal = strchr(maze, 'x');
146 maxnodes = strlen(maze);
148 path = a_star((void *) maze, start, goal, maxnodes, maze_cost, maze_cost, nth_neighbor);
150 printf("a_star() failed to return a path.\n");
153 for (i = 0; i < path->node_count; i++) {
154 char *p = path->path[i];
160 printf("%s\n", maze);
164 if (strcmp(solution, maze) == 0)