[Trigger] Terrain-based pathfinding

[halleylight]

Hi guys !

I have this one question: Is it possible to program a unit so it moves on its own and can only walk on a certain type of terrain (Grass, for example) ?

I don't want it to reach the target on other types of terrain (Dirt, Ice...), only Grass. Can anyone help me ?

Thank you very much !

 

[Zwiebelchen]

You can get the tile type with a JASS native.
Based on that, you can write an algorythm catching any target or point orders and assigning waypoints to the unit.
It's not an easy task, though and will require extensive vJASS and programming skills.
I'd say don't bother it and scrap the idea if you are a GUIer.

 

[Imp Midna]

It does neither require any JASS skills (not to mention vJASS, which is simply a pre-compiler which is why it can not do more than JASS or, for that matter, GUI with a few custom scripts can do), and looking at the limited possibilities that JASS provides in general, 'programming skills' are not required in thus far that you'd expect it when you read the word 'programming skills'. It's certainly easier with JASS, but totally doable when you are an advanced GUI user.

The only thing you really do need is knowledge about the algorithms. THIS is where it actually gets hard. Simple searching algorithms like in-depth-search will probably quickly exceed the op-limit and/or cause high cpu usage, making it rather unfortunate to be used frequently, while algorithms like A* are rather complex to implement. If you have trouble with the algorithms, THEN you definitely reached the point where you should scrap the idea. But for christs sake, don't scrap the idea just because some guy told you that you can not do it in GUI.

 

[Zwiebelchen]

It does neither require any JASS skills (not to mention vJASS, which is simply a pre-compiler which is why it can not do more than JASS or, for that matter, GUI with a few custom scripts can do), and looking at the limited possibilities that JASS provides in general, 'programming skills' are not required in thus far that you'd expect it when you read the word 'programming skills'. It's certainly easier with JASS, but totally doable when you are an advanced GUI user.

The only thing you really do need is knowledge about the algorithms. THIS is where it actually gets hard. Simple searching algorithms like in-depth-search will probably quickly exceed the op-limit and/or cause high cpu usage, making it rather unfortunate to be used frequently, while algorithms like A* are rather complex to implement. If you have trouble with the algorithms, THEN you definitely reached the point where you should scrap the idea. But for christs sake, don't scrap the idea just because some guy told you that you can not do it in GUI.

The direct connection is not there, sure, but let's be honest here:
The required algorythm for something like that is complicated enough to create even with advanced programming languages like C.
And then, with the even more limited possibilities of GUI, it will just turn out to be an insane task. I mean, come on, GUI doesn't even allow locals or user defined functions without custom code.
Pathing algorythms usually require recursive functions. You really wanna try that with GUI? Well, have fun then!

 

[Imp Midna]

I mean, come on, GUI doesn't even allow locals or user defined functions without custom code.

Well, thats why i was talking about "advanced GUI users". Local variables can be used in the GUI with the correct custom scripts, and i'm sure many GUI users that never actually touched JASS know about this trick, as it does not require any actual JASS knowledge to execute. Read: you DO have locals.
As for the functions, i've never seen anybody (beside me) using them in GUI indeed. However, executing a trigger is actually calling the triggers action function, resulting in a function call of a user defined function. And this user defined function can perfectly be used for recursive calls.
Therefor, the GUI does not really take any of the basic abilities most advanced programming languages offer. (except for pointers. oh how i miss those pointers.) Implementing a simple depth-first pathing recursive algorithm doesn't take much more than 15 c++ lines (providing a given data structure, in this case you will probably need a few more), and i don't think that will be too much of a problem. And year, i WOULD have fun doing this (much more than i would have in JASS btw, i just hate this 'language')

 

[deathismyfriend]

off topic
How do u hate Jass lol ? If u dont like it go to vJass, more flexibility. If u dont like the syntax i believe Zinc is the next step.

@ TO
im with zwiebelchen with this. You should just scrap the idea. If u really want to do it this way tho im betting there are some ppl here that can / will help u when u need it. But like zwiebelchen said the algorithms in GUI are a nightmare. Even the basic Algorithms in GUI are horrible.

 

[Arhowk]

It does neither require any JASS skills (not to mention vJASS, which is simply a pre-compiler which is why it can not do more than JASS or, for that matter, GUI with a few custom scripts can do), and looking at the limited possibilities that JASS provides in general, 'programming skills' are not required in thus far that you'd expect it when you read the word 'programming skills'. It's certainly easier with JASS, but totally doable when you are an advanced GUI user.

The only thing you really do need is knowledge about the algorithms. THIS is where it actually gets hard. Simple searching algorithms like in-depth-search will probably quickly exceed the op-limit and/or cause high cpu usage, making it rather unfortunate to be used frequently, while algorithms like A* are rather complex to implement. If you have trouble with the algorithms, THEN you definitely reached the point where you should scrap the idea. But for christs sake, don't scrap the idea just because some guy told you that you can not do it in GUI.

You joined less than two weeks ago and your already saying this? theyre all the same on runtime but what you can make in two months in GUI you can make in a month in JASS and u can make in two weeks in vJass. Using GUI and not vJass for any reason other than its harder and you need experience is an ignorant move, especially when you fill your gui with custom scripts.

If you truly "hate" the language than why are you posting about it? You cant do a full A* from top to bottom in C++ in under 100 lines. You can do it in java in 1 line, but java is a non-whitespace language

/ontopic/, first poster is right, you shouldnt be bothering with pathfinding as its quite complicated

 

[Zwiebelchen]

Implementing a simple depth-first pathing recursive algorithm doesn't take much more than 15 c++ lines (providing a given data structure, in this case you will probably need a few more), and i don't think that will be too much of a problem. And year, i WOULD have fun doing this (much more than i would have in JASS btw, i just hate this 'language')

15 lines? You kidding me?
Post that algorithm then, I'm curious to see your 15 lines pathing algorithm!

Also, it's not only the pathing algorithm alone that has to be made. You also need an order queue script to make the unit actually follow that pathing. Then you need to catch all orders send inbetween and process them. And this is not just done by replacing the move order with the pathing order queue!
You need to track all movement paths created by target orders aswell. And let's not forget that units have a collision size! This has to be tracked aswell! AND targetted units can even move away, making the unit follow the target.
And then, there's ranged units, that do not need to move into melee range of the target, so we have to take the attack range into account aswell, when we want to override the movement of the unit with the custom pathing.

Now that I think about it... I think the pathing algorithm isn't even the hardest thing about this. It's the order queue and catching all those cases and processing them correctly.

You really want to do that without object orientated programming?

Yes, it can be done. Then again, winning the lottery also CAN. But that doesn't mean it's very likely to achieve.
Heck, even with vJASS, it would be a total headache to do that. Now imagine someone having to use endless dropdown menus for every single line of code...

 

[deathismyfriend]

You joined less than two weeks ago and your already saying this? theyre all the same on runtime but what you can make in two months in GUI you can make in a month in JASS and u can make in two weeks in vJass. Using GUI and not vJass for any reason other than its harder and you need experience is an ignorant move, especially when you fill your gui with custom scripts.

i believe it to be faster than that lol. I wrote my whole map about 2 months work in GUI. About 50 triggers or so. Then in the next month i converted all those triggers into vJass and made 9 minigames. Including a checkers style minigame / race / shooting / others. After a month of vJass i had about 100 - 150 triggers.

 

[DJAB]

Hi guys !

I have this one question: Is it possible to program a unit so it moves on its own and can only walk on a certain type of terrain (Grass, for example) ?

I don't want it to reach the target on other types of terrain (Dirt, Ice...), only Grass. Can anyone help me ?

Thank you very much !

Well, Put the unit at any place in the map, and move it to its starting location at Map Initialization. Then you could programme it like :

"Event
Unit-A unit enters gen001
Condition
Entering unit Equal to Player 1
Action
Unit-Order entering unit to move to gen002 "

The same way, when it reaches that region, you can trigger it to move to the next region on the grass and keep it moving on the grass !

 

[deathismyfriend]

thats not exactly what he was asking lol.
He wants the unit to only move on grass not in a region.

Also when ur triggering dont use entering unit. instead use triggering unit.

 

[defskull]

Is it possible to program a unit so it moves on its own

For this problem, we usually apply the unit with Wander (Neutral) OR Tornado Wander (Tornado) ability that will make the unit to move around wandering the lands.

But since you want this;

and can only walk on a certain type of terrain

We should just trigger all of it (the movement AND the restrictions).

Here's a test map showing 3 unit-type, each having their own restriction area.
The wandering attributes can be configured in the setup trigger.

If you don't understand how to use the system, ask me.

Here's what you should do;

• Actions
  • Set RM_UnitSet = YourUnit
  • Set RM_TerrainTypeSet = YourTerrainType
  • Set RM_IntervalOrderSet = YourIntervalPerMovementChange
  • Set RM_MinWanderDistanceSet = YourMinimumWanderPerimeter
  • Set RM_MaxWanderDistanceSet = YourMaximumWanderPerimeter
  • Trigger - Run RM Save <gen> (ignoring conditions)

After you have set all those variables, don't forget to run the trigger RM Save <gen> just like in the test map.
You have to do this for each unit in the map.

 

[Imp Midna]

I don't usually answer to posts that have such a high possibility of ending in a flame war, and i feel a little guilty to get off topic after defskull finally came and postet something that was actually usefull to the OP, but i feel like there are a lot of misconceptions left to clear out. Therefor, I'm trying to use this post to clear up the ones i can clear up. I'd also like to advice you for the sake of future collaboration to try and stay objective rather than letting the matter break through your emotional control. (hm, didn't find a better translation for "Affektkontrolle", but emotional control still doesn't seem to express the actual meaning of that word... anyways)

From top to bottom:

You joined less than two weeks ago and your already saying this?

I wonder how the day i signed up onto this very website actually affects my possibilities to answer, judge or help. At least it would be rather naive to judge over my experience in terms of programming or wc3-modding by this date, and i guess you can all imagine why so i won't explain it in detail here.

Using GUI and not vJass for any reason other than its harder and you need experience is an ignorant move, especially when you fill your gui with custom scripts.

This part actually made me smile a bit, as the usage of the word 'ignorant' seems pretty self-ironic at this point. In fact, they are plenty of reasons for and against using vJass with only a very small part of them basing on the actual speed of implementing things with these methods. Having a rather one-sided subjective weight to those reasons (like me) seems indeed sort of ignorant, but pushing all of them aside leaving nothing but the speed in which things can be implemented as the only reason for and against using it seems way more ignorant to me.

you truly "hate" the language than why are you posting about it?

In case you noticed, i am not actually the first one that posted about these languages. All i did was trying to explain that you don't necessarily need this pure language to actually fulfill this task, trying to encourage the OP not to stop his project. The actually questioning of those principles did not originate from my part, and my personal preferences do not stand in any connection to the advices i gave.

off topic
How do u hate Jass lol ? If u dont like it go to vJass, more flexibility. If u dont like the syntax i believe Zinc is the next step.

Mainly the look of it, the heavy usage of keywords like set and call, endfunction, the missing ability to declare local variables in the middle of the function, inconsistent function names.
About vJass, it shares the same problems in general. The ability to encapsulate is rather insignificant for me, as i do not intend to use systems that other people created (I'm doing this for fun, and copynpasting the solution of a problem is NOT fun), and the structs, while looking rather attractive, give me headaches about how they are implemented. It's my map and i really don't like not to know whats going on inside of it.
As for Zinc, it does indeed seem tempting to me. If i could get my hands on the source code and change a few things (mainly the bison file though), i'd probably go for it.

Implementing a simple depth-first pathing recursive algorithm doesn't take much more than 15 c++ lines (providing a given data structure, in this case you will probably need a few more), and i don't think that will be too much of a problem. And year, i WOULD have fun doing this (much more than i would have in JASS btw, i just hate this 'language')

15 lines? You kidding me?

depth-first-searching is pretty damn easy.

Depth-First-Search ing 14 lines

bool depthFirstSearch(Node* thisNode) {
	if(thisNode->visited || thisNode->terrain != passable) return false;
	thisNode->visited = true;
	if(thisNode->loc == searchedPos) {
		path.push_back(thisNode->loc);
		return true;
	}
	if(thisNode->neighbours == NULL || thisNode->neighbours->empty()) return false;
	for(auto it = thisNode->neighbours->begin(); it != thisNode->neighbours->end(); it++) {
		if(*it != NULL && depthFirstSearch(*it)) {
			path.push_back(thisNode->loc);
			return true;
		}
	}
	return false;
}

You also need an order queue script to make the unit actually follow that pathing.

Not a trivial task but totally doable if you control its movement

And then, there's ranged units, that do not need to move into melee range of the target, so we have to take the attack range into account aswell, when we want to override the movement of the unit with the custom pathing.

Actually, the OP did not precisely ask for such a task. The word "reach" might as well just mean to "walk to" the location, which, in the context of a pathing algorithm, seems more reasonable to me. And even if he did mean what you said, it's merely another challenge to embrace. We are modding because modding is fun, and overcoming challenges is practically the core element of modding, or for that matter, every non-commercial programming.

Yes, it can be done. Then again, winning the lottery also CAN. But that doesn't mean it's very likely to achieve.

a weird comparison. Winning a lottery is pure luck, while fulfilling this task using GUI is a challenge completely based on skill.

Now imagine someone having to use endless dropdown menus for every single line of code...

I read some criticism about the GUI out of this. In fact, having used the GUI for a few years now, i need about 5 seconds to find the action i am searching for, and since you use most actions multiple times, copying it down is even quicker. There are indeed a few things that are quite unfortunate in GUI (namely set variables and string concatenations), but you might as well use custom scripts for those.

--------------------------------------------------------------------------

Now, to not be entirely useless and actually at least write something related to the topic:
@OP:
1: Look up shadow locals. You will need them.
2: Find a simple algorithm that fits your needs. If i think about it, i'd actually recommend breadth-first-search rather then depth-first-search. Google it and see if you understand it.
3:If it fits your needs and you decide to use it, but have trouble implementing it, feel free to come back, I (and probably some others here) will surely assist you
4: The Movement itself is another topic that you might as well turn to after having done the pathing algorithm, but what defskull posted seems pretty darn useful.

 

[rulerofiron99]

I recall a system over at wc3c that did exactly this, but here's the closest I could find:
http://www.wc3c.net/showthread.php?t=89813

Other than that, an extremely simple yet limited method would be to use pathing types.
ground
naval
air

and then place pathing blockers appropriately.

EDIT: Found it. http://www.wc3c.net/showthread.php?t=80824

 

[Arhowk]

Oh well, since you seem to be "one of those people" and this thread will be closed in a few posts ill leave with this. If you find any valid counterargument, feel free to contact me otherwise.

This part actually made me smile a bit, as the usage of the word 'ignorant' seems pretty self-ironic at this point. In fact, they are plenty of reasons for and against using vJass with only a very small part of them basing on the actual speed of implementing things with these methods. Having a rather one-sided subjective weight to those reasons (like me) seems indeed sort of ignorant, but pushing all of them aside leaving nothing but the speed in which things can be implemented as the only reason for and against using it seems way more ignorant to me.

There are few cases in which GUI triumphs over vJass. The only acceptable ones are

1. JNGP is not supported on your computer
2. Coding knowledge is inadequate

(as stated)

and there are much more reasons to use vJass

1. Great introductory language to programming
2. Speed, obviously
3. Unlocking potentials that was not given through JASS
4. Relating to 1 but standard OOP which is becoming more and more used with the introduction of more advanced microchips
5. Access to many useful resources for WC3 modding

In case you noticed, i am not actually the first one that posted about these languages. All i did was trying to explain that you don't necessarily need this pure language to actually fulfill this task, trying to encourage the OP not to stop his project. The actually questioning of those principles did not originate from my part, and my personal preferences do not stand in any connection to the advices i gave.

Noone here is discouraging OP to stop making his map but rather that the solution he is looking for is too advanced for his current skill level. Noone ever said you need pure vJass to make it, its just so much faster in vJass (although im not really sure what defskull posted, assuming it either cancels movement or uses a different library's pathing system)

Mainly the look of it, the heavy usage of keywords like set and call, endfunction, the missing ability to declare local variables in the middle of the function, inconsistent function names.
About vJass, it shares the same problems in general. The ability to encapsulate is rather insignificant for me, as i do not intend to use systems that other people created (I'm doing this for fun, and copynpasting the solution of a problem is NOT fun), and the structs, while looking rather attractive, give me headaches about how they are implemented. It's my map and i really don't like not to know whats going on inside of it.
As for Zinc, it does indeed seem tempting to me. If i could get my hands on the source code and change a few things (mainly the bison file though), i'd probably go for it.

Referring to your ZINC comment, since its simply a text converter and not compiler its not that hard to make your own JASS-based language...

Yeah, the keywords are annoying, but it just becomes commonplay after a while, i hardly notice it when switching between jass/java/js.

[/quote]

depth-first-searching is pretty damn easy.

Depth-First-Search ing 14 lines

bool depthFirstSearch(Node* thisNode) {
	if(thisNode->visited || thisNode->terrain != passable) return false;
	thisNode->visited = true;
	if(thisNode->loc == searchedPos) {
		path.push_back(thisNode->loc);
		return true;
	}
	if(thisNode->neighbours == NULL || thisNode->neighbours->empty()) return false;
	for(auto it = thisNode->neighbours->begin(); it != thisNode->neighbours->end(); it++) {
		if(*it != NULL && depthFirstSearch(*it)) {
			path.push_back(thisNode->loc);
			return true;
		}
	}
	return false;
}

Thats just psuedoscript... none of those classes exist and warcraft 3 does not have them. Anyone that has built these items obviously built them for a pathfinder system and thus it would be foolish to not build in several different pathing algorhitms

Actually, the OP did not precisely ask for such a task. The word "reach" might as well just mean to "walk to" the location, which, in the context of a pathing algorithm, seems more reasonable to me. And even if he did mean what you said, it's merely another challenge to embrace. We are modding because modding is fun, and overcoming challenges is practically the core element of modding, or for that matter, every non-commercial programming.

Theres a difference between modding for fun and learning to mod. I barely entered JASS within a year of modding and I couldn't do anything near what im doing at the moment. You can play COD for fun but your not getting max prestige (idfk what it is) the first time you play, no matter how you much u want it.

a weird comparison. Winning a lottery is pure luck, while fulfilling this task using GUI is a challenge completely based on skill.

What

I read some criticism about the GUI out of this. In fact, having used the GUI for a few years now, i need about 5 seconds to find the action i am searching for, and since you use most actions multiple times, copying it down is even quicker. There are indeed a few things that are quite unfortunate in GUI (namely set variables and string concatenations), but you might as well use custom scripts for those.

--------------------------------------------------------------------------

Now, to not be entirely useless and actually at least write something related to the topic:
@OP:
1: Look up shadow locals. You will need them.
2: Find a simple algorithm that fits your needs. If i think about it, i'd actually recommend breadth-first-search rather then depth-first-search. Google it and see if you understand it.
3:If it fits your needs and you decide to use it, but have trouble implementing it, feel free to come back, I (and probably some others here) will surely assist you
4: The Movement itself is another topic that you might as well turn to after having done the pathing algorithm, but what defskull posted seems pretty darn useful.

Basically just restating what you've said in the thread

For #1, no you dont need shadow locals as they allocate unnessecary memory.

1. You have the global already, why not use it?
2. If you use it in a Wait action, waits are highly unstable and normally should't be used
3. The best solution is to use a MUI system with UnitIndexer (probably what defskull posted)

(i know this is kind of ironic but)

/\/\/\/\/\/\/\/\/\/\/\no plang war below this line/\/\/\/\/\\/\/\/\/\\/\/\/\

(unless the mods decide to close it anyway, in which case the OP will probably end up starting a new thread. In that case, Sorry OP! )

 

[deathismyfriend]

waits arent unstable just inaccurate. shadowing locals is very nice for GUIers. It allows them to use the global and not have to worry about it getting overwritten.
for ur #3 i agree with u there.
I kinda like the syntax for vJass although ive never used any other type of programming. If u put syntax beside, vJass still has a lot more flexibility, processing speed, writing speed compared to GUI.
If u write something in GUI that takes a month u can easily write it in vJass in less than 2 weeks.
And rating a programming language simply on there syntax is really stupid / ignorant IMO.

 

[Arhowk]

waits arent unstable just inaccurate. shadowing locals is very nice for GUIers. It allows them to use the global and not have to worry about it getting overwritten.
for ur #3 i agree with u there.
I kinda like the syntax for vJass although ive never used any other type of programming. If u put syntax beside, vJass still has a lot more flexibility, processing speed, writing speed compared to GUI.
If u write something in GUI that takes a month u can easily write it in vJass in less than 2 weeks.
And rating a programming language simply on there syntax is really stupid / ignorant IMO.

I said no more of this discussion, so please don't.

 

[defskull]

I believe I had posted the perhaps-a-solution-to-his-problem post instead of arguing over which language best to be used, dafuq.

 

[deathismyfriend]

ya u and ruleofiron did lol

 

[rulerofiron99]

I said no more of this discussion, so please don't.

So you have the final word, no backsies? lol.

 

[Arhowk]

So you have the final word, no backsies? lol.

What he said was just repeating the information that was already given in the thread. If you read my post, I said in the beginning that if you have any valid rebuttal to the argument than contact me otherwise, else we're just spamming OP's thread (which we're still doing)

 

[halleylight]

Thank you all for trying to help me !

I didn't really expect this problem to become something so controversial. Not surprisingly, most of solutions everyone provided here weren't so understandable to me. And I'm just a normal GUI user, so I don't think I can follow any JASS, or AI algorithm, etc..

At the moment, I am using a workaround to this problem by constantly scanning the terrain type of tiles surrounding a unit and if it isn't grass, I set the Walkability of that tile to Off. The result is just as I expected, where units only walk on grass and it "looks" like they understand that they cannot walk on other types of land. There are some minor problems here and there, but that's what I got and at this stage, I'm pleased with it.

Again, thank everyone for your passionate discussion to my problem ! I wish you all the best !

 

[deathismyfriend]

U could try to post ur triggers we may be able to help improve. Also if ur searching for the grass type then u are using a basic pathing.

 

[halleylight]

Well, I didn't ask for anything grand lol. I'm dazzled by the complexity of everyone's posts.

 

[deathismyfriend]

U should make every trigger as efficient as possible that's y I suggested posting it on here so we can help improve it of possible. Also u may want to take a look at my tutorial Things a GUIer should know. It should help u to improve ur triggers on ur own.

 

[defskull]

Have you looked in this post: http://www.hiveworkshop.com/forums/2339664-post12.html
The system is easy to understand.

 

[Arhowk]

Thank you all for trying to help me !

I didn't really expect this problem to become something so controversial. Not surprisingly, most of solutions everyone provided here weren't so understandable to me. And I'm just a normal GUI user, so I don't think I can follow any JASS, or AI algorithm, etc..

At the moment, I am using a workaround to this problem by constantly scanning the terrain type of tiles surrounding a unit and if it isn't grass, I set the Walkability of that tile to Off. The result is just as I expected, where units only walk on grass and it "looks" like they understand that they cannot walk on other types of land. There are some minor problems here and there, but that's what I got and at this stage, I'm pleased with it.

Again, thank everyone for your passionate discussion to my problem ! I wish you all the best !

If you can't understand defskull's post, I'd recommend looping through every terrain tile in the area and if isn't grass than put a pathing blocker

 

[halleylight]

Thank you very much ! I'd really appreciate all the help here ^^.