AI Behavior Communication

[benhumphreys]

I'm making a game where there are a some small animals that communicate their state to each other. For instance one will communicate to others that it is feeding, or that it is running away. Then others within a certain range will change their behavio(u)r accordingly. In the real world this communication would happen via sight, smell or hearing.

I'm trying to design how to do this best in Lua.

The best idea I have so far is to use the Publisher/Subscriber type pattern that is implemented in Kikito's beholder.lua. Each time the animal changes state they would announce it. Other animals that have behaviours that are affected by that change would subscribe those keys (and not to others).

To implement limiting message range, animals would include their XY positions with the message. Receivers would compare that to their own position and ignore the messages outside of their range. This means that the greater the number of animals sending messages across the whole world, the greater the slowdown. This is a big flaw.

My questions are:

• Can anyone think of problems that this might create?
• Is there a better solution I haven't thought of? In particular one that avoids the XY filtering problem.

[szensk]

Rather than having the event handler be the animal, create another system. This system would have a spatial hash* containing every animal. When an animal announces a state change, the system looks at the creatures location and broadcast range and finds the other animals within that area. This system would need to be made aware of animal movements, so as to update the spatial hash. This should reduce the problem domain from O(n^2) to something more reasonable.

* You could use any data structure you like, so long as it separates the animals into smaller buckets based on location. Off the top of my head other options are quad trees, some form of sweep & prune, buckets.

[kikito]

I don't think Beholder is a good match for what you're trying to do. This is because for it to be practical, you need a way to "filter" calls so that every entity does not get messages from every other entity on every frame - the cost of such a process scales up quickly with each new entity you add (10 entities involve 100 calls, 100 entities involve 10000 calls).

As szensk mentions, the usual way to model this is via some sort of spatial index, which Beholder doesn't have.

Depending on your game, a simple grid might be enough. The process, on every frame, looks like this:

Code: Select all

* All entities move around
* All tile marks are removed
* Every entity marks all the "tiles" where it can be seen, with a mark that says "Entity XX can be seen from this tile"
* Same goes for other senses: Mark the tiles from which the entity can be heard or smelled, if the game has those senses.

On the next frame, the entity just has to query its current tile: And the tile will say "You can see entity XX from here".

That's the general idea. I hope this helps.