main.cpp (9266B)
1 #include <chrono> 2 #include <iostream> 3 #include <map> 4 #include <ncurses.h> 5 #include <string> 6 #include <thread> 7 #include <time.h> 8 #include <unistd.h> 9 10 #include "colors.hpp" 11 #include "maze_gen.hpp" 12 #include "pathfinding.hpp" 13 #include "state.hpp" 14 #include "timer.hpp" 15 #include "ui.hpp" 16 #include "vec2.hpp" 17 18 unsigned long mix(unsigned long a, unsigned long b, unsigned long c) 19 { 20 a = a - b; 21 a = a - c; 22 a = a ^ (c >> 13); 23 b = b - c; 24 b = b - a; 25 b = b ^ (a << 8); 26 c = c - a; 27 c = c - b; 28 c = c ^ (b >> 13); 29 a = a - b; 30 a = a - c; 31 a = a ^ (c >> 12); 32 b = b - c; 33 b = b - a; 34 b = b ^ (a << 16); 35 c = c - a; 36 c = c - b; 37 c = c ^ (b >> 5); 38 a = a - b; 39 a = a - c; 40 a = a ^ (c >> 3); 41 b = b - c; 42 b = b - a; 43 b = b ^ (a << 10); 44 c = c - a; 45 c = c - b; 46 c = c ^ (b >> 15); 47 return c; 48 } 49 50 struct node { 51 vec2<int> pos; 52 node* parent = nullptr; 53 std::vector<node*> neighbors; 54 bool isVisited = false; 55 int g = 0; 56 // adds valid neighbors 57 void AddNeighbors( 58 const bool* field, 59 node* grid, 60 const int& width, 61 const int& height) 62 { 63 neighbors.clear(); 64 // up 65 if (pos.y > 2 && field[(pos.y - 1) * width + pos.x]) 66 neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]); 67 // down 68 if (pos.y < height - 2 && field[(pos.y + 1) * width + pos.x]) 69 neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]); 70 // left 71 if (pos.x > 2 && field[(pos.y * width) + pos.x - 1]) 72 neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]); 73 // right 74 if (pos.x < width - 2 && field[(pos.y * width) + pos.x + 1]) 75 neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]); 76 } 77 }; 78 79 void GetGridMap(const bool* field, node* grid, const int& width, const int& height, const vec2<int>& start) 80 { 81 // initializing the grid of nodes used for pointer locations 82 for (int y = 0; y < height; ++y) { 83 for (int x = 0; x < width; ++x) { 84 grid[(y * width) + x].pos.x = x; 85 grid[(y * width) + x].pos.y = y; 86 grid[(y * width) + x].isVisited = false; 87 grid[(y * width) + x].parent = nullptr; 88 grid[(y * width) + x].g = 0; 89 } 90 } 91 // initializes the open set with the start pos 92 std::queue<node*> q; 93 q.push(&grid[start.y * width + start.x]); 94 node* current = q.front(); 95 while (!q.empty()) { 96 current = q.front(); 97 current->isVisited = true; 98 q.pop(); 99 current->AddNeighbors(field, grid, width, height); 100 for (node* n : current->neighbors) { 101 if (!n->isVisited) { 102 n->parent = current; 103 n->g = current->g + 1; 104 q.push(n); 105 } 106 } 107 } 108 } 109 110 int main(int argc, char** argv) 111 { 112 113 // setting a suitable seed for the random number generator 114 srand(mix(clock(), time(NULL), getpid())); 115 116 // ncurses setup 117 initscr(); 118 cbreak(); 119 noecho(); 120 curs_set(0); 121 if (!has_colors()) { 122 endwin(); 123 std::cerr << "Your terminal does not support color!\n"; 124 return -1; 125 } 126 if (!can_change_color()) { 127 endwin(); 128 std::cerr << "Your terminal does not support redefining of colors!\n"; 129 return -1; 130 } 131 start_color(); 132 // COLOR_PAIR(n) 133 // 0 - COLOR_BLACK 134 // 1 - COLOR_RED 135 // 2 - COLOR_GREEN 136 // 3 - COLOR_YELLOW 137 // 4 - COLOR_BLUE 138 // 5 - COLOR_MAGENTA 139 // 6 - COLOR_CYAN 140 // 7 - COLOR_WHITE 141 init_color(COLOR_BLACK, 250, 250, 250); 142 init_color(COLOR_RED, 999, 300, 300); 143 init_color(COLOR_GREEN, 400, 999, 400); 144 init_color(COLOR_YELLOW, 999, 999, 400); 145 init_color(COLOR_BLUE, 15, 60, 870); 146 init_color(COLOR_MAGENTA, 650, 350, 650); 147 init_color(COLOR_CYAN, 200, 800, 800); 148 init_color(COLOR_WHITE, 999, 999, 999); 149 init_pair(black, COLOR_WHITE, COLOR_BLACK); 150 init_pair(red, COLOR_BLACK, COLOR_RED); 151 init_pair(green, COLOR_BLACK, COLOR_GREEN); 152 init_pair(yellow, COLOR_BLACK, COLOR_YELLOW); 153 init_pair(blue, COLOR_BLACK, COLOR_BLUE); 154 init_pair(purple, COLOR_BLACK, COLOR_MAGENTA); // not magenta, fix it | TODO 155 init_pair(cyan, COLOR_BLACK, COLOR_CYAN); 156 init_pair(white, COLOR_BLACK, COLOR_WHITE); 157 158 // declares variables used in the main loop to save memory allocations 159 vec2<int> start; 160 std::vector<vec2<int>> exits; 161 std::vector<vec2<int>> viableExits; 162 std::vector<vec2<int>> path; 163 164 // starts a daemon that handles user input 165 std::thread KeyUpdate(ui::ExecuteKeys); 166 167 while (true) { 168 // setting suitable width and height (odd) 169 int height = LINES; 170 int width = (COLS / 2); 171 if (height % 2 == 0) 172 --height; 173 if (width % 2 == 0) 174 --width; 175 176 // initializing the binary field 177 bool field[width * height]; 178 for (int i = 0; i < width * height; ++i) 179 field[i] = false; 180 181 // setting the background to white 182 s::draw.lock(); 183 attron(COLOR_PAIR(white)); 184 for (int y = 0; y < height; ++y) { 185 for (int x = 0; x < width; ++x) { 186 mvprintw(y, x * 2, " "); 187 } 188 } 189 attroff(COLOR_PAIR(white)); 190 refresh(); 191 s::draw.unlock(); 192 193 // generates the maze and renders it 194 generators[s::generator](field, width, height); 195 196 // gets the length of the longest path in the maze 197 start = vec2<int>((std::rand() % ((width - 1) / 2)) * 2 + 1, 198 (std::rand() % ((height - 1) / 2)) * 2 + 1); 199 node grid[width * height]; 200 // flood fill the grid 201 GetGridMap(field, grid, width, height, start); 202 { 203 // get node that's furthest away from initial point 204 node* current = &grid[0]; 205 for (int y = 1; y < height; y += 2) { 206 for (int x = 1; x < width; x += 2) { 207 if (grid[(y * width) + x].g > current->g) 208 current = &grid[(y * width) + x]; 209 } 210 } 211 start = current->pos; 212 } 213 // flood fill the grid 214 GetGridMap(field, grid, width, height, start); 215 int longestPathLength; 216 { 217 // get node that's furthest away from initial point 218 node* current = &grid[0]; 219 for (int y = 1; y < height; y += 2) { 220 for (int x = 1; x < width; x += 2) { 221 if (grid[(y * width) + x].g > current->g) 222 current = &grid[(y * width) + x]; 223 } 224 } 225 std::vector<vec2<int>> path; 226 node* previous = current; 227 // get (longest) path length between them 228 do { 229 path.push_back(previous->pos); 230 previous = previous->parent; 231 } while (previous != nullptr); 232 longestPathLength = path.size(); 233 } 234 235 // sets random start 236 start = vec2<int>((std::rand() % ((width - 1) / 2)) * 2 + 1, 237 (std::rand() % ((height - 1) / 2)) * 2 + 1); 238 239 // draws random start 240 s::draw.lock(); 241 attron(COLOR_PAIR(green)); 242 mvprintw(start.y, start.x * 2, " "); 243 attroff(COLOR_PAIR(green)); 244 refresh(); 245 s::draw.unlock(); 246 247 // sets random exit(s) 248 exits.clear(); 249 viableExits.clear(); 250 GetGridMap(field, grid, width, height, start); 251 s::draw.lock(); 252 attron(COLOR_PAIR(yellow)); 253 for (int y = 1; y < height; y += 2) { 254 for (int x = 1; x < width; x += 2) { 255 if (grid[(y * width) + x].g > (longestPathLength / 3)) { 256 viableExits.push_back(grid[y * width + x].pos); 257 /* mvprintw(grid[y * width + x].pos::y, grid[y * width + x].pos::x * 2, " "); */ 258 } 259 } 260 } 261 attroff(COLOR_PAIR(yellow)); 262 refresh(); 263 s::draw.unlock(); 264 for (int i = 0; i < 2; ++i) { 265 exits.push_back(viableExits[std::rand() % viableExits.size()]); 266 } 267 268 // draws random exit(s) 269 s::draw.lock(); 270 attron(COLOR_PAIR(red)); 271 for (vec2<int> e : exits) { 272 mvprintw(e.y, e.x * 2, " "); 273 } 274 attroff(COLOR_PAIR(red)); 275 refresh(); 276 s::draw.unlock(); 277 278 // gets the final path and renders the pathfinding 279 path = pathfinders[s::pathfinder](field, width, height, start, exits); 280 281 s::draw.lock(); 282 refresh(); 283 s::draw.unlock(); 284 285 // draws the final path 286 timer cycle; 287 vec2<int>* prev = &path.front(); 288 for (int i = 1; i < path.size(); ++i) { 289 s::draw.lock(); 290 attron(COLOR_PAIR(yellow)); 291 if (i != path.size() - 1) 292 mvprintw(path[i].y, path[i].x * 2, " "); 293 mvprintw((prev->y + path[i].y) / 2, (prev->x + path[i].x), " "); 294 attroff(COLOR_PAIR(yellow)); 295 refresh(); 296 s::draw.unlock(); 297 prev = &path[i]; 298 cycle.WaitInterval(s::time_path); 299 } 300 301 cycle.WaitInterval(s::time_main); 302 } 303 endwin(); 304 return 0; 305 }