by Demerzel » Thu Oct 21, 2010 12:19 am
I understand where you all are coming from but I think you're way overcomplicating it, and I did at first too.
I wasn't going to share my methods since the competition is still going but it's pretty simple at its core, thinking in terms of trees and spatial reasoning is going to introduce a ton of bugs and possible efficency problems not to mention you'll probably be outperformed by bots that do nothing more than pick the smallest number out of a possible 20.
There are a max of 23x23 distances - these can be (and are by my bot since version 0.0.1) cached as soon as turn1. Then to create hops you do the hop algorithm I posted up before. All you need is a closestEnemy(planetIndex) function that simply runs through the distances for planetIndex and returns the smallest one that has an enemy on the other side.
You now have a minimum distance to enemy. A simple way (not my way but the way most right-below-top bots work from observation) to use this information is then to send all your ships to whichever of your planets returns the smallest number and you have a front line.
You can extend this same logic to create multiple fronts which is a simplified version of how my bot works: check if planetIndex to planetIndex2 is less than planetIndex2 <-> enemy.if so, you now have a 'covering' planet in planetIndex. So you can use this information to say Planet[planetIndex] is the closest to the enemy AND you now know that planetIndex2 doesn't need ships sitting on it because ships from planetIndex can cover it because it's closer to 2 than the enemy is and just start sending all of your ships on Planet[planetIndex2] to planetIndex. If planetIndex2 is NOT covered by planetIndex then find out if it's closer to the enemy than any other planets, any planets that have at least 1 planet closer are now just feeding to the closest planets that do.
You have a frontline and a supply route, just like that - it didn't take anything more than checking distances.
I did play with territories and x/y and even had a whole target system set up on whether they were within my 'box' and based on the average distance to enemy were they closer, but it had all kinds of issues like what if I have an L shaped territory then all of them qualify or vice versa - or large maps vs small maps the averages might be thrown off etc.
Bottom line is that if you're considering a heuristic approach I guarantee you there's a better cold mathematical one that probably doesn't take much actual math beyond <>=, at least in regards to front lines.
If you use this info then beat me just give me some credit for saving you a few days of frustration!