I think people are looking at this incorrectly. When you stutter step units you do not care about the direction you go, but rather the path you take. You are after finding a path to take which is safe and that naturally gives you a direction to go which is safe.
Lets say we want the unit to be able to move 5 tiles safely. A stupid approach to it would be to try 16 possible target routes centred on the unit 5 units away with a 22.5 degree angle between them (in a circle). You could check for blockages along each route (can you path there) by checking the path length to the point, if it deviates too much then it must be indirect or blocked so require a detour (such as going up a ramp). A better approach would be to somehow use the in-built path finder (might only be possible with LotV?) as then you can get the actual path the unit will take to get to the point.
You then factor in enemies. For each point along the path you determine the "threat" of all the enemies you will encounter. This could be done by iteratively searching in a line for simple directional paths. For more advanced path (such as from the path finder) you need to iteratively check between path nodes. Tougher enemies need to add more threat than weak enemies, after all a path through 2 Zerglings is a lot safer than a path through an Ultralisk despite there being only 1 of them and 2 Zerglings. You repeat this for all paths.
Finally you take the path which has the least threat. It might not be perfect (could still be enemies) but it should be a pretty optimal choice.
Dead end protection is another problem since the above would only solve finding an optimum path in the short term, but not one that will not get you trapped in the long term. A dead end is an area where there is only 1 path in or out. Big dead end sections can be ignored since they might be so large that you can kite around them no problems. Small dead ends are a problem however as they might just be big enough for a single unit to get in at a time and hold only a few units. An exclusion region could be made for small dead ends so that paths leading into them are never considered. The size of dead end to consider small is likely based on the length of paths you consider, a reasonable size dead end needs to be able to have multiple path samples inside it in which case there should be no problem moving around inside it.
For performance you can group units together. After all a marine right next to another marine can function like a single unit as long as they remain close and so will share optimum paths.
You'd run into problems if structures were a thing. You end up with huge values when your destination point is inside of a building.
Which you can reject as impossible.
The actual way to implement it would be some kind of custom pathing algorithm and a heat map, however that likely is impossible as well due to resource constraints.
For example if you mapped the threat within 32*32 tiles around the unit into a 2D array and then use a bitmap pathing algorithm to search for the path with the lowest heat through the bitmap you would get optimum results always. Unpathable places are logically entered as impossible heat (max) so form an impossible to pass barricade. This likely is too resource intensive however.
Rollback Post to RevisionRollBack
To post a comment, please login or register a new account.
I think people are looking at this incorrectly. When you stutter step units you do not care about the direction you go, but rather the path you take. You are after finding a path to take which is safe and that naturally gives you a direction to go which is safe.
Lets say we want the unit to be able to move 5 tiles safely. A stupid approach to it would be to try 16 possible target routes centred on the unit 5 units away with a 22.5 degree angle between them (in a circle). You could check for blockages along each route (can you path there) by checking the path length to the point, if it deviates too much then it must be indirect or blocked so require a detour (such as going up a ramp). A better approach would be to somehow use the in-built path finder (might only be possible with LotV?) as then you can get the actual path the unit will take to get to the point.
You then factor in enemies. For each point along the path you determine the "threat" of all the enemies you will encounter. This could be done by iteratively searching in a line for simple directional paths. For more advanced path (such as from the path finder) you need to iteratively check between path nodes. Tougher enemies need to add more threat than weak enemies, after all a path through 2 Zerglings is a lot safer than a path through an Ultralisk despite there being only 1 of them and 2 Zerglings. You repeat this for all paths.
Finally you take the path which has the least threat. It might not be perfect (could still be enemies) but it should be a pretty optimal choice.
Dead end protection is another problem since the above would only solve finding an optimum path in the short term, but not one that will not get you trapped in the long term. A dead end is an area where there is only 1 path in or out. Big dead end sections can be ignored since they might be so large that you can kite around them no problems. Small dead ends are a problem however as they might just be big enough for a single unit to get in at a time and hold only a few units. An exclusion region could be made for small dead ends so that paths leading into them are never considered. The size of dead end to consider small is likely based on the length of paths you consider, a reasonable size dead end needs to be able to have multiple path samples inside it in which case there should be no problem moving around inside it.
For performance you can group units together. After all a marine right next to another marine can function like a single unit as long as they remain close and so will share optimum paths.
-
View User Profile
-
View Posts
-
Send Message
Curse Premium@ImperialGood: Go
You'd run into problems if structures were a thing. You end up with huge values when your destination point is inside of a building.
Which you can reject as impossible.
The actual way to implement it would be some kind of custom pathing algorithm and a heat map, however that likely is impossible as well due to resource constraints.
For example if you mapped the threat within 32*32 tiles around the unit into a 2D array and then use a bitmap pathing algorithm to search for the path with the lowest heat through the bitmap you would get optimum results always. Unpathable places are logically entered as impossible heat (max) so form an impossible to pass barricade. This likely is too resource intensive however.