/* This file is part of Minitrem. Minitrem is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version. Minitrem is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Minitrem. If not, see . */ #include "common.hpp" namespace world { static const v2f_t path_margin(5, 5); // The path finder will try to walk in the eight directions listed below. static const tile_index_t path_offsets[8] = { {+1, 0}, {+1, +1}, {0, +1}, {-1, +1}, {-1, 0}, {-1, -1}, {0, -1}, {+1, -1} }; path_finder_t::~path_finder_t() { delete[] nodes; } void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_, cflags_t cflags_) { rectf_t src_margin, dst_margin; tile_index_t end; src = src_; dst = dst_; cflags = cflags_; tile_center = v2f_t(0.5, 0.5); shortest_dist = INFINITY; src_margin[0] = src - path_margin; src_margin[1] = src + path_margin; dst_margin[0] = dst - path_margin; dst_margin[1] = dst + path_margin; bounds = src_margin | dst_margin; base = tile_index_at(bounds[0]); end = tile_index_at(bounds[1]); width = end[0] - base[0] + 1; height = end[1] - base[1] + 1; nodes = new path_node_t[width * height]; for (size_t i = 0; i < width * height; i++) { nodes[i].accessible = true; nodes[i].dist = INFINITY; } } void path_finder_t::eliminate_nodes(rectf_t bounds) { rect_t index_bounds; tile_index_t index; bounds[0] -= tile_center; bounds[1] -= tile_center; index_bounds[0] = tile_index_t(bounds[0].ceil()) - base; index_bounds[1] = tile_index_t(bounds[1].floor()) - base; if (index_bounds[0][0] < 0) index_bounds[0][0] = 0; if (index_bounds[0][1] < 0) index_bounds[0][1] = 0; if (index_bounds[1][0] >= (coord_t)width) index_bounds[1][0] = width - 1; if (index_bounds[1][1] >= (coord_t)height) index_bounds[1][1] = height - 1; for (index[1] = index_bounds[0][1]; index[1] <= index_bounds[1][1]; index[1]++) for (index[0] = index_bounds[0][0]; index[0] <= index_bounds[1][0]; index[0]++) { path_node_t *node; node = nodes + index[1] * width + index[0]; node->accessible = false; } } path_node_t *path_finder_t::node_at(tile_index_t index) { return nodes + index[1] * width + index[0]; } bool path_finder_t::is_accessible(tile_index_t index) { if (index[0] < 0 || index[1] < 0 || index[0] >= (coord_t)width || index[1] >= (coord_t)height) return false; return node_at(index)->accessible; } // Walking diagonally requires an additional accessibility test. The tables // below list when it's needed and which tile is to be tested. For example, // when walking north-west, the north and the west neighbors have to be tested // for accessibility. bool path_finder_t::diagonal_test(tile_index_t index, size_t i) { static const bool do_test[8] = { false, true, false, true, false, true, false, true }; static const tile_index_t offsets[8][2] = { {}, {{+1, 0}, {0, +1}}, {}, {{0, +1}, {-1, 0}}, {}, {{-1, 0}, {0, -1}}, {}, {{0, -1}, {+1, 0}} }; if (!do_test[i]) return true; for (size_t j = 0; j < 2; j++) if (!is_accessible(index + offsets[i][j])) return false; return true; } static const int visit_orders[4][8] = { {0, 7, 1, 2, 6, 5, 3, 4}, // prefer +x {2, 3, 1, 0, 4, 7, 5, 6}, // prefer +y {4, 5, 3, 2, 6, 1, 7, 0}, // prefer -x {6, 5, 7, 0, 4, 3, 1, 2} // prefer -y }; static const int *visit_order(v2f_t delta) { if (delta[1] > delta[0]) { if (delta[1] > -delta[0]) return visit_orders[1]; else return visit_orders[2]; } else { if (delta[1] > -delta[0]) return visit_orders[0]; else return visit_orders[3]; } return visit_orders[0]; } void path_finder_t::find_r(tile_index_t index, float dist, float limit) { path_node_t *node; v2f_t delta; float dist_to_dst; const int *order; node = nodes + index[1] * width + index[0]; if (!node->accessible) return; if (node->dist <= dist) return; node->dist = dist; path.push_back(index); delta = dst - v2f_t(base + index) - tile_center; dist_to_dst = delta.len(); if (dist_to_dst < 1.0f && dist + dist_to_dst < shortest_dist) { shortest_path = path; shortest_dist = dist + dist_to_dst; return; } order = visit_order(delta); for (size_t i = 0; i < 8; i++) { tile_index_t offset, next; offset = path_offsets[order[i]]; next = index + offset; if (!is_accessible(next)) continue; if (!diagonal_test(index, order[i])) continue; if (dist + v2f_t(offset).len() > limit) continue; find_r(next, dist + v2f_t(offset).len(), limit); if (shortest_path.size()) return; } path.pop_back(); } bool path_finder_t::find(void) { tile_index_t start; start = tile_index_at(src) - base; find_r(start, 0.0f, 100.0f); return shortest_path.size() > 0; } void path_finder_t::export_path(std::list *list) { list->clear(); for (tile_index_t &index : shortest_path) list->push_back(v2f_t(index + base) + tile_center); list->push_back(dst); } } // namespace world