1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#pragma once
#include "compat/defs.hpp"
#include "global-coords.hpp"
#include <vector>
#include <tsl/robin_set.h>
namespace floormat {
struct astar_edge;
struct astar_hash {
size_t operator()(const astar_edge& e) const;
};
struct astar_edge
{
bool operator==(const astar_edge&) const noexcept;
fm_DECLARE_DEFAULT_COPY_ASSIGNMENT_(astar_edge);
astar_edge(global_coords coord1, Vector2b off1, global_coords coord2, Vector2b off2);
astar_edge(chunk_coords_ ch1, local_coords t1, Vector2b off1,
chunk_coords_ ch2, local_coords t2, Vector2b off2);
size_t hash() const;
astar_edge swapped() const;
int16_t from_cx, from_cy, to_cx, to_cy;
int8_t from_cz, to_cz;
uint8_t from_t, to_t;
int8_t from_offx, from_offy, to_offx, to_offy;
static constexpr auto INF = (uint32_t)-1;
private:
astar_edge();
};
struct astar_edge_tuple
{
static constexpr auto MAX = (uint32_t)-1;
friend bool operator<(const astar_edge_tuple& a, const astar_edge_tuple& b);
astar_edge e;
uint32_t dist = MAX;
};
struct astar final
{
void reserve(size_t count);
bool empty() const { return Q.empty(); }
[[nodiscard]] bool add_visited(const astar_edge& value);
void push(const astar_edge& value, uint32_t dist);
astar_edge_tuple pop();
void clear();
private:
static constexpr bool StoreHash = true; // todo benchmark it
tsl::robin_set<astar_edge,
astar_hash, std::equal_to<>,
std::allocator<astar_edge>,
StoreHash> seen;
std::vector<astar_edge_tuple> Q;
};
} // namespace floormat
|
