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
66
67
68
69
70
71
72
73
74
75
|
#pragma once
#include "path-search.hpp"
#include "point.hpp"
#include <bitset>
#include <Corrade/Containers/Array.h>
namespace floormat::detail_astar {
struct cache;
struct chunk_cache;
struct cache
{
Vector2ui size;
Vector2i start{(int)((1u << 31) - 1)};
Array<chunk_cache> array;
cache();
fm_DECLARE_DELETED_COPY_ASSIGNMENT(cache);
size_t get_chunk_index(Vector2i chunk) const;
static size_t get_chunk_index(Vector2i start, Vector2ui size, Vector2i coord);
static size_t get_tile_index(Vector2i pos, Vector2b offset);
static Vector2ui get_size_to_allocate(uint32_t max_dist);
void allocate(point from, uint32_t max_dist);
void add_index(size_t chunk_index, size_t tile_index, uint32_t index);
void add_index(point pt, uint32_t index);
uint32_t lookup_index(size_t chunk_index, size_t tile_index);
chunk* try_get_chunk(world& w, chunk_coords_ ch);
std::array<chunk*, 8> get_neighbors(world& w, chunk_coords_ ch0);
};
} // namespace floormat::detail_astar
namespace floormat {
class astar
{
public:
struct visited
{
uint32_t dist = (uint32_t)-1;
uint32_t prev = (uint32_t)-1;
point pt;
};
using pred = detail_astar::pred;
fm_DECLARE_DELETED_COPY_ASSIGNMENT(astar);
astar();
void reserve(size_t capacity);
void clear();
// todo add simple bresenham short-circuit
path_search_result Dijkstra(world& w, point from, point to,
object_id own_id, uint32_t max_dist, Vector2ub own_size,
int debug = 0, const pred& p = detail_astar::never_continue());
private:
static constexpr auto initial_capacity = TILE_COUNT * 16 * detail_astar::div_factor*detail_astar::div_factor;
struct chunk_cache;
void add_to_heap(uint32_t id);
uint32_t pop_from_heap();
struct detail_astar::cache cache;
Array<visited> nodes;
Array<uint32_t> Q;
};
} // namespace floormat
|
