I'm coding a game where there are many ships controlled by AI pilots.
Ships are split into 2 teams, team 1 and team 2.
I'm trying to determine the basic AI decision process, and the problem I've run into is that I want each ship on either side to "acquire" an enemy target on the other side,
by finding the closest enemy target (I'm open to suggestions on other ways to find enemy targets), but in the worst case, this is a O(n^2) problem, not to mention calculating
distances can be quite expensive (although, I can use distance squared). The map itself also happens to be very large.

Some other notes:
- For simplicity we can assume that all ships can see each other.
- For broad-phase collision detection I've used a box-pruning algorithm (similar to sweep and prune), and I thought I could maybe use query boxes to see if there are any enemy ship close to the AI ship (like a radius check), but the radius would have to be a constant, and the AI ship might not be able to find a target close enough.

Any ideas?

You could use something like a spatial hash to quickly bucket the agents into regions; moreover, you could have an agent select an enemy randomly from the same bucket instead of bothering to do a distance check at all. I would question the robustness of focusing on nearest-distance as a metric for prioritizing targets anyways; you should attach a utility curve to it so that a really easy target is prioritized over a closer, but much tougher, opponent.

@ApochPiQ
- For spatial hashing, I was hoping I could do something with the box prune code that I had set up already instead of adding a new broad-phase technique just for acquiring targets. In addition my map is very large, I'm guessing spatial hash would take a lot of memory

- I think the random check would be easy to do, and if I have nothing better, I will use it,

- in combination with the prioritization of enemies based on their toughness as well as distance.

There was this game I played recently called Gratuitous Space Battles, and they had many ships and lasers flying around. My game is similar in style to that, but map size is larger.

The whole point of spatial hashing is that you tune its bucket volume to give you a reasonable balance between discretized buckets and good memory consumption. You will have to do some work to get it up to speed.

I don't know what you mean by "box pruning" code, but if you already have a viable broad-phase collision check... what's the difficulty in abusing it for culling distance checks as well?

@ApochiPiQ
I see.
By box pruning, I really meant a variant of sweep and prune.
You're probably right in that I should consider different ways to use my current system to do the checks. I had some difficulty before but I think with some extra effort, I can work something out.
Thanks for your help.