You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
97 lines
2.7 KiB
97 lines
2.7 KiB
#include "constants.hpp"
|
|
#include "pathing.hpp"
|
|
#include "dbc.hpp"
|
|
#include <vector>
|
|
|
|
using std::vector;
|
|
|
|
inline void add_neighbors(PointList &neighbors, Matrix &closed, size_t y, size_t x) {
|
|
for(matrix::in_box it{closed, x, y, 1}; it.next();) {
|
|
if(closed[it.y][it.x] == 0) {
|
|
closed[it.y][it.x] = 1;
|
|
neighbors.push_back({.x=it.x, .y=it.y});
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Used https://github.com/HenrYxZ/dijkstra-map as a reference.
|
|
*/
|
|
void Pathing::compute_paths(Matrix &walls) {
|
|
INVARIANT();
|
|
dbc::check(walls[0].size() == $width,
|
|
fmt::format("Pathing::compute_paths called with walls.width={} but paths $width={}", walls[0].size(), $width));
|
|
|
|
dbc::check(walls.size() == $height,
|
|
fmt::format("Pathing::compute_paths called with walls.height={} but paths $height={}", walls[0].size(), $height));
|
|
|
|
// Initialize the new array with every pixel at limit distance
|
|
matrix::assign($paths, WALL_PATH_LIMIT);
|
|
|
|
Matrix closed = walls;
|
|
PointList starting_pixels;
|
|
PointList open_pixels;
|
|
|
|
// First pass: Add starting pixels and put them in closed
|
|
for(size_t counter = 0; counter < $height * $width; counter++) {
|
|
size_t x = counter % $width;
|
|
size_t y = counter / $width;
|
|
if($input[y][x] == 0) {
|
|
$paths[y][x] = 0;
|
|
closed[y][x] = 1;
|
|
starting_pixels.push_back({x,y});
|
|
}
|
|
}
|
|
|
|
// Second pass: Add border to open
|
|
for(auto sp : starting_pixels) {
|
|
add_neighbors(open_pixels, closed, sp.y, sp.x);
|
|
}
|
|
|
|
// Third pass: Iterate filling in the open list
|
|
int counter = 1; // leave this here so it's available below
|
|
for(; counter < WALL_PATH_LIMIT && !open_pixels.empty(); ++counter) {
|
|
PointList next_open;
|
|
for(auto sp : open_pixels) {
|
|
$paths[sp.y][sp.x] = counter;
|
|
add_neighbors(next_open, closed, sp.y, sp.x);
|
|
}
|
|
open_pixels = next_open;
|
|
}
|
|
|
|
// Last pass: flood last pixels
|
|
for(auto sp : open_pixels) {
|
|
$paths[sp.y][sp.x] = counter;
|
|
}
|
|
}
|
|
|
|
void Pathing::set_target(const Point &at, int value) {
|
|
// FUTURE: I'll eventually allow setting this to negatives for priority
|
|
$input[at.y][at.x] = value;
|
|
}
|
|
|
|
void Pathing::clear_target(const Point &at) {
|
|
$input[at.y][at.x] = 1;
|
|
}
|
|
|
|
void Pathing::random_flood(const Point from, std::function<void(Point at, int dnum)> cb) {
|
|
// quick hack to try the idea
|
|
matrix::each_cell it{$paths};
|
|
it.x = from.x;
|
|
it.y = from.y;
|
|
|
|
while(it.next()) {
|
|
cb({it.x, it.y}, $paths[it.y][it.x]);
|
|
}
|
|
}
|
|
|
|
bool Pathing::INVARIANT() {
|
|
using dbc::check;
|
|
|
|
check($paths.size() == $height, "paths wrong height");
|
|
check($paths[0].size() == $width, "paths wrong width");
|
|
check($input.size() == $height, "input wrong height");
|
|
check($input[0].size() == $width, "input wrong width");
|
|
|
|
return true;
|
|
}
|
|
|