Jump to content
  • Advertisement
Sign in to follow this  
noaktree

Learning and remembering an environment

This topic is 4810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

An agent is placed inside of an unknown environment with boundaries. It begins to wander around the environment. It has no previous knowledge of its world. How can we build a memory map of the environment so that the agent can determine if it has already been some place and can, after some wandering, have a complete and accurate mental image of the world? My first thoughts were to enter at a set location let's say (x=0,y=0). This first position is entered into a dynamic array (or some other data structure). A constant radius value will be assigned for every point in the list which represents the area around the point. At every step we could check to see if the agent's position is already in the map (within the nearest point's area). If not then add the new point to the list. One of the problems with the above implementation is that we would need to iterate through the list O(n) and check the distance formula for every point in order to determine the nearest known point before checking to see if it is within the known area. This becomes very bad as the size of the environment increases. I'm sure this has been done before but I'm unsure of an optimal implementation. Any ideas? Neil [edit]I forgot to mention that I'm using C++[/edit] [Edited by - noaktree on July 29, 2005 11:12:53 AM]

Share this post


Link to post
Share on other sites
Advertisement
Well, if your intention is to just store knowledge of the locations where the agent has been and then search through them, then you could easily implement a constant search with a hash table.

You could calculate the hash value for the index into the hash table using both the x and y coordinate of the location.

Share this post


Link to post
Share on other sites
Anyway, what exactly are you going to have this agent ask? What kind of knowledge will it have to query?

If the agent has knowledge of it's environment, then I would suppose that it would ask questions like, "Where is the nearest tree?", "How far am I away from the player (assuming there is one)?", "Where did I last see the player". If everything is based on position and distance, then having some sort of multi index hash table would be acceptable. You could base it on some sort of location class/struct. You could associate a text string with a location so you could do something like this:


if(knowledge.find("food", location_list))
{
// iterate through returned locations for the closest one known
}
if(knowledge.find("tree", location_list))
{
// iterate through trees known
}


You could store and access just about anything's location doing this. You could even store and search a specific location like this:


location loc(20,20);
std::stringstream str_loc;
str_loc << "location{" << x << ',' << y << ')';
knowledge.store(str_loc.str(), loc);
if(knowledge.find(str_loc.str(), location_list))
{
// Do whatever
}


All of that would be pretty easy to implement. Though, if you need your agent to ask more than just location based questions, then you might want to look into semantic networks since it would allow you to add in a broader range of infomation in the language you are using.

Share this post


Link to post
Share on other sites
Quote:
Well, if your intention is to just store knowledge of the locations where the agent has been and then search through them, then you could easily implement a constant search with a hash table.

You could calculate the hash value for the index into the hash table using both the x and y coordinate of the location.
My intention is to build a mental image of the landscape itself. Nothing else (trees, rocks, etc). Just the shape of the world for now. In which case I'd need a fast search which would return the nearest point to a point given in the "whatever" structure of points. Would a hash table allow this search? I won't be storing every vertex where the agent has been, just points with an area of n radius around them.

Share this post


Link to post
Share on other sites
Ok, I think I understand what you are trying to do. Tell me if I have this right:

1. I draw a point on a map and draw a circle around it.
2. If I move outside of the radius of that circle, then I check whether I am in another existing circle.
3. If I am in an existing circle, then I identify myself as being in that circle.
4. If I am not in an existing circle, then I create a new point with a circle around it.
5. Goto step 2.

You might not want to have an agent explore using such a process. You would probably have to check all of the circles when you leave one. Also, there are possibilities that some circles are never revisted, because they are overlapped by several other circles.

Instead of using circles (which would be radius measurements), why not build the agent's representation of the world as a grid? This way, you wouldn't run into spaces that overlap. Also, the nearest node would be one of 4 or 8 directions (not sure if you would have diagonal movements) regardless of the size of the map. This would make the search constant. Leaving one of the boxes would be just as easy to check as leaving the radius of a circle too.

Share this post


Link to post
Share on other sites
Circle - man ?
I mean, circles are very useful. look at the wheel for example. the same wit`h ai

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
SLAM is an open issue. Up to now there is no close solution to the SLAM problem, except with very little maps. I think SLAM-related techniques are not suitable to game programming yet. A better solution would be based on grid-based map, provided that ur agent is able to determine only by its movements where it is.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!