Lots of AI = performance hit
Posted by Dathgale
April 19th, 2008 5:44 pm
I woke up about an hour ago and added most of the AI to the monsters. The only thing they don’t do yet is avoid collisions with each other, but I hardly notice it when the green squares overlap. When I add images it may be another story, but I’ll cross that bridge when I get there.
Here is a zoomed-out view of the action. Note the clusters that form when monsters wander near each other. I think it looks great in motion, except that I can count the framerate on one hand when there are this many monsters in the arena.
I’m taking a break for dinner, and when I get back, I’ll work on optimizing the AI so it doesn’t take up my entire processor (and then some).
Tags: Omnihunter
If the performance hit is coming from finding nearby enemies, you really want to use some sort of space-partitioning data structure for speedup. I’ve used kd-trees in the past with good results. I did it with the ANN library (http://www.cs.umd.edu/~mount/ANN/), but the algorithms involved aren’t that difficult to implement.
I’m embarrassed to say that I don’t have a clear idea of what KD trees would be… but a simple and effective method would be to use a good old rectangular grid and store a list of occupant ID:s in each grid cell. So for each tick you start by populating the cells (constant time per entity, grid[y/cellsize*width+x/cellsize].occupants.pushBack(me)), then when you need to find neighbors you just step through a few of the nearby grid cells and check the occupant lists of those. If you just need very close neighbors you can take the surrounding 3×3 block of cells for example.
This should nicely reduce the complexity from N^2 to roughly N (for all but the most clustered cases).