Embedded Files
Post date: Jul 4, 2011 5:31:14 PM
List
List
List, hay danh sách liên kết, là một đối tượng không thể thiếu trong quản lý một danh sách các đối tượng. Nó giải quyết được vấn đề của mãng, vốn có số lượng phần tử xác định. Tuy nhiên, list đòi hỏi các thực hiện phức tạp hơn, quản lý khó khăn, và tốn chi phí hơn.
Bạn hoàn toàn có thể implement list, tuy nhiên, có một thư viện khá mạnh, và được sử dụng rộng rãi, hổ có tốt các loại cấu trúc dữ liệu: tree, list, map, ... là STL.
STL được hổ trợ mặc định bởi thư viện C của visual studio. Hiện tại, cả Android và Xcode đều đã có hổ trợ STL. (xem thêm STL port)
Do chủ yếu làm việc với list, nên trong khuôn khổ bài này, chỉ đề cập đến list. Để sử dụng list, ta include list.h
#include "list"
using namespace std;
Tuy nhiên, khi sử dụng list, ta hay gặp vấn đề với cơ chế shadow copy của list nói riêng và STL nói chung.
Để thuận tiện trong sử dụng, ta thiết kế lớp wrapper cho list: CList.
CList header
#if CONFIG_PLATFORM==PLATFORM_WIN32_VS # define ListIterator(type) list::iterator #else # define ListIterator(type) _List_iterator #endif namespace GameTutor { template class CList { public: CList(); virtual ~CList(); void AddItem(element_type ele); void RemoveItem(element_type ele); element_type GetElement(int index); element_type operator[](int index); int GetCount(); void DeallocateElementPointer(); void Clear(); void BeginTravel(); element_type Travel(); bool IsEndOfTravel(); int GetTravelStepCounter() {return m_iTravelStepCounter;} protected: list* m_List; typename list::iterator m_CurrentIter; private: int m_iTravelStepCounter; }; }
Để tăng tốc việc duyệt qua các phần tử, ta sử dụng bộ 3 hàm: BeginTravel, Travel, IsEndOfTravel
mylist.BeginTravel();
while(!mylist.IsEndOfTravel())
{
element = mylist.Travel()
}
Trong đó element là biến cùng kiểu với template của CList.
Trong trường hợp element_type là kiểu con trỏ, DeallocateElementPointer dùng cho việc xóa vùng nhớ được trỏ tới bởi các phần tử trong list.
mylist.DeallocateElementPointer();
mylist.Clear();
CList.h
#ifndef __UTILS_H__ #define __UTILS_H__ #include "Header.h" #include "list" using namespace std; #if CONFIG_PLATFORM==PLATFORM_WIN32_VS # define ListIterator(type) list<type>::iterator #else # define ListIterator(type) _List_iterator<type> #endif namespace GameTutor { template<typename element_type> class CList { public: CList(); virtual ~CList(); void AddItem(element_type ele); void RemoveItem(element_type ele); element_type GetElement(int index); element_type operator[](int index); int GetCount(); void DeallocateElementPointer(); void Clear(); void BeginTravel(); element_type Travel(); bool IsEndOfTravel(); int GetTravelStepCounter() {return m_iTravelStepCounter;} protected: list<element_type>* m_List; typename list<element_type>::iterator m_CurrentIter; private: int m_iTravelStepCounter; }; } template<typename element_type> GameTutor::CList<element_type>::CList() { m_List = new list<element_type>(); } template<typename element_type> GameTutor::CList<element_type>::~CList() { m_List->clear(); SAFE_DEL(m_List); } template<typename element_type> void GameTutor::CList<element_type>::AddItem(element_type ele) { m_List->push_back(ele); } template<typename element_type> void GameTutor::CList<element_type>::RemoveItem(element_type ele) { m_List->remove(ele); } template<typename element_type> element_type GameTutor::CList<element_type>::GetElement(int index) { ListIterator(element_type) i = m_List->begin(); int _i = 0; if ((unsigned)index < m_List->size()) { for (i = m_List->begin(); _i < index; i++, _i++){} return (*i); } return (*i); } template<typename element_type> element_type GameTutor::CList<element_type>::operator[] (int index) { return GetElement(index); } template<typename element_type> int GameTutor::CList<element_type>::GetCount() { if (!m_List) return 0; return m_List->size(); } template<typename element_type> void GameTutor::CList<element_type>::DeallocateElementPointer() { if (GetCount() > 0) { ListIterator(element_type) i; ListIterator(element_type) cur; for (i = m_List->begin(); i != m_List->end();) { cur = i; i++; if (*cur) { delete[] *cur; } } } } template<typename element_type> void GameTutor::CList<element_type>::Clear() { if (GetCount() > 0) { m_List->clear(); } } template<typename element_type> void GameTutor::CList<element_type>::BeginTravel() { m_CurrentIter = m_List->begin(); m_iTravelStepCounter = -1; } template<typename element_type> element_type GameTutor::CList<element_type>::Travel() { element_type re = (*m_CurrentIter); if (m_CurrentIter != m_List->end()) { m_CurrentIter++; m_iTravelStepCounter++; } return re; } template<typename element_type> bool GameTutor::CList<element_type>::IsEndOfTravel() { return ((GetCount()==0) || (m_CurrentIter == m_List->end())); } #endif
Các macro hổ trợ xóa vùng nhớ an toàn
Các macro hổ trợ xóa vùng nhớ an toàn
Khi làm việc với C++, thông thường ta hay mắc sai lầm như: xóa vùng nhớ, nhưng quên gán null; hoặc chỉ gán null khi muốn xóa vùng nhớ. Để thuận tiện trong việc xóa các vùng nhớ, ta sử dụng các macro sau:
Macros
#define SAFE_DEL(a) {if(a){delete (a);(a) = NULL;}}
#define SAFE_DEL_ARRAY(a) {if(a){delete[] (a);(a) = NULL;}} #define SAFE_DEL_ARRAY_TYPE(a, t) {if((t)a){delete[] ((t)(a));(a) = NULL;}} #define SAFE_DEL_ARRAY_OBJ(p, n) {if ((p)!=NULL) {for (int __i = 0; __i < (n); __i++) SAFE_DEL((p)[__i]); SAFE_DEL_ARRAY(p);}} #define SAFE_DEL_ARRAY_ARRAY(p, n) {if ((p)!=NULL) {for (int __i = 0; __i < (n); __i++) SAFE_DEL_ARRAY((p)[__i]); SAFE_DEL_ARRAY(p);}}
Lớp sinh số ngẫu nhiên
Lớp sinh số ngẫu nhiên
Là một lớp khá quan trọng trong game, dùng để phát sinh các bộ test, hay tạo các sự kiện mang tính ngẫu nhiên, xác suất. Ví dụ với dạng game tower defend, mỗi wave cần ngẫu nhiên với xác suất 50% creep loại A, 30% loại B, 20% loại C cho level 1, ... Trong những tình huống này, có 2 cách xử lý:
- Thiết kế trước file level, qui định từng màn, khi nào xuất hiện creep nào, số lượng bao nhiêu
- Dùng bộ sinh ngẫu nhiên. Cách này giúp cho game trở nên thú vị hơn, vì trong mỗi lần chơi, người chơi đều có cảm giác mới mẽ.
Có nhiều cách để sinh số ngẫu nhiên đơn giản như:
Xem trang này để có thêm chi tiết
Trong ví dụ sau sử dụng phương pháp Additive congruential:
a[0] = seed
a[i] = (b*a[i]) % m , i < c
a[j] = (a[j-b] + a[j-c]) % max, j >= c
Với b=55, c=31
Random
// Additive congruential // a[0] = seed // a[i] = (b*a[i]) % m , i < c // a[j] = (a[j-b] + a[j-c]) % m, j >= c #define RND_MAX_VAL_SHIFT 30 #define RND_MAX_VAL_MASK 0x3fffffffl #define RND_HALF_MAX_VAL_SHIFT 15 #define RND_HALF_MAX_VAL_MASK 0x7fffl #define RND_C 55 #define RND_B 31 class CRandom { public: CRandom() { SetSeed(CDevice::GetInstance()->GetTimer()); } CRandom(__UINT64 seed) { SetSeed(seed); } void SetSeed(__UINT64 seed) { m_Val[0] = seed; for (m_iRandomIndex = 1; m_iRandomIndex < RND_C; m_iRandomIndex++) { m_Val[m_iRandomIndex] = (Mult(RND_B, m_Val[m_iRandomIndex - 1])) & RND_MAX_VAL_MASK; } } __UINT32 NextInt(__UINT32 max) { m_iRandomIndex = (m_iRandomIndex + 1) % RND_C; int shift1 = (m_iRandomIndex + (RND_C - 1) - RND_B) % RND_C; int shift2 = (m_iRandomIndex + (RND_C - 1)) % RND_C; m_Val[m_iRandomIndex] = (m_Val[shift1] + m_Val[shift2]) & RND_MAX_VAL_MASK; int rint = ((m_Val[m_iRandomIndex] >> RND_HALF_MAX_VAL_SHIFT)*max) >> RND_HALF_MAX_VAL_SHIFT; return rint; } __UINT32 NextTrueFalse() { return NextInt(100) > 50?1:0; } __UINT32 NextTrue(int percent) { return NextInt(100) < percent?1:0; } private: __UINT64 m_Val[RND_C]; __UINT32 m_iRandomIndex; private: __UINT64 Mult(__UINT64 a, __UINT64 b) // mul 2 number without overflow. Assume a, b are 30bits integers. { __UINT64 a1 = a>>RND_HALF_MAX_VAL_SHIFT; __UINT64 a0 = a&RND_HALF_MAX_VAL_MASK; __UINT64 b1 = b>>RND_HALF_MAX_VAL_SHIFT; __UINT64 b0 = b&RND_HALF_MAX_VAL_MASK; __UINT64 mul = (((((a0*b1) + (a1*b0)) & RND_HALF_MAX_VAL_MASK) << RND_HALF_MAX_VAL_SHIFT) + a0*b0) & RND_MAX_VAL_MASK; return mul; } };
Trong đó:
- CRandom(): khởi tạo lớp Random với seed là giờ hệ thống
- CRandom(__UINT64 seed): khởi tạo lớp Random với seed cho trước
- void SetSeed(__UINT64 seed): reset seed và dãy số random.
- __UINT32 NextInt(__UINT32 max): sinh số integer ngẫu nhiên, với giá trị tối đa là max
- __UINT32 NextTrueFalse(): trả về true/false (1/0) với xác suất 50-50
- __UINT32 NextTrue(int percent): trả về true (1) với xác suất cho trước (dùng cho việc ra quyết định AI)
Các hàm tiện ích
Các hàm tiện ích
Bao gồm các hàm kiểm tra, chuyển đổi, xử lý đơn giản. Trong ví dụ sau là một số hàm thường dùng
- Math_Abs: lấy trị tuyệt đối
- Math_Min/Math_Max: lấy min/max
- Math_Log2: Lấy log cơ số 2
- Math_IsPo2: Kiểm tra 1 số có phải là 2 mũ n không
- Str_ToUpper: Chuyển đổi chuổi thành dạng chữ hoa
- Str_ToLower: chuyển đổi chuỗi thàng dạng chữ thường
- ...
Utils
template inline T Math_Abs(T a) { return (a<0?-a:a); } template void Math_GetLog2(T input, __UINT32 &val, __UINT32 &mod) { __UINT32 num = __UINT32(input); val = 0; mod = 0; if (num == 0) { return; } else if (num == 1) { val = 0; mod = 1; return; } else { __UINT32 tmp = num; while (tmp > 1) { val++; tmp>>=1; } mod = num - (1< inline T Math_Min(T a, T b) { return (a inline T Math_Max(T a, T b) { return (a>b?a:b); } template inline bool Math_IsPO2(T a) { if (a < 0) return false; __INT32 num = __UINT32(a); return ((num&(-num))==num); } inline void Str_ToUpper(char *input, __INT32 size) { if (input) { for (int i = 0; i < size; i++) { if (input[i] >= 'a' && input[i] <= 'z') { input[i] += 'A' - 'a'; } } } } inline void Str_ToLower(char *input, __INT32 size) { if (input) { for (int i = 0; i < size; i++) { if (input[i] >= 'A' && input[i] <= 'Z') { input[i] += 'a' - 'A'; } } } } }
Thư viện số fix-point
Thư viện số fix-point
Page updated
Google Sites
Report abuse