Shadow/Melee Gun

Shadow Sub-pages:: Shadow - Version History - Archived Talk 20040725 - Archived Talk 20090724 - Melee Gun

Shadow's melee gun is one of the best melee guns around today, no doubt. But what's the secret behind it?

If you have ever watched Shadow closely, you should noticed that it implements two things that you have on your to-do list of your melee gun:

Swarm Targeting: Why does my bot always choose that lonely target when it could be targeting that tight pack in the other corner?
Prey on the weak: Why waste my energy trying to hit Diamond when SittingDuck is there just a little bit further asking to be killed?
Wasting energy is bad for survival: If it doesn't hit Diamond, will it still hit someone behind him and give you your energy back, or will it go to waste against a wall?

How does it work?

Want to know how? If you have a working Dynamic Clustering melee gun, here is the recipe:

Speed it up. A kd-Tree (Simonton's is what Shadow used) and a fast play-it forward algorithm are good bets.
Compute the k-best firing solutions for each of the enemies on the field. Yes, all of them.
Collect them all in a big array of angle/tolerance. Also keep the hitting distance for each one.
Select the angle with the biggest probability of hitting, weighting them by the inverse distance.
Fire at the best one, it will hit someone somewhere... :)

Not hard, eh? Simple (20 minutes work), effective (10% hitrate increase), cool to watch. This is why I love this game!

This article is talking about Shadow's gun, which is DC-PIF, but this technique can also be applied to GuessFactor or Displacement Vector targeting.