Mercurial > public > maze-solver

annotate algo.c @ 7:a9dd80a69887

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add images
author Dennis <denniscmartin@protonmail.com>
date Sun, 16 Oct 2022 17:17:15 +0200
parents 64d0988b0911
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
1 //
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
2 // Created by Dennis Concepción Martín on 15/10/22.
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
3 //
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
4
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
5 #include "algo.h"
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
6
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
7 int isPath(unsigned x, unsigned y, png_bytep* pRows) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
8 png_byte *pRow = pRows[y];
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
9 png_byte *pPixel = &pRow[x * 4];
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
10
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
11 /*
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
12 * pPixel[0] -> R
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
13 * pPixel[1] -> G
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
14 * pPixel[2] -> B
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
15 */
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
16
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
17 if (pPixel[0] == 255) {
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
18 pPixel[1] = 0;
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
19 pPixel[2] = 0;
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
20
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
21 return 1;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
22 } else {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
23 return 0;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
24 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
25 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
26
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
27
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
28 void wallFollower(png_bytep* pRows, unsigned int width) {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
29 unsigned int x = 0;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
30 unsigned int y = 1;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
31 char direction = 'R';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
32
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
33 isPath(x, y, pRows);
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
34
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
35 while (x < width && y < width) {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
36
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
37 if (x == width - 1 && y == width - 2) {
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
38 break;
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
39 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
40
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
41 switch (direction) { // NOLINT(hicpp-multiway-paths-covered)
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
42 case 'R':
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
43
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
44 // Check if down position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
45 if (isPath(x, y + 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
46 ++y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
47 direction = 'D';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
48 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
49
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
50 // Check if right position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
51 else if (isPath(x + 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
52 ++x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
53 direction = 'R';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
54 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
55
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
56 // Check if up position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
57 else if (isPath(x, y - 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
58 --y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
59 direction = 'U';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
60 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
61
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
62 // Turn 180
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
63 else {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
64 --x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
65 direction = 'L';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
66 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
67
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
68 break;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
69
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
70 case 'L':
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
71
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
72 // Check if up position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
73 if (isPath(x, y - 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
74 --y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
75 direction = 'U';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
76 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
77
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
78 // Check if left position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
79 else if (isPath(x - 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
80 --x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
81 direction = 'L';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
82 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
83
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
84 // Check if down position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
85 else if (isPath(x, y + 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
86 ++y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
87 direction = 'D';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
88 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
89
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
90 // Turn 180
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
91 else {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
92 ++x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
93 direction = 'R';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
94 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
95
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
96 break;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
97
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
98 case 'U':
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
99
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
100 // Check if right position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
101 if (isPath(x + 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
102 ++x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
103 direction = 'R';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
104 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
105
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
106 // Check if up position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
107 else if (isPath(x, y - 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
108 --y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
109 direction = 'U';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
110 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
111
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
112 // Check if left position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
113 else if (isPath(x - 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
114 --x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
115 direction = 'L';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
116 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
117
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
118 // Turn 180
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
119 else {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
120 ++y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
121 direction = 'D';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
122 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
123
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
124 break;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
125
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
126 case 'D':
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
127
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
128 // Check if left position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
129 if (isPath(x - 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
130 --x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
131 direction = 'L';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
132 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
133
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
134 // Check if down position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
135 else if (isPath(x, y + 1, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
136 ++y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
137 direction = 'D';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
138 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
139
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
140 // Check if right position is white
2
64d0988b0911 refactor code
Dennis <denniscmartin@protonmail.com>
parents: 1
diff changeset
141 else if (isPath(x + 1, y, pRows)) {
1
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
142 ++x;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
143 direction = 'R';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
144 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
145
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
146 // Turn 180
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
147 else {
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
148 --y;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
149 direction = 'U';
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
150 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
151
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
152 break;
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
153 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
154 }
edee16cfda92 algo working but inefficient
Dennis <denniscmartin@protonmail.com>
parents:
diff changeset
155 }