[event] name=sighted behavior
Moderator: Forum Moderators
Forum rules
- Please use [code] BBCode tags in your posts for embedding WML snippets.
- To keep your code readable so that others can easily help you, make sure to indent it following our conventions.
Re: [event] name=sighted behavior
No.Anonymissimus wrote:What if variable=1.0 and then variable is queried if it's numerical_equal to 1.0, is that as fast as equals in that case ?
If you only compare values that you have written yourself, then plain "equals" is sufficient. But some values come from outside, e.g. values computed by the engine ([store_unit], [set_variable], and so on). For such values, it is safer to assume the representation is inconsistent.Anonymissimus wrote:So numerical_equals or boolean_equals only make sense if the variables' values are inconsistent.
Re: [event] name=sighted behavior
While technically equals= is faster than numerical_equals=, the amount of speed difference is imperceptible to humans.
So use whichever one is most correct and/or suits your needs best.
Also, while we're speaking of optimization, I'd like to point out that you can probably speed up your "nearest hex" search by excluding the hexes you have already searched. Just use a [not] location filter with a smaller radius= attribute. The actual speed gains from this approach would likely depend on how complex your filter is.
So use whichever one is most correct and/or suits your needs best.
Also, while we're speaking of optimization, I'd like to point out that you can probably speed up your "nearest hex" search by excluding the hexes you have already searched. Just use a [not] location filter with a smaller radius= attribute. The actual speed gains from this approach would likely depend on how complex your filter is.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
-
- Inactive Developer
- Posts: 2461
- Joined: August 15th, 2008, 8:46 pm
- Location: Germany
Re: [event] name=sighted behavior
So in things likeIf you only compare values that you have written yourself, then plain "equals" is sufficient. But some values come from outside, e.g. values computed by the engine ([store_unit], [set_variable], and so on). For such values, it is safer to assume the representation is inconsistent.Anonymissimus wrote:So numerical_equals or boolean_equals only make sense if the variables' values are inconsistent.
Code: Select all
...
[store_locations]
variable={VARIABLE_NAME}
[not]
[/not]
[/store_locations]
[while]
[variable]
name={VARIABLE_NAME}.length
equals=0
[/variable]
...
We're talking about variable queries inside of loops, which can again be inside of at least one outer loop. I wouldn't care about it that much. Still imperceptible ?Sapient wrote:While technically equals= is faster than numerical_equals=, the amount of speed difference is imperceptible to humans.
Already wondered about that. Another approach would be [not] with find_in=locations(_from_previous_search_step). That way one doesn't need to calculate the previous radius, or an extra variable to store the previous radius.Also, while we're speaking of optimization, I'd like to point out that you can probably speed up your "nearest hex" search by excluding the hexes you have already searched. Just use a [not] location filter with a smaller radius= attribute. The actual speed gains from this approach would likely depend on how complex your filter is.
But, all hexes already searched don't match {FILTER} and should be excluded quite fast. In the name=sighted event replacement macro, filter is only
Code: Select all
[filter]
side={VIEWING_SIDE}
[/filter]
Code: Select all
[not]
terrain=Xu,Qxu,Ql,Wo
[/not]
[not]
[filter]
[/filter]
[/not]
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
Re: [event] name=sighted behavior
I doubt there is any issue with this particular case. But there are some other cases (FormulaAI?) where I wouldn't be so sure.Anonymissimus wrote:{VARIABLE_NAME}.length is engine-computated. Should I assume that it might be inconsistent, although for array lengths only unsigned int variables do make sense ?
Yes, it probably cannot be noticed. Interpretation of WML is so slow that the extra cost of doing a numeric comparison instead of a plain comparison will be in the noise. In other words, the comparison itself is not what takes time when interpreting WML.Anonymissimus wrote:We're talking about variable queries inside of loops, which can again be inside of at least one outer loop. I wouldn't care about it that much. Still imperceptible ?Sapient wrote:While technically equals= is faster than numerical_equals=, the amount of speed difference is imperceptible to humans.
- solsword
- Code Contributor
- Posts: 291
- Joined: January 12th, 2009, 10:21 pm
- Location: Santa Cruz, CA
- Contact:
Re: [event] name=sighted behavior
I'm also quite curious about this question. As Anonymissus pointed out, adding the extra [not] block with either a radius or a find_in just adds extra ways to disqualify those spaces (in this case). Depending on the filter given, it might be faster or slower than the extra disqualifying block. Can one of you devs comment on the expected relative speed of the following (as in, are they noticeable different when applied to hundreds of hexes? If so, which are faster/slower) in the context of a location filter:Anonymissimus wrote: But, all hexes already searched don't match {FILTER} and should be excluded quite fast. In the name=sighted event replacement macro, filter is onlyAt another point where NEAREST_HEX is used, {FILTER} isCode: Select all
[filter] side={VIEWING_SIDE} [/filter]
(finding vacant hexes since find_vacant from unstore_unit does not analyse terrain for impassability!)Code: Select all
[not] terrain=Xu,Qxu,Ql,Wo [/not] [not] [filter] [/filter] [/not]
Code: Select all
[filter]
[not]
[/not]
[/filter]
Code: Select all
[not]
x,y={X},{Y}
radius={N}
[/not]
Code: Select all
[not]
find_in=$already_searched
[/not]
The Knights of the Silver Spire campaign.
http://www.cs.hmc.edu/~pmawhorter - my website.
Teamcolors for everyone! PM me for a teamcolored version of your sprite, or you can do it yourself. If you just happen to like magenta, no hard feelings?
http://www.cs.hmc.edu/~pmawhorter - my website.
Teamcolors for everyone! PM me for a teamcolored version of your sprite, or you can do it yourself. If you just happen to like magenta, no hard feelings?
Re: [event] name=sighted behavior
That's cheap, relatively to WML interpretation cost.solsword wrote:If so, which are faster/slower) in the context of a location filter:
Code: Select all
[filter] [not] [/not] [/filter]
Complexity is O(n^2*log(n)). (Yes, this is terribly bad, as there is no theoretical reason for it not to be O(1). Coders are welcome.)solsword wrote:Code: Select all
[not] x,y={X},{Y} radius={N} [/not]
Complexity is O(n) with n the array length. This is not that bad; but you definitely don't want to have it check against hundreds of hexes inside a loop.solsword wrote:Code: Select all
[not] find_in=$already_searched [/not]
To summarize, the first one has an almost negligible cost. The last two have not.
Re: [event] name=sighted behavior
The filter algorithm depends what context the SLF is used in:
A) For testing whether or not a single location matches a given filter
B) For gathering all locations that match a given filter.
In the case of store_locations, it would use algorithm B.
The code for both paths is visible in terrain_filter.cpp/hpp
And I really don't think O(n^2*log(n)) is correct...
(I think you are assuming it would use algorithm A)
A) For testing whether or not a single location matches a given filter
B) For gathering all locations that match a given filter.
In the case of store_locations, it would use algorithm B.
The code for both paths is visible in terrain_filter.cpp/hpp
And I really don't think O(n^2*log(n)) is correct...
(I think you are assuming it would use algorithm A)
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
Re: [event] name=sighted behavior
Sure, but that's not what I was replying to. Solsword was asking about "location filter", which I interpreted as meaning [filter_location].Sapient wrote:In the case of store_locations, it would use algorithm B.
In the case of [store_locations], I agree the effect is much smaller. Adding a radius/not-radius filter just increases the overall complexity by O((n^2+t)*log(n)), with n the radius and t the number of tiles left by the previous filters.
-
- Inactive Developer
- Posts: 2461
- Joined: August 15th, 2008, 8:46 pm
- Location: Germany
Re: [event] name=sighted behavior
Been playing a scenario with my SIGHTED_MOVETO macro now, and I had the impression that it adds a noticable slowdown - whenever one of my units ended its move. The slowdown disappeared once the event had fired. This must be caused by the filter that calculates the visibility area.solsword wrote:Hmmm... maybe I'm calling it a lot more than I should be. I'll have to look at my code now. Or maybe something else is slowing things down...Anonymissimus wrote: I have slow hardware and the slowdown is still acceptable I think. I hardly noticed anything when testing the macro.
Now, to be sure that this is no placebo effect, I'd need access to system time and debug-output it, any way to do such a thing in wml or with wesnoth ?
Or, I'd need to arrange a blind test without knowing whether the macro is currently enabled or not and must decide it based on the speed impression...
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
Re: [event] name=sighted behavior
You can use the "time" operation of [set_variable] to access a clock with millisecond resolution.Anonymissimus wrote:I'd need access to system time and debug-output it, any way to do such a thing in wml or with wesnoth ?
-
- Inactive Developer
- Posts: 2461
- Joined: August 15th, 2008, 8:46 pm
- Location: Germany
Re: [event] name=sighted behavior
Messured the time needed for the second event in my SIGHTED_MOVETO macro, between right after the first filter, and before the very end.
After it has fired, it's only 0 or 1 ms (so the variable query is negligible), but before it's roughly 200 ms. There is even definitely a messurable difference between units with max_moves=4 and max_moves=6 !
After it has fired, it's only 0 or 1 ms (so the variable query is negligible), but before it's roughly 200 ms. There is even definitely a messurable difference between units with max_moves=4 and max_moves=6 !
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
- solsword
- Code Contributor
- Posts: 291
- Joined: January 12th, 2009, 10:21 pm
- Location: Santa Cruz, CA
- Contact:
Re: [event] name=sighted behavior
That's good information to have. 200ms is a very slight but noticeable delay, especially if it happens every time any unit moves, although I suppose that it's probably not noticeable relative to the time it takes the AI to compute the next move these days. Still, it'll be more for units with lots of moves (especially since terrain isn't taken into account), and it's certainly not something that you want to do in a loop for a bunch of different units, or anything like that. Thanks for testing this.
Also, it's not surprising that moves=4 to moves=6 makes a big difference: there's an exponential expansion in the number of hexes to be searched. The branching factor is interesting: 6 for the first hex, then 2 for the second set of hexes, but after that it's either 2 or 1, for an average of 1.5.
Also, it's not surprising that moves=4 to moves=6 makes a big difference: there's an exponential expansion in the number of hexes to be searched. The branching factor is interesting: 6 for the first hex, then 2 for the second set of hexes, but after that it's either 2 or 1, for an average of 1.5.
The Knights of the Silver Spire campaign.
http://www.cs.hmc.edu/~pmawhorter - my website.
Teamcolors for everyone! PM me for a teamcolored version of your sprite, or you can do it yourself. If you just happen to like magenta, no hard feelings?
http://www.cs.hmc.edu/~pmawhorter - my website.
Teamcolors for everyone! PM me for a teamcolored version of your sprite, or you can do it yourself. If you just happen to like magenta, no hard feelings?
Re: [event] name=sighted behavior
There are numerous problems with your SIGHTED_MOVETO macro, so maybe you should fix that first before timing the WML engine.
1) For one thing, in the CASE#1 EVENT, you're using a suboptimal NEAREST_HEX algorithm (as I already discussed).
2) For another thing, in the CASE #2 EVENT, there's no need to even use a radius to determine if it was sighted, since you could just check [filter_vision] to see if it was sighted (and this would be more accurate since it doesn't rely on assumptions about terrain, fog, delay shroud updates, etc).
3) Even if you did need to run a location filter in CASE#2, you should do it using [store_locations] instead of [store_unit] because if you do it with [store_unit] then it must iterate over every unit in the unit_map and in the recall list. Using [store_locations] allows the terrain filter to be analyzed once instead of running it for every unit.
1) For one thing, in the CASE#1 EVENT, you're using a suboptimal NEAREST_HEX algorithm (as I already discussed).
2) For another thing, in the CASE #2 EVENT, there's no need to even use a radius to determine if it was sighted, since you could just check [filter_vision] to see if it was sighted (and this would be more accurate since it doesn't rely on assumptions about terrain, fog, delay shroud updates, etc).
3) Even if you did need to run a location filter in CASE#2, you should do it using [store_locations] instead of [store_unit] because if you do it with [store_unit] then it must iterate over every unit in the unit_map and in the recall list. Using [store_locations] allows the terrain filter to be analyzed once instead of running it for every unit.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
-
- Inactive Developer
- Posts: 2461
- Joined: August 15th, 2008, 8:46 pm
- Location: Germany
Re: [event] name=sighted behavior
Is already improved according to suggestions in this thread.Sapient wrote:1) For one thing, in the CASE#1 EVENT, you're using a suboptimal NEAREST_HEX algorithm (as I already discussed).
This approach does not take into account the case that the unit that's to be spotted is a specific one - according to reference wml, filter_vision only accepts a side key, not an id or better, SUF. And: I'd need to filter on the vision of the viewed side (If this is possible at all - ais aren't shroud-aware...), because filtering on the viewing side's (=the player) vision doesn't take into account the case that the move is made and after that the shroud update reveals unit(s) to be spotted (with delay shroud on).2) For another thing, in the CASE #2 EVENT, there's no need to even use a radius to determine if it was sighted, since you could just check [filter_vision] to see if it was sighted (and this would be more accurate since it doesn't rely on assumptions about terrain, fog, delay shroud updates, etc).
I think I've tried that, too...probably worth another thought. But again, I want to have a SUF for the unit(s) to be spotted.3) Even if you did need to run a location filter in CASE#2, you should do it using [store_locations] instead of [store_unit] because if you do it with [store_unit] then it must iterate over every unit in the unit_map and in the recall list. Using [store_locations] allows the terrain filter to be analyzed once instead of running it for every unit.
projects (BfW 1.12):
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
A Simple Campaign: campaign draft for wml starters • Plan Your Advancements: mp mod
The Earth's Gut: sp campaign • Settlers of Wesnoth: mp scenario • Wesnoth Lua Pack: lua tags and utils
updated to 1.8 and handed over: A Gryphon's Tale: sp campaign
Re: [event] name=sighted behavior
Regarding point#1, I'd like to see your code just to be sure.
I'll try to post up some code later if this doesn't make sense.
Regarding point#2, the filter_vision goes inside a Standard Unit Filter, so you already have a Standard Unit Filter available to you right there. Perhaps you are confused because you were trying to put it in the [event][filter] instead of the [store_unit][filter]. Or maybe you are confused because you are forgetting that a unit such as a scout shares its "view" with its entire side.Anonymissimus wrote:This approach does not take into account the case that the unit that's to be spotted is a specific one - according to reference wml, filter_vision only accepts a side key, not an id or better, SUF. And: I'd need to filter on the vision of the viewed side (If this is possible at all - ais aren't shroud-aware...), because filtering on the viewing side's (=the player) vision doesn't take into account the case that the move is made and after that the shroud update reveals unit(s) to be spotted (with delay shroud on).2) For another thing, in the CASE #2 EVENT, there's no need to even use a radius to determine if it was sighted, since you could just check [filter_vision] to see if it was sighted (and this would be more accurate since it doesn't rely on assumptions about terrain, fog, delay shroud updates, etc).
Regarding point #3, perhaps you are forgetting that Standard Location Filter can contain a [filter] for units. Or perhaps you are forgetting that once a location with a desired unit is known, it is trivial to store the unit at that location.Anonymissimus wrote:I think I've tried that, too...probably worth another thought. But again, I want to have a SUF for the unit(s) to be spotted.3) Even if you did need to run a location filter in CASE#2, you should do it using [store_locations] instead of [store_unit] because if you do it with [store_unit] then it must iterate over every unit in the unit_map and in the recall list. Using [store_locations] allows the terrain filter to be analyzed once instead of running it for every unit.
I'll try to post up some code later if this doesn't make sense.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."