Path Check for TD

[Marcelo Hossomi]

Hello guys,

After millions of years away from the Hive and map editing, I have come back for a while with a few ideas to try out.

One of them is a TD with dynamic path check. That is, the path will be checked at the moment a player places a tower.

The arena is always rectangular, possibly with obstacles, and divided in 64x64 squares (cells) like the screenshot. I already have means to know the status of each cell (passable or blocked), and now I need an algorithm to find a path (any path) between the start (green !) and the end (orange !).

I have tried some approaches (depth-first, breadth-first, simplified A*) but all of them stops for no reason when the path gets too long. Could the reason be a JASS function limitation (function executed for too long, or too many loop iterations)?

Thanks already

 

[Nestharus]

Look in my signature under resources in JASS folder. You'll find something pleasantly surprising =). You'll know it when you see it.

depth-first, breadth-first, and A* massively freeze wc3 when accounting for op limit. You need a more specialier algorithm

A* is ok when there is a path. It's terrible when there isn't one ;P.

A* is meant to find the shortest path, it isn't meant to check if a path exists or not .

 

[Adiktuz]

probably just do it how wc3 natively handles it, a little step at a time... possibly using just simple algorithms that might be able to get handled within the OP limit...

or you could probably separate parts by separate triggers so that you can evade the OP limit...

 

[Nestharus]

I had to comment on this : P

From me

depth-first, breadth-first, and A* massively freeze wc3 when accounting for op limit.

And Adiktuz replies with

or you could probably separate parts by separate triggers so that you can evade the OP limit...

 

[Marcelo Hossomi]

Look in my signature under resources in JASS folder. You'll find something pleasantly surprising =). You'll know it when you see it.

You sure have a lot of things in there o_o

Anyway, I just guess that "IsPathBlocked" might be useful
I will try that later, thanks.

I tried those because they were the most straight and common-sense approach, didn't think much about effectiveness... But I should have imagined that they would be too heavy.

 

[Cokemonkey11]

You sure have a lot of things in there o_o

Anyway, I just guess that "IsPathBlocked" might be useful
I will try that later, thanks.

I tried those because they were the most straight and common-sense approach, didn't think much about effectiveness... But I should have imagined that they would be too heavy.

Since no one has actually explained the issue as to why your algorithm failed, it's because jass has a strict maximum number of "actions" (operations) that can occur in any given "virtual thread". It's hard to measure how many operations each native takes, but essentially this value is called the op-limit (operation limit of a virtual thread)

You can evade the issue by starting new virtual threads. I suggest using ExecuteFunc.

Again, Nestharus' resource may be the correct solution to the problem, but evading the op-limit is a nice thing to know about.