|
5390 Posts
On February 24 2020 20:31 juvenal wrote:
I play since the game released and have no idea what pathable terrain is. Agree with LML, just be nice and tolerant to each other folks.
pathable = walkable = the square is green in the pics above
Or, if you want to understand pathing in more depth (and grow your e-penis length for future measuring contests) give this a read:
https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack
|
Croatia9497 Posts
On February 24 2020 19:42 pebble444 wrote:
this thread escaladed pretty quickly
Very nice.
|
On February 24 2020 18:47 LML wrote:
Why does everyone who has the knowledge about it feel so superior and has to write in such an arrogant and condescending way, instead of explaining it in a normal manner? Clearly the person asking isn't familiar with the ins and outs of map making.
Some things never change.
Anyway, I guess what Freakling is trying to say is you need to learn how to make a good wall with the tile. One picture of a ZvZ wall making use of the tile would have been worth all the words in this thread. At least it's easy enough to test since you can make the zerglings yourself. It looks like any wall with the tile is going to be slightly less effective since more surface area of the spawning pool is exposed, but it's not the biggest deal... incidentally, it looks like that also might increase the surface area of the sunken on the inside. I guess it depends if you built the pool above or to the right, and whether or not that affects gas mining if you build the sunken also to the right so the whole geyser is covered.
|
Sorry if my explanation was too hard to understand. If it's just words confusing the matter and you want a picture, here are some right from out of SCMDraft.
Grey terrain is unwalkable ("unpassable" microtile flag overlay), red tiles are unbuildable ("building placability" (sic!) tile flag overlay). Yellow borders show pathfinding regions, red rectangles are unit collision boxes.
Again note: unwalkable (on at least one minitile) implies unbuildable, but Creep spread solely depends on the buildability flag, hence even spreads over and on top of (partially) unwalkable tiles.
Here's how it looks on bottom left and how to wall against Lings with the Pool:
+ Show Spoiler [Show image] +
Here's how it looks for bottom right.
+ Show Spoiler [Show image] +
And here how it looks with the unwalkable tiles replaced by standard terrain tiles, note the changes in the surrounding pathfinding region layout:
+ Show Spoiler [Show images] +
I would explain to you how this layout is bad and causes bugs, but only it does not, it is perfectly fine, so those awkward tiles would actually not even be needed in this case. I suspect they were added to balance an older map version, before some of the other terrain changes the map underwent, and then kept in as just an editing artifact.
|
On February 24 2020 18:47 LML wrote:
Why does everyone who has the knowledge about it feel so superior and has to write in such an arrogant and condescending way, instead of explaining it in a normal manner? Clearly the person asking isn't familiar with the ins and outs of map making. I agree. Instead of the small community looking to create a good space for discussion, it become increasingly insular instead.
|
On February 25 2020 02:04 Freakling wrote:Sorry if my explanation was too hard to understand. If it's just words confusing the matter and you want a picture, here are some right from out of SCMDraft. Grey terrain is unwalkable ("unpassable" microtile flag overlay), red tiles are unbuildable ("building placability" (sic!) tile flag overlay). Yellow borders show pathfinding regions, red rectangles are unit collision boxes. Again note: unwalkable (on at least one minitile) implies unbuildable, but Creep spread solely depends on the buildability flag, hence even spreads over and on top of (partially) unwalkable tiles. Here's how it looks on bottom left and how to wall against Lings with the Pool: + Show Spoiler [Show image] +Here's how it looks for bottom right. + Show Spoiler [Show image] +And here how it looks with the unwalkable tiles replaced by standard terrain tiles, note the changes in the surrounding pathfinding region layout: + Show Spoiler [Show images] +I would explain to you how this layout is bad and causes bugs, but only it does not, it is perfectly fine, so those awkward tiles would actually not even be needed in this case. I suspect they were added to balance an older map version, before some of the other terrain changes the map underwent, and then kept in as just an editing artifact.
Interesting. Functionally is a 'pathfinding region' really just a point in some instances? I imagine it might work like, you click a point anywhere in the map to make a unit move there, and then to pathfind it works out the lowest number of regions to go through to get there and then units go from point to point along that path until they end up at the last region and go to the point you clicked instead for the last one. And then I guess you're saying the size or shape of regions can be different depending on the unpathable red tiles. So is it ideal if all the minerals and the town hall end up in the same path region, thus they don't have to go to the center of the region before going to the town hall?
Well that's neat.
![[image loading]](https://i.imgur.com/RridUmw.jpg)
I wonder if he will go path A because there's a region in between, or if there is an exception when a beeline can be made with no red regions in the way and he will take path B instead... And if that's so, why peons don't get that exception when they're mining. I haven't played in many years so I don't remember how funny the pathing gets... it looks like if you just click a little ahead it would always work out, and clicking two regions worth might be more than a screenful enough of the time that you don't notice. Oh well, it will just have to be an unsolved mystery 
|
I like to read these kind of threads !
Now i will go back to my all time friend map FS ! No problems there 
|
On February 25 2020 21:45 prosatan wrote:I like to read these kind of threads ! Now i will go back to my all time friend map FS ! No problems there
Except for tons of pathfinding related issues :
Mining bugs in about half of the bases, some random Reaver jams, a ramp vortex...
@Chef: It is not an unsolved mystery. But to explain to you exactly how it works would take a few paragraphs and a couple of screenshots, so I cannot do it till I am back at home.
|
On February 25 2020 22:27 Freakling wrote:Show nested quote +On February 25 2020 21:45 prosatan wrote:I like to read these kind of threads ! Now i will go back to my all time friend map FS ! No problems there Except for tons of pathfinding related issues : Mining bugs in about half of the bases, some random Reaver jams, a ramp vortex...
Yeah , I remember a pro game where dragoons got stucked on a ramp, on FS. They are so clumsy haha
|
On February 25 2020 22:30 prosatan wrote:Show nested quote +On February 25 2020 22:27 Freakling wrote:On February 25 2020 21:45 prosatan wrote:I like to read these kind of threads ! Now i will go back to my all time friend map FS ! No problems there Except for tons of pathfinding related issues : Mining bugs in about half of the bases, some random Reaver jams, a ramp vortex... Yeah , I remember a pro game where dragoons got stucked on a ramp, on FS. They are so clumsy haha
Not the goons' fault, solely an issue with the pathfinding region node on that tamp. Affects all ground units equally.
|
Bisutopia19229 Posts
"You can be mean to me as long as you teach me a lesson." I tell my wife the same thing. Fantastic thread!
|
On February 26 2020 01:26 BisuDagger wrote:
"You can be mean to me as long as you teach me a lesson." I tell my wife the same thing. Fantastic thread!
The only thing that really bothers me is that the OP does not seem to even have put in the two minutes of in-game investigation it would have taken him to figure out a few things himself.
Sorry Chef, I do not feel like writing a complete guide to BW pathfinding today, so here's a bare minimum version to address your specific question:
As a start, if you really want to delve a bit deeper into it, I suggest you read further here (link provided by Sonko).
Broodwar uses a variation of the A* algorithm described there that works on an irregular grid of regions and nodes.
If you really want to delve deep, of course you can always study the OpenBW code.
So let's have a look at your problem:
First let's see what can actually be seen on the image and get some terminology straight:
+ Show Spoiler [show image] +
Let's colour some regions to make them easier to reference:
+ Show Spoiler [show image] +
So our problem is to find the "shortest" path a ground unit (here represented by a Zergling) can take from a point in the blue region to the cursor marker position in the green region.
Step one is for the game to determine which path is approximately the shortest between those two points. As they are in different regions, the game uses region node distances as an approximation. For our purposes we can easily eyeball the solution for this simple example and get the following path:
+ Show Spoiler [show image] +
So now we know that the Zergling will try to go to the green region via the yellow region and, this is the important part, avoid all other regions, (mostly) travel only in vertical, horizontal or diagonal directions and try to find the most direct path towards the respective next region it wants to reach (as a short distance pathfinding solution). The resulting path will look something like the following (this is only my prediction, feel free to check it in-game):
+ Show Spoiler [show image] +
So the Zergling will move a bit to the side to avoid that little outcrop of the cyan region (crossing which the pathfinding algorithm would consider a detour from the "optimal" route!), then cross the yellow region in a straight line to reach the green region and zero in on the target location once it reaches its destination region.
As another example let's look at the worker mining paths:
+ Show Spoiler [show image] +
The relevant region layout here is very simple – the blue region contains the resource depot and all the mineral fields, the green region contains the geyser and is directly connected to the blue region by a straight line from the right side of the geyser, where workers will respawn after mining. Approximate mining paths are outlined in white.
Let's compare this to the layout with the unwalkable tiles in both bases removed:
+ Show Spoiler [show image] +
Looks a bit more complicated now. The regions have shifted around in reaction to the terrain changes. The green region contains the geyser, the blue region contains the resource depot and some of the mineral patches. There are, however, also some mineral patches in the yellow and red regions. Nevertheless this setup mines just as fine (at least for this layout of mineral patches) – all the regions are still directly accessible by straight line travel, so stuff being in different regions causes no issues.
Finally let me show you an example what can actually go wrong – this is Fighting Spirit 1.3, bottom right natural:
+ Show Spoiler [show image] +
The important point to notice here is that by avoiding the "indirect" route through the red region workers on the bottom two mineral patches are forced into an inefficient mining path (particularly noticeable for Terran with a Comsat attached).
|
Freakling, it didn't even occur to me that the tile was not only unbuildable but unwalkable because all I saw was that creep wasn't spreading. I tried various things and with other races but didn't think to build a space to the right because I didn't imagine it would be ling tight. Maybe my title was a bit alarmist, but it was because I didn't know better. I feel silly that I didn't try your suggestion to begin with. In other words it's not that I didn't try... I just am ignorant with this map making trick. I still think it's not ideal because it makes gas mining slightly worse.
I think highly of your map making knowledge and have spent some time reading your posts so thanks for your reply.
|
Bisutopia19229 Posts
I'm just being silly Freakling. I see where you are coming from and you have a great history of being patient and detailed with people on TL so I'm not judging you. <3
|
It wouldn't had been hard for people to just simply write that the unbuildable tile was unwalkable instead ofall those hostile posts.
|
Thanks Freakling, that makes perfect sense to me. So it starts out with a coarse search to find a path just through the regions, then once it has established the optimal coarse path, it figures out the higher resolution 1x1 squares path where units can move one of 8 directions to navigate the smaller search space through each region.
It looks like in your FS example it's the centre tile of the CC that matters.
|
Whenever Freakling posts s.th., I feel dumb and lazy and know that my possiblities to further improve in this game are limited...
Dankeschön.
|
On February 27 2020 02:08 Chef wrote:
Thanks Freakling, that makes perfect sense to me. So it starts out with a coarse search to find a path just through the regions, then once it has established the optimal coarse path, it figures out the higher resolution 1x1 squares path where units can move one of 8 directions to navigate the smaller search space through each region.
It looks like in your FS example it's the centre tile of the CC that matters.
The centre of the building space (coordinates rounded up, so if the building is an even number of tiles wide or high it will be on the tile down and to the right from the exact centre) is what determines to which tile/minitile, and accordingly region, a building belongs.
|
im missing something here i know i am, but, dont build the pool there?
|
FWIW ZerO also complained on stream about this layout on Escalade saying that he wants to put a pool top left for ZvZ. So I'm not the only one!
|
|
|
|
|
|
EPT![[image loading]](https://i.imgur.com/PWusW7i.jpg)
![[image loading]](https://i.imgur.com/HNsfkGf.jpg)
![[image loading]](https://i.imgur.com/EZavhAX.jpg)
![[image loading]](https://i.imgur.com/iFNz6RL.jpg)
![[image loading]](https://i.imgur.com/Mh63LLw.jpg)
![[image loading]](https://i.imgur.com/5SPSp5g.jpg)
![[image loading]](https://i.imgur.com/HHXIjKq.jpg)
![[image loading]](https://i.imgur.com/oBPyQQi.jpg)
![[image loading]](https://i.imgur.com/WgQcIMu.jpg)
![[image loading]](https://i.imgur.com/Idi8vGa.jpg)
![[image loading]](https://i.imgur.com/r5gb4AQ.jpg)
