From c9a0aff5a9333cf5e0ee55ba5c8551457a3ae13c Mon Sep 17 00:00:00 2001 From: Paweł Redman Date: Mon, 26 Mar 2018 19:27:17 +0200 Subject: WIP --- src/common.hpp | 1 + src/game/interface.cpp | 6 ++++- src/game/units.cpp | 14 +++++++---- src/path_finder.cpp | 64 +++++++++++++++++++++++++++++--------------------- 4 files changed, 52 insertions(+), 33 deletions(-) diff --git a/src/common.hpp b/src/common.hpp index 6042e08..d4950e4 100644 --- a/src/common.hpp +++ b/src/common.hpp @@ -256,6 +256,7 @@ namespace game { bool paused; ntime_t t0; size_t frames = 0, frames_since_t0, frames_behind = 0; + ntime_t pathfinder_time = 0; void start(void); void stop(void); diff --git a/src/game/interface.cpp b/src/game/interface.cpp index 262c3ae..bd70dbb 100644 --- a/src/game/interface.cpp +++ b/src/game/interface.cpp @@ -277,7 +277,11 @@ void state_t::render_to(render::state_t *render) x[1] += em; ss.str(std::string()); ss << std::fixed << std::setprecision(3); - ss << "Game t/F/B: " << game->time * 1.0e-9 << "/" << game->frames << "/" << game->frames_behind; + ss << "Game t/F/B/PFT: "; + ss << game->time * 1.0e-9 << "/"; + ss << game->frames << "/"; + ss << game->frames_behind << "/"; + ss << game->pathfinder_time * 1.0e-9 << " (" << ((float)game->pathfinder_time / game->time * 100.0f) << "%)"; render->render_text(x, em, ss.str(), render::ALIGN_LEFT_TOP, sf::Color::White); } diff --git a/src/game/units.cpp b/src/game/units.cpp index edb41ec..5f722aa 100644 --- a/src/game/units.cpp +++ b/src/game/units.cpp @@ -163,6 +163,8 @@ bool unit_t::keep_moving(double speed) bool unit_t::start_moving(v2f_t dst) { world::cmodel_t rep; + ntime_t t0; + bool rv; if (!world) { printf("unit_t::start_moving: entity is not linked\n"); @@ -175,7 +177,10 @@ bool unit_t::start_moving(v2f_t dst) rep.cflags = move.cflags & ~(cmodel.cflags); rep.bounds = cmodel.bounds; - if (!world->find_path(x, move.dst, &rep, this, &move.path)) { + t0 = nclock(); + rv = world->find_path(x, move.dst, &rep, this, &move.path); + game->pathfinder_time += nclock() - t0; + if (!rv) { move.moving = false; return false; } @@ -531,8 +536,8 @@ void unit_soldier_t::render_late_to(render::state_t *render) unit_spider_t::unit_spider_t(game::state_t *game) : unit_t(game, UNIT_SPIDER) { - size[0] = v2f_t(-0.2f, +0.0f); - size[1] = v2f_t(+0.2f, +0.3f); + size[0] = v2f_t(-0.3f, +0.0f); + size[1] = v2f_t(+0.3f, +0.3f); render_size[0] = v2f_t(-0.3f, -0.3f); render_size[1] = v2f_t(+0.3f, +0.3f); cmodel.cflags = CF_BODY_SMALL; @@ -560,7 +565,7 @@ void unit_spider_t::target_and_attack(void) return; start_moving(target->x); - next_targetting = game->now + 0.2; + next_targetting = game->now + 500.0; if (last_attack + 0.5 > game->now) return; @@ -588,7 +593,6 @@ void unit_spider_t::on_think(void) void unit_spider_t::on_wake(void) { - next_targetting = game->now; } void unit_spider_t::on_death(void) diff --git a/src/path_finder.cpp b/src/path_finder.cpp index 8a61cc6..04f4d57 100644 --- a/src/path_finder.cpp +++ b/src/path_finder.cpp @@ -136,10 +136,36 @@ bool path_finder_t::diagonal_test(tile_index_t index, size_t i) 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]; @@ -148,31 +174,37 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit) if (node->dist <= dist) return; - path.push_back(index); node->dist = dist; + path.push_back(index); - dist_to_dst = (v2f_t(base + index) + tile_center - dst).len(); + 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[i]; + offset = path_offsets[order[i]]; next = index + offset; if (!is_accessible(next)) continue; - if (!diagonal_test(index, i)) + 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(); @@ -181,31 +213,9 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit) bool path_finder_t::find(void) { tile_index_t start; - float dist_simple; - - dist_simple = (src - dst).len(); - - if (dist_simple < 0.5f) - return true; start = tile_index_at(src) - base; - node_at(start)->accessible = false; - - for (size_t i = 0; i < 8; i++) { - tile_index_t next; - v2f_t offset; - - next = start + path_offsets[i]; - - if (!is_accessible(next)) - continue; - - if (!diagonal_test(start, i)) - continue; - - offset = (src - v2f_t(base)) - v2f_t(next) - tile_center; - find_r(next, v2f_t(offset).len(), dist_simple * 3); - } + find_r(start, 0.0f, 100.0f); return shortest_path.size() > 0; } -- cgit