EPTTricks with pathfinding - Page 6
| Forum Index > SC2 General |
|
DuneBug
United States668 Posts
| ||
|
Raysalis
Malaysia1034 Posts
 I think checking for natural expansion and especially the scrap station thingy might be a bit broken for certain maps. I think most of this can probably be 'fix' by making small changes to the maps though, since I am not a big fan of increasing the memory require to have the 'perfect' path finding system. | ||
|
hugman
Sweden4644 Posts
On May 03 2011 03:59 Furycrab wrote: ScrapStation thing... is the only legit problem, but it's a map specific thing... If it became a serious issues, I'd rather have one map modified (and it is possible) than throw a wrench in the whole pathfinding. At least not something where I would rush a quick fix. You could do the same thing on Typhon, or on old Shakuras. I don't think it's a problem though, it's equal for all players and you can try to deny LoS to your expansions if you're good. | ||
|
artanis2
United States732 Posts
On May 03 2011 04:30 Raysalis wrote: Wow, you sir are a genius for finding this. I think checking for natural expansion and especially the scrap station thingy might be a bit broken for certain maps. I think most of this can probably be 'fix' by making small changes to the maps though, since I am not a big fan of increasing the memory require to have the 'perfect' path finding system. There would be no performance penalty with the fix. The fact that you don't see their building as soon as it is built is fact enough that the vision information is available. The pathing just needs to utilize it. | ||
|
AzurewinD
United States569 Posts
On May 03 2011 01:51 artanis2 wrote: It is not a hard problem. Dynamic pathfinding that has to update itself in real time across hundreds of individual units, all being aware of each other's positions while attempting to find the most optimal way to any given location at any given time is indeed a hard problem. What sounds easy about this task? Consider the necessary requirements that the pathfinding must be both intelligent and yet also be computationally efficient on a large scale. Now also consider that there can be as many as 8 players in a single game, all controlling up to 200 (not large numbers by computing standards, of course, but exponentially they can be) individual units, all having completely unique map awarenesses that shift on a second by second basis. Thats a big task to tackle. Simply saying "Make it rely on a player's vision" may not be quite so simple a fix when you get down to the implementation. In general, we have no way of knowing what their implementation is. Thus we can't assume anything is a "simple fix" and we certainly can't say that pathfinding is an easy task. | ||
|
artanis2
United States732 Posts
On May 03 2011 04:41 AzurewinD wrote: Dynamic pathfinding that has to update itself in real time across hundreds of individual units, all being aware of each other's positions while attempting to find the most optimal way to any given location at any given time is indeed a hard problem. What about this task sounds easy? Consider the necessary requirements that the pathfinding must be both intelligent and yet also be computationally efficient on a large scale. Now also consider that there can be as many as 8 players in a single game, all controlling up to 200 individual units, all having completely unique map awarenesses that shift on a second by second basis. Thats a big task to tackle. Simply saying "Make it rely on a player's vision" may not be quite so simple a fix when you get down to the implementation. In general, we have no way of knowing what their implementation is. Thus we can't assume anything is a "simple fix" and we certainly can't say that pathfinding is an easy task. Yes, and all of that problem has already been solved. Adjusting it to ignore certain buildings to within a range is an easy problem. For example: ![[image loading]](http://i.imgur.com/Z3Cvv.png) Instead of generating the grey line, they generate the blue line. They do this by creating a path that ignores all buildings that cannot be seen initially, when the vision changes it is recalculated and tacked on to the current path. This can all be done when the unit is first told to move, or incrementally as the vision is adjusted for a unit's movements. Just because you guys haven't solved this kind of problem before doesn't mean others haven't... | ||
|
Raysalis
Malaysia1034 Posts
On May 03 2011 04:46 artanis2 wrote: Yes, and all of that problem has already been solved. Adjusting it to ignore certain buildings to within a range is an easy problem. For example: Instead of generating the grey line, they generate the blue line. They do this by creating a path that ignores all buildings that cannot be seen initially, when the vision changes it is recalculated and tacked on to the current path. This can all be done when the unit is first told to move, or incrementally as the vision is adjusted for a unit's movements. Just because you guys haven't solved this kind of problem before doesn't mean others haven't... Well, from the video, it is quite clear that the pathing system is currently not tied to the player vision at all and the players vision is a completely different system. While it sounds easy, trying to link 2 different system that is not link before is probably more complicated than what we initially perceive to be (from experience). Not saying you are wrong, since there is a good chance that you are right and it is an easy fix ^^. Obviously if they can do what you suggested, Blizzard should do it. | ||
|
ManaO
Italy185 Posts
| ||
|
TheOnlyOne
Germany155 Posts
On May 03 2011 05:03 Raysalis wrote: Well, from the video, it is quite clear that the pathing system is currently not tied to the player vision at all and the players vision is a completely different system. While it sounds easy, trying to link 2 different system that is not link before is probably more complicated than what we initially perceive to be (from experience). Not saying you are wrong, since there is a good chance that you are right and it is an easy fix ^^. Obviously if they can do what you suggested, Blizzard should do it. His solution can even be done in the Map Editor ; and it works with a line of sight pathing. So if Blizzard actual cares, they give us "exactly" his fix. But as we know Blizzard, it will take approx 2 months to get a pseudo fix and another 3 months for a reasonable fix. Just takes too much time ... | ||
|
TedJustice
Canada1324 Posts
I'm not saying it's not possible, but it's not an "easy fix". It's something that would really need to be done carefully, and there'd be a lot of side effects to work out. I'm sure Blizzard was well aware of this problem when they made the pathfinding system. But I do think it should be fixed. If not in a patch, then in Heart of the Swarm. For those people saying "they shouldn't patch out cool tricks like this", sure there are some awesome tricks that I wish they didn't patch out. I wish void ray fazing still existed. I wish the viking flower and the archon toilet still existed. These were all awesome tricks from a spectator perspective. But this trick isn't very exciting. You can't even tell someone's doing it from a spectator's perspective unless you specifically watch their scout for it. I just don't think it's a nice enough trick that they should keep it in. It would just cause confusion more than anything else. | ||
|
artanis2
United States732 Posts
On May 03 2011 05:15 TedJustice wrote: The problem with that "easy fix" is that when you have 200/200 worth of zerglings all having their paths calculated (or a potential 1600/1600 worth of zerglings in a 4v4), you don't want that path to constantly have to be recalculated based on vision. It would cause an insane amount of lag. The path is only recalculated when a new building is uncovered. How many buildings are typically built during a game? Cheese ends with <10 buildings, a 45 minute game may have 50+ per player. Now how many times do you command a unit in a game? Thousands. Those 50 path recalculations aren't hurting performance... | ||
|
sjschmidt93
United States2518 Posts
| ||
|
Seldon
90 Posts
On May 03 2011 05:15 TedJustice wrote: The problem with that "easy fix" is that when you have 200/200 worth of zerglings all having their paths calculated (or a potential 1600/1600 worth of zerglings in a 4v4), you don't want that path to constantly have to be recalculated based on vision. It would cause an insane amount of lag. To be fair, the path isn't calculated for every unit individually, the group of selected units is first divided into subgroups and then a path is calculated for every subgroup (and that's the reason we have magic boxing ). When a unit in a subgroup finds an obstacle this is solved with faster algorithms that do not involve global path-finding (line of sight, flocking, avoidance, local path-finding...).Anyway, what I wanted to say is that the path is already being recalculated occasionally (due to depots being raised or burrowed or buildings being constructed/destroyed) so nothing new would have to be added in this sense. It's just that the frequency of these recalculations would increase cause now you have to take into account things coming inside and outside the fog. So it's slower but not exponentially slower as suggested. Every client would also need a little more RAM to keep every team's AI view. To me the main difficulty is not technical as it is organizational. The software engineer in charge is not gonna be happy if they ask him to fix this, they are gonna have to do major changes to the simulation classes that will require extensive, maybe month-long, testing in Windows and Mac to avoid desynchronization. Also, they may have to do tricky stuff in order to keep compatibility with old replays and saved games, which will require more testing. For such a stable product it's a pain in the ass when you are asked to introduce a major change that may cause a ton of regressions. So if Blizzard doesn't fix this I'm pretty sure it will be mainly cause of the organizational challenge, SC2 is not very profitable compared to WoW and they may have some trouble justifying something major such as this. There's a reason most of the new features Blizzard are bringing us such as observing overlays are stuff that can be scripted or just added as a resource. i.e: non-engineering stuff that doesn't break anything. | ||
|
kzn
United States1218 Posts
On May 03 2011 04:46 artanis2 wrote: Yes, and all of that problem has already been solved. Adjusting it to ignore certain buildings to within a range is an easy problem. For example: Instead of generating the grey line, they generate the blue line. They do this by creating a path that ignores all buildings that cannot be seen initially, when the vision changes it is recalculated and tacked on to the current path. This can all be done when the unit is first told to move, or incrementally as the vision is adjusted for a unit's movements. Just because you guys haven't solved this kind of problem before doesn't mean others haven't... Wouldn't this result in stupid pathfinding with regard to previously seen buildings that are in fog of war? | ||
|
Swwww
Switzerland812 Posts
| ||
|
corpuscle
United States1967 Posts
| ||
|
Silent331
United States356 Posts
| ||
|
artanis2
United States732 Posts
On May 03 2011 06:23 kzn wrote: Wouldn't this result in stupid pathfinding with regard to previously seen buildings that are in fog of war? No. The pathfinding will path around any obstacle that you can see, so you would get the grey path every time in the future. This includes buildings that you once saw but are no longer actually there, so if that main building had been destroyed or moved, you would path around it, until your unit saw that it was missing and then the path would be recalculated to move through the now empty space. There are some interesting cases where if there are multiple paths to a location, your unit may end up taking the long way around because you previously saw a wall. That wall might be gone, but your units wont see that fact unless you specifically scout it. With the existing pathing your units magically know that the building is gone and will go up an unblocked ramp that your vision tells you is blocked. This is a bug. One other quirk with the current pathfinding is when there is no path to a location the unit prefers to get as close as possible even if there is a wall in the way. So for example your scouting worker will sit below a base that is walled off hugging a wall nearest your path destination. I think the correct path should make the unit get as far as possible via the shortest blocked path. This way the unit would move up whichever ramp gets you closest and stop there, instead of by some wall in the middle of nowhere. | ||
|
Steel
Japan2283 Posts
 | ||
|
asdfjh
Canada230 Posts
| ||
| ||
