| BWMN Time |
| 11/21/2024 |
| 13:18 |
| News |
| new account |
| list users |
| Login: |
| Replays |
| Map DB |
| ICCup |
| Map Access |
| New map |
| Edit map |
 |
| Worker pathing guide - How to debug and balance resour | 28 2013f February 2013 12:17 AM | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Posted by: Freakling  Worker pathing - how to debug and balance resource gathering The matter this article is about is a very important one - how do you make the resources balanced for the different starting position on a map? Naively thinkning one could consider this a simple, even trivial, task, but unfortunately it's in fact a messy chore you'll have to go through to make your map fit for serious play. It is possible though, and there are reliable methods to do it, but that's about all the good news; it will still reuqire a certain amount of meticulous testing and trial-and error for every new map made. The matter is very complex, and pretty much a matter of experimental approach/reverse engineering, since the actual StarCraft pathfinding algorithm is unknown - and on top of that probably not even fully understodd by the guys who patched it together (as this recent article by SC developer Patrick Wyatt suggests). Soe things I write about are good guesses and reuqire further systematic testing. I will mark those parts with *** and italicize them. I will suggest further test procedures to test those hypotheses in the last section of this guide. This guide could probably need some improvements in structure and overall readability, on the other hand this is basically a hug data dumb by design, hence it is presumambly going to be a work in progress for a while anyway and I am leaving those chenges to be dealt with later for now... To get right to the point: The problem is a well known one: That BW the path finding algorithm for gorund units is an ugly, more or less improvised mess of workarounds, that is known to cause all kinds of seemingly retarded, disoriented behaviour in units. And workers are no excepion. And because players cannot constantly micro their workers around, but have to rely on the little buggers doing what they are supposed to do when they are not watched, it's on the mapper to make sure they behave. To make things worse, while gathering resources workers (can) behave differently for the three races. ***The reason for that most likely does not lie in the workers themselves - they have the same collision size and should therefore show identical pathfinding (other things like attac animations certainly make a difference in worker behaviour, but should not influence actual pathfinding) - but in the different collision box sizes of main buildings and gas gathering facilities for Zerg, Terran and Protoss:
Workers need to move to the collision box of a building (or mineral patch, but they have full collision size) to gather or return minerals, and they will respawn just outside the collision box when leaving a gas gathering facility, resulting in different worker path finding depending on their race.*** This section mentions some things that people tend to make a big deal - and false assumptions - of, but should not, because they reall do not matter. So it does not really matter that much itself, and you can skip ahead if you are short on time. I. Naive assumption: Worker pathfinding is determined by the relative position of a resource unit (gas gathering structure/mineral patch) to the main building (Hatch/Nexus/CC) This assumption is what all articles and advice on resource placement I have ever read is based on. Obviously no one ever considered to test or at least question this assumption, probably because it seems plausible and maybe ecause it isn not even entirely wrong. But the problem is, that is also is not entirely right, in fact it is quite far from right. Besides the relative position to the main building, the absolute position on the map (the x/y coordinates the resources are placed on), the map itself (i.e. different maps may have different worker behaviour at the same spot) and probably the map's terrain also have a noticible influence on worker behaviour. II. The "gas issue" is completely solved From (I) directly follows that this is only partially true. It also follows that it is not possible to determine the mining rate of a geyser solely on its position. ***What you can get is a reonable expectation for how efficiently a geyser will mine ingame***. However, every geyser still needs to be tested manually, to determine its actual mining rate. III. There is a method to place balanced mineral formations on a map from the get-go From (I) follows... Yep, same story! Some say, just copy "pro" mineral lines, and you'll be fine. Nope. If it were that simple, why would kespa mappers bother to create new, different mineral lines for every new map, instead of just recycling the old, "proven" ones? Others just mirror their mineral lines, assuming that'll do the job (JungleTerrain does this a lot on his maps). Of course you can use either of these methods to get initial mineral formations as a starting point, but what you get will just be as good or bad as any other formation you could place down. So my advice would be to just place something that looks pleasing. This section just introduces some terminology I will use throughout the main sections of this guide to refer to certain worker behaviours and methods to fix them. If this just seems to like incomprehensible techno-babble right now, I suggest you do the reasonable thing and skip this part and read the following parts first, it'll make all much more sense to you after that.
Let's first have a look at mineral mining. The problem of balanced mineral mining is more complex, than it seems at first, because of the problem of different saturations: -subsaturation: less workers than mineral patches, mining rates vary, depending on the patches used. -single saturation: exactly one worker per patch, no migration occuring -medium saturation: More workers that mineral patches (typically between 1.5 an 2.5 workers/patch), a lot of migration is happening. -peak saturation: the point, where all mineral patches are constantly mined from, little migration, because of the lack of free patches to aquire -oversaturation: more workers on a mineral formations, than required to saturate it. Because of different migration behaviour, it is not guaranteed that two mineral lines are equally balanced for all saturation levels. However, the good news is, that bad mining outputs are strogly linked to bad worker pathfinding bugs and can reliably be fixed by eliminating all bad worker behaviour. Let's talk about the easy case to balance first: For medium to high saturations, the major cause of slow mining is rear migration. You don't need a fancy animation for that, do you? A simple picture will suffice, you know what I am refering to - this(!):  Workers do this a) because BW pathing algorithm is really bad drugs, and they feel like tripping or b) because the shortest path from one mineral patch to another, unoccupied one actually leads the worker behind the mineral formation. Nothing can be done about a), besides actual testing and eliminating problems via trial and error. So always test your mineral lines! (You will hear that a lot from me in this article...) Fixing b), however, is pretty straight forward, because it is mostly determined by how the gaps in your mineral formations are made up: Most liklely good:  maybe good - or not...:  Seriously inviting trouble big time:  As a side note, your resources should always be placed in a way that makes it unambiguous, where the main building should be placed, because if there are multiple good positions for the main building, you either have to debug you resources for all those positions, which is hardly possible, or force players into a situation, where their mining rates are somewhat luck based, or very detailled map knowledge is required, to know where to place the main building of a certain expansion. The other interesting case to have a look at is the single sturation, not because it occurs often or for extended durations in actual games (it's very important to balance it though, because sub-to-single sturation is what you'll see in typically ZvZs, though), but because of the fact that all mineral patches are occupied, but there is no migration. In this case slow mining is without exception caused by worker pathing bugs, most notably detours and far returns. By eliminating all mineral positions and changing one's mineral formations around, until there are no worker pathing bugs occuring any more, mineral lines can be balanced (almost) perfectly for the low saturation case. Moved back and diagonal mineral pathces will always mine a bit slower, but as long as you don't go really weirdo and strategically place minerals only on the edges or something like that (JUST DON'T!), there shouldbe no balance impairing effect. You can always slow down minng rates, by moving minerals back, though, if required. Most of you with Brood War mapping, or playing, experience probably have a pretty good idea what I am talking about now. For the rest I have brought some animations, showing actual footage of worker behaviour in the wild. So let's start by having a look at what your workers' mining should look like:
So what could possibly go wrong here? Watch what those little buggers are fooling around when you don't watch them... Or if you watch them, they are that ill-mannered...
And there are some additional complications: Worker orbits are not neccessarily stable. Most of them are, meaning that worker will always take the same paths to and from the minerals; and will soon graduate back to that stable orbit, if you manually order them to approach a mineral field from a different angle or go along a different path. Some orbits are just metastable however, meaning that there are multiple stable orbits that a worker can obtain, some of which are ususally bugged. Getting workers from a bugged orbit to a good one requires manual microing from the player, but the worker will stay in the good orbit after that. Most often this happens with the outmost minerals of a formation, because the others restrict pathing to each other too much to allow for multiple orbits. These do not neccessarily need fixing, if it is the good orbit that is automatically acquired through worker migration.
Finally, sometime orbits are just unstable, meaning that a worker will show a different behaviour on adjoining trips. These have periodicities, in which a worker goes through all the stages, that can from 2, as shown here, to 3 or even higher, so you should watch your workers very closely for quite some extended period of time, to make sure you haven't got one of these.
Balancing gas means balancing mining rates for 3 workers (which automatically balances mining rates for or two workers as well), because with 4 workers on gas one can gather the maximum rate of about 308 gas min-1 (a minute means game minute, of course, not a real time minute) from almost all positions. Balancing gas has somewhat more aspects top it than balancing minerals, which is, as pointed out in the previous section, strictly about preventing worker pathfinding bugs. However, just as with minerals bad mining behaviour can for the most part be linked to bad worker pathing. However, there is one additional complication with gas, which is the fact that a worker does not just go to the geyser and back, but actually enters the processing building to pick up gas and respawns after some time... And just as pathing is screwed up, the SC engine more often than not has trouble figuring out where a worker should actually respawn as close as possible to the respective main building, to minimize travel time. Another consequence of the act of respawn is, that orbits for gas gatherers always shift around by some degree, because workers only respawn out of collision of any following worker returning or waiting in line. As mentioned before, just knowing where a geyser is, relative to the main building, does not absolutely determine worker behaviour, and therefore gathering rates, but there are expectation values, i.e. a certain optimal worker behaviour that is linked to an expected mining rate for that position. It's not what you can be sure to get, but at least it is what you can hope for. My ultimate goal is, to link standard worker behaviour to expected gatheringrates for different positions, as well as providing as many animations as possible to document what worker behaviour should be like, as well as common pathing bugs, to allow reliable debugging based on worker observation (which is much quicker than actual mining rate tests). However, even going by the resonable assumption that geysers are always placed as close to the main building as possible, there are 50 different gas positions. Fortunately they can be narrowed down pretty effectively. First of, it is long known that there are only 3 gas positions that achieve gathering rates reaching the maximum output rate, i.e. about 300 gas min-1:  These should be used for all mains, because they have plenty of space and relative gas positions are little important for balance, whereas gas mining rates are, espcially in low economy matchups like ZvZ. However, as mentioned before, putting the gas in those positions does not gurantee an outcome. Pathing bugs are possible and will impair the mining rate of any affected geyser. For details, I refer you to the case by case anylysis below. For solutions, read the section about debuging procedures below. Another thing that is universally true, is that all positions that do not have any vertical ot horizontal overlap with the main building are just plain bad, because they force diagonal worker pathing, which is always much slower than straight vertical or horizontal travel. This leaves, give or take, these positions as potentially promissing.  I'll break them down clockwise, going from hardest (which are the right positions) to rather easy (top position). right gas positions Gas positions on the right of a main building entail two peculiar complications: - a far respawn bug, that makes mining rates the slowest for these positions, but can be fixed - terran comsat stations are build on this side; and further exacerbate the already abysmal worker behaviour seen at these positions.
Conclusion: Use the first position with a doodad fix whenever you can by any means arrange it... bottom gas positions These positions mine pretty slowly, compared to top and left positions, for reasons that are entirely inexplicable. It just seems like workers are somewhat moving more sluggish here, an issue that cannot be fixed by any means.
Conclusion: Centre position seems best, but this location is kinda odd, and I'll wait for further findings about actual mining rates, before drawig a final conclusion. Just so you know: Plastering most of your geyser in unwalkable (doodad) tiles can fix almost anything, but it is a really awkward solution... left gas positions These positions are genrally very good. Mining rates are minimally slower for Protoss, because collision box of Assimilators is cut out pretty far on the side (which is why Troy gates work). However, this is also somewhat true for top posions.
top gas positions
This section will describe the most important procedures you should employ to balance and debug your maps' resources I. Worker tracking method (minerals and gas) This method solely relies on observing worker behaviour and tracking down and fixing all found pathing bugs. It is the best all-purpose debugging method and has proven to be reliable and more tim efficient than any other method (because you do not need any long-period mining tests or numerical analysis). You can reliably balance mineral mining rates with this and find bugged geysers as well. It's not refined enought to suffice for gas balancing though (except for main gas positions), but I am confident that with incresing knowledge of the finenesses of gas gathering that can be achieved just as well. Step by step guide. 1. Preparation: - finish your map (terrain etc.) - place your initial resource formations at all expos. Observe some basic rules:
2: Debugging procedure: 1. Open single player game, select Zerg (seems most prone to pathing bugs; is most crucial to be balanced, because of low-econ nature), chose one computer enemy (or you cannot make a game) 2. Enter cheat codes: "Show me the money" (+10000 minerals & gas), "operation cwal" (fast building), "food for thought" (prevents supply block), "power overwhelming" (god mode), "staying alive" (so you can kill the AI enemy without ending the game) 3. Rush some basic military units and send them scouting/killing the computer player, while pursuing your test procedure 4. build a main building and gas processing building at all expos 5. single-saturate all expos (1 worker per mineral patch, 3 per gas geyser) 6. watch worker pathing for each expo, make a list of all bugs you find (I usually just scribble them on paper, using som somple code, like "3rd9-4" [meaning 4th mineral patch clockwise at 3rd at 9 o'clock is bugged]) 7. After single sturation testing is done, repeat the same with double saturation (~2 workers/mineral patch, this causes a lot of worker migration), make a list, like before, of all spots where worker migrate behind mineral lines 8. End the game, open the map in SCMDraft and permutate all bugged positions you found (i.e. move the affected resource units around)
9. Rinse and Repeat the testing for all expansions that were previously bugged, until finally all bugs have been fixed (it is a trial-and-error method, but the decreasing amount of expos to be tested each round makes it pretty time-efficient) 10. Now do the whole procedure again for Protoss and finally Terran. Remember to also retest all expos for the other races, if you need to make further changes. II. Timed mining test (gas) This method was mostly developed by TechnicS, when he helped me test the BWMN Open maps. It is designed to give you reliable information about actual 3-worker gas mining rates on different locations. We used it to test mining rate balance for the naturals, and I consider it a good idea to do that, until hopefully the worker tracking method for gas is refined enough to allow appropriate judgement. Testing procedure: 1. Open single player game with one computer enemy, select whichever race you want to test 2. Enter cheat codes: "Show me the money" (+10000 minerals & gas), "operation cwal" (fast building), "food for thought" (prevents supply block), "power overwhelming" (god mode), "staying alive" (so you can kill the AI enemy without ending the game) 3. Rush some basic military units and send them scouting/killing the computer player, while pursuing your test procedure 4. build a main building, a gas processing building and 3 workers at all expos you want to test 5. Move all workers close to the geyser and assign each group to a hotkey 6. Order them all to start gas mining at the same time (i.e. go through all the control groups and right-click on the geyser as fast as you can) 7. Wait for 5 minutes (you can use any other time span, of course, but 5 minutes is pretty resonable; do something else in the meantime: work on another map, surf the internet, make a phone call, have some lunch, or a shower...) 8. end the game 9. load the replay and run it to the exact moment where your workers start mining (remember that time) 10. fast forward the replay and stop it at the point exactly 5 game minutes (or whatever time you chose to test) from there and stop the replay 11. Note the amount of gas remaining at that time on all geysers you tested. 12. Calculate ((starting amount of gas on the geyser)-(remaining gas on the geyser))/(time mined) to calculate mining rate (around 300 is perfect, everything above 275 is good, below 260 is bad) I also used this to test the natural geysers of some recent and popular kespa maps; and seeing how bad some of them fare, it seems pretty safe to say that they don't know anything that I don't know. These are my results so far:  III. Build order timing test (minerals) Another test method suggested by TechnicS, used to test if mining rates for main minerals are balanced. It's pretty stright forward, you just compare timings of certain build orders for different locations. You can do that by either using a launcher that has an inbuild ingame timer, using the replay timer, or just using multiplayer and comparing timings for different locations with another player, by the first player who reaches a certain step pausing the game and comapring the amount of banked minerals at those points. Testing procedure: 1. Open game, depending on which kind of actual timer you use 2. Execute your test build order (suggestion for Zerg: 9 Ovi, 12 Expo, 11 Pool; for Protoss 8 Pylon, 11 Forge, 14 Nexus; for terran: 9 Depot, 11 Rax, 14 CC), compare timings for each step. I consider this kind of testing obsolete for practical balancing purposes, because worker tracking has proven reliably to provide very good results at this test. There are still some things that need further testing; and I'll definitely write this section, when I am actually motivated to do so ;) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Comments:
| CrystalDrag |
| :DD This needs to be Bold Title in the Articles, will be so important. And maybe Red. Your animations are awesome :D modified by CrystalDrag |
| JungleTerrain |
| nice! thanks freakling... also, does the mineral type 1,2, or 3 have any effects on pathing? just wondering and thanks for the shout-out haha Im the example of what not to do :) |
| Freakling |
| No, mineral types are only different sprites, otherwise identical. And you are not an example of what not to do. It just doesn't matter whether you mirror your mineral lines intially or not, because chances are that eventually you'll end up with something completely different anyway. I'd just advise you against copying mineral lines from other (p.e. kespa) maps, because that's obviously not worth the additional work it makes. |
| traceurling |
| Haha I noticed your first comment became the last xD also for some reason some but not all of the pics are brokeb And your comment is broken still lol modified by traceurling |
| Freakling |
| OK, still a mess, but the most important parts are out now, you can start debugging. It's really all just about workers going bananas, and you have to stop them. :P Made the title red, because Crystal urged me to ;) modified by Freakling |
| traceurling |
| Nice write up...also, you should mention for the gas timed test, set the speed to slowest since you're in single player, then set them to start mining, then set speed to slowest to minimize difference... This forum is gonna look like a rainbow modified by traceurling |
| Freakling |
| We're actually a gay forum, didn't you know ;P You're right, I actually did reduce the speed to slowest... |
| CrystalDrag |
| Ah yes we are a gay forum... When freakling started using green after I started using cyan. :3 Good job with the red text. ^^ Very good job with the article. I did the exact same procedure with TERU ._. But i did something else... 1. Saved the same finished map except for testing as "(4)TERU(g)" [g = gas, m too close to n] 2. Deleted all the map triggers, set player 2 to computer, move his start location to an unused area, and unchecked all "randomize spawn location" 3. Save the file again as "(4)TERU(g)" 4. Saved the file as a new one as "(4)TERU(t)" [terran] 5. Went through all the expansions and put a command center where the CC should be... and copy and pasted 9 scvs towards all the expansions. 6. Then just tested each minerals, not using SCVs when appropiate... Wrote down which ones were bugged. Then your steps 5-8. Then do step 4-6 except for the other two races. Once satisfied with the minerals, i then went back to "(4)TERU(n) and changed all the minerals fields appropriately to mirror the bug free minerals. Tying in cheat codes and steamrolling over computers can be quite boring. :P modified by CrystalDrag |
| Freakling |
| That's it so far, not very helpful yet, But hopefully entertaining enough to put you off a bit more. Second part, about gas and actual debugging procedures, will hopefully be done by tomorrow. And why is the post order screwed up like this O_o?!!! modified by Freakling |
| panschk[FP] |
| Wow, I'm impressed:) |
| JungleTerrain |
modified by JungleTerrain |
| JungleTerrain |
| None of the graphics are working for me, and this page takes so long for me to load... |
| Rickv100491 |
| Is there gonna be a new version of this article? or maybe some new pics, because some don't appear I think... although it is really good article, I always read it, with the new version of scmdraft, Is this article gonna be renewed? just asking :) |
| NastyMarine |
| Another great article! Keep them coming! |
| Chef |
| Many pathing errors are both caused by the player and can be fixed by the player. I can't say without repeating your tests with as much thoroughness as you have, but I think a lot of your 'sometimes this happens' statements can be the cause of sending a peon to mine from a particular direction. You often see good players do this in FPVODs at least at the start of the game. Your misconception #1 is not based on hearsay, I believe that a lot of that info is from an extremely well worked out paper with more testing than you have done even here. One of its interesting findings was that neo forte's naturals had the most efficient setup for mining. I am not sure if that article is still on the internet for download, but it was very good and you'd be interested in it. Still, if your method gets you results, it can't be too bad ;p |
| JungleTerrain |
| CardinalAllin is so poetic |
| traceurling |
| Will the Catholic Church persecute us for being rainbow? |
| CardinalAllin |
| Broken comment modified by CardinalAllin |
| CardinalAllin |
| Broken comment modified by CardinalAllin |
| CardinalAllin |
| For example; On gemlong you can pylon prison workers much easier on the two south mains than on the two north ones. I think this is an important factor relating to mineral formations balance. Another balance factor relating to mineral formations is the option to trap a probe behind the minerals for corsair stacks in PvZ. Often I see maps where some spawns are able to do it and others arent. This has the capability to decide games, I think its worth mentioning here. modified by CardinalAllin |
| Freakling |
| More editing time, less in-game testing time. I guess it depends on what you prefer... I'll update the guide with alternative procedures. |
| CardinalAllin |
| Thankyou very much for sharing all this information. Some of the animations are blank for me too. 3 mineral ones: (Mining Mineral sequence/Erratic/Unstable orbit) 2 gas ones: (Bottom left gas doodad bug/left gas) Regarding the right gas, I think you have displayed the wrong animation for the 4th one labelled "It also helps SCVs dealing with comsats a lot!" Just to check but do you know that you can test play a map on your own by closing the AI slot during the 5 second countdown. Then just click 'Continue playing' and you dont need to worry about being attacked by the ai. May I suggest putting a concise Quick Reference section at the Top of the article. This will mean in future when someone comes back to the article to check the basic rules, they can quickly see them straight away. eg Gas on the right: Place inline with top edge of townhall and put a 2 tile doodad below it. I do think this issue is important. It does matter if you get more mutas out than the other person in a zvz etc. However, I think it needs to be noted that there are more important issues that affect balance to a much larger degree that dont have their own articles. But, I really am happy that Im lucky enough to be able to learn more about BW in ways I never expected. Ive probably got more to say, but Ive run out of time for now. So again, thankyou. |
| M1nerals |
| im the biggest bird modified by M1nerals |
Add your comment:
 |