Tìm đường dựa trên lưới

Trong hướng dẫn này, chúng ta sẽ tạo một mô phỏng tìm đường dựa trên một lưới mảng 2 chiều. Điều này sẽ giúp chúng ta có ý tưởng cơ bản trong việc tạo các hoạt động tìm đường cho trò chơi của chúng ta. Chúng ta sẽ hình dung lưới sử dụng các đối tượng hình vuông trống như các ô và một đối tượng hình tròn như hình đại diện của chúng ta, đối tượng này có thể di chuyển trên khu vực lưới đó theo lệnh của chúng ta.

I. Thiết lập các đối tượng

Chúng ta chỉ sử dụng bốn đối tượng trong dự án của mình. Hình đại diện màu xanh của chúng ta, một ô màu xanh, một chướng ngại vật màu trắng và nhãn lưới để thiết lập và hình dung lưới của chúng ta.

Hình đại diện

Hình đại diện của chúng ta là một đối tượng trống có tỷ lệ x và y là 50%. Thiết lập va chạm của nó thành hình tròn để nó trông giống như hình bên dưới. Đối tượng này sẽ có ba thuộc tính được định sẵn: trên ô, ô trước đó và ô mục tiêu. Đặt giá trị mặc định của các thuộc tính này thành số không để chúng không có giá trị null khi chúng ta cố gắng lấy chúng sau này.

Đối tượng ô

Tạo một đối tượng trống khác được sử dụng để hình dung các ô trong lưới của chúng ta. Tỷ lệ của nó cũng là 50% và chỉ có một thuộc tính được định sẵn: trên ô. Cũng đặt giá trị này thành số không.

Đối tượng chướng ngại vật

Tạo một đối tượng trống khác sẽ đóng vai trò là chướng ngại vật trong lưới của chúng ta. Đây là một đối tượng trống màu trắng có tỷ lệ là 40%. Hình đại diện của chúng ta sẽ không thể đi vào ô có chướng ngại vật ở trên.

Nhãn lưới

Đây chỉ là một nhãn có các hành vi cho phép thiết lập và hình dung lưới của chúng ta. Nó có các thuộc tính được định sẵn: bắt đầu x với giá trị 4 và bắt đầu y với giá trị 3. Những giá trị này là các số bù sẽ được sử dụng làm tham chiếu khi sinh các ô của chúng ta để vị trí của lưới được gọn gàng ở giữa.

Các thuộc tính được định sẵn của hình đại diện / ô:

Chúng ta định nghĩa một ô ở đây là một mảng 2 kích thước mà sẽ có giá trị x và y dựa trên lưới của chúng ta.

• trên ô - đây là giá trị ô mà đối tượng của chúng ta hiện đang đứng trên lưới của chúng ta
• ô trước đó - ô mà hình đại diện của chúng ta đã từng đi qua trước đây
• ô mục tiêu - ô mà hình đại diện của chúng ta sẽ di chuyển đến

II. Thiết lập lưới

Bên trong nhãn lưới là nơi chúng ta sẽ định nghĩa mảng 2D của chúng ta và việc sinh ra lưới. Có 2 điểm chính trong đối tượng này: thiết lập mảng và hình dung mảng. Hãy thực hiện trước gói thiết lập mảng.

Thiết lập mảng - gói

Đầu tiên là tạo một mảng trống có tên "Grid". Mảng này sẽ chứa mảng 2 chiều của chúng ta. Chúng ta sẽ có một hộp chứa có tên là "x row count" với giá trị là 24 và một mảng trống khác có tên là "y row" với 18 giá trị trống.

Hành vi đầu tiên trong gói của chúng ta là một vòng lặp với số lần lặp lại là "x row count". Đối với mỗi bước của vòng lặp này, chúng ta sẽ thêm một "y row" trống vào mảng "Grid". Điều này sẽ tạo ra một mảng bên trong một mảng với kích thước 24x18.

Chú ý rằng chúng ta đã kết nối một nhận xét không hoạt động ở đầu gói của chúng ta để ngăn chặn việc tự động thực thi hành vi gốc này. Hành vi gốc là một hành vi không được kích hoạt dựa trên bất kỳ sự kiện nào và được đặt mở trong giao diện.

Hình dung lưới - gói

Điều chính mà chúng ta sẽ làm ở đây là duyệt qua từng giá trị của mảng "Grid" và sinh một đối tượng ô. Chúng ta cũng sẽ thêm một điều kiện vào vòng lặp của mình cho phép sinh ra một chướng ngại vật trắng trên đỉnh đối tượng ô.

Đầu tiên là lấy số lượng mảng của mảng "y row", giá trị thuộc tính "start x" của đối tượng này và "start y".

Tạo một vòng lặp có số lần lặp lại là "x row count" và cho mỗi bước của vòng lặp này, chúng ta sẽ thêm giá trị chỉ mục của vòng lặp đó và giá trị thuộc tính "start x". Điều này sẽ tạo ra vị trí x tuyệt đối mà chúng ta sẽ sử dụng để định vị các ô được sinh ra của mình sau này. Tiếp theo là vòng lặp "y row" có số lần lặp lại là "y row count". Đối với mỗi bước của vòng lặp này, chúng ta sẽ thêm giá trị chỉ mục của vòng lặp đó và giá trị thuộc tính "start y", điều này sẽ tạo ra vị trí y tuyệt đối.

Sau khi thêm các giá trị dưới vòng lặp "y row" là để sinh đối tượng màu xanh. Đặt số đối tượng sống của đối tượng đó thành 999 vì chúng ta sẽ cần rất nhiều chúng cho lưới của mình, và cũng với thời gian là 0. Sau đó di chuyển đối tượng sinh ra đó đến điểm x với giá trị từ vòng lặp x "thêm giá trị", và điểm y với giá trị từ vòng lặp y "thêm giá trị".

Tiếp theo là thêm một mảng với 2 giá trị trống có tên là "On tile" mà chúng ta sẽ chỉ sử dụng như một dấu chỗ cho mảng. Sau khi di chuyển đối tượng ô, là để sửa đổi mảng "On tile" bằng cách thay thế giá trị của nó ở chỉ mục 0 bằng giá trị của vòng lặp "x row". Sau đó, thêm một sửa đổi mảng khác mà thay thế giá trị ở chỉ mục 1 bằng "chỉ số y row". Đây là tọa độ x và y của lưới mà đối tượng sẽ có thuộc tính "on tile".

Bây giờ, thiết lập thuộc tính của đối tượng sinh ra với một khóa động, "on tile", và với giá trị là "On tile - array".

Vẫn là dưới vòng lặp y row, là điều kiện sinh ra chướng ngại vật màu trắng. Chúng ta sẽ có 2 trong số 5 cơ hội để thực hiện gói này mà sẽ thêm sự ngẫu nhiên vào lưới của chúng ta. Sau đó, chúng ta sẽ đánh dấu một giá trị là 1 cho tọa độ x và y trong mảng "Grid" của chúng ta, cho chúng ta biết rằng tọa độ đó đã có một chướng ngại vật được sinh ra.

Đầu tiên là có một số ngẫu nhiên từ 1 đến 5. Nếu số đó nhỏ hơn hoặc bằng 2, chúng ta sẽ sinh ra chướng ngại vật. Đặt số đối tượng sống của nó là 999 và di chuyển đối tượng đó đến cùng một điểm như ô màu xanh mà chúng ta đã sinh ra trước đó, và cũng với thời gian là 0.

Tiếp theo là lưu trữ thông tin rằng tọa độ này đã được chiếm giữ bởi một chướng ngại vật, nếu nó đã được sinh ra. Chúng ta thực hiện việc này bằng cách đánh dấu tọa độ đó với giá trị là 1. Đầu tiên là lấy giá trị tại chỉ mục "x row" của mảng "Grid". Giá trị này sẽ cung cấp cho chúng ta một mảng của một "y row". Chúng ta sẽ sửa đổi "y row" này bằng cách thay thế giá trị của nó ở chỉ mục "y row" bằng giá trị 1, đó là giá trị đã được đánh dấu. Bởi vì việc sửa đổi giá trị này chỉ áp dụng cho giá trị đó, và không cho "Grid itself", chúng ta vẫn cần phải sửa đổi mảng "Grid". Thay thế giá trị tại chỉ mục "x row" của mảng "Grid" bằng giá trị "modify y row - array".

Trong khi chơi, nó phải dẫn đến hình dạng như thế này.

III. Nhấn vào ô

Để có thể tương tác với lưới chính nó, chúng ta sẽ cần một hành vi gói bất cứ khi nào chúng ta nhấn một ô màu xanh. Nhấn đầu tiên sẽ dẫn đến sự xuất hiện của hình đại diện của chúng ta trong lưới, và bất kỳ lần nhấn tiếp theo sau sự kiện đó sẽ bắt đầu việc tìm đường của nó.

Bên trong đối tượng màu xanh là một gói hành vi có 3 điểm chính: làm lại ô trước đó của hình đại diện của chúng ta, thiết lập ô của nó / thiết lập ô mục tiêu của nó, sau đó thiết lập một hoạt hình màu để hình dung sự kiện chạm vào màn hình.

Đầu tiên là lấy thuộc tính "on tile" của đối tượng ô. Đặt thuộc tính "ô trước" của hình đại diện của chúng ta thành 0. Hình đại diện của chúng ta sẽ tránh không quay trở lại một "ô trước" mà chúng ta đã đặt, đó là lý do tại sao chúng ta phải thiết lập lại "ô trước" mỗi khi nhấn vào ô.

Tiếp theo là lấy thuộc tính "on tile" của hình đại diện của chúng ta. Điều kiện đầu tiên là liệu giá trị "on tile" có bằng số không. Điều này có nghĩa là nếu hình đại diện chưa xuất hiện thì điều này sẽ dẫn đến đúng. Nếu đúng, chúng ta sẽ thiết lập thuộc tính "on tile" của nó với giá trị của thuộc tính "on tile" của đối tượng ô. Sau đó di chuyển vị trí của hình đại diện bằng cách lấy vị trí của đối tượng ô, chỉ chỉ định giá trị x và y của nó đến điểm đó với khoảng thời gian là 0.

Nếu giá trị "on tile" không bằng 0. chúng ta sẽ thiết lập thuộc tính ô mục tiêu của hình đại diện của chúng ta với giá trị thuộc tính "on tile" của đối tượng ô. Điều này có nghĩa là hình đại diện của chúng ta đã có mặt trong lưới của chúng ta, và sau đó, chúng ta có thể thực hiện gói hành vi "tìm đường". Chúng ta vẫn chưa có hành vi này, nhưng chúng ta sẽ sửa chữa điều này sau khi làm phần sau của hướng dẫn này cho gói "tìm đường".

Bây giờ mà chúng ta đã thiết lập đúng hình đại diện của mình với lưới của chúng ta, chúng ta chỉ cần hình dung sự kiện nhấn này. Đầu tiên hãy có một hành vi gốc "lấy màu" để lấy màu gốc của nó. Sau đó, sau sự kiện nhấn, chúng ta sẽ thiết lập màu của đối tượng ô thành màu đen với khoảng thời gian là 0, sau đó thiết lập lại màu của nó về giá trị gốc với khoảng thời gian là 0,2.

Nhấn vào một ô màu xanh sẽ dẫn đến điều này.

IV. Thực hiện gói tìm đường

Đối với phần cuối cùng của hướng dẫn này, chúng ta sẽ thực hiện thuật toán cho phép chúng ta tìm ô gần nhất mà hình đại diện của chúng ta có thể lấy để đến đích của nó. Gói này sẽ được thực hiện liên tục cho mỗi bước ô mà hình đại diện của chúng ta di chuyển trên lưới của chúng ta.

Chúng ta sẽ thiết lập thuật toán bên trong đối tượng hình đại diện của chúng ta và nó sẽ có ba điểm chính: tìm các ô kề, tìm ô kề gần nhất và di chuyển đến ô kề đó.

Tìm các ô kề

Trong phần này, chúng ta sẽ thu thập tất cả các ô kề mà hình đại diện của chúng ta có thể đi qua. Chúng ta sẽ kiểm tra bốn ô kề theo hướng và xem các ô đó có chướng ngại vật ở trên hay có phải là ô đã đi qua trước đó hay không.

Điều đầu tiên là thêm mảng "Adjacent tiles" của chúng ta. Một mảng "Direction" với 2 giá trị trống và bốn mảng hướng có 2 giá trị cho mỗi mảng: N (0,1), S (0,-1), E (1,0), W( -1,0).

Hành vi đầu tiên trong gói của chúng ta là xóa các ô kề của chúng ta. Bởi vì chúng ta sẽ thực hiện gói này liên tục, chúng ta cần có các "ô kề" được thu thập để thiết lập lại mỗi lần. Bốn hành vi tiếp theo là các sửa đổi với mảng "Direction". Chúng ta đặt mảng của mảng "Direction" bốn lần với bốn mảng hướng, sau đó thực hiện gói bên dưới. Chúng ta làm điều này để tạo ra một vòng lặp với các giá trị khác nhau của mảng "Direction" mỗi lần.

Bây giờ mà chúng ta có hướng, chúng ta chỉ cần kết hợp các giá trị x và y của chúng với thuộc tính "on tile" của hình đại diện của chúng ta. Sau đó, chúng ta sẽ có thể lấy giá trị mục tiêu trong mảng "Grid" để biết liệu ô đó đã có chướng ngại vật hay chưa.

'Direction x' là giá trị của mảng 'Direction' tại chỉ mục 0, 'lấy on tile' x là giá trị của 'lấy on tile' tại chỉ mục 0. Giá trị mục tiêu x là tổng giá trị của 'direction x' và 'lấy on tile x'. Cũng tương tự với các giá trị y nhưng với chỉ số mục tiêu là 1.

'Target y row' là giá trị mảng của mảng 'Grid' tại chỉ mục 'Target x'. Và sau đó "Target index in y row" sẽ là giá trị của mảng "Target y row" tại chỉ mục của 'Target y'. Đó là tọa độ trong lưới của chúng ta sẽ cho chúng ta biết liệu nó đã được đánh dấu với một chướng ngại vật hay chưa.

Nếu giá trị trong "Target index in y row" là 1, thì ô mục tiêu đó đã bị đánh dấu là bị chặn. Nhưng nếu giá trị không bằng 1, thì chúng ta có thể tiếp tục trong gói của mình.

Bởi vì giá trị "Target x" và "y" đã vượt điều kiện của chúng ta, chúng ta đã thêm một mảng ô trống mới có tên là "New adjacent tile". Điều này sẽ lưu trữ các giá trị của Target x và y như một mảng ô. Chúng ta sẽ đặt giá trị của Target x vào chỉ mục 0 của "New adjacent tile" và Target y vào chỉ mục 1 của nó.

Bây giờ hãy lấy thuộc tính "ô trước" của hình đại diện của chúng ta. Nếu "ô trước" không bằng "mới ô kề", điều này có nghĩa là ô mới không phải là ô đã đi qua trước đó. Sau đó, chúng ta có thể an toàn thêm "New Adjacent tile" vào mảng "Adjacent tiles" bằng cách ghép nó vào. Chúng ta sẽ thiết lập giá trị "ô trước" sau này sau khi di chuyển hình đại diện của chúng ta đến một ô khác.

"Bạn có thể mở rộng gói này bằng cách tạo một mảng hướng 8, cho phép hình đại diện của bạn di chuyển theo các hướng chéo."

Tìm ô kề gần nhất

Bây giờ mà chúng ta đã thu thập được các ô kề chất lượng, chúng ta chỉ cần lấy ô kề gần nhất với ô mục tiêu của hình đại diện. Chúng ta sẽ thực hiện phép tính bằng cách sử dụng một công thức khoảng cách được cung cấp bởi các giá trị x và y của ô mục tiêu và các ô kề.

Có hai điểm chính trong gói này: khởi tạo các biến cho phép tính và phép tính khoảng cách ô bên trong một vòng lặp.

a. Khởi tạo các biến

Đầu tiên là lấy số lượng mảng của các ô kề của chúng ta. Sau đó lấy thuộc tính "ô mục tiêu" của hình đại diện của chúng ta và lấy giá trị x và y của nó. Chúng ta sẽ thêm 2 hộp chứa mới: "Min distance" và "Target tile index". Chúng ta đặt giá trị ban đầu của "Min distance" thành 9999, và giá trị của "Target tile index" thành 0. Khoảng cách min được đặt thành một số lớn bởi vì chúng ta cần khoảng cách nhỏ nhất từ bắt đầu. Chỉ mục ô mục tiêu là chỉ số tham chiếu của chúng ta trong mảng "Adjacent tiles" có khoảng cách nhỏ nhất đến "ô mục tiêu" của chúng ta.

Mục tiêu chính của chúng ta ở đây là lấy chỉ số của ô trong mảng "Adjacent tiles" gần nhất với "ô mục tiêu".

b. Tính toán khoảng cách ô

Trong gói này, chúng ta sẽ thực hiện phép tính bên trong một vòng lặp mà chúng ta sẽ thực hiện cho mỗi ô kề. Vòng lặp lặp lại theo "số lượng ô kề" và chúng ta sẽ lấy giá trị ô của mảng "Adjacent tiles" sử dụng chỉ số của vòng lặp đó.

Lấy giá trị x và y của ô kề đó và sau đó chúng ta sẽ lấy khoảng cách giữa "ô mục tiêu" và "ô kề" sử dụng công thức này:

distance = sqrt((x2 - x1)^2+(y2 - y1)^2)
x1 = Target x
x2 = Adjacent x
y1 = Target y
y2 = Adjacent y

Chúng ta trước tiên trừ giá trị x và y của chúng, nhân nó với chính nó để có được giá trị lũy thừa của nó, thêm các giá trị đó lại với nhau, và cuối cùng là căn bậc hai của các giá trị được thêm vào, để lấy giá trị khoảng cách.

Nếu giá trị "Distance" nhỏ hơn giá trị trong hộp chứa "Min distance", chúng ta sẽ đặt giá trị "target tile index" về chỉ số hiện tại của vòng lặp, đó là chỉ số của ô mà chúng ta đã lấy trong mảng "Adjacent tiles". Chúng ta cũng đặt giá trị của hộp chứa "Min distance" bằng giá trị "Distance" để so sánh với ô tiếp theo trong vòng lặp.

Cuối cùng vòng lặp, chúng ta đã so sánh từng ô kề và chúng ta đã có giá trị chỉ số của ô kề gần nhất với ô mục tiêu của chúng ta.

Di chuyển đến ô kề

Trong gói cuối cùng của hướng dẫn này, chúng ta sẽ di chuyển hình đại diện của chúng ta đến ô kề gần nhất và thực hiện lại toàn bộ gói "Tìm đường" nếu chúng ta chưa di chuyển đến ô mục tiêu.

Điều đầu tiên là kiểm tra xem "số lượng ô kề" của chúng ta có lớn hơn 0 không. Điều này để đảm bảo rằng chúng ta chỉ di chuyển nếu chúng ta đã lấy được ít nhất một ô kề đáng tin cậy.

Tiếp theo, chúng ta "Lấy ô gần nhất" bằng cách sử dụng giá trị "Target tile index" từ gói trước để lấy giá trị mảng của mảng "Adjacent tiles".

Để lấy chính xác điểm mà hình đại diện của chúng ta sẽ di chuyển đến, chúng ta sẽ cần giá trị tọa độ x và y của ô đó, và cũng lấy giá trị thuộc tính "start x" và "start y" của nhãn "Grid" của chúng ta. Sau đó, thêm giá trị x của "nearest tile" với giá trị "start x", và cũng như vậy với các giá trị y. Những giá trị đã cộng này là điểm x và y mục tiêu mà hình đại diện của chúng ta sẽ di chuyển đến.

Trước khi chúng ta di chuyển đến điểm đó, hãy đặt "ô trước" của hình đại diện của chúng ta với giá trị thuộc tính "on tile" hiện tại của nó. Chúng ta có thể lấy giá trị "on tile" này từ các gói trước. Sau đó, di chuyển hình đại diện của chúng ta đến các điểm mục tiêu của mình với khoảng thời gian là 0,2.

Sau khi hoàn thành hành vi "Di chuyển đến điểm", chúng ta sẽ đặt giá trị thuộc tính "on tile" của hình đại diện của chúng ta với giá trị mảng "Get nearest tile". Nếu giá trị mảng "Get nearest tile" không bằng giá trị "ô mục tiêu", chúng ta sẽ thực hiện gói hành vi "Tìm đường", do đó thực hiện lại toàn bộ gói một lần nữa. Giá trị thuộc tính "ô mục tiêu" có thể được lấy từ gói trước.

Bằng cách nhấn vào bất kỳ ô màu xanh nào, và sau sự xuất hiện của hình đại diện của chúng ta trên lưới, gói "Tìm đường" sẽ được thực hiện. Điều này sẽ kích hoạt việc di chuyển của hình đại diện từ ô này sang ô khác.

Kết luận

Trong hướng dẫn này, chúng ta đã học cách tạo một hoạt động tìm đường cho đối tượng bằng cách sử dụng một mảng mà chúng ta gọi là "Grid", được sử dụng để lưu trữ thông tin về việc ô đó đã bị chiếm giữ hay chưa. Bạn có thể mở rộng ý tưởng này bằng cách sử dụng các id đối tượng như thông tin lưu trữ thay vì chỉ là một số lớn cho mảng "Grid". Điều này sẽ cung cấp cho chúng ta thông tin đáng tin cậy hơn mà chúng ta có thể sử dụng khi thực hiện tìm đường. Ví dụ, chúng ta có thể lấy các thuộc tính của id đối tượng đó để biết nó có sống hay không, liệu nó có cho phép chúng ta bước lên ô của nó hay không.

Hướng dẫn này chỉ cung cấp ý tưởng cơ bản về việc tìm đường. Một nhược điểm của điều này là nó không tạo ra đường đi ngắn nhất có thể đến ô mục tiêu và chỉ kiểm tra ô kề hiện tại. Điều này có thể dẫn đến việc di chuyển trong một vòng lặp không đạt đến đâu cả.

Tuy nhiên, điều này có thể được giải quyết bằng cách mở rộng thuật toán tìm đường của chúng ta. Chúng ta có thể thực hiện điều này bằng cách lặp lại ô kề mà chúng ta đã lấy để tìm các ô kề của nó cho đến khi chúng ta tìm thấy ô mục tiêu. Mỗi ô kề gần nhất tìm thấy sẽ được thêm vào một danh sách. Để ngăn chặn vòng lặp vô tận, thêm một điều kiện rằng nếu ô kề đó đã được kiểm tra, ô đó sẽ không được thêm vào danh sách của chúng ta. Ngoài ra, thêm một giới hạn tối đa về số lần lặp lại để ngăn chặn vòng lặp vô tận gây ra bởi ô mục tiêu nếu nó quá xa hoặc không thể tìm thấy. Khi lần lặp đó tìm thấy ô mục tiêu, chúng ta sẽ thoát khỏi lần lặp đó và bắt đầu di chuyển hình đại diện từ ô này sang ô khác sử dụng danh sách ô.