The mineral gathering algorithm(s) in action
Improving mineral gathering rate in StarCraft 2 (using the bot API)
EDIT: turns out that I set the experiment on RealTime mode (thus giving inaccurate frame count). New data below
As some of you may know, the default behavior of worker units is not optimal. This is the case in BW ( http://www.teamliquid.net/forum/brood-war/484849-improving-mineral-gathering-rate-in-brood-war ), but it is also true for StarCraft 2.
So for Brood War I implemented some algorithms to improve the gathering rate. I implemented those in SC2 as well and I now have some preliminary results already. It was quite interesting to see that even in SC2 there was still much gain from optimizing the mineral gathering rate.
Details of the algorithms can be found in the TL link above, I will mainly discuss results here
The following algorithms are used:
- Built-In
- Mineral Lock
- Queue System
- Co-operative Pathfinding
- Co-operative Pathfinding + Queue System
The research setup is as follows:
All algorithms start at the top left start location of InterloperLE and play for 4000 frames. Each algorithms builds 2 SCVs, then 1 supply depot, then SCVs until it has 16 SCVs (the recommended #workers).
Built-In:
The Built-In algorithm basically lets the internal worker management do its thing. In SC2 the internal worker management works more like the Mineral Lock system. So unlike BW there is not much difference between this and the Mineral Lock
Mineral Lock
Essentially making sure that each worker unit stays assigned to a certain mineral field. The frantic switching of mineral field in BW only rarely occurs in SC2, thus making this almost the same as the Built-In
Queue System
After some testing, it turns out that I cannot get accurate enough data from the API. Especially when exactly worker units are mining (and how much time they still need). This makes the results of the queue system worse than the more standard mineral lock.
Either way, the queue system uses a greedy scheduler, so the result can still be improved
The Co-operative wasn't really needed in SC2 due to how unit collisions work in SC2 compared to BW (in BW units are more like solid blocks whereas in SC2 units behave like a fluid). The optimized movement to the mineral fields was thus the main focus here.
I was surprised that it improved the #minerals at all, but I soon saw that just like in BW the worker units slow down when approaching a mineral field (just like in BW). The effect isn't as profound as in BW though.
Combining the 2 systems will
Github source code
The preliminary source code is currently up on the github for LetaBotSC2. Now updated to not use realtime mode.
https://github.com/MartinRooijackers/LetaBotSC2/tree/master/Research/MineralAlgorithms
It still needs a better setup for gathering results (mainly adding Protoss and Zerg as well), but it should work for those willing to try it out themselves. A compiled .exe is available as well if you just want to see it in action (currently only for Terran).
Raw Data
Raw data from some of the tests that I have run can be seen by clicking on the spoiler.
Updated for the non-realtime mode.
+ Show Spoiler +
TopLeft Interloper LE:
Taken at intervals of 250 frames
So the first result is frame 250 , the last one when the #frames was at 4000
BuildIn:
Current Frames: 250 Total Minerals: 70
Current Frames: 500 Total Minerals: 55
Current Frames: 750 Total Minerals: 135
Current Frames: 1000 Total Minerals: 220
Current Frames: 1250 Total Minerals: 385
Current Frames: 1500 Total Minerals: 540
Current Frames: 1750 Total Minerals: 710
Current Frames: 2000 Total Minerals: 885
Current Frames: 2250 Total Minerals: 1055
Current Frames: 2500 Total Minerals: 1225
Current Frames: 2750 Total Minerals: 1400
Current Frames: 3000 Total Minerals: 1565
Current Frames: 3250 Total Minerals: 1730
Current Frames: 3500 Total Minerals: 1905
Current Frames: 3750 Total Minerals: 2080
Current Frames: 4000 Total Minerals: 2250
EvenSplit:
Current Frames: 250 Total Minerals: 85
Current Frames: 500 Total Minerals: 65
Current Frames: 750 Total Minerals: 145
Current Frames: 1000 Total Minerals: 240
Current Frames: 1250 Total Minerals: 405
Current Frames: 1500 Total Minerals: 575
Current Frames: 1750 Total Minerals: 740
Current Frames: 2000 Total Minerals: 920
Current Frames: 2250 Total Minerals: 1090
Current Frames: 2500 Total Minerals: 1265
Current Frames: 2750 Total Minerals: 1430
Current Frames: 3000 Total Minerals: 1600
Current Frames: 3250 Total Minerals: 1770
Current Frames: 3500 Total Minerals: 1935
Current Frames: 3750 Total Minerals: 2115
Current Frames: 4000 Total Minerals: 2280
Queue:
Current Frames: 250 Total Minerals: 90
Current Frames: 500 Total Minerals: 65
Current Frames: 750 Total Minerals: 150
Current Frames: 1000 Total Minerals: 245
Current Frames: 1250 Total Minerals: 400
Current Frames: 1500 Total Minerals: 570
Current Frames: 1750 Total Minerals: 745
Current Frames: 2000 Total Minerals: 915
Current Frames: 2250 Total Minerals: 1075
Current Frames: 2500 Total Minerals: 1245
Current Frames: 2750 Total Minerals: 1405
Current Frames: 3000 Total Minerals: 1580
Current Frames: 3250 Total Minerals: 1745
Current Frames: 3500 Total Minerals: 1915
Current Frames: 3750 Total Minerals: 2085
Current Frames: 4000 Total Minerals: 2255
Path:
Current Frames: 250 Total Minerals: 95
Current Frames: 500 Total Minerals: 75
Current Frames: 750 Total Minerals: 155
Current Frames: 1000 Total Minerals: 255
Current Frames: 1250 Total Minerals: 415
Current Frames: 1500 Total Minerals: 580
Current Frames: 1750 Total Minerals: 745
Current Frames: 2000 Total Minerals: 925
Current Frames: 2250 Total Minerals: 1105
Current Frames: 2500 Total Minerals: 1280
Current Frames: 2750 Total Minerals: 1445
Current Frames: 3000 Total Minerals: 1625
Current Frames: 3250 Total Minerals: 1805
Current Frames: 3500 Total Minerals: 1970
Current Frames: 3750 Total Minerals: 2130
Current Frames: 4000 Total Minerals: 2315
Path+Queue:
Current Frames: 250 Total Minerals: 90
Current Frames: 500 Total Minerals: 70
Current Frames: 750 Total Minerals: 155
Current Frames: 1000 Total Minerals: 255
Current Frames: 1250 Total Minerals: 415
Current Frames: 1500 Total Minerals: 580
Current Frames: 1750 Total Minerals: 740
Current Frames: 2000 Total Minerals: 920
Current Frames: 2250 Total Minerals: 1090
Current Frames: 2500 Total Minerals: 1260
Current Frames: 2750 Total Minerals: 1430
Current Frames: 3000 Total Minerals: 1595
Current Frames: 3250 Total Minerals: 1775
Current Frames: 3500 Total Minerals: 1935
Current Frames: 3750 Total Minerals: 2115
Current Frames: 4000 Total Minerals: 2280