commit fe9a71d7f5564df0e610fa7054469e53b7309f75
Author: Petar Yotsev <petar@yotsev.xyz>
Date: Tue, 16 Jun 2020 10:57:27 +0100
Initial commit
Diffstat:
| A | LICENSE | | | 339 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Makefile | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | README.md | | | 44 | ++++++++++++++++++++++++++++++++++++++++++++ |
| A | colors.hpp | | | 17 | +++++++++++++++++ |
| A | main.cpp | | | 309 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | maze_gen.cpp | | | 829 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | maze_gen.hpp | | | 36 | ++++++++++++++++++++++++++++++++++++ |
| A | pathfinding.cpp | | | 415 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | pathfinding.hpp | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | state.hpp | | | 37 | +++++++++++++++++++++++++++++++++++++ |
| A | timer.cpp | | | 33 | +++++++++++++++++++++++++++++++++ |
| A | timer.hpp | | | 21 | +++++++++++++++++++++ |
| A | ui.cpp | | | 342 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | ui.hpp | | | 18 | ++++++++++++++++++ |
| A | vec2.hpp | | | 143 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
15 files changed, 2675 insertions(+), 0 deletions(-)
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,339 @@
+ GNU GENERAL PUBLIC LICENSE
+ Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+ Preamble
+
+ The licenses for most software are designed to take away your
+freedom to share and change it. By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users. This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it. (Some other Free Software Foundation software is covered by
+the GNU Lesser General Public License instead.) You can apply it to
+your programs, too.
+
+ When we speak of free software, we are referring to freedom, not
+price. Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+
+ To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+ For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have. You must make sure that they, too, receive or can get the
+source code. And you must show them these terms so they know their
+rights.
+
+ We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+ Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software. If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+ Finally, any free program is threatened constantly by software
+patents. We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary. To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+ The precise terms and conditions for copying, distribution and
+modification follow.
+
+ GNU GENERAL PUBLIC LICENSE
+ TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+ 0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License. The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language. (Hereinafter, translation is included without limitation in
+the term "modification".) Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope. The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+
+ 1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+ 2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+ a) You must cause the modified files to carry prominent notices
+ stating that you changed the files and the date of any change.
+
+ b) You must cause any work that you distribute or publish, that in
+ whole or in part contains or is derived from the Program or any
+ part thereof, to be licensed as a whole at no charge to all third
+ parties under the terms of this License.
+
+ c) If the modified program normally reads commands interactively
+ when run, you must cause it, when started running for such
+ interactive use in the most ordinary way, to print or display an
+ announcement including an appropriate copyright notice and a
+ notice that there is no warranty (or else, saying that you provide
+ a warranty) and that users may redistribute the program under
+ these conditions, and telling the user how to view a copy of this
+ License. (Exception: if the Program itself is interactive but
+ does not normally print such an announcement, your work based on
+ the Program is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole. If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works. But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+ 3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+ a) Accompany it with the complete corresponding machine-readable
+ source code, which must be distributed under the terms of Sections
+ 1 and 2 above on a medium customarily used for software interchange; or,
+
+ b) Accompany it with a written offer, valid for at least three
+ years, to give any third party, for a charge no more than your
+ cost of physically performing source distribution, a complete
+ machine-readable copy of the corresponding source code, to be
+ distributed under the terms of Sections 1 and 2 above on a medium
+ customarily used for software interchange; or,
+
+ c) Accompany it with the information you received as to the offer
+ to distribute corresponding source code. (This alternative is
+ allowed only for noncommercial distribution and only if you
+ received the program in object code or executable form with such
+ an offer, in accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it. For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable. However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+ 4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License. Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+
+ 5. You are not required to accept this License, since you have not
+signed it. However, nothing else grants you permission to modify or
+distribute the Program or its derivative works. These actions are
+prohibited by law if you do not accept this License. Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+
+ 6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions. You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+
+ 7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License. If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all. For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices. Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+ 8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded. In such case, this License incorporates
+the limitation as if written in the body of this License.
+
+ 9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time. Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+
+Each version is given a distinguishing version number. If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation. If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+Foundation.
+
+ 10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission. For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this. Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+ NO WARRANTY
+
+ 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+ 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+ END OF TERMS AND CONDITIONS
+
+ How to Apply These Terms to Your New Programs
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+ To do so, attach the following notices to the program. It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+ <one line to give the program's name and a brief idea of what it does.>
+ Copyright (C) <year> <name of author>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along
+ with this program; if not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) year name of author
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+ This is free software, and you are welcome to redistribute it
+ under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License. Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary. Here is a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+ `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+ <signature of Ty Coon>, 1 April 1989
+ Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs. If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library. If this is what you want to do, use the GNU Lesser General
+Public License instead of this License.
diff --git a/Makefile b/Makefile
@@ -0,0 +1,41 @@
+# WITH FLAGS
+CC = g++
+CC_FLAGS = -lpanel -lncurses -std=c++11 -pthread -O2
+EXEC = termaze
+
+
+$(EXEC): main.o ui.o maze_gen.o pathfinding.o
+ $(CC) $(CC_FLAGS) main.o maze_gen.o pathfinding.o ui.o timer.o -o $(EXEC)
+
+
+main.o: main.cpp maze_gen.o pathfinding.o ui.o timer.o state.hpp vec2.hpp colors.hpp CLI11.hpp
+ $(CC) -c $(CC_FLAGS) maze_gen.o pathfinding.o ui.o main.cpp
+
+ui.o: ui.cpp maze_gen.o pathfinding.o state.hpp colors.hpp
+ $(CC) -c $(CC_FLAGS) maze_gen.o pathfinding.o ui.cpp
+
+maze_gen.o: maze_gen.cpp vec2.hpp timer.o state.hpp colors.hpp
+ $(CC) -c $(CC_FLAGS) maze_gen.cpp
+
+pathfinding.o: pathfinding.cpp timer.o vec2.hpp state.hpp colors.hpp
+ $(CC) -c $(CC_FLAGS) pathfinding.cpp
+
+timer.o: timer.cpp state.hpp
+ $(CC) -c timer.cpp
+
+# to do: figure out hot to use precompiled heeaders
+
+# state.hpp: state.hpp
+# $(CC) -c state.hpp
+
+# vec2.hpp: vec2.hpp
+# $(CC) -c vec2.hpp
+
+# colors.hpp: colors.hpp
+# $(CC) -c colors.hpp
+
+# CLI11.hpp: CLI11.hpp
+# $(CC) -c CLI11.hpp
+
+clean:
+ rm -f $(EXEC) *.o *.gch
diff --git a/README.md b/README.md
@@ -0,0 +1,44 @@
+# termaze
+
+---
+
+A program that visualizes maze generation and pathfinding algorithms written in
+C++. It's designed with minimal dependencies and performance in mind. It runs in
+the terminal.
+
+## Features
+
+* Maze generation algorithms
+ * [X] Recursive backtracker
+ * [ ] Recursive divider
+ * [X] Recursive divider - flood fill version
+ * [X] Modified Kruskal's algorithm
+ * [X] Modified Prim's algorithm
+ * [ ] Modified Prim's algorithm - weighted graph
+ * [ ] Growing tree
+ * [X] Wilson's random walk algorithm
+* Pathfinding algorithms
+ * [X] A*
+ * [X] Dijkstra's
+ * [X] Breadth first search
+ * [X] Depth first search
+
+## Usage
+
+ ./termaze
+
+## Dependencies
+
+* ncurses
+
+You probably already have it if you use linux.
+
+## Installation
+
+ git clone https://git.sr.ht/~petar-yotsev/termaze
+ cd termaze
+ make
+
+## License
+
+GPLv2
diff --git a/colors.hpp b/colors.hpp
@@ -0,0 +1,17 @@
+#pragma once
+
+#ifndef COLORS_HPP
+#define COLORS_HPP
+
+enum color {
+ black = 1,
+ red,
+ green,
+ yellow,
+ blue,
+ purple,
+ cyan,
+ white
+};
+
+#endif //COLORS_HPP
diff --git a/main.cpp b/main.cpp
@@ -0,0 +1,309 @@
+#include <chrono>
+#include <iostream>
+#include <map>
+#include <ncurses.h>
+#include <string>
+#include <thread>
+#include <time.h>
+#include <unistd.h>
+
+/* #include "CLI11.hpp" */
+#include "colors.hpp"
+#include "maze_gen.hpp"
+#include "pathfinding.hpp"
+#include "state.hpp"
+#include "timer.hpp"
+#include "ui.hpp"
+#include "vec2.hpp"
+
+unsigned long mix(unsigned long a, unsigned long b, unsigned long c)
+{
+ a = a - b;
+ a = a - c;
+ a = a ^ (c >> 13);
+ b = b - c;
+ b = b - a;
+ b = b ^ (a << 8);
+ c = c - a;
+ c = c - b;
+ c = c ^ (b >> 13);
+ a = a - b;
+ a = a - c;
+ a = a ^ (c >> 12);
+ b = b - c;
+ b = b - a;
+ b = b ^ (a << 16);
+ c = c - a;
+ c = c - b;
+ c = c ^ (b >> 5);
+ a = a - b;
+ a = a - c;
+ a = a ^ (c >> 3);
+ b = b - c;
+ b = b - a;
+ b = b ^ (a << 10);
+ c = c - a;
+ c = c - b;
+ c = c ^ (b >> 15);
+ return c;
+}
+
+struct node {
+ vec2<int> pos;
+ node* parent = nullptr;
+ std::vector<node*> neighbors;
+ bool isVisited = false;
+ int g = 0;
+ // adds valid neighbors
+ void AddNeighbors(
+ const bool* field,
+ node* grid,
+ const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 2 && field[(pos.y - 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && field[(pos.y + 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 2 && field[(pos.y * width) + pos.x - 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && field[(pos.y * width) + pos.x + 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+};
+
+void GetGridMap(const bool* field, node* grid, const int& width, const int& height, const vec2<int>& start)
+{
+ // initializing the grid of nodes used for pointer locations
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ grid[(y * width) + x].isVisited = false;
+ grid[(y * width) + x].parent = nullptr;
+ grid[(y * width) + x].g = 0;
+ }
+ }
+ // initializes the open set with the start pos
+ std::queue<node*> q;
+ q.push(&grid[start.y * width + start.x]);
+ node* current = q.front();
+ while (!q.empty()) {
+ current = q.front();
+ current->isVisited = true;
+ q.pop();
+ current->AddNeighbors(field, grid, width, height);
+ for (node* n : current->neighbors) {
+ if (!n->isVisited) {
+ n->parent = current;
+ n->g = current->g + 1;
+ q.push(n);
+ }
+ }
+ }
+}
+
+// initializes the state class that holds the configuration of the program
+state& s = state::GetInstance();
+
+int main(int argc, char** argv)
+{
+ // handling of command line arguments
+ /* CLI::App app; */
+ /* app.add_option("-p,--pathfinder", s.pathfinder, "Select a pathfinder"); */
+ /* app.add_option("-g,--generator", s.generator, "Select a generator"); */
+ /* CLI11_PARSE(app, argc, argv); */
+
+ // setting a suitable seed for the random number generator
+ srand(mix(clock(), time(NULL), getpid()));
+
+ // ncurses setup
+ initscr();
+ cbreak();
+ noecho();
+ curs_set(0);
+ if (!has_colors()) {
+ endwin();
+ printf("Your terminal does not support color!\n");
+ return -1;
+ }
+ if (!can_change_color()) {
+ endwin();
+ printf("Your terminal does not support redefining of colors!\n");
+ return -1;
+ }
+ start_color();
+ // COLOR_PAIR(n)
+ // 0 - COLOR_BLACK
+ // 1 - COLOR_RED
+ // 2 - COLOR_GREEN
+ // 3 - COLOR_YELLOW
+ // 4 - COLOR_BLUE
+ // 5 - COLOR_MAGENTA
+ // 6 - COLOR_CYAN
+ // 7 - COLOR_WHITE
+ init_color(COLOR_BLACK, 250, 250, 250);
+ init_color(COLOR_RED, 999, 300, 300);
+ init_color(COLOR_GREEN, 400, 999, 400);
+ init_color(COLOR_YELLOW, 999, 999, 400);
+ init_color(COLOR_BLUE, 15, 60, 870);
+ init_color(COLOR_MAGENTA, 650, 350, 650);
+ init_color(COLOR_CYAN, 200, 800, 800);
+ init_color(COLOR_WHITE, 999, 999, 999);
+ init_pair(black, COLOR_WHITE, COLOR_BLACK);
+ init_pair(red, COLOR_BLACK, COLOR_RED);
+ init_pair(green, COLOR_BLACK, COLOR_GREEN);
+ init_pair(yellow, COLOR_BLACK, COLOR_YELLOW);
+ init_pair(blue, COLOR_BLACK, COLOR_BLUE);
+ init_pair(purple, COLOR_BLACK, COLOR_MAGENTA); // not magenta, fix it | to do
+ init_pair(cyan, COLOR_BLACK, COLOR_CYAN);
+ init_pair(white, COLOR_BLACK, COLOR_WHITE);
+
+ // declares variables used in the main loop to save memory allocations
+ vec2<int> start;
+ std::vector<vec2<int>> exits;
+ std::vector<vec2<int>> viableExits;
+ std::vector<vec2<int>> path;
+
+ // starts a daemon that handles user input
+ std::thread KeyUpdate(ui::ExecuteKeys);
+
+ while (true) {
+ // setting suitable width and height (odd)
+ int height = LINES;
+ int width = (COLS / 2);
+ if (height % 2 == 0)
+ --height;
+ if (width % 2 == 0)
+ --width;
+
+ // initializing the binary field
+ bool field[width * height];
+ for (int i = 0; i < width * height; ++i)
+ field[i] = false;
+
+ // setting the background to white
+ s.draw.lock();
+ attron(COLOR_PAIR(white));
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ mvprintw(y, x * 2, " ");
+ }
+ }
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+
+ // generates the maze and renders it
+ generators[s.generator](field, width, height);
+
+ // gets the length of the longest path in the maze
+ start = vec2<int>((std::rand() % ((width - 1) / 2)) * 2 + 1,
+ (std::rand() % ((height - 1) / 2)) * 2 + 1);
+ node grid[width * height];
+ GetGridMap(field, grid, width, height, start);
+ {
+ node* current = &grid[0];
+ for (int y = 1; y < height; y += 2) {
+ for (int x = 1; x < width; x += 2) {
+ if (grid[(y * width) + x].g > current->g)
+ current = &grid[(y * width) + x];
+ }
+ }
+ start = current->pos;
+ }
+ GetGridMap(field, grid, width, height, start);
+ int longestPathLength;
+ {
+ node* current = &grid[0];
+ for (int y = 1; y < height; y += 2) {
+ for (int x = 1; x < width; x += 2) {
+ if (grid[(y * width) + x].g > current->g)
+ current = &grid[(y * width) + x];
+ }
+ }
+ std::vector<vec2<int>> path;
+ node* previous = current;
+ do {
+ path.push_back(previous->pos);
+ previous = previous->parent;
+ } while (previous != nullptr);
+ longestPathLength = path.size();
+ }
+
+ // sets random start
+ start = vec2<int>((std::rand() % ((width - 1) / 2)) * 2 + 1,
+ (std::rand() % ((height - 1) / 2)) * 2 + 1);
+
+ // draws random start
+ s.draw.lock();
+ attron(COLOR_PAIR(green));
+ mvprintw(start.y, start.x * 2, " ");
+ attroff(COLOR_PAIR(green));
+ refresh();
+ s.draw.unlock();
+
+ // sets random exit(s)
+ exits.clear();
+ viableExits.clear();
+ GetGridMap(field, grid, width, height, start);
+ s.draw.lock();
+ attron(COLOR_PAIR(yellow));
+ for (int y = 1; y < height; y += 2) {
+ for (int x = 1; x < width; x += 2) {
+ if (grid[(y * width) + x].g > (longestPathLength / 3)) {
+ viableExits.push_back(grid[y * width + x].pos);
+ /* mvprintw(grid[y * width + x].pos.y, grid[y * width + x].pos.x * 2, " "); */
+ }
+ }
+ }
+ attroff(COLOR_PAIR(yellow));
+ refresh();
+ s.draw.unlock();
+ for (int i = 0; i < 2; ++i) {
+ exits.push_back(viableExits[std::rand() % viableExits.size()]);
+ }
+
+ // draws random exit(s)
+ s.draw.lock();
+ attron(COLOR_PAIR(red));
+ for (vec2<int> e : exits) {
+ mvprintw(e.y, e.x * 2, " ");
+ }
+ attroff(COLOR_PAIR(red));
+ refresh();
+ s.draw.unlock();
+
+ // gets the final path and renders the pathfinding
+ path = pathfinders[s.pathfinder](field, width, height, start, exits);
+
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+
+ // draws the final path
+ timer cycle;
+ vec2<int>* prev = &path.front();
+ for (int i = 1; i < path.size(); ++i) {
+ s.draw.lock();
+ attron(COLOR_PAIR(yellow));
+ if (i != path.size() - 1)
+ mvprintw(path[i].y, path[i].x * 2, " ");
+ mvprintw((prev->y + path[i].y) / 2, (prev->x + path[i].x), " ");
+ attroff(COLOR_PAIR(yellow));
+ refresh();
+ s.draw.unlock();
+ prev = &path[i];
+ cycle.WaitInterval(s.time_path);
+ }
+
+ cycle.WaitInterval(s.time_main);
+ }
+ endwin();
+ return 0;
+}
diff --git a/maze_gen.cpp b/maze_gen.cpp
@@ -0,0 +1,829 @@
+#include <cstdlib>
+#include <exception>
+#include <ncurses.h>
+
+#include <algorithm>
+#include <functional>
+#include <map>
+#include <random>
+#include <set>
+#include <stack>
+#include <thread>
+#include <vector>
+
+#include "colors.hpp"
+#include "maze_gen.hpp"
+#include "state.hpp"
+#include "timer.hpp"
+#include "vec2.hpp"
+
+void maze_gen::Backtracker(bool* field, const int& width, const int& height)
+{
+ enum dir {
+ up,
+ down,
+ left,
+ right
+ };
+
+ // setting the coordinates of each cell according to their placement in the
+ // array because the contents of the cells will map to their locations in
+ // memory making addressing easier
+ vec2<int> grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].y = y;
+ grid[(y * width) + x].x = x;
+ }
+ }
+ std::stack<vec2<int>*> cells;
+ std::vector<dir> dirs;
+ timer cycle;
+
+ auto offset = [&](int x, int y) {
+ return ((cells.top()->y + y) * width) + cells.top()->x + x;
+ };
+ auto drawoffset = [&](int x, int y) {
+ s.draw.lock();
+ mvprintw(cells.top()->y + y, (cells.top()->x + x) * 2, " ");
+ s.draw.unlock();
+ };
+
+ // setting a random root position
+ // because the mazes look more interesting when having irregular roots
+ cells.push(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width)
+ + ((std::rand() % (width / 2)) * 2) + 1]);
+ field[offset(0, 0)] = true;
+ drawoffset(0, 0);
+
+ while (!cells.empty()) {
+ // checking for viable directions
+ dirs.clear();
+ if (cells.top()->y > 1 && !field[offset(0, -2)])
+ dirs.emplace_back(up);
+ if (cells.top()->y < height - 2 && !field[offset(0, 2)])
+ dirs.emplace_back(down);
+ if (cells.top()->x > 1 && !field[offset(-2, 0)])
+ dirs.emplace_back(left);
+ if (cells.top()->x < width - 2 && !field[offset(2, 0)])
+ dirs.emplace_back(right);
+
+ // picks a random viable direction and carves a path two cells in that
+ // direction
+ if (!dirs.empty()) {
+ shuffle(dirs.begin(), dirs.end(),
+ std::default_random_engine(std::rand()));
+ switch (dirs[std::rand() % dirs.size()]) {
+ case up:
+ field[offset(0, -1)] = true;
+ field[offset(0, -2)] = true;
+ drawoffset(0, -1);
+ drawoffset(0, -2);
+ cells.push(&grid[offset(0, -2)]);
+ break;
+ case down:
+ field[offset(0, 1)] = true;
+ field[offset(0, 2)] = true;
+ drawoffset(0, 1);
+ drawoffset(0, 2);
+ cells.push(&grid[offset(0, 2)]);
+ break;
+ case left:
+ field[offset(-1, 0)] = true;
+ field[offset(-2, 0)] = true;
+ drawoffset(-1, 0);
+ drawoffset(-2, 0);
+ cells.push(&grid[offset(-2, 0)]);
+ break;
+ case right:
+ field[offset(1, 0)] = true;
+ field[offset(2, 0)] = true;
+ drawoffset(1, 0);
+ drawoffset(2, 0);
+ cells.push(&grid[offset(2, 0)]);
+ break;
+ }
+ } else {
+ // if there are no viable directions it backtracks
+ cells.pop();
+ }
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ }
+ }
+}
+
+void maze_gen::Kruskal(bool* field, const int& width, const int& height)
+{
+ struct cell {
+ vec2<int> pos;
+ cell* parent = nullptr;
+ };
+ struct edge {
+ cell* primary = nullptr;
+ cell* secondary = nullptr;
+ } current;
+
+ // setting the coordinates of each cell according to their placement in the
+ // array because the contents of the cells will map to their locations in
+ // memory making addressing easier
+ cell grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+
+ // initializing the list of edges
+ std::vector<edge> edges;
+ for (int y = 1; y < height - 1; y += 2) {
+ for (int x = 1; x < width - 1; x += 2) {
+ // initializing horizontal edges
+ if (x < width - 3) {
+ current.primary = &grid[(y * width) + x];
+ current.secondary = &grid[(y * width) + x + 2];
+ edges.push_back(current);
+ }
+ // initializing vertical edges
+ if (y < height - 3) {
+ current.primary = &grid[(y * width) + x];
+ current.secondary = &grid[((y + 2) * width) + x];
+ edges.push_back(current);
+ }
+ // setting the squares where it's guarantied to always be a path
+ // here instead of later when the path is being carved to prevent
+ // multiple unnecessary changes to the path when edges of the same
+ // cell are being evaluated
+ field[(y * width) + x] = true;
+ }
+ }
+
+ shuffle(edges.begin(), edges.end(),
+ std::default_random_engine(std::rand()));
+
+ // initializing the roots for set identification of cells
+ cell* pRoot; // primary cell root
+ cell* sRoot; // secondary cell root
+ cell* prev;
+ vec2<int> edgePos;
+ timer cycle;
+
+ attron(COLOR_PAIR(black));
+ for (edge e : edges) {
+ // finds the root of the primary cell
+ prev = e.primary;
+ while (prev->parent != nullptr) {
+ prev = prev->parent;
+ }
+ // if the cell has no root it sets the root to itself
+ if (prev == nullptr) {
+ pRoot = e.primary;
+ } else {
+ pRoot = prev;
+ }
+
+ // finds the root of the secondary cell
+ prev = e.secondary;
+ while (prev->parent != nullptr) {
+ prev = prev->parent;
+ }
+ // if the cell has no root it sets the root to itself
+ if (prev == nullptr) {
+ sRoot = e.secondary;
+ } else {
+ sRoot = prev;
+ }
+
+ // checks if the primary cell and the secondary cell are part of the
+ // same tree if not it joins the two trees until there is only one tree
+ // left (the maze)
+ if (pRoot != sRoot) {
+ edgePos = (e.primary + (e.secondary - e.primary) / 2)->pos;
+ field[(edgePos.y * width) + edgePos.x] = true;
+
+ s.draw.lock();
+ mvprintw(e.primary->pos.y, e.primary->pos.x * 2, " ");
+ mvprintw(e.secondary->pos.y, e.secondary->pos.x * 2, " ");
+ mvprintw(edgePos.y, edgePos.x * 2, " ");
+
+ // need to add meta data option to state class
+ mvprintw(sRoot->pos.y, sRoot->pos.x * 2, " ");
+ sRoot->parent = pRoot;
+ attron(COLOR_PAIR(red));
+ mvprintw(pRoot->pos.y, pRoot->pos.x * 2, " ");
+ attroff(COLOR_PAIR(red));
+ s.draw.unlock();
+
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ }
+ }
+ }
+ s.draw.lock();
+ mvprintw(sRoot->pos.y, sRoot->pos.x * 2, " ");
+ s.draw.unlock();
+ attroff(COLOR_PAIR(black));
+}
+
+void maze_gen::Prim(bool* field, const int& width, const int& height)
+{
+ struct cell {
+ vec2<int> pos;
+ const cell* parent;
+ std::vector<cell*> neighbors;
+ // adds valid neighbors
+ void AddNeighbors(const bool* field, cell* grid, const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 1 && !field[(pos.y - 2) * width + pos.x])
+ neighbors.emplace_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && !field[(pos.y + 2) * width + pos.x])
+ neighbors.emplace_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 1 && !field[(pos.y * width) + pos.x - 2])
+ neighbors.emplace_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && !field[(pos.y * width) + pos.x + 2])
+ neighbors.emplace_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+ };
+
+ // setting the coordinates of each cell according to their placement in the
+ // array because the contents of the cells will map to their locations in
+ // memory making addressing easier
+ cell grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+
+ // gives the index of a cell in the field
+ auto Index = [&](vec2<int> v) { return v.y * width + v.x; };
+
+ // initializing the open set with a viable random position, aka the root
+ // because the mazes look more interesting when having irregular roots
+ std::vector<cell*> openSet;
+ openSet.push_back(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width)
+ + ((std::rand() % (width / 2)) * 2) + 1]);
+ /* field[(openSet[0]->pos.y * width) + openSet[0]->pos.x] = true; */
+ /* mvprintw(openSet[0]->pos.y, openSet[0]->pos.x * 2, " "); */
+ openSet[0]->parent = openSet[0];
+
+ int index;
+ cell* current;
+ vec2<int> midpoint;
+ timer cycle;
+
+ // carving a path to a random unexplored cell
+ // until there are no more explorable cells
+ while (!openSet.empty()) {
+ index = std::rand() % openSet.size();
+ current = openSet[index];
+ openSet.erase(openSet.begin() + index);
+
+ // if the current position is not part of the maze, make it one
+ if (!field[Index(current->pos)]) {
+ current->AddNeighbors(field, grid, width, height);
+ s.draw.lock();
+ attron(COLOR_PAIR(red));
+ for (cell* n : current->neighbors) {
+ n->parent = current;
+ openSet.push_back(n);
+ mvprintw(n->pos.y, n->pos.x * 2, " ");
+ }
+ attroff(COLOR_PAIR(red));
+ s.draw.unlock();
+
+ midpoint = (current + (current->parent - current) / 2)->pos;
+ field[Index(current->pos)] = true;
+ field[Index(midpoint)] = true;
+ s.draw.lock();
+ mvprintw(current->pos.y, current->pos.x * 2, " ");
+ mvprintw(midpoint.y, midpoint.x * 2, " ");
+ if (s.render_maze_gen) {
+ refresh();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ }
+ s.draw.unlock();
+ }
+ }
+}
+
+void maze_gen::Wilson(bool* field, const int& width, const int& height)
+{
+ enum direction { up,
+ down,
+ left,
+ right };
+
+ // setting the coordinates of each cell according to their placement in the
+ // array because the contents of the cells will map to their locations in
+ // memory making addressing easier
+ vec2<int> grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].y = y;
+ grid[(y * width) + x].x = x;
+ }
+ }
+ std::vector<vec2<int>*> cells;
+ std::vector<direction> dirs;
+ vec2<int>* nextCell;
+ vec2<int>* prevCell;
+ vec2<int>* wall;
+ timer cycle;
+
+ // gives the index of a cell in the grid
+ auto Index = [&](vec2<int>* v) { return v->y * width + v->x; };
+ // gives the index of a cell with a coordinate offset in the grid
+ auto IndexOffset = [&](int x, int y) {
+ return ((cells.back()->y + y) * width) + cells.back()->x + x;
+ };
+ // draws a cell in the grid
+ auto Draw = [&](vec2<int>* v) {
+ s.draw.lock();
+ mvprintw(v->y, v->x * 2, " ");
+ s.draw.unlock();
+ };
+ // draws a cell with a coordinate offset
+ auto DrawOffset = [&](int x, int y) {
+ s.draw.lock();
+ mvprintw(cells.back()->y + y, (cells.back()->x + x) * 2, " ");
+ s.draw.unlock();
+ };
+
+ // looping through all path cells in the grid that are not part of the maze
+ field[width + 1] = true;
+ s.draw.lock();
+ mvprintw(1, 2, " ");
+ s.draw.unlock();
+ for (int y = 1; y < height; y += 2) {
+ for (int x = 1; x < width; x += 2) {
+ if (!field[y * width + x]) {
+ cells.clear();
+ cells.emplace_back(&grid[y * width + x]);
+ Draw(cells.back());
+
+ // going on a loop erased random walk until the maze is reached
+ while (!field[IndexOffset(0, 0)]) {
+ dirs.clear();
+ if (cells.back()->y > 1)
+ dirs.emplace_back(up);
+ if (cells.back()->y < height - 2)
+ dirs.emplace_back(down);
+ if (cells.back()->x > 1)
+ dirs.emplace_back(left);
+ if (cells.back()->x < width - 2)
+ dirs.emplace_back(right);
+ switch (dirs[std::rand() % dirs.size()]) {
+ case up:
+ nextCell = &grid[IndexOffset(0, -2)];
+ break;
+ case down:
+ nextCell = &grid[IndexOffset(0, 2)];
+ break;
+ case left:
+ nextCell = &grid[IndexOffset(-2, 0)];
+ break;
+ case right:
+ nextCell = &grid[IndexOffset(2, 0)];
+ break;
+ }
+
+ // looping through the cells in the random walk
+ // to test if a loop has been created and erase it
+ attron(COLOR_PAIR(white));
+ for (int i = cells.size() - 1; i >= 0; i--) {
+ if (cells[i] == nextCell) {
+ while (cells.back() != nextCell) {
+ Draw(cells.back());
+ prevCell = cells.back();
+ cells.pop_back();
+ wall = cells.back() + (prevCell - cells.back()) / 2;
+ Draw(wall);
+ }
+ goto self_collision;
+ }
+ }
+ attroff(COLOR_PAIR(white));
+
+ // if no loop was detected committing the new cell to the
+ // walk
+ wall = cells.back() + (nextCell - cells.back()) / 2;
+ Draw(nextCell);
+ Draw(wall);
+ cells.emplace_back(nextCell);
+ self_collision:
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_soft_maze_gen);
+ }
+ }
+
+ // committing the random walk to the maze
+ prevCell = cells[0];
+ field[Index(prevCell)] = true;
+ for (int i = 1; i < cells.size(); ++i) {
+ wall = prevCell + (cells[i] - prevCell) / 2;
+ field[Index(wall)] = true;
+ field[Index(cells[i])] = true;
+ prevCell = cells[i];
+ }
+
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ }
+ }
+ }
+ }
+}
+
+void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height)
+{
+ struct cell {
+ vec2<int> pos;
+ bool isVisited = false;
+ char setName;
+ std::vector<cell*> neighbors;
+ // adds valid neighbors
+ void AddNeighbors(
+ cell* grid,
+ const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 2 && !grid[(pos.y - 2) * width + pos.x].isVisited)
+ neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && !grid[(pos.y + 2) * width + pos.x].isVisited)
+ neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 2 && !grid[(pos.y * width) + pos.x - 2].isVisited)
+ neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && !grid[(pos.y * width) + pos.x + 2].isVisited)
+ neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+ std::vector<cell*> GetNeighbors(
+ cell* grid,
+ const int& width,
+ const int& height)
+ {
+ std::vector<cell*> ns;
+ if (pos.x > 2)
+ ns.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ if (pos.x < width - 2)
+ ns.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ if (pos.y > 2)
+ ns.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ if (pos.y < height - 2)
+ ns.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ return ns;
+ }
+ };
+
+ // gets rid of the walls inside the maze
+ s.draw.lock();
+ attron(COLOR_PAIR(black));
+ for (int y = 1; y < height - 1; ++y) {
+ for (int x = 1; x < width - 1; ++x) {
+ field[y * width + x] = true;
+ mvprintw(y, x * 2, " ");
+ }
+ }
+ // sets the corner squares to walls for consistent representation of maze
+ for (int y = 2; y < height - 2; y += 2) {
+ for (int x = 2; x < width - 2; x += 2) {
+ field[y * width + x] = false;
+ }
+ }
+ if (s.render_maze_gen)
+ refresh();
+ attroff(COLOR_PAIR(black));
+ s.draw.unlock();
+ // initializes the grid
+ cell grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+ // populates the globals set
+ std::vector<cell*> l; // l for local set
+ for (int y = 1; y < height; y += 2) {
+ for (int x = 1; x < width; x += 2) {
+ l.push_back(&grid[y * width + x]);
+ }
+ }
+
+ timer cycle;
+
+ std::function<void(std::vector<cell*>&)>
+ Divide = [&](std::vector<cell*>& l) {
+ // base case
+ if (l.size() < 4)
+ return;
+
+ // cleans the set from previous data
+ s.draw.lock();
+ attron(COLOR_PAIR(purple));
+ for (cell* c : l) {
+ c->setName = 'l';
+ c->neighbors.clear();
+ c->isVisited = false;
+ mvprintw(c->pos.y, c->pos.x * 2, " ");
+ }
+ attroff(COLOR_PAIR(purple));
+ s.draw.unlock();
+
+ // gets two random seeds for set a and b respectively
+ cell* seedA = l[std::rand() % l.size()];
+ seedA->setName = 'a';
+ cell* seedB;
+ do {
+ seedB = l[std::rand() % l.size()];
+ } while (seedB == seedA);
+ seedB->setName = 'b';
+ std::vector<cell*> o; // o stands for the open set
+ o.push_back(seedA);
+ o.push_back(seedB);
+ seedA->isVisited = true;
+ seedB->isVisited = true;
+ s.draw.lock();
+ attron(COLOR_PAIR(red));
+ mvprintw(seedA->pos.y, seedA->pos.x * 2, " ");
+ attroff(COLOR_PAIR(red));
+ attron(COLOR_PAIR(blue));
+ mvprintw(seedB->pos.y, seedB->pos.x * 2, " ");
+ attroff(COLOR_PAIR(blue));
+ if (s.render_maze_gen)
+ refresh();
+ s.draw.unlock();
+
+ // expands a and b until they cover the whole of the local set
+ int index;
+ cell* current;
+ while (!o.empty()) {
+ index = std::rand() % o.size();
+ current = o[index];
+ o.erase(o.begin() + index);
+ current->AddNeighbors(grid, width, height);
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ attron(COLOR_PAIR(red));
+ if (current->setName == 'b')
+ attron(COLOR_PAIR(blue));
+ mvprintw(current->pos.y, current->pos.x * 2, " ");
+ attroff(COLOR_PAIR(blue));
+ attroff(COLOR_PAIR(red));
+ refresh();
+ s.draw.unlock();
+ }
+ for (cell* c : current->neighbors) {
+ c->setName = current->setName;
+ o.push_back(c);
+ }
+ if (!current->isVisited && s.render_maze_gen) {
+ cycle.WaitInterval(s.time_soft_maze_gen);
+ }
+ current->isVisited = true;
+ }
+
+ // separates set a and b from the local set for further division
+ // and gets the boundary between set a and b
+ std::vector<cell*> a;
+ std::vector<cell*> b;
+ vec2<int>* midpoint;
+ std::vector<vec2<int>*> w; // wall
+ for (cell* c : l) {
+ if (c->setName == 'a') {
+ a.push_back(c);
+ } else {
+ b.push_back(c);
+ }
+ for (cell* n : c->GetNeighbors(grid, width, height)) {
+ // to do: see if you can avoid executing this twice
+ // i.e. c -> n wall and n -> c wall when n becomes c
+ if (c->setName != n->setName && c->setName != 's' && n->setName != 's') {
+ midpoint = &(c + (n - c) / 2)->pos;
+ w.push_back(midpoint);
+ // build a wall on the boundary
+ field[midpoint->y * width + midpoint->x] = false;
+ }
+ }
+ }
+ // draws the corners of the wall
+ s.draw.lock();
+ attron(COLOR_PAIR(white));
+ for (vec2<int>* mid : w) {
+ std::vector<cell*> wallCorners;
+ if (mid->y % 2 == 0) { // vertical wall | positions start from 0
+ if (mid->x > 1)
+ wallCorners.push_back(&grid[(mid->y * width) + mid->x - 1]);
+ if (mid->x < width - 1)
+ wallCorners.push_back(&grid[(mid->y * width) + mid->x + 1]);
+ } else { // horizontal wall
+ if (mid->y > 1)
+ wallCorners.push_back(&grid[(mid->y - 1) * width + mid->x]);
+ if (mid->y < height - 1)
+ wallCorners.push_back(&grid[(mid->y + 1) * width + mid->x]);
+ }
+ for (cell* c : wallCorners) {
+ int nNeighborWalls = 0;
+ if (!field[(c->pos.y - 1) * width + c->pos.x])
+ ++nNeighborWalls;
+ if (!field[(c->pos.y + 1) * width + c->pos.x])
+ ++nNeighborWalls;
+ if (!field[(c->pos.y * width) + c->pos.x - 1])
+ ++nNeighborWalls;
+ if (!field[(c->pos.y * width) + c->pos.x + 1])
+ ++nNeighborWalls;
+ if (nNeighborWalls > 1) {
+ mvprintw(c->pos.y, c->pos.x * 2, " ");
+ }
+ }
+ }
+ // draws the middle of the wall
+ for (vec2<int>* mid : w) {
+ mvprintw(mid->y, mid->x * 2, " ");
+ }
+ attroff(COLOR_PAIR(white));
+ if (s.render_maze_gen)
+ refresh();
+ s.draw.unlock();
+ if (s.render_maze_gen)
+ cycle.WaitInterval(s.time_soft_maze_gen);
+ // punches a hole in the wall
+ midpoint = w[std::rand() % w.size()];
+ field[midpoint->y * width + midpoint->x] = true;
+
+ s.draw.lock();
+ attron(COLOR_PAIR(black));
+ mvprintw(midpoint->y, midpoint->x * 2, " ");
+ attroff(COLOR_PAIR(black));
+ if (s.render_maze_gen)
+ refresh();
+ s.draw.unlock();
+ if (s.render_maze_gen)
+ cycle.WaitInterval(s.time_hard_maze_gen);
+
+ // cleans up after a division is made
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ attron(COLOR_PAIR(black));
+ for (cell* c : l) {
+ c->setName = 's';
+ mvprintw(c->pos.y, c->pos.x * 2, " ");
+ }
+ attroff(COLOR_PAIR(black));
+ refresh();
+ s.draw.unlock();
+ } else {
+ for (cell* c : l) {
+ c->setName = 's';
+ }
+ }
+
+ Divide(a);
+ Divide(b);
+ };
+
+ Divide(l);
+
+ if (!s.render_maze_gen) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ }
+}
+
+/* void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height) */
+/* { */
+/* for (int y = 1; y < height - 1; ++y) { */
+/* for (int x = 1; x < width - 1; ++x) { */
+/* field[y * width + x] = true; */
+/* mvprintw(y, x * 2, " "); */
+/* } */
+/* } */
+
+/* auto RandOdd = [&](int a, int b) { */
+/* return (a >= b) ? (std::rand() % ((a - b) / 2)) * 2 + 1 */
+/* : (std::rand() % ((b - a) / 2)) * 2; */
+/* }; */
+
+/* auto RandEven = [&](int a, int b) { */
+/* return (a >= b) ? (std::rand() % ((a - b - 1) / 2)) * 2 + 1 */
+/* : (std::rand() % ((b - a - 1) / 2)) * 2 + 1; */
+/* }; */
+
+/* refresh(); */
+/* timer cycle; */
+
+/* std::function<void(vec2<int>&, vec2<int>&)> Divide = */
+/* [&](vec2<int>& top_left, vec2<int>& bottom_right) { */
+/* if (top_left.x >= bottom_right.x || top_left.y >= bottom_right.y) */
+/* return; */
+
+/* attron(COLOR_PAIR(white)); */
+/* int vwallx = top_left.x + RandOdd(top_left.x, bottom_right.x); */
+/* for (int y = top_left.y; y <= bottom_right.y; ++y) { */
+/* field[y * width + vwallx] = false; */
+/* mvprintw(y, vwallx * 2, " "); */
+/* } */
+/* attroff(COLOR_PAIR(white)); */
+/* getch(); */
+
+/* attron(COLOR_PAIR(black)); */
+/* int vwallholey = top_left.y + RandEven(top_left.y, bottom_right.y); */
+/* field[vwallholey * width + top_left.x + vwallx] = true; */
+/* mvprintw(vwallholey, (top_left.x + vwallx) * 2, " "); */
+/* attroff(COLOR_PAIR(black)); */
+/* getch(); */
+
+/* attron(COLOR_PAIR(white)); */
+/* int hwally = top_left.y + RandOdd(top_left.y, bottom_right.y); */
+/* for (int x = top_left.x; x <= bottom_right.x; ++x) { */
+/* field[hwally * width + x] = false; */
+/* mvprintw(hwally, x * 2, " "); */
+/* } */
+/* attroff(COLOR_PAIR(white)); */
+/* getch(); */
+
+/* attron(COLOR_PAIR(black)); */
+/* int vwallholex1 = top_left.x + RandEven(top_left.x, bottom_right.x); */
+/* int vwallholex2 = top_left.x + RandEven(top_left.x, bottom_right.x); */
+/* field[hwally * width + top_left.x + vwallholex1] = true; */
+/* field[hwally * width + top_left.x + vwallholex2] = true; */
+/* mvprintw(hwally, (top_left.x + vwallholex1) * 2, " "); */
+/* mvprintw(hwally, (top_left.x + vwallholex2) * 2, " "); */
+/* attroff(COLOR_PAIR(black)); */
+/* getch(); */
+
+/* refresh(); */
+
+/* vec2<int> tl(top_left); */
+/* vec2<int> br(top_left.x + vwallx, top_left.y + hwally); */
+/* /1* std::thread worker_tl(Divide, tl, br); *1/ */
+/* cycle.WaitInterval(s.time_hard_maze_gen); */
+/* Divide(tl, br); */
+
+/* tl = vec2<int>(top_left.x + vwallx, top_left.y); */
+/* br = vec2<int>(bottom_right.x, top_left.y + hwally); */
+/* /1* std::thread worker_tr(Divide, tl, br); *1/ */
+/* cycle.WaitInterval(s.time_hard_maze_gen); */
+/* Divide(tl, br); */
+
+/* tl = vec2<int>(top_left.x, top_left.y + hwally); */
+/* br = vec2<int>(top_left.x + vwallx, bottom_right.y); */
+/* /1* std::thread worker_bl(Divide, tl, br); *1/ */
+/* cycle.WaitInterval(s.time_hard_maze_gen); */
+/* Divide(tl, br); */
+
+/* tl = vec2<int>(top_left.x + vwallx, top_left.y + hwally); */
+/* br = vec2<int>(bottom_right); */
+/* /1* std::thread worker_br(Divide, tl, br); *1/ */
+/* cycle.WaitInterval(s.time_hard_maze_gen); */
+/* Divide(tl, br); */
+
+/* /1* worker_tl.join(); *1/ */
+/* /1* worker_tr.join(); *1/ */
+/* /1* worker_bl.join(); *1/ */
+/* /1* worker_br.join(); *1/ */
+/* }; */
+/* vec2<int> tl(1, 1); */
+/* vec2<int> br(width - 1, height - 1); */
+/* Divide(tl, br); */
+/* } */
+
+std::map<std::string,
+ void (*)(
+ bool* field,
+ const int& width,
+ const int& height)>
+ generators = {
+ { "Backtracker", maze_gen::Backtracker },
+ { "Kruskal", maze_gen::Kruskal },
+ { "Prim", maze_gen::Prim },
+ { "Wilson", maze_gen::Wilson },
+ { "RecursiveDivider", maze_gen::RecursiveDivider }
+ };
+
diff --git a/maze_gen.hpp b/maze_gen.hpp
@@ -0,0 +1,36 @@
+#pragma once
+
+#ifndef MAZE_GEN_HPP
+#define MAZE_GEN_HPP
+
+#include <ncurses.h>
+
+#include <algorithm>
+#include <functional>
+#include <map>
+#include <random>
+#include <stack>
+#include <thread>
+#include <vector>
+
+#include "colors.hpp"
+#include "state.hpp"
+#include "timer.hpp"
+#include "vec2.hpp"
+
+namespace maze_gen {
+void Backtracker(bool* field, const int& width, const int& height);
+void Kruskal(bool* field, const int& width, const int& height);
+void Prim(bool* field, const int& width, const int& height);
+void Wilson(bool* field, const int& width, const int& height);
+void RecursiveDivider(bool* field, const int& width, const int& height);
+}; // namespace maze_gen
+
+#endif // MAZE_GEN_HPP
+
+extern std::map<std::string,
+ void (*)(
+ bool* field,
+ const int& width,
+ const int& height)>
+ generators;
diff --git a/pathfinding.cpp b/pathfinding.cpp
@@ -0,0 +1,415 @@
+#include <ncurses.h>
+
+#include <algorithm>
+#include <map>
+#include <queue>
+#include <stack>
+#include <string>
+#include <vector>
+
+#include "colors.hpp"
+#include "pathfinding.hpp"
+#include "state.hpp"
+#include "timer.hpp"
+#include "vec2.hpp"
+
+std::vector<vec2<int>> pathfinding::Breadth(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits)
+{
+ struct node {
+ vec2<int> pos;
+ node* parent = nullptr;
+ std::vector<node*> neighbors;
+ bool isVisited = false;
+ // adds valid neighbors
+ void AddNeighbors(
+ const bool* field,
+ node* grid,
+ const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 2 && field[(pos.y - 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && field[(pos.y + 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 2 && field[(pos.y * width) + pos.x - 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && field[(pos.y * width) + pos.x + 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+ };
+
+ // initializing the grid of nodes used for pointer locations
+ node grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+
+ // initializes the open set with the start pos
+ std::queue<node*> q;
+ q.push(&grid[start.y * width + start.x]);
+
+ node* current = q.front();
+ node* parent = current;
+ node* middle = nullptr;
+ timer cycle;
+
+ while (!q.empty()) {
+ attron(COLOR_PAIR(green));
+ s.draw.lock();
+ mvprintw(start.y, start.x * 2, " ");
+ s.draw.unlock();
+ attron(COLOR_PAIR(green));
+
+ current = q.front();
+ current->isVisited = true;
+ if (current->parent != nullptr)
+ parent = current->parent;
+ for (vec2<int> e : exits) {
+ if (current->pos == e) {
+ std::vector<vec2<int>> path;
+ node* previous = current;
+ do {
+ path.push_back(previous->pos);
+ previous = previous->parent;
+ } while (previous != nullptr);
+ return path;
+ }
+ }
+ s.draw.lock();
+ attron(COLOR_PAIR(blue));
+ mvprintw(current->pos.y, current->pos.x * 2, " ");
+ mvprintw(((current->pos + parent->pos) / 2).y,
+ ((current->pos + parent->pos) / 2).x * 2, " ");
+ attroff(COLOR_PAIR(blue));
+ s.draw.unlock();
+ q.pop();
+
+ current->AddNeighbors(field, grid, width, height);
+
+ s.draw.lock();
+ attron(COLOR_PAIR(cyan));
+ for (node* n : current->neighbors) {
+ if (!n->isVisited) {
+ n->parent = current;
+ q.push(n);
+ middle = (n + (current - n) / 2);
+ mvprintw(middle->pos.y, middle->pos.x * 2, " ");
+ }
+ }
+ attroff(COLOR_PAIR(cyan));
+ s.draw.unlock();
+ if (s.render_pathfinding) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_pathfinding);
+ }
+ }
+ return std::vector<vec2<int>>();
+}
+
+std::vector<vec2<int>> pathfinding::Depth(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits)
+{
+ struct node {
+ vec2<int> pos;
+ node* parent = nullptr;
+ std::vector<node*> neighbors;
+ bool isVisited = false;
+ // adds valid neighbors
+ void AddNeighbors(
+ const bool* field,
+ node* grid,
+ const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 2 && field[(pos.y - 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && field[(pos.y + 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 2 && field[(pos.y * width) + pos.x - 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && field[(pos.y * width) + pos.x + 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+ };
+
+ // initializing the grid of nodes used for pointer locations
+ node grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+
+ // initializes the open set with the start pos
+ std::stack<node*> q;
+ q.push(&grid[start.y * width + start.x]);
+
+ node* current = q.top();
+ node* parent;
+ node* wall;
+ node* middle = nullptr;
+ timer cycle;
+
+ while (!q.empty()) {
+ attron(COLOR_PAIR(green));
+ s.draw.lock();
+ mvprintw(start.y, start.x * 2, " ");
+ s.draw.unlock();
+ attron(COLOR_PAIR(green));
+ current = q.top();
+ current->isVisited = true;
+ if (current->parent != nullptr) {
+ parent = current->parent;
+ } else {
+ parent = current;
+ }
+ // finding the node pointer containing the
+ // wall between the current and previous nodes
+ // so the path doesn't have gaps when drawn
+ wall = parent + (current - parent) / 2;
+ for (vec2<int> e : exits) {
+ if (current->pos == e) {
+ std::vector<vec2<int>> path;
+ node* previous = current;
+ do {
+ path.push_back(previous->pos);
+ previous = previous->parent;
+ } while (previous != nullptr);
+ return path;
+ }
+ }
+ attron(COLOR_PAIR(blue));
+ s.draw.lock();
+ mvprintw(current->pos.y, current->pos.x * 2, " ");
+ mvprintw(wall->pos.y, wall->pos.x * 2, " ");
+ s.draw.unlock();
+ attroff(COLOR_PAIR(blue));
+ q.pop();
+ current->AddNeighbors(field, grid, width, height);
+
+ attron(COLOR_PAIR(cyan));
+ s.draw.lock();
+ for (node* n : current->neighbors) {
+ if (!n->isVisited) {
+ n->parent = current;
+ q.push(n);
+ middle = (n + (current - n) / 2);
+ mvprintw(middle->pos.y, middle->pos.x * 2, " ");
+ }
+ }
+ s.draw.unlock();
+ attroff(COLOR_PAIR(cyan));
+ if (s.render_pathfinding) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_pathfinding);
+ }
+ }
+ return std::vector<vec2<int>>();
+}
+
+std::vector<vec2<int>> pathfinding::AStar(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits)
+{
+ struct node {
+ vec2<int> pos;
+ node* parent = nullptr;
+ int g;
+ float h, f;
+ std::vector<node*> neighbors;
+ // adds valid neighbors
+ void AddNeighbors(
+ const bool* field,
+ node* grid,
+ const int& width,
+ const int& height)
+ {
+ neighbors.clear();
+ // up
+ if (pos.y > 2 && field[(pos.y - 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]);
+ // down
+ if (pos.y < height - 2 && field[(pos.y + 1) * width + pos.x])
+ neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]);
+ // left
+ if (pos.x > 2 && field[(pos.y * width) + pos.x - 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]);
+ // right
+ if (pos.x < width - 2 && field[(pos.y * width) + pos.x + 1])
+ neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]);
+ }
+ };
+
+ // initializing the grid of nodes used for pointer locations
+ node grid[width * height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].pos.x = x;
+ grid[(y * width) + x].pos.y = y;
+ }
+ }
+
+ // adding the neighbors of all the cells
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[(y * width) + x].AddNeighbors(field, grid, width, height);
+ }
+ }
+
+ int index;
+ node* current = nullptr;
+ std::vector<vec2<int>> path;
+ std::vector<node*> neighbors;
+ int g_temp;
+ node* neighbor = nullptr;
+ node* middle = nullptr;
+ vec2<int> finish;
+ timer cycle;
+
+ std::vector<node*> openSet;
+ std::vector<node*> closedSet;
+ openSet.push_back(&grid[start.y * width + start.x]);
+ current = openSet.front();
+ current->parent = nullptr;
+ current->g = 0.0f;
+ finish = exits[0];
+ for (int i = 1; i < exits.size(); ++i) {
+ if ((exits[i] - current->pos).GetLength()
+ < (finish - current->pos).GetLength()) {
+ finish = exits[i];
+ }
+ }
+ current->h = (current->pos - finish).GetLength();
+ current->f = current->g + current->h;
+
+ while (!openSet.empty()) {
+ index = 0;
+ for (int i = 1; i < openSet.size(); ++i) {
+ if (openSet[i]->f < openSet[index]->f)
+ index = i;
+ }
+ current = openSet[index];
+
+ for (vec2<int> e : exits) {
+ if (current->pos == e) {
+ node* previous = current;
+ do {
+ path.push_back(previous->pos);
+ previous = previous->parent;
+ } while (previous != nullptr);
+ return path;
+ }
+ }
+
+ closedSet.push_back(current);
+ openSet.erase(openSet.begin() + index);
+ neighbors = current->neighbors;
+ if (current->parent != nullptr) {
+ middle = current + (current->parent - current) / 2;
+ } else {
+ middle = current;
+ }
+ s.draw.lock();
+ attron(COLOR_PAIR(blue));
+ mvprintw(current->pos.y, current->pos.x * 2, " ");
+ mvprintw(middle->pos.y, middle->pos.x * 2, " ");
+ attroff(COLOR_PAIR(blue));
+ s.draw.unlock();
+ if (current->pos == start) {
+ s.draw.lock();
+ attron(COLOR_PAIR(green));
+ mvprintw(start.y, start.x * 2, " ");
+ attroff(COLOR_PAIR(green));
+ s.draw.unlock();
+ }
+
+ for (int i = 0; i < neighbors.size(); ++i) {
+ neighbor = neighbors[i];
+ // checks if neighbor is in the closed set
+ // if not, it processes it
+ if ((std::find(closedSet.begin(), closedSet.end(), neighbor)
+ == closedSet.end())) {
+ g_temp = current->g + 1;
+
+ // checks if the neighbor is already in the open set
+ // if not, it adds it
+ if ((std::find(openSet.begin(), openSet.end(), neighbor)
+ == openSet.end())) {
+ openSet.push_back(neighbor);
+ s.draw.lock();
+ middle = (neighbor + (current - neighbor) / 2);
+ attron(COLOR_PAIR(cyan));
+ mvprintw(middle->pos.y, middle->pos.x * 2, " ");
+ attroff(COLOR_PAIR(cyan));
+ s.draw.unlock();
+ } else if (g_temp >= neighbor->g) {
+ continue;
+ }
+
+ finish = exits[0];
+ for (int i = 1; i < exits.size(); ++i) {
+ if ((exits[i] - neighbor->pos).GetLength()
+ < (finish - neighbor->pos).GetLength()) {
+ finish = exits[i];
+ }
+ }
+
+ neighbor->g = g_temp;
+ neighbor->h = (neighbor->pos - finish).GetLength();
+ neighbor->f = neighbor->h + neighbor->g;
+ neighbor->parent = current;
+ }
+ if (s.render_pathfinding) {
+ s.draw.lock();
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_pathfinding);
+ }
+ }
+ }
+ return path;
+}
+
+std::map<std::string,
+ std::vector<vec2<int>> (*)(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits)>
+ pathfinders = {
+ { "Breadth", pathfinding::Breadth },
+ { "Dijkstra", pathfinding::Breadth },
+ { "Depth", pathfinding::Depth },
+ { "A*", pathfinding::AStar }
+ };
diff --git a/pathfinding.hpp b/pathfinding.hpp
@@ -0,0 +1,51 @@
+#pragma once
+
+#ifndef PATHFINDING_HPP
+#define PATHFINDING_HPP
+
+#include <ncurses.h>
+
+#include <algorithm>
+#include <map>
+#include <queue>
+#include <stack>
+#include <vector>
+
+#include "colors.hpp"
+#include "state.hpp"
+#include "timer.hpp"
+#include "vec2.hpp"
+
+namespace pathfinding {
+std::vector<vec2<int>> Breadth(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits);
+
+std::vector<vec2<int>> Depth(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits);
+
+std::vector<vec2<int>> AStar(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits);
+}; // pathfinding
+
+#endif // PATHFINDING_HPP
+
+extern std::map<std::string,
+ std::vector<vec2<int>> (*)(
+ const bool* field,
+ const int& width,
+ const int& height,
+ const vec2<int>& start,
+ const std::vector<vec2<int>>& exits)>
+ pathfinders;
diff --git a/state.hpp b/state.hpp
@@ -0,0 +1,37 @@
+#pragma once
+
+#ifndef STATE_HPP
+#define STATE_HPP
+
+#include <mutex>
+#include <string>
+
+class state {
+public:
+ static state& GetInstance()
+ {
+ static state instance;
+ return instance;
+ }
+ state(state const&) = delete;
+ void operator=(state const&) = delete;
+ std::mutex draw;
+ // add meta data variable
+ state() {};
+ int time_hard_maze_gen = 10; // time between algorithm cycles
+ int time_soft_maze_gen = 1; // time between cycles within algorithms cycles
+ int time_hard_pathfinding = 15; // time between algorithm cycles
+ int time_soft_pathfinding = 2; // time between cycles within algorithms cycles
+ int time_main = 1500; // time between main loops
+ int time_path = 15; // time between drawing steps in final path
+ bool render_maze_gen = true; // should you render maze generating proccess?
+ bool render_pathfinding = true; // should you render pathfinding proccess?
+ bool ui_is_open = false; // is ui open or waiting to be rendered?
+ bool ui_render_is_safe = false; // is it safe to render ui?
+ std::string pathfinder = "A*";
+ std::string generator = "RecursiveDivider";
+};
+
+#endif // STATE_HPP
+
+extern state& s;
diff --git a/timer.cpp b/timer.cpp
@@ -0,0 +1,33 @@
+#include "timer.hpp"
+#include "state.hpp"
+#include <chrono>
+#include <thread>
+
+timer::timer()
+{
+ initTime = std::chrono::steady_clock::now();
+}
+
+timer::~timer()
+{
+}
+
+void timer::WaitInterval(const float& time_ms)
+{
+ using namespace std::chrono;
+ if (s.ui_is_open) {
+ s.ui_render_is_safe = true;
+ while (s.ui_is_open) {
+ std::this_thread::sleep_for(milliseconds(3));
+ }
+ s.ui_render_is_safe = false;
+ initTime = std::chrono::steady_clock::now();
+ elapsedTime = milliseconds(0);
+ } else {
+ elapsedTime += duration<float>(time_ms / 1000);
+ steady_clock::time_point now = steady_clock::now();
+ if (initTime + elapsedTime - now > milliseconds(0)) {
+ std::this_thread::sleep_for(initTime + elapsedTime - now);
+ }
+ }
+}
diff --git a/timer.hpp b/timer.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+#ifndef TIMER_HPP
+#define TIMER_HPP
+
+#include "state.hpp"
+#include <chrono>
+#include <thread>
+
+class timer {
+public:
+ timer();
+ ~timer();
+ void WaitInterval(const float& time);
+
+private:
+ std::chrono::steady_clock::time_point initTime;
+ std::chrono::duration<float> elapsedTime = std::chrono::milliseconds(0);
+};
+
+#endif // TIMER_HPP
diff --git a/ui.cpp b/ui.cpp
@@ -0,0 +1,342 @@
+#include <chrono>
+#include <map>
+#include <mutex>
+#include <ncurses.h>
+#include <panel.h>
+#include <string>
+#include <thread>
+#include <vector>
+
+#include "colors.hpp"
+#include "maze_gen.hpp"
+#include "pathfinding.hpp"
+#include "state.hpp"
+#include "ui.hpp"
+
+static std::string Option(
+ const std::vector<std::string>& options,
+ const std::string& current)
+{
+ // getting the right size for the sub window
+ int win_height = options.size() + 2;
+ int win_width = options[0].size();
+ for (std::string opt : options)
+ if (opt.size() > win_width)
+ win_width = opt.size();
+ win_width += 2 + 10;
+ int y_max, x_mas;
+ // creating and rendering the sub window
+ s.ui_is_open = true;
+ while (!s.ui_render_is_safe) {
+ std::this_thread::sleep_for(std::chrono::milliseconds(1));
+ }
+ s.draw.lock();
+ attron(COLOR_PAIR(black));
+ getmaxyx(stdscr, y_max, x_mas);
+ WINDOW* win = newwin(
+ win_height,
+ win_width,
+ (y_max / 2) - (win_height / 2),
+ (x_mas / 2) - (win_width / 2));
+ PANEL* pan = new_panel(win);
+ box(win, 0, 0);
+ int highlight = 0;
+ // putting the highlight on the currently selected option
+ for (int i = 0; i < options.size(); ++i)
+ if (options[i] == current)
+ highlight = i;
+ int key;
+ while (true) {
+ for (int y = 0; y < options.size(); ++y) {
+ if (y == highlight)
+ wattron(win, A_REVERSE);
+ // prints the option
+ mvwprintw(win, y + 1, 2, options[y].c_str());
+ // prints white space up to the selection box for proper
+ // highlighting
+ for (int x = options[y].size() + 2; x < win_width - 2; ++x)
+ mvwprintw(win, y + 1, x, " ");
+ // prints the selection box
+ mvwprintw(win, y + 1, win_width - 5, "[ ]");
+ if (options[y] == current)
+ mvwprintw(win, y + 1, win_width - 4, "*");
+ wattroff(win, A_REVERSE);
+ }
+ getkey:
+ key = wgetch(win);
+ switch (key) {
+ case 'j':
+ case KEY_DOWN:
+ ++highlight;
+ if (highlight >= options.size())
+ highlight = 0;
+ break;
+ case 'k':
+ case KEY_UP:
+ --highlight;
+ if (highlight < 0)
+ highlight = options.size() - 1;
+ break;
+ case 10: // enter
+ case 32: // space
+ case 'l':
+ hide_panel(pan);
+ del_panel(pan);
+ update_panels();
+ attroff(COLOR_PAIR(black));
+ s.draw.unlock();
+ s.ui_is_open = false;
+ return options[highlight];
+ break;
+ case 27: // escape
+ case 'h':
+ case 'q':
+ hide_panel(pan);
+ del_panel(pan);
+ update_panels();
+ attroff(COLOR_PAIR(black));
+ s.draw.unlock();
+ s.ui_is_open = false;
+ return current;
+ break;
+ default:
+ goto getkey;
+ break;
+ }
+ }
+}
+
+static std::string Option(const std::vector<std::string>& options)
+{
+ // getting the right size for the sub window
+ int win_height = options.size() + 2;
+ int win_width = options[0].size();
+ for (std::string opt : options)
+ if (opt.size() > win_width)
+ win_width = opt.size();
+ win_width += 2 + 10;
+ int y_max, x_mas;
+ // creating and rendering the sub window
+ s.ui_is_open = true;
+ while (!s.ui_render_is_safe) {
+ std::this_thread::sleep_for(std::chrono::milliseconds(1));
+ }
+ s.draw.lock();
+ attron(COLOR_PAIR(black));
+ getmaxyx(stdscr, y_max, x_mas);
+ WINDOW* win = newwin(
+ win_height,
+ win_width,
+ (y_max / 2) - (win_height / 2),
+ (x_mas / 2) - (win_width / 2));
+ PANEL* pan = new_panel(win);
+ box(win, 0, 0);
+ int highlight = 0;
+ int key;
+ while (true) {
+ for (int y = 0; y < options.size(); ++y) {
+ if (y == highlight)
+ wattron(win, A_REVERSE);
+ // prints the option
+ mvwprintw(win, y + 1, 2, options[y].c_str());
+ // prints white space up to the selection box for proper
+ // highlighting
+ for (int x = options[y].size() + 2; x < win_width - 2; ++x)
+ mvwprintw(win, y + 1, x, " ");
+ wattroff(win, A_REVERSE);
+ }
+ getkey:
+ key = wgetch(win);
+ switch (key) {
+ case 'j':
+ case KEY_DOWN:
+ ++highlight;
+ if (highlight >= options.size())
+ highlight = 0;
+ break;
+ case 'k':
+ case KEY_UP:
+ --highlight;
+ if (highlight < 0)
+ highlight = options.size() - 1;
+ break;
+ case 10: // enter
+ case 32: // space
+ case 'l':
+ hide_panel(pan);
+ del_panel(pan);
+ update_panels();
+ attroff(COLOR_PAIR(black));
+ s.draw.unlock();
+ s.ui_is_open = false;
+ return options[highlight];
+ break;
+ case 27: // escape
+ case 'h':
+ case 'q':
+ hide_panel(pan);
+ del_panel(pan);
+ update_panels();
+ attroff(COLOR_PAIR(black));
+ s.draw.unlock();
+ s.ui_is_open = false;
+ return "";
+ break;
+ default:
+ goto getkey;
+ break;
+ }
+ }
+}
+
+void ui::RenderUI()
+{
+ std::vector<std::string> choices = {
+ "Maze generator =>",
+ "Pathfinder =>",
+ "Render maze generation",
+ "Render path-finding",
+ "Soft time of maze generation",
+ "Hard time of maze generation",
+ "Soft time of path-finding",
+ "Hard time of path-finding",
+ "Hard time for final path drawing",
+ "Time between maze generation"
+ };
+
+ std::string mmenu;
+ /* std::string mmenu = choices[0]; */
+ while (true) {
+
+ mmenu = Option(choices);
+ /* mmenu = Option(choices, mmenu); */
+
+ if (mmenu == "")
+ break;
+
+ if (mmenu == "Maze generator =>") {
+ std::vector<std::string> names;
+ // extracts the keys from the generators map and puts them in names
+ for (std::map<std::string,
+ void (*)(
+ bool*field,
+ const int&width,
+ const int&height)>::iterator it
+ = generators.begin();
+ it != generators.end();
+ ++it) {
+ names.push_back(it->first);
+ }
+ s.generator = Option(names, s.generator);
+ }
+
+ if (mmenu == "Pathfinder =>") {
+ std::vector<std::string> names;
+ // extracts the keys from the pathfinders map and puts them in names
+ for (std::map<std::string,
+ std::vector<vec2<int>> (*)(
+ const bool*field,
+ const int&width,
+ const int&height,
+ const vec2<int>&start,
+ const std::vector<vec2<int>>&exits)>::iterator it
+ = pathfinders.begin();
+ it != pathfinders.end(); ++it) {
+ names.push_back(it->first);
+ }
+ s.pathfinder = Option(names, s.pathfinder);
+ }
+ }
+}
+
+void ui::ExecuteKeys()
+{
+ int width, height;
+ int c;
+ while (true) {
+ getmaxyx(stdscr, height, width);
+ c = getch();
+ s.draw.lock();
+ attron(COLOR_PAIR(white));
+ // clears the top portion of the screen of previous text
+ for (int i = 0; i <= width; ++i) {
+ mvprintw(0, i, " ");
+ }
+ // handles key presses
+ switch (c) {
+ case 'k':
+ s.time_hard_maze_gen += 1;
+ mvprintw(0, 0, "Maze generation hard time: %d", s.time_hard_maze_gen);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'K':
+ s.time_soft_maze_gen += 1;
+ mvprintw(0, 0, "Maze generation soft time: %d", s.time_soft_maze_gen);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'j':
+ s.time_hard_maze_gen -= 1;
+ mvprintw(0, 0, "Maze generation hard time: %d", s.time_hard_maze_gen);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'J':
+ s.time_soft_maze_gen -= 1;
+ mvprintw(0, 0, "Maze generation soft time: %d", s.time_soft_maze_gen);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'i':
+ s.time_hard_pathfinding += 1;
+ mvprintw(0, 0, "Pathfinding hard time: %d", s.time_hard_pathfinding);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'I':
+ s.time_soft_pathfinding += 1;
+ mvprintw(0, 0, "Pathfinding soft time: %d", s.time_soft_pathfinding);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'u':
+ s.time_hard_pathfinding -= 1;
+ mvprintw(0, 0, "Pathfinding hard time: %d", s.time_hard_pathfinding);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 'U':
+ s.time_soft_pathfinding -= 1;
+ mvprintw(0, 0, "Pathfinding soft time: %d", s.time_soft_pathfinding);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ case 27:
+ attroff(COLOR_PAIR(white));
+ s.draw.unlock();
+ RenderUI();
+ break;
+ case 'q':
+ attroff(COLOR_PAIR(white));
+ s.draw.unlock();
+ endwin();
+ exit(0);
+ default:
+ mvprintw(0, 0, "Unknown mapping: <%d>", c);
+ attroff(COLOR_PAIR(white));
+ refresh();
+ s.draw.unlock();
+ break;
+ }
+ std::this_thread::sleep_for(std::chrono::milliseconds(3));
+ }
+}
diff --git a/ui.hpp b/ui.hpp
@@ -0,0 +1,18 @@
+#pragma once
+
+#ifndef UI_HPP
+#define UI_HPP
+
+#include <ncurses.h>
+
+#include "colors.hpp"
+#include "maze_gen.hpp"
+#include "pathfinding.hpp"
+#include "state.hpp"
+
+namespace ui {
+extern void RenderUI();
+extern void ExecuteKeys();
+}
+
+#endif // UI_HPP
diff --git a/vec2.hpp b/vec2.hpp
@@ -0,0 +1,143 @@
+#pragma once
+
+#ifndef VEC2_HPP
+#define VEC2_HPP
+
+#include <cmath>
+#include <iostream>
+
+template <class T = float>
+struct vec2 {
+ vec2() = default;
+ vec2(const T x, const T y)
+ : x(x)
+ , y(y) {};
+ template <class O>
+ vec2(const vec2<O>& other)
+ : x(other.x)
+ , y(other.y) {};
+ bool operator==(const vec2& rhs) const;
+ bool operator!=(const vec2& rhs) const;
+ vec2& operator=(const vec2& rhs);
+ vec2 operator+(const vec2& rhs) const;
+ vec2& operator+=(const vec2& rhs);
+ vec2 operator-(const vec2& rhs) const;
+ vec2& operator-=(const vec2& rhs);
+ vec2 operator*(float rhs) const;
+ vec2& operator*=(float rhs);
+ vec2 operator/(float rhs) const;
+ vec2& operator/=(float rhs);
+ T GetLengthSq() const;
+ float GetLength() const;
+ vec2<T> GetNormalized() const;
+ vec2<T>& Normalize();
+ template <typename U>
+ friend std::ostream& operator<<(std::ostream& os, const vec2<U>& v);
+
+ T x;
+ T y;
+};
+
+template <typename T>
+bool vec2<T>::operator==(const vec2& rhs) const
+{
+ return x == rhs.x && y == rhs.y;
+}
+
+template <typename T>
+bool vec2<T>::operator!=(const vec2& rhs) const
+{
+ return x != rhs.x || y != rhs.y;
+}
+
+template <typename T>
+vec2<T>& vec2<T>::operator=(const vec2& rhs)
+{
+ x = rhs.x;
+ y = rhs.y;
+ return *this;
+}
+
+template <typename T>
+vec2<T> vec2<T>::operator+(const vec2& rhs) const
+{
+ return vec2<T>(x + rhs.x, y + rhs.y); // Can I get away with no T here?
+}
+
+template <typename T>
+vec2<T>& vec2<T>::operator+=(const vec2& rhs)
+{
+ return *this = *this + rhs;
+}
+
+template <typename T>
+vec2<T> vec2<T>::operator-(const vec2& rhs) const
+{
+ return vec2<T>(x - rhs.x, y - rhs.y);
+}
+
+template <typename T>
+vec2<T>& vec2<T>::operator-=(const vec2& rhs)
+{
+ return *this = *this - rhs;
+}
+
+template <typename T>
+vec2<T> vec2<T>::operator*(float rhs) const
+{
+ return vec2<T>(x * rhs, y * rhs);
+}
+
+template <typename T>
+vec2<T>& vec2<T>::operator*=(float rhs)
+{
+ return *this = *this * rhs;
+}
+
+template <typename T>
+vec2<T> vec2<T>::operator/(float rhs) const
+{
+ return vec2<T>(x / rhs, y / rhs);
+}
+
+template <typename T>
+vec2<T>& vec2<T>::operator/=(float rhs)
+{
+ return *this = *this / rhs;
+}
+
+template <typename T>
+T vec2<T>::GetLengthSq() const
+{
+ return (x * x) + (y * y);
+}
+
+template <typename T>
+float vec2<T>::GetLength() const
+{
+ return std::sqrt(GetLengthSq());
+}
+
+template <typename T>
+vec2<T> vec2<T>::GetNormalized() const
+{
+ const float len = GetLength();
+ if (len != 0.0f) {
+ return *this / len;
+ }
+ return *this;
+}
+
+template <typename T>
+vec2<T>& vec2<T>::Normalize()
+{
+ return *this = this->GetNormalized();
+}
+
+template <typename T>
+std::ostream& operator<<(std::ostream& os, const vec2<T>& v)
+{
+ return os << "(" << v.x << ", " << v.y << ")";
+}
+
+#endif // VEC2_HPP
