Thuật toán và game
#thuật toán
4
White

Nguyễn Ân Phúc viết ngày 29/01/2019

alt text
Ảnh https://alifkurniawan08.wordpress.com/

Thuật toán là gì ? Nó có mục đích gì trong game ?

Thuật toán(algorithm.) là gì ? Có khá nhiều định nghĩa về thuật toán, nhưng chúng ta có thể hiểu, thuật toán là từng bước một để hoàn thành một nhiệm vụ nào đó(task).

Chẳng hạn như bạn muốn hoàn thành task đi từ Đà Nẵng => Sài Gòn. Bạn sẽ cần “thuật toán” mua vé -> bắt grab ra sân bay -> đi máy bay. Một trường hợp khác chẳng hạn bạn muốn tìm kiếm tên “Phúc” trong bảng điểm của trường bạn sẽ tìm đến vần P -> tìm đến chữ Ph -> và cứ thế.

Trong khoa học máy tính, algorithm là từng bước để hoàn thành một task, việc tìm ra một thuật toán tốt rất quan trọng đối với chương trình.

Các loại thuật toán trong game

alt text
Cuộc sống cũng chứa đầy thuật toán

  • Một số thuật toán được sử dụng trong game lẫn trong các chương trình khác chẳng hạn như thuật toán nén (compression algorithm) để nén một lượng dữ liệu lớn qua internet một cách nhanh chóng, hoặc nén một âm thanh để giảm tải dung lượng cài đặt trên điện thoại.

  • Một thuật toán khác cũng rất phổ biến là thuật toán tìm đường(route finding), không chỉ áp dụng cho trí thông minh nhân tạo của các nhân vật game. Nó còn sử dụng rộng rộng rãi trong google map. Có rất nhiều thuật toán tìm đường khác nhau chẳng hạn như Djikstra, A star...

  • Một số thuật toán khác phải kể ra như MinMax dùng trong trò chơi cờ, spatial partitioning trong đồ họa, numerical integration cho vật lý cơ bản để mô phỏng lò xo,và chuyển động trong giao diện người dùng, Sorting algorithms khi bạn muốn làm một túi đồ cho nhân vật …nếu bạn biết về các thuật toán, bạn có thể tiết kiệm nhiều công sức và tối ưu hóa cho mỗi trường hợp cụ thể.

alt text
Djikstra được sử dụng để tìm đường không theo khoảng cách vật lý. (ảnh Stack Overflow)

Không phải mọi thuật toán của danh sách trên đều được sử dụng khi muốn phát triển game, một số thuật toán chỉ là toán học cơ bản,do đó bạn cần có kiến thức về toán như vector, góc, nội suy tuyến tính. Tùy vào trò chơi mà bạn muốn phát triển, sẽ có hàng tấn thuật toán khác nhau. Tuy nhiên đây là một bước quan trọng khi bạn muốn bắt đầu. Khi bạn làm việc với nhiều khía cạnh lớn khác nhau của trò chơi, việc thiết kế để quản lý cấu trúc dữ liệu là bắt buộc.

Nếu bạn đã biết rõ về các thuật toán., bạn có thể biết được những hạn chế và ưu điểm của mỗi thuật toán tìm đường khác nhau, nó có thể ảnh hưởng đến thiết kế trò chơi. Đôi khi bạn có thể phải thiết kế lại trò chơi.

alt text
Thuật toán MinMax trong chò chơi cờ caro, ảnh https://www.ocf.berkeley.edu/

Việc thiết kế các thuật toán bị ảnh hưởng bởi hai yếu tố chính là chính xác và hiệu quả. Chẳng hạn như khi tôi muốn tạo một thuật toán xác định va chạm giữa 2 hình tròn. Tôi có thể sử dụng thuật toán mô phỏng vật lý có sẵn hoặc lựa chọn tự viết cho mình một thuật toán mới đơn giản hơn. Tương tự đối với mỗi yêu cầu trò chơi khác nhau, bạn sẽ cần viết rất nhiều thuật toán khác nhau để tìm kiếm, mô phỏng, tập hợp, trí thông minh, toán học, đồ họa …

Điều gì tạo nên một thuật toán tốt ?

alt text

Có 2 tiêu chí của một thuật toán tốt, đó là tính chính xác và hiệu suất. Hầu hết các trường hợp chúng ta chỉ quan tâm đến tính chính xác. Đôi khi chúng ta không thể có một kết quả chính xác cho kết quả và nó mất nhiều thời gian. Một số thuật toán hiệu suất cao hơn những thuật toán khác. Nếu muốn tìm hiểu thêm về thuật toán bạn có thể tham khảo, bạn có thể đọc cuốn Introduction to Algorithms của tác giả Thomas H. Cormen.

Kết luận

Tùy thuộc vào vấn đề mà chúng ta muốn xử lý, sẽ có nhiều thuật toán khác nhau, thuật toán bản thân nó chỉ là một công thức để giải quyết vấn đề. Đôi khi cả một chương trình cũng được coi là một thuật toán phức tạp.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Nguyễn Ân Phúc

1 bài viết.
3 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Bài viết liên quan
White
2 0
Mô tả Quick Sort là một thuật toán sắp xếp hiệu quả dựa trên việc phân chia mảng thành các nhóm phần tử nhỏ hơn. Giải thuật sắp xếp nhanh chia mản...
Dần Huỳnh viết 9 ngày trước
2 0
White
19 3
Tìm đường đi ngắn nhất Find Shortest Path 1. Giới thiệu Nhắc đến giải thuật duyệt đồ thị, chắc ai cũng biết đến 2 thuật toán cơ bản: DepthFirst...
Hải Đinh Thanh viết hơn 1 năm trước
19 3
White
5 1
5. Thuật toán FloydWarshall Trước khi xem tiếp, các bạn hãy xem phần 1 mình đã đăng ở (Link) Trong phần này, đầu tiên mình sẽ giới thiệu về thu...
Hải Đinh Thanh viết hơn 1 năm trước
5 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
1 bài viết.
3 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!