My last couple of posts have been casual and without focus. I think this tends to be my state of mind after concluding a complex project. The A2 interpreted language continues to be a great programming experience for me. I was able to get practical functionality into the language within a short amount of time. It is at this time in version 0.2. Development of A2 will be paused as I rethink certain systems which interpret and compile the language and continue with additional Summer goals. I will also use this downtime to study other interpreted languages, such as lua and angel script, to get an improved perspective on the interpreted paradigm. As it stands now A2 is a fully operational battle station...woops!(wrong project) I mean scripting language. It can be downloaded from my website and includes a user's manual as well as an example source showing how to use A2 with C++.
Return of the Troll...
Let's now think about my little troll friend. He has been so lonely sitting there in his polygonal prison. If you remember from a previous post I mentioned doing a Black & White style creature AI with him. I haven't forgotten about him and would still like to do some learning programming with the troll. Who knows maybe I'll be able to use A2 in a practical way. [wink]
One of the first things the troll agent should do after entering her or his world is to explore it and develop an equivalent mental image. I've had so many ideas about how to implement this and have finally settled on using a dynamic two dimensional array to store the map. Essentially the agent enters the world not knowing anything about it. The agent's state would then switch to "explore" as there will be a strong urge to do so. Other characteristics about the agents personality will determine exactly how far the agent explores before defining her or his territory, but that's beside the point.
The agent is at the point of entry into the world. The agent is now aware of the area surrounding it. This area is represented as a square (later to be a cubic volume) with a constant area. This squared area is represented in our 2D memory map using a 2D vector. The creature begins to explore her or his environment. As the creature leaves the first known area another area is added to the map in the direction the troll moved from the square. It must be stated here that all area points are exactly the length of the side of each square away from each other. This forms a perfect grid over the world made of square areas which the creature can identify with certain events, objects, and actions. The grid will also serve as a path finding structure for A* searches.
Take for example the following world. It has an unusual shape to explore and will serve as an excellent testing environment. You see that as the agent enters the environment it is aware of only one square area. Then you see, that after a few moments time, the troll is more "aware" of its world. More complicated worlds will be used to test the algorithm such as the one shown in green.
The dynamic 2D array class...
In order to store the agent's internal world image we will need a data structure that can grow dynamically as the agent's "awareness" grows. In this case we are using a two dimensional array. Using STL vectors, and the wonderful power of templates, I was able to create such a dynamic object. Columns and rows can be added in the positive direction (right and bottom) without having to shift the data. Negative columns and rows (left and top) are added in the same way except the data is shifted relative to the number of columns and rows added. If one of you gurus out there knows a faster way to shift-copy the array data then I'd appreciate your help in this matter. Here is the source code for the dynamic 2d array generic class.
template class Dynamic_2D_Array{private: // Vector of a vector of generic type T std::vector > ___Data; public: // Constructors Dynamic_2D_Array(void){}; Dynamic_2D_Array(size_t Row_Size, size_t Column_Size) { Reset(Row_Size, Column_Size); } // Operator [] for data access inline std::vector & operator[](size_t i){return ___Data;} inline const std::vector & operator[](size_t i) const {return ___Data;} void Reset(size_t Row_Size, size_t Column_Size) { // Clear ___Data.clear(); // Reset the array to a new size ___Data.resize(Row_Size); for(size_t i = 0; i < Row_Size; ++i) ___Data.resize(Column_Size); } void Grow_Array_Positive(size_t Rows_To_Add, size_t Columns_To_Add) { // Get new array sizes size_t New_Row_Count = (size_t)___Data.size() + Rows_To_Add; size_t New_Column_Count = (size_t)___Data[0].size() + Columns_To_Add; // Add the new rows and columns to the 2d array // No need to shift data as rows and columns are appended ___Data.resize(New_Row_Count); for(size_t i = 0; i < (size_t)New_Row_Count; ++i) ___Data.resize(New_Column_Count); } void Grow_Array_Negative(size_t Rows_To_Add, size_t Columns_To_Add) { size_t Shift_Row_Start = ___Data[0].size() - 1; size_t Shift_Column_Start = ___Data.size() - 1; size_t New_Row_Count = ___Data.size() + Rows_To_Add; size_t New_Column_Count = ___Data[0].size() + Columns_To_Add; // Add the new rows and columns to the 2d array // at the end of the rows and columns ___Data.resize(New_Row_Count); for(size_t i = 0; i < New_Row_Count; ++i) ___Data.resize(New_Column_Count); // Shift the data over according to how many rows and columns // were added. We use an integer for the loops because i and j // loop variables will need to be negative to exit. for(int i=(int)Shift_Row_Start; i>=0; i--) { for(int j=(int)Shift_Column_Start; j>=0; j--) { // Shift the data ___Data[j + Columns_To_Add] = ___Data<span style="font-weight:bold;">[j];<br> <span class="cpp-comment">// Clear the old data</span><br> ___Data<span style="font-weight:bold;">[j] = T(); <br> }<br> }<br> }<br>};<br><br></pre></div><!–ENDSCRIPT–> <div>
</div>
But the picture of the bunny costume was funny though [smile]
So is this a case of "Watch This Space" for Neil's upcoming plans for world universal domination...?
Provided you've got A2 upto scratch, wouldn't hurt to try and road test it a bit [grin]
That troll learning thing is great, can we have a go with it when it's working on the more complex worlds?
I wrote a somewhat simple genetic/flock learning AI demo a couple of years back, it's a bit sad to admit, but I watched it for hours as they flew around. Mine just avoided a landscape and preditors, so no complex path finding required...
I'm definitely no C++ guru... but I'll share an algorithm I used for a somewhat more boring project at work.
Presumably you're familiar with the way that a "vector" (in the ADS style) grows it's storage by, usually, doubling the amount allocated. Doing so each time it runs out.
I developed something like this with a char[] array in Java, but when inserting characters into the document the code had to shuffle all subsequent characters along by a certain amount (Thanks to Java, no memcpy [headshake]). Worst case was inserting at the start of the array - it had to move every single element along.
So it was changed... the actual contents of the array were placed in the *middle* and padding was used either side. The array became 3x the size it needed to be, and the trade-off was that any insertion, in the worst case, moved 1/2 of the document.
Dunno if that'll be of any use to you though [smile]
Jack