Public Group

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

## 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();
}
}


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 on other sites
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 on other sites
Quote:
 Original post by b3rs3rkit'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.

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 16
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009843
• ### Who's Online (See full list)

There are no registered users currently online

×