examples

commit 2e243c188fccf8aacb2495b32142962be0bec964
parent 335d5b90a0455229079ab2c2b449b0b3ce9c6d92
Author: Henry Wilson <henry@henryandlizzy.uk>
Date:   Fri, 22 Sep 2023 21:33:37 +0100

pathfind: Add example pathfinding algorithm

Diffstat:
M
build.sh
 | 
1
+
A
src/pathfind.cpp
 | 
78
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 79 insertions(+), 0 deletions(-)
diff --git a/build.sh b/build.sh
@@ -50,6 +50,7 @@ mkdir -p "bin"
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/model src/model.cpp )
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/mutex_container src/mutex_container.cpp )
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/owning_ptr src/owning_ptr.cpp )
+(c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/pathfind src/pathfind.cpp )
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/pulse-async-client src/pulse-async-client.cpp -lpulse)
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/sdl src/sdl.cpp -lSDL2)
 (c++ -std=c++20 -Wall -Wextra -Werror -fdiagnostics-color=always -fsanitize=undefined,address -o bin/sorts src/sorts.cpp )
diff --git a/src/pathfind.cpp b/src/pathfind.cpp
@@ -0,0 +1,78 @@
+#include <iostream>
+#include <format>
+#include <vector>
+#include <deque>
+#include <algorithm>
+#include <set>
+
+struct node {
+    std::string name;
+    std::vector<node*> edges;
+};
+
+std::deque<node> all_stations;
+
+void connect(node& a, node& b)
+{
+    a.edges.push_back(&b);
+    b.edges.push_back(&a);
+}
+
+struct visitation
+{
+    node* location;
+    visitation* from;
+};
+
+std::vector<node*> pathfind(node& start, node& dest)
+{
+    std::deque<visitation> candidates{{&start, nullptr}};
+    std::deque<visitation> visited;
+
+    while (not candidates.empty())
+    {   
+        visited.emplace_back(candidates.front());
+        candidates.pop_front();
+        auto& visiting = visited.back();
+
+        if (visiting.location == &dest)
+        {
+            std::vector<node*> backtrack;
+            visitation* v = &visiting;
+            do
+                backtrack.push_back(v->location);
+            while ((v = v->from));
+            std::ranges::reverse(backtrack);
+            return backtrack;
+        }
+
+        for (auto next : visiting.location->edges)
+            if (std::ranges::none_of(visited, [next](auto const& v) { return v.location == next; }))
+                candidates.emplace_back(next, &visiting);
+    }
+    
+    return {};
+}
+
+int main()
+{
+    auto& a = all_stations.emplace_back("A");
+    auto& b = all_stations.emplace_back("B");
+    auto& c = all_stations.emplace_back("C");
+    auto& d = all_stations.emplace_back("D");
+    auto& e = all_stations.emplace_back("E");
+    auto& f = all_stations.emplace_back("F");
+    auto& g = all_stations.emplace_back("G");
+    all_stations.emplace_back("Unconnected");
+
+    connect(a, b);
+    connect(b, c);
+    connect(c, d);
+    connect(d, e);
+    connect(e, f);
+    connect(f, g);
+    connect(c, e);
+
+    for (auto s : pathfind(b, f))
+        std::cout << std::format("'{}'\n", s->name);
+}