|
I'm messing around with a potential new feature for ScmDraft: real time preview of the paths units would take on a map from A to B. I was wondering whether this would be considered useful for anything other than me just having fun.
I could see it being used to verify wall-ins, but this is an overkill solution to that problem. It may also locate some degenerate pathing cases. But it will still be a lot of work to get fully functional, even with a ton of the groundwork being done thanks to TSCMoo letting me base my implementation on the OpenBW one.
This is what it looks like now, it displays the path the selected units would take to the point under the cursor, and is continuously updated as the cursor moves.
![[image loading]](https://i.imgur.com/iLrrwnG.jpg)
Direct Link
They don't appear to take the shortest straight line path, but I believe the results accurately match what the game does.
![[image loading]](https://i.imgur.com/HXVSm0W.jpg)
Direct Link
This was from a previous version with predefined endpoints:
![[image loading]](https://i.imgur.com/AkF2Uc9.jpg)
Direct Link
The extra sidetrip appears to match what SC does from in-game testing. I guess the marine likes to go sightseeing.
E: No idea why the images work when previewing the post, but do not work when viewing the final one, just click em, they work.
|
You can upload images directly to TL via imgur, or go on imgur yourself. You probably have image linking disabled on the site?
As far as utility, I'm not sure how much benefit there would be to players in general since if you wall, you want to wall tight usually, so it doesn't matter where the enemy is coming from. Also, I think players tend to send multiple commands at least in the early game which in theory would change the path trajectory? Interesting anyway.
|
Hi S.I., great to hear that you are still working on it.
Are you kidding? Of course this would be useful (and not just for your own nerd fun). Some examples:
- automatically measure scouting distances/durations (so displaying the calculated path length in both pixels and game seconds would be great)
- quickly evaluate shortest paths around a map
- evaluate how static obstacles (like neutral buildings or mineral walls) affect pathfinding around the map.
- getting exact mining paths and distances in the editor (would this take accelerations and turning rates into account too? – then we could finally get to a point where mining rates could actually be calculated frame-perfect in advance to allow for perfect mineral line balance)
From your description I guess this will just progressively simulate the pathfinding, taking into account the terrain pathfinding regions and static obstacles (pre-placed units or unit sprites)?
Not sure which "degenerate pathing cases" you have in mind, but there are a ton of possible fringe cases to consider:
- different kinds of neutral units (including unit sprites, because that's how most units need to be placed for melee maps) etc,, including Troy Gates, Scarab Holes or not
- restricted chokes (815 ramps, Blue Storm chokes, Scarab-only chokes [example map])
- on the other Hand it is actually possible to generate passable chokes between non-connected pathfinding regions [example map]
Ideally this would work without the need to place actual units though (or cleanup work would be required every time afterwards). But I guess due to differences in bounding boxes unit type is actually important, so maybe you can use "virtual units" (that are not saved in the map file).
Air unit pathing is of course pretty trivial, but having a range/duration display would still be good (e.g. for measuring Overlord scouting distances).
Another important related feature would be to have a proper range display for Reavers to better detect Reaver jam locations. Having a complete debugging algorithm that automatically classifies all pairs of tiles within a range of 8 by their real distance to pathfinding heuritic distance quotient would be ideal, of course, but just having it for one tile at a time would already be very helpful.
I probably forgot as many uses for advanced pathfinding analyzing tools as I mentioned, so yes, everything in that direction would be very useful and welcome tools, maybe the most important new feature that could be added to ScmDraft at this point (pathfinding regions alone have already been completely ground-breaking), given how much of melee map making revolves around pathfinding optimizations (and how little fun doing that part of it actually is, compared to doing deco  ).
So, yeah, go ahead. Please. Already looks promising.
|
Yeah, this could actually be game-changing if players knew the exact amount of time it takes for a particular unit to travel a certain distance. I'm 100% for you to continue doing this.
|
I can't think of the full breadth of utility of this but I would be interested to see what you and other people more knowledgeable than me will find.
Additionally, this is the first time i've seen Freakling impressed and excited. So you're really onto something here :D
|
If I get that tool that would like a natural check list for me before playing any important match on a particular map to select the right build.
|
Croatia8146 Posts
This would be very neat and useful! It'll be really nice to verify some of the intricacies of BW's path finding algorithm.
Btw, the images wouldn't load because TL was trying to load them through HTTPS, and the SSL certificate of that server has expired (or has never existed). I rehosted your images on imgur so they show up, hope that's ok.
|
Another huge thing about this is that we can already see from screens how bad pathing is, so by putting these lines against some of the most common paths for scouting or rushing with single marine / zealot / vulture you can know that you have to manually optimize it to get few extra seconds on your attack. (and doing it manually is nothing new but its seldom that people realize how much it can help you)
|
This is amazing for mappers tho!
|
Yes, those paths in the images look exactly like how units move in-game ;P
I suspect I'd actually like pre-defined end points better than having my mouse permanently bound to it. Some defined pre-settins (like SL to SL paths) would be helpful too.
I am curious what main to main Dragoon paths on Blue Storm or Arkanoid look like with the current level of implementation. Could you maybe post some screenshots?
|
On December 11 2018 01:30 Freakling wrote:Yes, those paths in the images look exactly like units move in-game ;P I suspect I'd actually like pre-defined end points better than having my mouse permanently bound to it. Some defined pre-settins (like SL to SL paths) would be helpful too. I am curious what main to main Dragoon paths on Blue Storm or Arkanoid look like with the current level of implementation. Could you maybe post some screenshots?
That's actually a great point, I want to see if there is some sort of stable pattern that the Dragoon starts following, how it gets to said pattern, etc. Heat map?
|
Freakling: A lot of those things are 4 or more steps down the road from having this feature complete. Right now this is just a very first proof of concept, bolting together two completely different subsystems, and getting this to work accurately has taken 3+ weeks. It'll be at least twice that to integrate it properly, so don't hold your breath ;(
On December 10 2018 19:17 JieXian wrote:
I can't think of the full breadth of utility of this but I would be interested to see what you and other people more knowledgeable than me will find.
Additionally, this is the first time i've seen Freakling impressed and excited. So you're really onto something here :D
You should have seen him when I first added the pathfinding region display.
On December 10 2018 20:18 kogeT wrote:
If I get that tool that would like a natural check list for me before playing any important match on a particular map to select the right build.
I hope this just doesn't end up adding too much overanalysis of maps to the game.
On December 10 2018 20:59 2Pacalypse- wrote:
This would be very neat and useful! It'll be really nice to verify some of the intricacies of BW's path finding algorithm.
Btw, the images wouldn't load because TL was trying to load them through HTTPS, and the SSL certificate of that server has expired (or has never existed). I rehosted your images on imgur so they show up, hope that's ok.
I don't have HTTPS on my site, that explains it. Didn't want to deal with the added expense back when I configured my hosting
On December 11 2018 01:48 Jealous wrote:Show nested quote +On December 11 2018 01:30 Freakling wrote:Yes, those paths in the images look exactly like units move in-game ;P I suspect I'd actually like pre-defined end points better than having my mouse permanently bound to it. Some defined pre-settins (like SL to SL paths) would be helpful too. I am curious what main to main Dragoon paths on Blue Storm or Arkanoid look like with the current level of implementation. Could you maybe post some screenshots? That's actually a great point, I want to see if there is some sort of stable pattern that the Dragoon starts following, how it gets to said pattern, etc. Heat map?
Looks like this (Note, this is not doing inter unit collision, grouping, etc):
![[image loading]](https://i.imgur.com/ssuJK7c.jpg)
Basically the pathfinder finds a rough path (long path) which goes through the cliff gap, and when calculating the exact pixel based path (aka short path) it gets stuck because the dragoon doesn't fit through the gap, and the pathfinder resources are restricted in such a way that it doesn't find the long long way around over the main ramps.
|
I like to read you guys , even if i am not a mapmaker at all 
|
Oh and here is the other main. Behaves the same way. I haven't tried it in-game yet, so I do not know how accurate it is, but I expect it to be identical, except the real pathfinder may give up earlier. The red line is connection between the end of the path and where it is supposed to go.
![[image loading]](https://i.imgur.com/uVXRlji.jpg)
|
On December 11 2018 05:06 prosatan wrote:I like to read you guys , even if i am not a mapmaker at all
Me too
|
Your first Blue Storm screenshot has all thew doodads missing for some reason…
On December 11 2018 09:11 S.I. wrote:Oh and here is the other main. Behaves the same way. I haven't tried it in-game yet, so I do not know how accurate it is, but I expect it to be identical, except the real pathfinder may give up earlier. The red line is connection between the end of the path and where it is supposed to go.
Interesting that it givers up at some point. Probably after walking through the same cycles a few (lots and lots of?) times? Sometimes units seem to wander around "aimlessly" virtually forever, sometimes they don't. I thought the only case where they would default back to stop command to be when they are actually completely blocked by other units in close vicinity (annoyingly this tends to happen when moving a tightly packed army consisting of multiple control groups as well).
Your pathfinder is accurate, though, jusdging by in-game behaviour – with one exception: Yours does not take unit collision (in this case with minerals) into consideration, but I guess I don't need to tell you Anyway, can you also make a screenshot with the paths a Goon would take from the very centre of the map to either SL?
|
So no more Blue Storm in the future I guess xD (jk) (kind of serious)
|
Are you able to compute the time required to travel the path after having found the path? That would be very interesting and useful.
|
Obviously just a matter of calculating path length / unit speed.
|
On December 12 2018 01:09 Freakling wrote:
Your first Blue Storm screenshot has all thew doodads missing for some reason…
Artifact of map unprotection, is fixed in the newer screenshots I hope
On December 12 2018 01:09 Freakling wrote:
Interesting that it givers up at some point. Probably after walking through the same cycles a few (lots and lots of?) times? Sometimes units seem to wander around "aimlessly" virtually forever, sometimes they don't. I thought the only case where they would default back to stop command to be when they are actually completely blocked by other units in close vicinity (annoyingly this tends to happen when moving a tightly packed army consisting of multiple control groups as well).
I'm not sure whether the "give up" criteria I have in the editor match the ones in starcraft, but having the editor hang forever or really really slowly run out of memory just because you hovered over the wrong pixel is very bad UI design
On December 12 2018 01:09 Freakling wrote:Your pathfinder is accurate, though, jusdging by in-game behaviour – with one exception: Yours does not take unit collision (in this case with minerals) into consideration, but I guess I don't need to tell you Anyway, can you also make a screenshot with the paths a Goon would take from the very centre of the map to either SL?
Yep … units are now taken into account, but it doesn't have a nice fast lookup for nearby units, it has to loop over all units on the map all the time which is time consuming. Again, just a proof of concept.
This is basically the limit of where you can order it to move where it takes a "sane" path:
![[image loading]](https://i.imgur.com/bwg7WsX.jpg)
Closer to the ramp it takes detours. Changing the target by single pixels vastly changes the path taken
![[image loading]](https://i.imgur.com/0RNuy9G.jpg)
A few more detours, and an example of how quickly the path can change (The path gets worse even thought the target coordinate is closer to the start):
![[image loading]](https://i.imgur.com/XaKUSvW.jpg)
![[image loading]](https://i.imgur.com/ub1EuWr.jpg)
And at some point it no longer reaches the destination (within the step limit)
![[image loading]](https://i.imgur.com/V4h0hZb.jpg)
On December 12 2018 03:13 JieXian wrote:
Are you able to compute the time required to travel the path after having found the path? That would be very interesting and useful.
It's still missing unit speed, acceleration, etc, but at some point yes.
|
Yep, that's very similar to what I have observed in-game.
|
What if dragoons communicate by dancing across the map and you just cracked the code?
|
If I increase the resource limits significantly, the dragoon will (almost) always find a path, but ends up still taking the detour. The detour can probably be avoided if the detailed path is calculated with a larger long path look ahead jump, but both of these end up using a significant amount of additional CPU time so I can understand why the pathfinder was tuned the way it is.
|
|
|
|
|
|
WCS
