summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compat/prelude.hpp3
-rw-r--r--src/object.cpp5
-rw-r--r--src/path-search-dijkstra.cpp25
-rw-r--r--src/path-search-result.cpp3
-rw-r--r--src/path-search.cpp2
-rw-r--r--src/path-search.hpp21
-rw-r--r--test/dijkstra.cpp2
-rw-r--r--test/path-search.cpp2
8 files changed, 37 insertions, 26 deletions
diff --git a/compat/prelude.hpp b/compat/prelude.hpp
index a1c5e436..443ab382 100644
--- a/compat/prelude.hpp
+++ b/compat/prelude.hpp
@@ -5,6 +5,9 @@
#include <Corrade/Utility/Macros.h>
#include <Magnum/Magnum.h>
+#define DBG_nospace (::Corrade::Utility::Debug{::Corrade::Utility::Debug::Flag::NoSpace})
+#define DBG (::Corrade::Utility::Debug{})
+
#if !(defined __cpp_size_t_suffix || defined _MSC_VER && _MSVC_LANG < 202004)
#ifdef _MSC_VER
#pragma system_header
diff --git a/src/object.cpp b/src/object.cpp
index 1d089bf6..bed5ef88 100644
--- a/src/object.cpp
+++ b/src/object.cpp
@@ -7,6 +7,7 @@
#include "shaders/shader.hpp"
#include <cmath>
#include <algorithm>
+#include <Magnum/Math/Functions.h>
namespace floormat {
@@ -110,8 +111,6 @@ void object::rotate(size_t, rotation new_r)
const_cast<rotation&>(r) = new_r;
}
-template <typename T> constexpr T sgn(T val) { return T(T(0) < val) - T(val < T(0)); }
-
point object::normalize_coords(global_coords coord, Vector2b cur_offset, Vector2i new_offset)
{
auto off_tmp = Vector2i(cur_offset) + new_offset;
@@ -119,7 +118,7 @@ point object::normalize_coords(global_coords coord, Vector2b cur_offset, Vector2
constexpr auto half_tile = iTILE_SIZE2/2;
for (auto i = 0uz; i < 2; i++)
{
- auto sign = sgn(off_new[i]);
+ auto sign = Math::sign(off_new[i]);
auto absval = std::abs(off_new[i]);
if (absval > half_tile[i])
{
diff --git a/src/path-search-dijkstra.cpp b/src/path-search-dijkstra.cpp
index 4a71ef8d..bb29e402 100644
--- a/src/path-search-dijkstra.cpp
+++ b/src/path-search-dijkstra.cpp
@@ -37,7 +37,7 @@ constexpr bbox<T> bbox_union(bbox<T> bb1, bbox<T> bb2)
return { Math::min(bb1.min, bb2.min), Math::max(bb1.max, bb2.max) };
}
-constexpr auto directions = [] constexpr
+constexpr auto directions = []() constexpr
{
struct pair { Vector2i dir; uint32_t len; };
constexpr auto len1 = div_size;
@@ -104,13 +104,7 @@ size_t astar::edge_hash::operator()(const edge& e) const
path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id own_id,
point from_, point to_, uint32_t max_dist, const pred& p)
{
- auto heap_comparator = [this](uint32_t a, uint32_t b) {
- fm_debug_assert(std::max(a, b) < nodes.size());
- const auto& n1 = nodes[a];
- const auto& n2 = nodes[b];
- return n2.dist < n1.dist;
- };
-
+ const auto heap_comparator = make_heap_comparator();
const auto [from, from_offset] = from_;
const auto [to, to_offset] = to_;
@@ -130,13 +124,10 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
return {};
clear();
- fm_debug_assert(nodes.empty());
const auto start_bbox = bbox_from_pos(Vector2(from.local()), from_offset, own_size);
- const auto from_offset_len = Math::max(1u, (uint32_t)(Vector2(from_offset).length() + 0.5f));
path_search_result result;
- fm_debug_assert(result._node); // todo
auto& path = result._node->vec; path.clear();
indexes[from_] = 0;
@@ -146,16 +137,22 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
if (!from_offset.isZero())
{
+ const auto from_offset_len = Math::max(1u, (uint32_t)(Vector2(from_offset).length() + 0.5f));
uint32_t idx = 1;
// todo also add 4 subdivisions within the tile the same way
- auto bb = bbox_union(start_bbox, Vector2i(from.local()), {}, own_size);
- if (path_search::is_passable(w, chunk_coords_{from}, bb, own_id, p))
+ if (auto bb = bbox_union(start_bbox, Vector2i(from.local()), {}, own_size);
+ path_search::is_passable(w, chunk_coords_{from}, bb, own_id, p))
{
indexes[{from, {}}] = idx;
nodes.push_back({.dist = from_offset_len, .prev = 0, .coord = from, .offset = {}});
Q.push_back(idx++);
std::push_heap(Q.begin(), Q.end(), heap_comparator);
}
+ else
+ {
+
+ }
+
}
while (!Q.empty())
@@ -221,7 +218,7 @@ path_search_result astar::Dijkstra(world& w, Vector2ub own_size, const object_id
}
}
- //Debug {} << "done!" << nodes.size() << "nodes";
+ //DBG << "done!" << nodes.size() << "nodes," << indexes.size() << "indexes," << edges.size() << "edges.";
// todo...
return result;
diff --git a/src/path-search-result.cpp b/src/path-search-result.cpp
index 4e921abd..9e62a30f 100644
--- a/src/path-search-result.cpp
+++ b/src/path-search-result.cpp
@@ -1,6 +1,7 @@
#include "path-search.hpp"
#include "path-search-result.hpp"
#include "compat/assert.hpp"
+#include <Corrade/Containers/ArrayView.h>
#include <utility>
namespace floormat {
@@ -56,7 +57,7 @@ size_t path_search_result::size() const { return _node->vec.size(); }
auto path_search_result::data() const -> const pair* { return _node->vec.data(); }
path_search_result::operator bool() const { return !_node->vec.empty(); }
-path_search_result::operator ArrayView<const pair>() const
+path_search_result::operator ArrayView<const path_search_result::pair>() const
{
fm_debug_assert(_node);
return {_node->vec.data(), _node->vec.size()};
diff --git a/src/path-search.cpp b/src/path-search.cpp
index c543fc9f..95ba1f2d 100644
--- a/src/path-search.cpp
+++ b/src/path-search.cpp
@@ -12,7 +12,7 @@ namespace floormat {
namespace {
-constexpr auto div = path_search::subdivide_factor;
+constexpr auto div = path_search::div_factor;
constexpr int div_BITS = 2;
static_assert(1 << div_BITS == div);
diff --git a/src/path-search.hpp b/src/path-search.hpp
index b6c3f38c..a78d67c3 100644
--- a/src/path-search.hpp
+++ b/src/path-search.hpp
@@ -35,8 +35,8 @@ class path_search final
friend struct path_search_result;
public:
- static constexpr int subdivide_factor = 4;
- static constexpr auto div_size = iTILE_SIZE2 / subdivide_factor;
+ static constexpr int div_factor = 4;
+ static constexpr auto div_size = iTILE_SIZE2 / div_factor;
static constexpr auto min_size = div_size / 2;
template<typename T> struct bbox { VectorTypeFor<2, T> min, max; };
@@ -119,14 +119,13 @@ public:
{
nodes.reserve(capacity);
indexes.reserve(capacity);
- edges.reserve(capacity);
+ edges.reserve(capacity*4);
Q.reserve(capacity);
}
astar()
{
- constexpr auto capacity = TILE_COUNT * 16;
indexes.max_load_factor(.4f);
- reserve(capacity);
+ reserve(initial_capacity);
}
void clear()
{
@@ -135,11 +134,23 @@ public:
edges.clear();
Q.clear();
}
+ auto make_heap_comparator()
+ {
+ return [this](uint32_t a, uint32_t b) {
+ fm_debug_assert(std::max(a, b) < nodes.size());
+ const auto& n1 = nodes[a];
+ const auto& n2 = nodes[b];
+ return n2.dist < n1.dist;
+ };
+ }
// todo add simple bresenham short-circuit
path_search_result Dijkstra(world& w, Vector2ub own_size, object_id own_id,
point from, point to, uint32_t max_dist,
const pred& p = path_search::never_continue());
+
+ static constexpr auto div_factor = path_search::div_factor;
+ static constexpr auto initial_capacity = TILE_COUNT * 16 * div_factor*div_factor;
};
} // namespace floormat
diff --git a/test/dijkstra.cpp b/test/dijkstra.cpp
index 1db3ff22..817f944a 100644
--- a/test/dijkstra.cpp
+++ b/test/dijkstra.cpp
@@ -15,7 +15,7 @@ void bench_run(StringView name, F&& fun)
using clock = high_resolution_clock;
const auto t0 = clock::now();
fun();
- for (int i = 0; i < 10; i++)
+ for (int i = 0; i < 1000; i++)
fun();
const auto tm = clock::now() - t0;
Debug{} << "test" << name << "took" << duration_cast<milliseconds>(tm).count() << "ms.";
diff --git a/test/path-search.cpp b/test/path-search.cpp
index b2a50524..20645c63 100644
--- a/test/path-search.cpp
+++ b/test/path-search.cpp
@@ -13,7 +13,7 @@ namespace {
template<typename T> using bbox = path_search::bbox<T>;
using pred = path_search::pred;
-constexpr auto div = path_search::subdivide_factor;
+constexpr auto div = path_search::div_factor;
constexpr auto min_size = path_search::min_size;
constexpr bbox<int> get_value(Vector2ub sz, Vector2ub div, rotation r)
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 04:25:53 +0000