Hi, I've been working on a little game framework as a learning experience but have hit a brick wall.
My game is tile-based and will have agents moving about.
I've gotten agent-to-tile collision working with a constant time complexity (yay) which means moving n-agents, I only have to do n-work to check if their new positions will collide with a tile; cool.
However, agent-to-agent collision is much harder for me =/
I've been thinking of solutions but have been hard pressed to come up with any.
If I do a naive implementation (as I have done), I'll end up with (n-1) comparisons for moving one agent and [n(n-1)]/2 comparisons for moving n-agents. That is, check each agent and see if they collide; if they don't, allow them to move.
I've thought of a bunch of ways; like having them in a list sorted by x-coordinates at all times so that the checks I have to do is significantly less. But then, I run into the problem of having to update the list as I move the units and swapping things around. Even thought of splitting the game-world that the agents live into grids of 5 tiles but that doesn't solve my book-keeping problem.
I just can't really wrap my head around an efficient algorithm. My agents are always 32.32 pixels in size (so that's one thing that's made slightly easier.)
Are there any hints on how I could store my agents that always have their locations changing?
