Cách viết chữ lên màn hình trong XNA

Posted On December 25, 2010

Filed under XNA

Comments Dropped leave a response

Trong khi viết một game, nhiều lúc bạn muốn in một thông báo ra mà hình. Bài viết này sẽ giúp bạn làm việc đó.

(Read More)

Advertisements

Bắt đầu với XNA.

Posted On December 6, 2010

Filed under XNA

Comments Dropped leave a response

Chúng ta sẽ thử bắt đầu  với việc tạo một đối tượng lên màn hình và làm cho nó di chuyển.
Để đơn giản ta bắt đầu với một hình tròn. Cần chuẩn bị một file circle.png vẽ một hình tròn hoặc bất kể file ảnh nào mà bạn muốn vẽ lên màn hình…….

(Read More)

Bài toán 8 puzzle–thiết kế và cài đặt.

Posted On December 2, 2010

Filed under AI

Comments Dropped one response

Sau khi đưa bài toán về đưới dạng đồ thị, áp dụng thuật toán A* để xác đinh đường đi từ trạng thái đầu đến trạng thái đích.
Các class :
class BOARD: Lưu giữ thông tin về một trạng thái hiện tại của bảng, có thể dung một mảng kiểu int gồm 9 phần tử, trong đó vị trí của các số từ 1 đến 8 tương ứng là vị trí của 8 mảnh ghép, vị trí của số 0 tương ứng với khoảng trống, việc sử dụng mảng 2 chiều hay 1 chiều. đều cố những ưu nhược điểm riêng.
Quan trọng nhất là hàm ước lượng khoảng cách H từ board hiện tại đến board kết thúc, có nhiều cách để ước lượng, một trong những cách phổ biến nhất là phương pháp Mahatan. Đó là tính tổng số bước cần di chuyển đối với các mảnh ghép đâng nằm sai vị trí.
(Read More)

Giới thiệu về XNA

Posted On December 1, 2010

Filed under XNA

Comments Dropped leave a response

– XNA là một công nghệ của Microsoft phục vụ cho mục đích lập trình game. Ưu điểm của nó là tốc độ làm game nhanh, quản lý tài nguyên (hình ảnh, âm thanh, ….) một cách hiệu quả và đơn giản, hỗ trợ nhiều ngôn ngữ.

– XNA platform là gì? Platform, chúng ta tạm dịch là nền tảng, bao gồm cả phần cứng và phần mềm mà ứng dụng chạy trên đó. Vd như chúng ta chơi game Fifa trên PC, thì PC và HĐH Windown chính là platform. Một game có thể chạy trên một hoặc nhiều flatform, VD như PES có thể chạy trên PC và cả Playstation. Đối với một game thương mại thì việc chạy được trên nhiều flatform ảnh hưởng rất lớn đến thị phần của nó. XNA cho phép ta lập trình game chạy trên PC + Windows, XBOX360, ZUNE, mỗi loại đều có ưu điểm nhược điểm riêng.
(Read More)

Bài toán 8_Puzzle

Posted On November 24, 2010

Filed under AI

Comments Dropped 2 responses

Bài toán:
Cho một hình vuông được chia ra làm 9 vị trí(3×3), mỗi vị trí là một số từ 1 đến 8 và một khoảng trống. Tại một thời điểm ta có thể di chuyển một số có giáp một cạnh với khoảng trống vào khoảng trống đó. Yêu cầu của bài toán là từ trạng thái ban đầu tìm cách dịch chuyển các ô số một cách tối ưu để đạt được một trong 2 trạng thái đích.
Trạng thái 1:                       Trạng thái 2:
_ -1-2                                      1-2-3
3- 4-5                                      4-_-5
6-7-8                                       6-7-8

(Read More)

Khủng hoảng thời gian.

Posted On November 24, 2010

Filed under Lung tung.

Comments Dropped leave a response

Mình đang rơi vào khủng hoảng, một cuộc khủng hoảng thực sự về thời gian, mình không còn khả năng quản lí thời gian của mình nữa, thời gian bị lãng phí quá nhiều, các công việc đè lên nhau tùm lum, chỉ cần một sự thay đổi nhỏ của  một công việc cũng làm mình rối tung lên. Giá như bây giờ mình có thể phân thân thành 2 hoặc 3 người thì tốt quá, nhưng mà không thể, đành hi sinh một số thứ để ổn định trở lại, nếu không thay đổi, hậu quả chắc chắn sẽ rất thảm hại.

Ngôn ngữ Prolog.

Posted On November 19, 2010

Filed under Prolog

Comments Dropped leave a response

Trước khi nói về prolog, xin nói một chút về các ngôn ngữ khác:

C, Pascla: Là ngôn ngữ lập trình cấu trúc (Structural Programming), nghĩa là chúng ta giải quyết bài toán bằng cách chia nhỏ bài toán thành nhiều vấn đề nhỏ, giải quyết các vấn đề nhỏ bằng các hàm, và các kiểu, cấu trúc dữ liệu mà ta xây dựng.
C++, C#: Là ngôn ngữ lập  trình hướng đối tượng(OOP), nghĩa là chúng ta chia bài tón thành các đối tượng, giải quyết bài toán thông qua việc xử lý các đối tượng.
Đối với 2 cách lập trình này quan trọng nhất là: Data structure + Algorithm = Program.
Prolog: Là ngôn ngữ lập trình logic, chúng ta giải quyết bài toán dựa trên các mệnh đề logic, tức là dựa trên các đối tượng và sự quan hệ các đối tượng.
Đối với cách lập trình này quan trọng nhất là: Algorithm = logic+control.

Việc phân chia chỉ mang tính tương đối, cái quan trọng là tư duy giải quyết bài toán đi theo hướng nào.

Thuật giải Astar.

Posted On November 19, 2010

Filed under AI

Comments Dropped leave a response

Thuật toán Dijkstra tuy được đánh giá là chính xác và khá hiệu quả, nhưng trong các bài toán lớn vẫn không sử dụng được, vd như trong bài toán tìm đường đi trên bản đồ thành phố( theo lời thầy thì khoảng vài tiếng cho cỡ bản đồ thành phố HCM). Vì vậy dựa trên thuật toán Dijksta, người ta đã phát triển lên thuật toán A*.

Ý tưởng của A* cũng như Dijkstra, là sử dụng phép duyệt lan truyền, chỉ khác là tại mỗi điểm đang xét, chọn điểm xét tiếp theo sao cho khoảng cách dự đoán từ đỉnh đó đến đỉnh tiếp theo là nhỏ nhất, nghĩa là ta sẽ xây dựng một hàm Heuristic h(x)  dự đoán khoảng cách từ x đến đích, sau đó chọn đỉnh kế sao cho f(x) = g(x)+h(x) là nhỏ nhất.

Về thuật giải tương tự nhue Dijkstra, chỉ khác ở bước 2, chọn x theo tiêu chí là f(x) chứ không phải là g(x).

Tính hiệu quả, chúng ta nhận thấy rằng, về thuật giải, thuật giải A* không có gì khác so với thuật toán Dijkstra, thậm chí còn tốn thêm thời gian tính h(x) và f(x), vậy tại sao nó hiệu quả hơn.
Để thấy rõ tính hiệu quả của nó, ta xem xét bài toán tìm đường trên bản đồ, với h(x) được tính bằng khoảng cách tính theo đường chim bay từ x đến đích. Bắt đầu từ đinhr xuất phát, Dijkstra sẽ chọn đỉnh tiếp theo gần nó nhất, bước tiếp theo cũng vậy, và rất nhiều khả năng có hướng ngược lại so với hướng ta cần đi, còn A* chọn đỉnh tiếp theo sao cho khoảng cách dự kiến là thấp nhất, nghĩa là chắc chắn nó sẽ hướng về đích. Nếu như Dijkstra tiến hành quét theo tất cả các hướng, nghĩa là mở khu vực xét theo hình tròn, thì Dijkstra chỉ mở theo hướng hướng về đích, nghĩa là chỉ mở theo hình quạt.
Thành  hay bại của A* nằm ở việc xây dựng h(x), trong trường hợ lí tưởng là h*(x) bằng chính xác khoảng cách từ x đến đích, như vậy ta chỉ cần đi đúng một lần từ đỉnh đầu đến đỉnh cuối,  nếu ta xây dựng hàm h(x) không hợp lý, |h(x) – h*(x)| càng lớn thì hiệu quả của A* càng thấp, và kết quả cuối cùng cũng càng chênh lệch so với kết quả chính xác.

Thuật toán Dijkstra.

Posted On November 13, 2010

Filed under AI

Comments Dropped leave a response

Xét bài toán sau: Cho một đồ thị liên thông có trọng số dương, tìm đường đi ngắn nhất đi từ đỉnh u đến đỉnh v của đồ thị.

Để giải bài toán này một cách chính xác nhất ta sử dụng thuật toán Dijkstra. Cho đến thời điểm này, thuật toán Dijkstra là thuật toán tìm được lời giải chính xác và tốn ít chi phí nhất. Ý tưởng của thuật toán Dijkstra là sử dụng phép duyệt lan truyền,bắt đầu duyệt từ đỉnh xuất phát, tại mỗi đỉnh tính khoảng cách từ đỉnh xuất phát đến các đỉnh kế của đỉnh dang xét, sau đó chọn đỉnh tiếp theo sao cho khoảng cách từ đỉnh đó đến đỉnh ban đầu là nhỏ nhất(so với các đỉnh kế khác), duyệt đến khi gặp được đỉnh cuối thì dừng lại hoặc không còn đỉnh kế thì dừng lại.
Thuật toán:
Đặt Open = tập các đỉnh kế.
Close = tập các đỉnh đã duyệt.
Prev(x) là đỉnh trước đỉnh x trong phép duyệt.
g(x) là khoảng cách từ đỉnh đầu đến đỉnh x.
u là đỉnh ban đầu, v  là đỉnh kết thúc.
B1: Khởi tạo Open = { u }; Close = { }; g(u) =0; Prev(u) = null;
B2. Trong khi Open!= { }
2.1: Chọn x thuộc Open sao cho g(x) là nhỏ nhất.
2.2 Kiem tra nếu x==v thì dừng và đưa ra kết luận.
2.3 Xét tất cả các y là đỉnh kế của x
2.3.1 Nếu y là đỉnh mới thì g(y) = g(x)+d(x,y); Prev(y) = x; Thêm y vào Open.
2.3.2 Nếu y nằm trong Open, Nếu g(x)+d(x,y) <g(y) thì g(y) = g(x)+d(x,y), Prev(y) =x.

Độ phức tạp của thuật toán là O(n^2+m), để tăng hiệu quả thuật toán ta có thể sử dụng cấu trúc Heap để lưu giữ các cạnh kề, khi đó độ phức tạp sẽ chỉ là O( (m+n)log(n) ) với n là số đỉnh, còn m là số cạnh.

Thuật toán này mang tên nhà khoa học máy tính Dijkstra, người đã phát minh ra nó.

Bài toán tìm chu trình Haminton nhỏ.

Posted On October 24, 2010

Filed under AI

Comments Dropped leave a response

Để giải một bài toán thương có nhiều cách, và sau đây là một cách khá đơn giản nhưng hiệu quả cũng khá cao.
Ý tưởng:
-Dựa vào kiến thức toán học ta có:
+ Một đồ thị đầy đủ gồm n đỉnh thì có n(n-1)/2 cạnh.
+ Một chu trình đi qua n đỉnh thì gồm n cạnh và bậc của các đỉnh đều bằng 2.
=> Để có thể tìm một chu trình nhỏ ta có thể làm như sau: Bắt đầu với đồ thị gồm n đỉnh và chưa có cạnh, lần lượt thêm các cạnh có trọng số tương đối nhỏ đến khi đạt được chu trình. Trong quá trình thêm các cạnh phải đảm bảo không xuất hiện chu trình con, và không có đỉnh nào có nhiều hơn 3 cạnh được đưa vào chu trình.
Nguyên lí áp dụng khi xây dựng thuật giải:
Nguyên lí thứ tự: Đưa các cạnh vào chu trình theo thứ tự trọng số nhỏ trước lớn sau, các cạnh nối các đỉnh có giá trị lớn trước, nhỏ sau.
Nguyên lí tham lam: Một chu trình ngắn được hình thành từ những cạnh ngắn.
Dựa trên kiến thức con người về đồ thị, kinh nghiệm khi tìm đường đi: Khi tìm chu trình, chưa chắc đi theo các cạnh nhỏ nhất sẽ tìm được chu trình tốt, cần có một cái nhìn tổng quan về đồ thị để tránh được các cạnh lớn.

Ý tưởng cài đặt:
Xây dựng 3 list ưu tiên để lưu giữ các cạnh, list thứ nhất (list 1) lưu các cạnh nối giữa các đỉnh chưa được đưa vào chu trình, list này sẽ sắp xếp các cạnh ưu tiên theo thứ tự tăng dần của trọng số, nếu có 2 cạnh cùng trọng số thì ưu tiên cạnh nối với đỉnh có “giá trị” lớn hơn (“giá trị” của đỉnh ở đây là tổng trọng số các cạnh nối đến đỉnh đó). List 2 sẽ lưu các cạnh mà ít nhất một đỉnh của nó đã xuất hiện trong chu trình, các cạnh được sắp xếp  theo thứ tự tăng dần của giá trị của đỉnh mà nó nối tới(vì một cạnh nối với 2 đỉnh nên ta xét giá trị lớn hơn trong 2 đỉnh), hai cạnh cùng nối chung đến một đỉnh thì ưu tiên cạnh có trọng số nhỏ hơn. List3 dùng để lưu các cạnh mà ta sẽ chọn để tạo ra chu trình.
Lần lượt so sánh hai phần tử đầu tiên của list 1 và list2, chọn cạnh nhỏ hơn để đưa list3.
+ Nếu cạnh đó được chọn từ list 1, sau khi chọn thêm cạnh đó list 3, ta tiến hành chuyển các cạnh có đỉnh là một trong hai đỉnh của cạnh vừa được chọn từ list 1 vào list 2.
+ Nếu cạnh đó được chọn từ list thứ 2.
– Đỉnh nào xuất hiện 2 lần trong list3 thì xóa hết các cạnh nối tới đỉnh đó.
– Từ list1 chọn tất cả các cạnh nối tới 1 trong 2 đỉnh của cạnh vừa chọn, sau đó đưa tất cả các cạnh này vào list 2.
– Tìm cạnh trong list 2 có thể tạo với các cạnh ở list 3 thành một chu trình con, xóa cạnh trong list 2 để đảm bảo không tạo ra chu trình con trước khi tìm  được chu trình lớn.
Làm như vậy cho đến khi ta tìm được một chu trình.

Một đồ thị có n đỉnh thì có n*(n-1)/2 cạnh, do đó trong list1 ban đầu cũng se có n*(n-1)/2 cạnh, trong hàm main để có một chu trình ta cần một vòng lặp n lầm để thêm n cạnh vào chu trình, mỗi lần thêm một cạnh ta phải duyệt trong list 1 hoặc list 2, sô cạnh trong 2 list này tăng theo n*n, vậy độ phức tạp của thuật giải là n^3. So với thuật toán Nearest Neighbors trình bày trong entry trước thì độ phức tạp có lớn hơn một chút nhưng lời giải tìm đước lại tốt hơn khá nhiều.

Next Page »