[vJASS] Path finding algorithm

[MoCo]

Hi,

I need an efficient function that detects if a unit is able to reach the position of another unit or not. I've attached an example picture that shows a maze using pathing blockers. In the left maze, the red unit is able to reach the blue unit, in the right picture, it is not. This reachability should be detectable by the function.

Maybe someone has already faced this issue before?

Thanks and cheers

 

[Cokemonkey11]

Hello,

Pathfinding is a big pain in the behind in jass, unfortunately. The virtual machine is simply too slow to make a useful system for it.

Typically systems that do it are made for ad-hoc purposes, meaning a map developer will make a pathfinder which is bounded to some small area, and they know how large a gap has to be for their units to pass (as opposed to checking every 16x16 pathing point for a large scale, multi-purpose system).

Nestharus, who is something like a god of algorithms and data structures, especially among jass, tried this a couple years ago - http://www.hiveworkshop.com/forums/graveyard-418/system-needs-work-path-199207/

And it failed because he simply couldn't find a fast enough way to make it. I vaguely recall suggesting some optimization methods so as to permit its use on an ad-hoc basis, but I guess he found issues. You might want to try contacting him to see if he has had any revelations since then (I haven't been around much)

If you're interested in understanding pathfinding more generally, I suggest taking a look at the A* algorithm http://en.wikipedia.org/wiki/A*_search_algorithm

Good luck.

 

[MoCo]

Hi Cokemonkey11,

thanks a lot for these very helpful answers!
I suspected that this would be a tough issue and I was just checking the systems of Nestharus - thats really some awesome work.

The map background is that I want to create a map inspired by dungeon keeper. As in dungeon keeper, the player can mark squares of rock so that imps start diggin them out. The imps should act on their own so they automatically dig out marked rock tiles. However, I need a way to find out if a rock tile is reachable for them.. Maybe I can find another solution to this issue.

 

[rulerofiron99]

If you don't need it to be instant, you can create a dummy unit and order it to move there, wait until it stops moving, and if it isn't at the target location, it can't be pathed.

For the example maze this will take about a second, for an actual map where some mazing will be done... maybe a few minutes.

You could maybe increase the dummy's speed using http://www.hiveworkshop.com/forums/spells-569/movespeedx-gui-v1-1-0-0-a-207607/

 

[Nestharus]

http://www.hiveworkshop.com/forums/jass-resources-412/snippet-ispathblocked-211198/

Detects if there is a block, not whether a unit can go from point A to point B.
Pass in the suspected tower of blocking and it'll tell u whether that tower blocked or not.

 

[MoCo]

Thanks for your help. I guess I don't need the pathing anymore because I've just found a totally easy yet efficient solution to my issue.

Whenever a rock tile is marked, it is made hostile (else it is passive). In addition, the acquisition range of the imps is set to a value that includes the whole map. This system makes them automatically run and attack marked tiles.