What is the best way to add vision & hearing to game entities?

We have maybe 200 entities (creatures & traps) at max, and process the game tick every 250ms. My initial idea is to build a quadtree of these entities on each tick. And use raycasting then to see if they really see/hear each other if they are close enough. And then just give a proximity list to each entity for it to figure out what to do with it.

We are not (yet) using any physics. Does JME already do this sort of thing internally? Or Bullet? Or what is the de facto way to achieve this? Am I completely clueless?

The game is sort of RTS style.

A quad tree buys you nothing here. A sparse fixed grid would give you better performance if you want to bin your stuff.

Quad trees have one main advantage: you can skip checking entire sections if they are empty. The main disadvantage is that being able to skip entire sections largely depends on where things are and how well they fit the grid’s split hierarchy. It also presumes you will most often be checking from the root. The worst case for neighbor look ups is super super bad. (Many full depth tree traversals bad.)

On the other hand, a fixed width grid can be checked in constant time. The grid size then becomes a function of performance: number of cells checked versus average number of items likely to be in that cell.

Being “sparse” just means you aren’t wasting space on some huge array if your grid will be large. If your grid isn’t going to be that large then you might not bother with the sparse part.

If you are going to end up doing pair-wise checks then that’s probably the easiest way to trim things down to a reasonable number of checks. If your grid cell width is also your ‘visible’ distance then you only have to check surrounding grid cells.

Edit: also… in a fixed grid, insertion and removal are also constant time operations. That’s definitely not true for a quad tree where they are best for static data because insertion/removal times can vary.

Edit 2: I’m also having to be general because we know nothing about your scene. Outdoor versus indoor environments makes a pretty big difference.

2 Likes