Tìm đường 3D và đám đông

Trang này cho nhân vật do máy điều khiển tự đi trong màn 3D: tìm đường quanh tường, lên dốc, lên bục, nhảy qua khe; và đi thành đám đông mà không đâm vào nhau. Mọi thứ khai báo trong njin_nav3d.h, dựng trên Recast và Detour (thư viện tìm đường của rất nhiều game 3D), nằm trong engine.

Cần biết trước: Đồ họa 3D (begin_3d(), vật lý 3D). Game 2D theo lưới ô thì dùng nav_grid của Làm game top-down, đơn giản hơn nhiều.

Navmesh là gì

Navmesh là các đa giác phủ lên chỗ đi được của màn chơi: mặt sàn, mặt dốc, mặt bục, đã chừa ra một khoảng bằng bán kính nhân vật quanh tường và vật cản. Tìm đường trên đó nhanh hơn trên lưới ô rất nhiều, và đường đi ra là những đoạn thẳng gấp khúc ở góc vật cản, không đi zíc zắc theo ô.

Engine dựng navmesh từ hình học tĩnh mà game đưa vào, theo cỡ của nhân vật:

Trường của njin::navmesh3d_desc	Nghĩa
agent_radius	Chỗ đi được cách tường bấy nhiêu mét
agent_height	Chỉ chui qua chỗ trần cao hơn số này
agent_climb	Bậc cao nhất bước lên được
max_slope	Dốc nhất đi được, độ
cell_size, cell_height	Độ mịn khi dựng: nhỏ thì sát tường hơn, dựng lâu hơn
tile_size	Cạnh mỗi ô vuông của navmesh, để dựng lại từng vùng

Dựng navmesh

Tạo navmesh, thêm hình học, rồi dựng một lần lúc nạp màn:

const njin::navmesh3d_handle nav = njin::navmesh3d_create(ctx, {.agent_radius = 0.4f});
njin::navmesh3d_add_box(ctx, nav, {0, -0.5f, 0}, {30, 1, 30});   // sàn
njin::navmesh3d_add_model(ctx, nav, level_model, {0, 0, 0});     // model của màn
njin::navmesh3d_add_terrain(ctx, nav, ground);                   // địa hình của @ref world_3d
njin::navmesh3d_build(ctx, nav);

Hàm	Thêm gì
navmesh3d_add_box()	Một hình hộp, xoay được: sàn, tường, bục, bàn
navmesh3d_add_mesh()	Một lưới tam giác trong thế giới (được chép lại)
navmesh3d_add_model()	Các tam giác của một model, đặt như draw_model()
navmesh3d_add_terrain()	Một địa hình; độ cao đọc lại mỗi lần dựng
navmesh3d_add_link()	Lối tắt không liền mặt đất: nhảy qua khe, leo thang, nhảy xuống bục

Tam giác cần quay mặt trước lên trên (ngược chiều kim đồng hồ khi nhìn từ trên xuống, như mọi lưới của njin). Dựng mất từ vài chục mili giây (một căn phòng) đến vài giây (bản đồ lớn với cell_size nhỏ).

Khi màn chơi đổi (sửa địa hình, mở cửa, đặt thêm vật cản bằng navmesh3d_add_box()), navmesh3d_rebuild() dựng lại các ô vuông trong một vùng, không phải cả bản đồ. Tác tử đang đi tự tìm lại đường.

Hỏi navmesh

Hàm	Trả lời
navmesh3d_path()	Đường từ A đến B: các điểm gấp khúc. Không đến được B thì dừng ở chỗ gần B nhất
navmesh3d_nearest()	Điểm gần nhất trên navmesh
navmesh3d_raycast()	Đi thẳng trên mặt đất từ A về B, dừng ở mép đầu tiên: có thấy nhau không, lao tới được bao xa
navmesh3d_random_point()	Một điểm ngẫu nhiên trên cả navmesh
navmesh3d_random_point_near()	Một điểm ngẫu nhiên đi tới được, cách một tâm không quá bán kính: quái đi lang thang quanh ổ
navmesh3d_draw_debug()	Vẽ các đa giác bằng gizmo, để xem engine thấy chỗ nào đi được

std::vector<njin::vec3> path;
if (njin::navmesh3d_path(ctx, nav, guard_pos, player_pos, path))
  for (size_t i = 0; i + 1 < path.size(); i++)
    njin::gizmo_line3d(ctx, path[i], path[i + 1], njin::colors::yellow);

Điểm của đường đi và vị trí tác tử nằm trên mặt đất. Trên địa hình đã thêm bằng navmesh3d_add_terrain(), độ cao lấy đúng theo terrain3d_height(), và đoạn nào cắt qua đồi thì có thêm điểm giữa để đường bám mặt đất (cách không quá 5 cm). Trên hình học khác (model, hộp nghiêng) độ cao theo lưới chi tiết của navmesh, có thể sai vài cm; muốn chính xác thì lấy độ cao bằng một tia xuống, hoặc cho tác tử lái một nhân vật vật lý (phần dưới).

Đám đông

Tác tử (nav3d_agent_add()) là một nhân vật tự tìm đường và tự đi: game chỉ đặt đích. Các tác tử trên cùng một navmesh né nhau trên đường đi và tách nhau ra khi đứng sát, nên một nhóm quái đuổi theo người chơi không dồn thành một cục. Engine cập nhật chúng trong phase_post_update theo delta().

const njin::nav3d_agent_handle orc = njin::nav3d_agent_add(ctx, nav, {.position = spawn, .max_speed = 4.0f});
njin::nav3d_agent_set_target(ctx, orc, player_pos);    // gọi lại mỗi frame khi đích chạy cũng được
const njin::vec3 p = njin::nav3d_agent_position(ctx, orc);
const njin::vec3 v = njin::nav3d_agent_velocity(ctx, orc); // hướng quay mặt, chọn animation đi hay chạy
if (njin::nav3d_agent_arrived(ctx, orc))
  attack();

nav3d_agent_stop() bỏ đích, nav3d_agent_teleport() đặt sang chỗ khác ngay, nav3d_agent_remove() bỏ tác tử.

Lái nhân vật vật lý. Đặt nav3d_agent_desc::character là một njin::character3d_handle: mỗi frame vận tốc của tác tử thành vận tốc ngang của nhân vật, nhân vật rơi theo trọng lực khi không đứng trên sàn, và chỗ nhân vật thật sự đến (bị đẩy, va vào thùng) thành chỗ của tác tử. Game đừng tự đặt vận tốc cho nhân vật đó nữa.

Vùng và chi phí

Mỗi chỗ đi được thuộc một vùng, số từ 0 đến 15 (njin::nav3d_max_areas). Vùng 0 là mặt đất thường; các số khác game tự đặt nghĩa: đường cái, cỏ, đầm lầy, nước nông, ô cửa. Đánh dấu vùng theo hai cách:

• Cả một mảng hình học: tham số area cuối của navmesh3d_add_mesh(), navmesh3d_add_model(), navmesh3d_add_box(), navmesh3d_add_terrain() và navmesh3d_add_link() (lối tắt cũng có vùng: nhảy qua khe thì đắt).
• Một khối đứng trên bản đồ: navmesh3d_add_area() với tâm, cỡ, góc xoay quanh trục đứng và số vùng. Navmesh đã dựng thì các ô vuông khối chạm vào được dựng lại ngay; navmesh3d_remove_area() bỏ khối.

Bộ lọc (njin::nav3d_filter) nói cách tìm đường nhìn các vùng: cost[vùng] là giá mỗi mét (1 là bình thường, 8 là một mét ở đó tốn như tám mét đường thường) và excluded là các vùng cấm hẳn (bit 1 << vùng). Mỗi navmesh giữ 16 bộ lọc, đặt bằng navmesh3d_set_filter(); đổi bộ lọc không cần dựng lại navmesh, và tác tử đang đi theo nó tìm lại đường ngay. Bộ lọc 0 là bộ lọc mặc định: navmesh3d_path() không chọn bộ lọc dùng nó. Tác tử chọn bộ lọc bằng nav3d_agent_desc::filter, đổi bằng nav3d_agent_set_filter().

constexpr njin::u8 swamp = 2, door = 3;
njin::navmesh3d_add_area(ctx, nav, {-4.0f, 0.0f, 0.0f}, {10.0f, 4.0f, 14.0f}, 0.0f, swamp);
njin::nav3d_filter f{};
f.cost[swamp] = 8.0f;     // vòng qua đầm lầy, trừ khi vòng quá xa
f.excluded = 1u << door;  // không bao giờ đi qua cửa khóa
njin::navmesh3d_set_filter(ctx, nav, 1, f);
std::vector<njin::vec3> path;
njin::navmesh3d_path(ctx, nav, from, to, path, 1); // tìm đường theo bộ lọc 1

Khi hai mặt nằm sát nhau (đường cái phủ lên sàn), vùng số lớn hơn thắng. Khối của navmesh3d_add_area() luôn thắng vùng của hình học bên dưới.

Nhiều cỡ tác tử

Khoảng chừa quanh tường (agent_radius) được tính lúc dựng, nên mỗi cỡ tác tử cần một navmesh. navmesh3d_clone() chép hình học, vùng, lối tắt, vật cản và bộ lọc của một navmesh sang navmesh mới dựng theo cỡ khác; dựng cả hai, rồi thêm tác tử to vào navmesh to. Hình học, vùng hay vật cản thêm về sau thì thêm cho từng navmesh. Tác tử trên hai navmesh khác nhau không né nhau.

Vật cản di động

navmesh3d_add_obstacle() đặt một hộp (hay hình trụ, khi radius lớn hơn 0) lên navmesh: chỗ nó đứng không còn đi được, cách nó một khoảng agent_radius như tường. navmesh3d_move_obstacle() dời nó, navmesh3d_remove_obstacle() bỏ nó. Không cần thêm hình học hay gọi navmesh3d_rebuild(): engine dựng lại các ô vuông nó chạm vào ở các frame sau, tối đa navmesh3d_desc::obstacle_tiles_per_frame ô mỗi frame (mặc định 4), và tác tử tìm đường vòng qua nó. navmesh3d_pending_tiles() cho biết còn bao nhiêu ô chờ. Mỗi ô vuông 8 m dựng lại mất vài mili giây, nên dời vật cản khi nó thật sự đổi chỗ (thùng dừng lại, cửa đóng xong), không phải mỗi frame khi nó đang trượt.

Ví dụ đầy đủ

Một căn phòng có tường và bục có dốc; tám tác tử đi tới chỗ chuột trái bấm; đường từ con đầu tới chỗ chuột được vẽ thử.

#include <njin.h>
 
#include <vector>
 
namespace {
using namespace njin;
 
const camera3d camera{.position = {0.0f, 22.0f, 18.0f}, .target = {0.0f, 0.0f, 0.0f}, .fovy = 50.0f};
 
// Sàn, hai bức tường và một bục có dốc lên.
struct box {
  vec3 center, size, rotation;
};
const box level[] = {
    {{0.0f, -0.5f, 0.0f}, {30.0f, 1.0f, 30.0f}, {}},
    {{-4.0f, 1.0f, 0.0f}, {1.0f, 2.0f, 12.0f}, {}},
    {{5.0f, 1.0f, -4.0f}, {8.0f, 2.0f, 1.0f}, {}},
    {{8.0f, 1.0f, 8.0f}, {6.0f, 2.0f, 6.0f}, {}},
    {{2.2f, 0.9f, 8.0f}, {6.0f, 0.2f, 3.0f}, {0.0f, 0.0f, 20.0f}}, // dốc lên bục
};
 
navmesh3d_handle nav;
std::vector<nav3d_agent_handle> crowd;
std::vector<vec3> preview; // đường từ con đầu tới chỗ chuột
 
void load(context &ctx) {
  // Navmesh cho tác tử bán kính 0.4 m, cao 1.8 m, bước lên bậc 0.4 m.
  nav = navmesh3d_create(ctx, {.agent_radius = 0.4f, .agent_height = 1.8f, .agent_climb = 0.4f});
  for (const box &b : level) {
    navmesh3d_add_box(ctx, nav, b.center, b.size, b.rotation);
    body3d_create(ctx, {.shape = shape3d_box, .position = b.center, .rotation = b.rotation, .size = b.size});
  }
  navmesh3d_build(ctx, nav);
 
  // Một nhóm tác tử đứng thành hàng.
  for (i32 i = 0; i < 8; i++)
    crowd.push_back(nav3d_agent_add(ctx, nav, {.position = {-10.0f + (f32)i, 0.0f, 10.0f}}));
}
 
void update(context &ctx) {
  // Chuột trỏ chỗ nào trên sàn, cả nhóm đi tới đó; chuột trái là ra lệnh.
  const ray3d ray = camera3d_ray(ctx, camera, mouse_pos(ctx));
  const ray3d_hit hit = ray3d_plane(ray, {0.0f, 0.0f, 0.0f}, {0.0f, 1.0f, 0.0f});
  if (!hit.hit)
    return;
  navmesh3d_path(ctx, nav, nav3d_agent_position(ctx, crowd[0]), hit.point, preview);
  if (mouse_pressed(ctx, mouse_left))
    for (nav3d_agent_handle a : crowd)
      nav3d_agent_set_target(ctx, a, hit.point);
}
 
void render(context &ctx) {
  light3d_set(ctx, {.direction = {-0.4f, -1.0f, -0.3f}, .shadows = true, .shadow_range = 40.0f});
  begin_3d(ctx, camera);
  for (const box &b : level)
    draw_shape3d(ctx, {.kind = shape3d_box, .position = b.center, .rotation = b.rotation, .size = b.size},
                 rgba{0.7f, 0.68f, 0.62f, 1.0f});
  for (nav3d_agent_handle a : crowd) {
    const vec3 p = nav3d_agent_position(ctx, a);
    draw_capsule3d(ctx, p + vec3{0.0f, 0.4f, 0.0f}, p + vec3{0.0f, 1.4f, 0.0f}, 0.4f, colors::blue);
  }
  // Navmesh và đường đi, để xem engine thấy chỗ nào đi được.
  navmesh3d_draw_debug(ctx, nav);
  for (usize i = 0; i + 1 < preview.size(); i++)
    gizmo_line3d(ctx, preview[i] + vec3{0.0f, 0.1f, 0.0f}, preview[i + 1] + vec3{0.0f, 0.1f, 0.0f}, colors::yellow);
  end_3d(ctx);
}
 
void setup(context &ctx) {
  ecs_register(ctx, phase_startup, load, "load");
  ecs_register(ctx, phase_update, update, "update");
  ecs_register(ctx, phase_render, render, "render");
}
} // namespace
 
mod_desc crowd_module() { return {.name = "crowd", .setup = setup}; }

Vùng, bộ lọc, hai cỡ tác tử và một vật cản di động: lính gác đi qua cửa, tránh đầm lầy, đi đường cái; con quái to có navmesh riêng; phím K lấy chìa khóa của lính gác.

#include <njin.h>
 
namespace {
using namespace njin;
 
// Số vùng do game đặt nghĩa; 0 là mặt đất thường.
constexpr u8 area_road = 1;
constexpr u8 area_swamp = 2;
constexpr u8 area_door = 3;
 
// Bộ lọc 0: dân làng (tránh đầm lầy, đi đường cái). Bộ lọc 1: lính gác có chìa
// khóa, giống dân làng nhưng đi được qua cửa. Bộ lọc 0 cấm cửa.
constexpr i32 villager = 0;
constexpr i32 guard = 1;
 
navmesh3d_handle small_nav, big_nav;
nav3d_agent_handle walker, troll;
i32 crate = 0; // vật cản: một cái thùng bị đẩy qua lại
 
void load(context &ctx) {
  small_nav = navmesh3d_create(ctx, {.agent_radius = 0.4f});
  navmesh3d_add_box(ctx, small_nav, {0.0f, -0.5f, 0.0f}, {40.0f, 1.0f, 30.0f});
  navmesh3d_add_box(ctx, small_nav, {6.0f, 1.5f, -6.0f}, {0.5f, 3.0f, 10.0f}); // tường có ô cửa ở z = -0.5
  navmesh3d_add_box(ctx, small_nav, {6.0f, 1.5f, 6.0f}, {0.5f, 3.0f, 12.0f});
  // Đánh dấu vùng: đầm lầy giữa bản đồ, đường cái men theo phía bắc, ô cửa.
  navmesh3d_add_area(ctx, small_nav, {-4.0f, 0.0f, 0.0f}, {10.0f, 4.0f, 14.0f}, 0.0f, area_swamp);
  navmesh3d_add_area(ctx, small_nav, {-4.0f, 0.0f, 9.0f}, {30.0f, 4.0f, 3.0f}, 0.0f, area_road);
  navmesh3d_add_area(ctx, small_nav, {6.0f, 0.0f, -0.5f}, {1.0f, 4.0f, 1.0f}, 0.0f, area_door);
 
  // Chi phí: một mét đầm lầy tốn như tám mét đường thường, đường cái rẻ hơn.
  nav3d_filter f{};
  f.cost[area_swamp] = 8.0f;
  f.cost[area_road] = 0.6f;
  f.excluded = 1u << area_door; // dân làng không có chìa khóa
  navmesh3d_set_filter(ctx, small_nav, villager, f);
  f.excluded = 0;
  navmesh3d_set_filter(ctx, small_nav, guard, f);
 
  // Quái to cần navmesh riêng: cùng hình học, vùng và bộ lọc, chừa tường xa hơn.
  big_nav = navmesh3d_clone(ctx, small_nav, {.agent_radius = 1.2f, .agent_height = 3.0f});
  navmesh3d_build(ctx, small_nav);
  navmesh3d_build(ctx, big_nav);
 
  walker = nav3d_agent_add(ctx, small_nav, {.position = {-14.0f, 0.0f, 0.0f}, .filter = guard});
  troll = nav3d_agent_add(ctx, big_nav, {.position = {-14.0f, 0.0f, -4.0f}, .radius = 1.2f, .max_speed = 2.5f});
  nav3d_agent_set_target(ctx, walker, {14.0f, 0.0f, 0.0f});
  nav3d_agent_set_target(ctx, troll, {14.0f, 0.0f, -4.0f});
 
  // Vật cản di động: navmesh tự dựng lại các ô vuông nó chạm vào, vài ô mỗi frame.
  crate = navmesh3d_add_obstacle(ctx, small_nav, {.position = {0.0f, 1.0f, 9.0f}, .size = {2.0f, 2.0f, 2.0f}});
}
 
void update(context &ctx) {
  // Mỗi 3 giây thùng bị đẩy sang bên kia đường cái; tác tử tìm đường vòng qua nó.
  // Dời vật cản mỗi frame thì mỗi frame phải dựng lại vài ô vuông: dời khi nó thật
  // sự đổi chỗ.
  static i32 side = 0;
  const i32 now = (i32)(elapsed(ctx) / 3.0f) % 2;
  if (now != side) {
    side = now;
    navmesh3d_move_obstacle(ctx, small_nav, crate, {0.0f, 1.0f, side == 0 ? 9.0f : 7.0f});
  }
  // Phím K: lính gác mất chìa khóa, tìm đường như dân làng và không qua cửa được nữa.
  if (key_pressed(ctx, key_k))
    nav3d_agent_set_filter(ctx, walker, villager);
}
 
void render(context &ctx) {
  begin_3d(ctx, camera3d{.position = {0.0f, 30.0f, 22.0f}, .target = {0.0f, 0.0f, 0.0f}, .fovy = 50.0f});
  navmesh3d_draw_debug(ctx, small_nav);
  draw_sphere3d(ctx, nav3d_agent_position(ctx, walker) + vec3{0.0f, 0.5f, 0.0f}, 0.4f, colors::yellow);
  draw_sphere3d(ctx, nav3d_agent_position(ctx, troll) + vec3{0.0f, 1.2f, 0.0f}, 1.2f, colors::green);
  end_3d(ctx);
}
 
void setup(context &ctx) {
  ecs_register(ctx, phase_startup, load, "load");
  ecs_register(ctx, phase_update, update, "update");
  ecs_register(ctx, phase_render, render, "render");
}
} // namespace
 
mod_desc areas_module() { return {.name = "areas", .setup = setup}; }

Từ Lua

Script (Script Lua) gọi được njin.nav3d_path(navmesh, from, to) (bảng các điểm, hay nil), njin.nav3d_set_target(agent, target), njin.nav3d_stop, njin.nav3d_position, njin.nav3d_velocity và njin.nav3d_arrived, với navmesh và agent là số id của handle mà phía C++ đưa sang (ví dụ bằng script_set_global()). Vùng và vật cản:

• njin.nav3d_path(navmesh, from, to, filter): tìm đường theo bộ lọc số filter.
• njin.nav3d_set_filter(navmesh, index, {cost = {[2] = 8}, exclude = {3}}), njin.nav3d_agent_filter(agent, index).
• njin.nav3d_add_area(navmesh, center, size, yaw, area) trả về số của khối; njin.nav3d_remove_area(navmesh, id).
• njin.nav3d_add_obstacle(navmesh, {position = ..., size = ..., yaw = 0, radius = 0}) trả về số của vật cản; njin.nav3d_move_obstacle(navmesh, id, position, yaw), njin.nav3d_remove_obstacle(navmesh, id).

Giới hạn

• Vật cản cắt navmesh bằng cách dựng lại cả ô vuông nó chạm vào (vài mili giây mỗi ô 8 m), không phải bằng tile cache của Detour: hợp với thùng, xe đậu, cửa; không hợp với hàng chục vật cản cùng chạy mỗi frame.
• Các tác tử chỉ né nhau trên cùng một navmesh, nên tác tử to (navmesh to) và tác tử nhỏ không né nhau.
• Vùng chỉ có 16 số (0 đến 15).