Right now, it's naive about getting the k-nearest neighbors for any one chicken O(n^2). For my 1GHz computer, I can only run it up to around 50 chickens.
Anyone have good leads on algorithms to cull the number of comparison down to find the k-nearest neighbors? I've been looking at variants of the R-tree, but if there are other techniques, it'd help to know. Thanks ya'll.
Seriously, I did a lot of such simulations (in graduate school) and usually the simplest thing is the best.
-----
[1] Let's say your world is 100x100 units. You create 2D array of 10x10 cells (preallocate each cell to be able to hold max number of agents, so that you don't fragment memory and waste time on allocations/garbage collection/etc.).
In each step of the simulation, you go through all agents and place them in the correct cell (that's O(N) and constant is actually really cheap => cell[0.1 x agent.x][0.1 x agent.y]).
Then for the interactions, just check agents in your cell and also 8 neighboring ones (that's practically O(N) because of repulsion forces).
Huh, I had thought about that, but because the bins aren't dynamic, like they are with trees, I figured it would give some odd aberrations. I'll try this first since it's the simplest. Thanks. I didn't know that Craig Reynolds tried it out this way also.
You could try using the quadtree culling algorithms (seen here: http://lab.polygonal.de/2007/09/09/quadtree-demonstration/) used in collision detection. Just treat each chicken as a circle that's as big as the distance at which it stops considering other chickens its neighbor.
I am admittedly bad with this sort of thing, so it might really be the R-tree in disguise.
On another note, it's good to see someone on HN get interested in game development. The road is long, hard, and littered with half-finished projects, but also the occasional finished one. The sense of accomplishment and fun factor is several magnitudes higher than coding 'normal' stuff.
I'll look into it briefly, and though I haven't finished evaluating all my options, I get the notion that quadtrees were used for static collision detection culling, or it was precomputed for a model.
In addition, I think different trees have different insertion and deletion complexities (don't know which is which yet). I need something, like the other commenter says, that doesn't penalize for adjusting the tree.
I've not used an R-tree before, but from the Wikipedia description, it looks like it's for static point sets. Your chicken positions are dynamic, which could cause you to constantly rebuild the tree.
Anyone have good leads on algorithms to cull the number of comparison down to find the k-nearest neighbors? I've been looking at variants of the R-tree, but if there are other techniques, it'd help to know. Thanks ya'll.