Đường dẫn trên bản đồ lớn

Question

Tôi đang tạo trò chơi với 10.000 bản đồ 10.000.
Tôi muốn người dùng có thể đặt vị trí và nhờ đó máy tính tìm thấy đường đi tốt nhất ngay lập tức.
Tuy nhiên, vì bản đồ là 10.000 x 10.000, có 100.000.000 nút và tìm đường dẫn này thông qua một phương pháp thông thường như A * hoặc Dijkstra sẽ yêu cầu bộ nhớ lớn và thời gian dài.
Vì vậy, câu hỏi của tôi là: Làm thế nào tôi có thể tìm thấy con đường tốt nhất?
Thuật toán tôi đang xem xét sẽ chia thế giới thành 100 phần, mỗi phần có 1.000.000 nút. Mỗi phần sau đó sẽ được chia thành 100 phần phụ. Điều này sẽ được lặp lại cho đến khi mỗi phần con chứa 100 nút. Sau đó, thuật toán sẽ tìm đường dẫn tốt nhất của các phần, sau đó là các phần con, sau đó là các phần phụ cho đến khi tìm thấy tập hợp các nút tốt nhất. Điều này có hiệu quả và có cách nào tốt hơn không?
Tôi cũng đang xem xét tìm kiếm điểm nhảy, nhưng tôi không biết điều đó, và nó sẽ là một nỗi đau để tìm hiểu chỉ để thấy rằng nó không thể làm điều đó.

Chỉnh sửa: Tôi đã cố gắng thêm A *. Tuy nhiên, nó mất khoảng 5 giây để chạy, đó là khoảng 4 giây dài hơn lý tưởng.

Answer 1

Vì bản đồ là 10.000 x 10.000 nên số nút là 100.000.000. Sử dụng việc triển khai A * đơn giản sẽ không thực tế và chắc chắn sẽ không làm cho trò chơi có thể mở rộng được trong bản đồ hóa.

tôi sẽ khuyên bạn nên sử dụng các giải pháp sau đây, mà chủ yếu là những gì bạn đang nghĩ:

HPA * (Hierarchical Đường dẫn A *). Phương pháp này tạo ra các hệ thống phân cấp khác nhau của bản đồ. Bạn có thể tự động hóa quy trình bằng cách nói rằng mỗi khối 100x100 pixel là một vùng. Sau đó, đối với mỗi khối, chúng ta cần phải tìm các khối liền kề và nơi các mục nhập và thoát cho mỗi khối là. Nếu kết nối giữa hai khối nhiều hơn một nút thì chúng tôi sử dụng hai nút để biểu thị sự cố. Hình ảnh này giải thích biểu đồ mới mà chúng tôi đang cố gắng xây dựng. (Đen = chướng ngại vật và màu xám đang kết nối các nút giữa các khối).

Phương pháp này cung cấp kết quả tốt như có thể được nhìn thấy từ một thi sử dụng bản đồ từ các trò chơi Baldur Cổng với mỗi khối là 10x10.

Để biết thêm thông tin đọc bài viết này từ Nathan Sturtevant (ông là một trong những thành công nhất nghiên cứu con đường tìm hiểu khi nói đến trò chơi). https://skatgame.net/mburo/ps/path.pdf

Để được giải thích về HPA, vui lòng kiểm tra bài giảng này về Sturtevant (phút 43:50 cho HPA). https://www.youtube.com/watch?v=BVd5f66U4Rw

Ngoài ra, nếu bạn muốn xem HPA * trong tầm kiểm soát hành động video này mà Sturtevant thực hiện: https://www.youtube.com/watch?v=l7YQ5_Nbifo

Answer 2

Sự hiểu biết ban đầu của tôi về báo cáo sự cố như sau. Có các vị trí đầu cuối được xác định trước trên bản đồ. Người dùng chọn một vị trí trên bản đồ và tìm đường dẫn ngắn nhất/ngắn nhất tới vị trí gần nhất trong các vị trí đó.

Nếu hiểu biết của tôi là chính xác, thì bạn có thể tính toán trước các đường đi ngắn nhất cho tất cả các vị trí trên bản đồ của bạn thông qua một ứng dụng duy nhất của thuật toán BFS. Bạn có thể lưu trữ hiệu quả thông tin đó chỉ bằng 2 bit cho mỗi nút (giá trị được kết hợp với mỗi nút sẽ cho biết bạn phải di chuyển hướng nào từ nút đó để ở trên đường đi ngắn nhất).

Tuy nhiên, như tobias_k đã nhận xét, sự cố có thể được xác định khác nhau - người chơi chọn vị trí tùy ý trên bản đồ và tìm đường đi tốt nhất từ ​​vị trí hiện tại đến vị trí đó. Cách tiếp cận mô tả trước đây một lần nữa có thể được sử dụng, với điều kiện

1. người chơi không di chuyển xung quanh bản đồ quá nhanh và
2. một số thiếu chính xác có thể được dung thứ.

Sau đó, thuật toán đã mô tả được thực hiện để tìm đường đi ngắn nhất từ ​​bất kỳ vị trí nào trên bản đồ đến một chu vi nhỏ tập trung tại vị trí hiện tại của người chơi. Sau đó, trong một khoảng thời gian ngắn dữ liệu có thể được sử dụng để nhanh chóng định tuyến đường đi ngắn nhất tới bất kỳ vị trí nào trên bản đồ. Khi người chơi, trong khi di chuyển, quá gần ranh giới của vòng tròn đó, thuật toán được thực thi trước cho vị trí mới của người chơi.

Điểm bất lợi của phương pháp này là nó tiêu thụ rất nhiều tài nguyên CPU. Ưu điểm là tính đơn giản của nó.

Answer 3

Điều này sẽ lâu hơn một chút so với những gì phù hợp với nhận xét, do đó, do đó có câu trả lời.

Thiết lập của bạn yêu cầu làm rõ. 10,000x10,000 là tất cả tốt, nhưng tuyên bố này không phải là:

từ bản đồ là 10.000 bằng 10.000, có 100.000.000 nút

Tại sao sẽ có 1 nút cho mỗi đơn vị tọa độ hệ thống?Đây không phải là cách hoạt động của đường dẫn nút, thay vào đó các nút được cho là thưa thớt hơn, và do sự tồn tại của chúng mô tả các điểm riêng lẻ (thưa thớt) dọc theo đường dẫn. Giữa các điểm nút, đối tượng xử lý chuyển động bằng các phương tiện khác. Một hệ thống đường dẫn có thể, trong trường hợp xấu nhất (nếu không có trở ngại nào), có 100.000.000 điểm, nhưng khi Q đề cập đến các nút , tôi giả định đây là về đường dẫn nút.

100.000.000 nút

100.000.000 nút là 381 MB bộ nhớ nếu int32 và 763 mb nếu float64. Ngoài ra, có các nút kết nối. Tôi không có ý tưởng làm thế nào chúng sẽ được thiết lập trong trường hợp của bạn, nhưng mỗi kết nối đòi hỏi 2 số nguyên, nói 2 byte mỗi. I E. nếu có nhiều kết nối như các nút, cần thêm 381 mb nữa. Tất cả trong tất cả, chúng tôi kết thúc với dữ liệu đồ thị gần hơn một terabyte, và tôi tuyên bố rằng chắc chắn rằng một cái gì đó là sai sau đó.

Cách giải quyết vấn đề, miễn là chúng tôi vẫn có biểu đồ nút lớn/khu vực rộng lớn? Tôi có lẽ sẽ đơn giản hóa, bằng cách tạo phần tư lớn hơn (như bạn đã đề cập). Tuy nhiên, mỗi góc phần tư sẽ giữ các nút chỉ dọc theo 4 cạnh - tất cả các nút bên trong góc phần tư sẽ được thay thế bằng các đường thẳng. Bằng cách này, người ta sẽ giải quyết các điểm nhập cảnh/xuất cảnh cho mỗi góc phần tư. Đây sẽ là một biểu đồ nút riêng biệt, để tính toán sơ bộ. Sau đó, bên trong góc phần tư, người ta sẽ luôn tải biểu đồ nút bên trong cho góc phần tư đó chỉ tại thời điểm. Ofc sẽ có một số loại lỗi được phát hiện, nhưng hey, đó là cuộc sống thực, phải không? Nếu đây là hành vi của con người, thì nó không phải lúc nào cũng được tối ưu hóa hoàn toàn.

Tính toán trước, bộ nhớ cache, tốc độ, dữ liệu nhỏ là từ khóa trong mã hóa trò chơi.

Answer 4

Vì vậy, mặc dù có thể có n^4 đường đi ngắn nhất trên một hình vuông n theo n bản đồ. lưu trữ tất cả các đường dẫn không nhất thiết yêu cầu không gian O(n^4). Ý tưởng là đưa ra hai vị trí mục tiêu khác nhau trên bản đồ và cây con đường ngắn nhất của chúng, hơn hai điểm gần hơn trên bản đồ, các yếu tố phổ biến hơn sẽ là cây con đường ngắn nhất của chúng. Điều này đặc biệt đúng khi sử dụng bản đồ phẳng như lưới với các chướng ngại vật.

Vì vậy, ý tưởng là chỉ lưu trữ một số cây con đường ngắn nhất hoàn chỉnh cho một tập hợp nhỏ các vị trí mục tiêu (thậm chí có thể chỉ là một vị trí mục tiêu). Đối với phần còn lại của các vị trí đích chỉ có sự khác biệt của cây đường đi ngắn nhất của nó với một trong những cây con đường ngắn nhất được lưu trữ trước đó được lưu trữ. Sau đó, thuật toán để tìm đường đi ngắn nhất từ ​​một vị trí đến đích là tải một cây đường dẫn ngắn nhất được lưu trữ đầy đủ và sau đó áp dụng một số khác biệt cho nó để có được cây đường đi ngắn nhất của vị trí mục tiêu. Quay lại đầu trang Sau đó, chỉ vị trí của người chơi hiện tại cần được tìm thấy trên cây con đường ngắn nhất có độ phức tạp là O(n^2).

Tôi không có bất kỳ sự thật khó khăn nào về dung lượng lưu trữ cần thiết để lưu trữ các cây con đường ngắn nhất và các khác biệt của chúng, nhưng điều này có thể nằm trong khoảng O(n^2 log(n^2)). Tải một và appyling các diffs chỉ có thể có độ phức tạp thời gian của O(n^2).

Cây đường đi ngắn nhất cho vị trí mục tiêu thể hiện tất cả đường đi ngắn nhất từ ​​mọi vị trí trên bản đồ đến vị trí mục tiêu.

Giải pháp này cũng có thể giữ cho cây con đường ngắn nhất được sử dụng trong bộ nhớ và áp dụng các khác biệt khi cần thiết để có được cây con đường ngắn nhất mới sử dụng.Sau đó, sự phức tạp của việc cây con đường ngắn nhất không bị ràng buộc bởi kích thước của bản đồ, mà chỉ bằng kích thước của các khác biệt được áp dụng. Kịch bản này thực sự có thể hoạt động tốt cho các trò chơi như Sacred hoặc Diablo gốc.

Answer 5

Nếu bản đồ của bạn có trọng lượng đồng phục (trừ các chướng ngại vật dĩ nhiên), bạn có thể có hiệu suất tốt hơn với hoặc:

1. Thuật toán xử lý trước ô trống thành một biểu đồ, thu hẹp khoảng trống lớn thành một nút. Các lưới dẫn hướng phá vỡ khu vực di chuyển qua các đa giác lồi mà mỗi điểm có thể được di chuyển trong một bước. L1 path finder nhóm các chướng ngại vật lại với nhau, giảm chúng thành biểu đồ hiển thị để tính toán đường đi qua đó.

2. Thuật toán không mở rộng mọi nút. Jump-point search tận dụng sự đối xứng giữa các đường khác nhau, chỉ mở rộng các nút liền kề với các chướng ngại vật, trong khi A * sẽ mở rộng mọi nút dọc theo đường đi ngắn nhất.

Answer 6

Khái niệm cấp cao có thể là tìm điểm bắt đầu và điểm kết thúc (0,0) và điểm (10000, 10000) - và đoán sơ bộ đường đi từ đầu đến cuối cùng (trong trường hợp này nó sẽ chạy theo đường chéo toàn bộ con đường lên và sang phải) Sau đó bắt đầu kiểm tra để xem liệu nó có thể thành công đạt được điều đó (nếu có chướng ngại vật trên con đường đó hay không). Nếu có sau đó lập trình chọn đường dẫn tương tự, hoặc luân phiên tìm đường dẫn không thành công và bắt đầu ở đó và cố gắng lặp lại cho đến khi nó hoạt động, nó có thể không nhanh nhất 100% nhưng bạn sẽ nhận được kết quả tốt hơn nhiều so với tìm mọi cách có thể, sau đó suy ra con đường ngắn nhất từ ​​đó.

Thực hiện

• Phương pháp để tìm đầu con đường ngắn nhất
• Run để xem nếu nó hoạt động
  • Nếu nó không thành công sau đó, hoặc thử con đường tương tự hoặc bắt đầu từ thất bại

Answer 7

1. Đảm bảo rằng tất cả dữ liệu đồ thị nằm trong bộ nhớ
2. Sử dụng Dijkstra hai chiều - giả sử bạn có nhiều lõi
3. Xem xét sử dụng phân cấp co, điều này sẽ cải thiện hiệu suất.
4. Tính toán trước mọi thứ bạn có thể, chẳng hạn như trọng số đường dẫn.