LudumData

Lots of AI = performance hit

[raw] LD11LD #11 - Minimalist - 2008 19. Apr 2008 · 22:44 UTC · 46 hours after compo start by Dathgale · 0

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

Comments

DrPetter
20. Apr 2008 · 07:50 UTC
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).