Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    149
  • comments
    510
  • views
    95099

Some consistency please

Sign in to follow this  
noaktree

180 views

A2 reflection...

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[i + Rows_To_Add][j + Columns_To_Add] = ___Data[j];
// Clear the old data
___Data[j] = T();
}
}
}
};

Sign in to follow this  


7 Comments


Recommended Comments

Awesome post [grin]

Quote:
My last couple of posts have been casual and without focus.

But the picture of the bunny costume was funny though [smile]

Quote:
As it stands now A2 is a fully operational battle station…woops!(wrong project) I mean scripting language.

So is this a case of "Watch This Space" for Neil's upcoming plans for world universal domination...?

Quote:
Who knows maybe I’ll be able to use A2 in a practical way.

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...

Quote:
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.

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

Share this comment


Link to comment
Quote:
Provided you've got A2 upto scratch, wouldn't hurt to try and road test it a bit
Agreed. What’s the point in making something if you don’t use it? [smile]

Quote:
That troll learning thing is great, can we have a go with it when it's working on the more complex worlds?
I will be posting regular demos of the Troll. I’d like to make this a sort of community project if there is interest, so expect a lot more information about this one than my usual abstracted thoughts. [grin]

Quote:
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.
That’s just flocking awesome! Isn’t machine intelligence just amazing to watch?

Quote:
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.
Actually I was not familiar with this. I really know very little about how STL works internally and have only been using it for a short time. Perhaps my array should be doubled in size each time it runs out of room as well. This would save on the number of shifts.

Share this comment


Link to comment
Quote:
That’s just flocking awesome! Isn’t machine intelligence just amazing to watch?

Yup, not sure why either - mine was really quite simple and didn't do anything hugely "wow" [smile]

Quote:
Actually I was not familiar with this. I really know very little about how STL works internally and have only been using it for a short time. Perhaps my array should be doubled in size each time it runs out of room as well. This would save on the number of shifts.

From what I've seen, STL works in the same way as a standard Vector, but I'm not 100% sure.

Basically, if you were to create an array of 1000 elements, in order for you to add another (having 1001 elements) you'd have to create a new array of size 1001, copy everything across and then release the original 1000 element array. Very slow for adding a single element.

What a Vector will do is, for your original 1000 elements, allocate 2000 worth of storage. Thus there is no allocation/deallocation for a single insertion/deletion - just shuffling elements forwards (insert) or backwards (delete). When you've added 2000 elements it runs out of space - but increases the array to 4000 instead. When you hit these boundaries it's obviously slow - but because it happens a lot less, it's not so bad.

The above description has the problem that I originally described - inserting at the very beginning still requires you to shift every single element along by one (which is slow, even if there's no memory allocation required).

So the modification we made was to have a buffer at the start as well as the end of the array:

[------][01234567][------]

The bonus being that any insertion/deletion requiring elements to be shuffled along can limit their effect to AT MOST 1/2 of the "real" array...

In the above diagram inserting between [2,3] would shuffle 3 elements (0,1,2) left rather than 5 elements (3,4,5,6,7) right.

hth!
Jack

Share this comment


Link to comment
Shouldn't the troll be able to learn his environment by seeing?

He could learn it much faster and it seems more realistic. Of course if he's not sure of something he sees he'll tend to go that direction, etc. But it'd be neat to see him learn about things just by looking around.

Share this comment


Link to comment
Quote:
Shouldn't the troll be able to learn his environment by seeing?

He could learn it much faster and it seems more realistic. Of course if he's not sure of something he sees he'll tend to go that direction, etc. But it'd be neat to see him learn about things just by looking around.
Right on! The troll will learn with his eyes. He will have a view frustum attached to his head matrix. When exploring he will look around for areas which he hasn't yet been. I want the troll to "know" an area by actually experiencing it rather than just seeing it from a distance. Most objects will be able to be found by sight or by memory of their location.

Share this comment


Link to comment
Instead of using a 2d array, you might want to implement that with a graph and an associative container like std::map. The graph would consist of nodes that contain the square grid component, and its known connections. You can use the map to access a particular location node like (15,20).

The benefit to doing this is that the connection between spaces is abstract rather than physical. Portals would be a good example. The points between two portals are not exactly physically connected. Rather, they serve as an abstract connection between two points. Think of how you would have to implement the knowledge of the portal in your agent's memory using a 2d array. Either you resize your array to include the position which the agent is transported to, or you create a new array if that area is new or different from the one the creature is currently in.

Now, think of how you would implement that portal knowledge in your agent's memory using a graph. It would just be a connection. In fact, the portals would not have to be two way. Perhaps they are one way portals. Perhaps going back into the portal you came out of will not take you to the original location, but to a new location. Continuously going in the one you came out of might return you to the original location forming a chain.

Another problem with the 2d array, which was mentioned with the portals, is that you would need to store new ones for new areas, floors, levels, etc. If you use a graph, then the agent only needs one graph with perhaps an identifier preceeding the location to represent the node's location. Here are some examples:

sorrow_swamp(x,y)
hospital_hill(x,y)
jerrys_house(x,y)

You might even want to have a hierarchy for location names like:

jerrys_house(first_floor(bathroom(x,y)))

Anyway, using a graph and some kind of associative container might work out a lot better. It would definately reduce the memory requirements too.



Share this comment


Link to comment
The addition of portals or placment of the agent in different sections of the world adds an interesting complexity to an effective implementation. I will give this serious thought. Thanks again Zefrieg for your valuable input.

Timkin mentioned in my AI forum post:
Quote:
The prevalent solution to this problem is called SLAM: Simultaneous Localisation And Mapping. There is a wealth of information on implementation methods for SLAM online. It should give you more than enough information for your needs in a simulated world.
So I'll be researching this as well.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!