I have a program, where a 500x500 unit map is created. Individual star systems are precreated ie [1,20] [40,100] [2,40], etc Each new game, the star system will contain differnt planets. I need to figure out a best method for moving from star system to star system, via a AUTOSCOUT function. The only info that is avail ahead of time is the location of star systems on the x,y map. The systems are seperated in light year increments. It would be silly to start at point 100,100, and move to a system at 5,5 when there is a system at 100,105 95,110, etc. Im trying to come up with code that will sweep across the system. The 500x500 grid can be broken down into sub maps as well. Thank you for your input.

Is this for one ship or many ships? The logic will be different between those.

Will you allow movement directly between stars or will all movement be regulated by the grid squares (ie - moving one neighbor square at a time )



Optimal mapping paths for a single ship (to reach the most systems in a given anount of time could be done by building a N-tree and blocking paths to stars already visited for each new branch and stopping when a given time limit is reached.

That would be a brute force way of doing it.

There might be a faster non-guarabteed-optimal way of assessing clusters of stars that are near each other and testing that set of subtrees first, and expanding the 'best' gruping search from that new point to try to build a good path.

Create a list of all systems, sort the list by the distance from your current location, the winner is the closest system. Once you get there, repeat the process. There are inefficiencies to that, however.

As alluded to before, you may want to look for clusters of them. The best way to do that would be through an influence map. You want to use two of them. First, generate one using the local influences of each system. Radiate their presence out a certain distance (you will have to play with it to find a good radius). The influence map peaks will then show you the best clusters. However, that method does not account for distance. You can then do an influence map that radiates from your current position. By adding the two together to form an aggregate influcence map, you can determine the systems/clusters that are the biggest AND closest. For example, you may search a small cluster just because it is closer than the larger one.

This sounds like a variation of the http://en.wikipedia.org/wiki/Traveling_salesman_problem which is NP-Hard.

If you just want to sweep the system in a simplified way, then the influence map suggestion is a sound method.