Jump to content
  • Advertisement
Sign in to follow this  
signal_

Using std::multimap to Facilitate AI Spatial Inputs

This topic is 3617 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

I am using std::multimap as a container to provide spatial input data to AI agents. That is to say AI agents have a function associated with them called look() where they can receive spatial input. For example, in my 2D grid, an entity can say look ( x, y), which means look at that coordinate area and 'see' what is there: the lion looks at x1, y1 and sees a zebra. Could you guys take a look at my implementation and critique. The thing is that it works; however, I'd appreciate suggestions on making it faster/more efficient. Here's the code:
// THE ENTITY UPDATE FUNCTION TO BE CALLED ONCE PER FRAME
void EntityList::entityUpdate()
{
    // clear Entity Maps, then Update Entity Maps.
    contents.clear();

    for( int i = 0; i < entities.size(); i++ ) 
    {
        entities->update();

        addEnt( entities->GetX() / tileX, entities->GetY() / tileY,
                                entities->GetType() );    // map(loc -> type)
        
        entities->render();
     }
}

The addEnt function:
void EntityList::addEnt(int x, int y, std::string id)                          // Adds a map element (loc -> ID)
{
    // Function returns void.  This function accesses the map(loc -> ID) and adds a new member:
    // the new member is: map( "x,y" , ID )
    // Effectively the entity's ID is mapped to the entity's current location

    std::string key;

    key = conv_int_str(x);
    key.append(",");
    key.append( conv_int_str(y) );

    contents.insert( std::pair<std::string, std::string>(key, id) );
}

And, finally to access the information: the function getEntAt.
int EntityList::getEntAt(int x, int y)                                 // retrieve map element(s)
{
    // Function returns int countEnt of how many entities at location x,y
    // ID_holder is cleared and the entity ID's at x,y
    // are written to ID_holder array

    std::string key;
    int i = 0;
    int countEnt;

    clearID_holder();

    key = conv_int_str(x);          // convert int to std::string
    key.append(",");
    key.append( conv_int_str(y) );

    countEnt = contents.count(key);

    if ( countEnt != 0 )  //countEnt != 0
    {
        for( std::multimap<std::string,std::string>::iterator ii = contents.lower_bound(key); ii != contents.upper_bound(key); ++ii)
        {
            if ( i < 10 ) // don't want to go out of bounds of the id_holder container array
            {
            id_holder = ii->second;
            i++;
            }
        }
    }

    return countEnt;
}

So that's it. Entities that have the ability to look use the function getEntAt once per frame and effectively scan their area and then they react to this information. I am just wondering if I'm being efficient and is there a faster way to do this? This is important to me since these operations add cpu time thus limiting the number of entities that I can process at a given frame rate.

Share this post


Link to post
Share on other sites
Advertisement
it's just a tought, but if you need to provide spatial input data to entities, why don't you use a quadtree? You said you're using a 2D grid: so you can create a quadtree that partitions the entire scene and every leaf contains only the list of the entities in a particular sector of the grid.

This way you can find the entities in a sector (its size obviously depends on how far you go during quadtree creation), and not in a single cell of your grid, and then make your entity do whatever she wants...

always imho :)

Share this post


Link to post
Share on other sites
Quote:
Original post by b3rs3rk
it's just a tought, but if you need to provide spatial input data to entities, why don't you use a quadtree? You said you're using a 2D grid: so you can create a quadtree that partitions the entire scene and every leaf contains only the list of the entities in a particular sector of the grid.

This way you can find the entities in a sector (its size obviously depends on how far you go during quadtree creation), and not in a single cell of your grid, and then make your entity do whatever she wants...

always imho :)

Damn. I knew I should have used a quadtree. I'll look into that. I was going to use a quadtree for the collision detection system, but I opted for a sweep and prune algorithm and forgot about the quadtree.

At the same time, you have stimulated some thought in me. I am now wondering if I could use a variation of my collision detection system since it's already set up for me?

Instead of just using small bounding circles that enclose sprites I could use large perception circles that enclose entities and whatever they collide with the entity will perceive. I have to look into that as well.

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!