chỉ đạo một khối lượng kẻ thù cùng một lúc

Question

Tôi đang làm việc trên một trò chơi 2ngày đơn giản, nơi nhiều kẻ thù liên tục sinh ra và đuổi theo người chơi hoặc người chơi trong python + pygame. Một vấn đề tôi gặp phải, và một trong nhiều người đã lập trình loại trò chơi này đã chạy vào là kẻ thù hội tụ rất nhanh. Tôi đã thực hiện một giải pháp tạm thời cho vấn đề này với một chức năng đẩy bất kỳ hai kẻ thù một cách ngẫu nhiên nếu chúng quá gần nhau. Điều này làm việc tốt nhưng là về một thuật toán O (n^2) được chạy mỗi khung và ở kẻ thù cao chương trình bắt đầu chậm lại.

Khi chương trình của tôi chạy với chức năng này, kẻ thù dường như tạo thành đối tượng tròn tôi đặt biệt danh là một "cục bô". Các cụm có vẻ thường ecliptic nhưng thực sự có thể phức tạp hơn (không đối xứng) bởi vì khi người chơi di chuyển kẻ thù đang được kéo theo các hướng khác nhau. Tôi thích cách mà cụm này hoạt động, tuy nhiên tôi tự hỏi liệu có cách nào hiệu quả hơn để tính toán nó hay không. Hiện tại, mỗi kẻ thù trong các khối (thường là> 100) là lần đầu tiên di chuyển theo hướng của người chơi, và sau đó đẩy ra xa nhau. Nếu có thay vào đó là một cách để tính toán con số mà các khối tạo ra, và làm thế nào nó di chuyển nó sẽ tiết kiệm rất nhiều tính toán.

Tôi không chắc chắn cách tiếp cận vấn đề. Nó có thể được tính toán nơi biên giới của con số di chuyển, và sau đó mở rộng nó để đảm bảo khu vực vẫn giữ nguyên.

Ngoài hai chức năng của tôi hiện đang được sử dụng để di chuyển kẻ thù:

def moveEnemy(enemy, player, speed): 
    a = player.left-enemy.left 
    b = player.top-enemy.top 
    r = speed/math.hypot(a,b) 
    return enemy.move(r*a, r*b) 

def clump(enemys): 
    for p in range(len(enemys)): 
     for q in range(len(enemys)-p-1): 
      a = enemys[p] 
      b = enemys[p+q+1] 
      if abs(a.left-b.left)+abs(a.top-b.top)<CLUMP: 
       xChange = (random.random()-.5)*CLUMP 
       yChange = ((CLUMP/2)**2-xChange**2)**.5 
       enemys[p] = enemys[p].move(int(xChange+.5), int(yChange + .5)) 
       enemys[p+q+1] = enemys[p+q+1].move(-int(xChange+.5),-int(yChange+.5)) 
    return enemys 

Chỉnh sửa: một số ảnh chụp màn hình về cách thức lùm trông: http://imageshack.us/photo/my-images/651/elip.png/ http://imageshack.us/photo/my-images/ 832/newfni.png/

http://imageshack.us/photo/my-images/836/gamewk.png/

Các lùm vẻ là chủ yếu là một đối tượng tròn chỉ kéo dài (như một nhật thực nhưng có thể kéo dài trong nhiều hướng), tuy nhiên nó curre ntly có cạnh thẳng do kẻ thù hình chữ nhật.

Answer 1

Có một số cách để thực hiện việc này, tùy thuộc vào trò chơi của bạn. Dưới đây là một số ý tưởng để cải thiện hiệu suất:

1. Cho phép chồng chéo.
2. Giảm việc kiểm tra khoảng cách của bạn được thực hiện sau một số khung cố định.
3. Cải thiện công thức kiểm tra khoảng cách của bạn. Nếu bạn đang sử dụng công thức khoảng cách tiêu chuẩn, điều này có thể được tối ưu hóa theo nhiều cách. Đối với một, loại bỏ căn bậc hai. Độ chính xác không quan trọng, chỉ khoảng cách tương đối.
4. Mỗi đơn vị có thể theo dõi danh sách các đơn vị lân cận. Chỉ thực hiện các phép tính của bạn giữa các đơn vị trong danh sách đó. Thường xuyên, cập nhật danh sách đó bằng cách kiểm tra tất cả các đơn vị.
5. Tùy thuộc vào cách thiết lập trò chơi của bạn, bạn có thể chia nhỏ trường đó thành các khu vực, chẳng hạn như phần tư hoặc ô. Các đơn vị chỉ được thử nghiệm với các đơn vị khác trong ô đó.

CHỈNH SỬA: Khi đơn vị đến gần mục tiêu, nó có thể không hoạt động chính xác. Tôi sẽ đề nghị thay vì đưa họ về nhà từ mục tiêu chính xác từ xa, rằng họ thực sự tìm kiếm một mục tiêu gần đó ngẫu nhiên. Giống như một bù đắp từ mục tiêu thực sự của họ.

Tôi chắc chắn có nhiều cách khác để cải thiện điều này, nó hoàn toàn mở sau khi tất cả. Tôi cũng nên chỉ ra Boids và flocking có thể được quan tâm.

Answer 2

Bạn có thể xác định một cụm như một đối tượng riêng biệt với một số lượng cố định "khe" không gian cho mỗi đơn vị kẻ thù trong cụm. Mỗi khe sẽ có một tập hợp các tọa độ liên quan đến trung tâm nhóm và sẽ là trống hoặc sẽ giữ một tham chiếu đến một đơn vị.

Một đơn vị mới cố gắng gia nhập khối sẽ di chuyển về phía khe trống bên trong nhất, và một khi nó đến đó, nó sẽ "ở lại hình thành", vị trí của nó luôn là vị trí của khe mà nó chiếm đóng. Các cục sẽ có bán kính lớn hơn nhiều so với một đơn vị duy nhất, sẽ điều chỉnh vị trí để tránh chồng chéo các khối khác hoặc các đơn vị lỏng lẻo không cố gắng kết hợp cụm, v.v.

Tại một số điểm, bạn cần đối phó với các tương tác cho các đơn vị cá nhân trong các khối, mặc dù, vì vậy tôi không chắc chắn nó đáng giá. Tôi nghĩ rằng gợi ý của Austin Henley về việc tách lĩnh vực này thành các tế bào/vùng và chỉ thử nghiệm đối với các đơn vị trong các tế bào lân cận là cách tiếp cận thực tế nhất.

Answer 3

Tôi nghĩ bạn đang tìm kiếm flocking.

Answer 4

Giới thiệu tốt nhất để đổ/chuyển động hành vi chỉ đạo: http://www.red3d.com/cwr/steer/. Xem giấy đính kèm red3d paper. Và số liên quan OpenSteer