Smart Area Reclaim TSP Optimization
Posted: 03 Sep 2009, 19:46
Thinking about resurrecting this with a better (well, an actual) traveling salesman implementation:
http://springrts.com/phpbb/viewtopic.php?f=23&t=15835
Telling a unit to reclaim a dense clump of features is pretty easy to optimize... he can just move around it from the outside.
The problem I was running into with the previous algorithms dealt with isolated clusters. I have a possible solution.
When a construction unit is given an area reclaim command, smart area reclaim splits the area into a grid (Figure A). It then splits grid cells containing features into quadrants (green squares). Adjacent quadrants and high-density quadrants are considered to be clusters of features (blue circles) (Figure B).
Further optimization: clusters can be given a value based on their density. When traveling to a new cluster, a builder can factor density and distance to assign a value to each cluster. It will choose the most valuable cluster.
These values could be extrapolated into a true traveling salesman algorithm by factoring future adjacent clusters into a cluster's value. For example, a very dense cluster far off the path with no adjacent clusters will be worth less than a nearby small cluster with several other nearby small clusters.
Thoughts?
http://springrts.com/phpbb/viewtopic.php?f=23&t=15835
Telling a unit to reclaim a dense clump of features is pretty easy to optimize... he can just move around it from the outside.
The problem I was running into with the previous algorithms dealt with isolated clusters. I have a possible solution.
When a construction unit is given an area reclaim command, smart area reclaim splits the area into a grid (Figure A). It then splits grid cells containing features into quadrants (green squares). Adjacent quadrants and high-density quadrants are considered to be clusters of features (blue circles) (Figure B).
Further optimization: clusters can be given a value based on their density. When traveling to a new cluster, a builder can factor density and distance to assign a value to each cluster. It will choose the most valuable cluster.
These values could be extrapolated into a true traveling salesman algorithm by factoring future adjacent clusters into a cluster's value. For example, a very dense cluster far off the path with no adjacent clusters will be worth less than a nearby small cluster with several other nearby small clusters.
Thoughts?