[event] name=sighted behavior

[silene]

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 ?

No.

So numerical_equals or boolean_equals only make sense if the variables' values are inconsistent.

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.

[Sapient]

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.

[Anonymissimus]

So numerical_equals or boolean_equals only make sense if the variables' values are inconsistent.

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.

So in things like

Code: Select all

...
	[store_locations]
		variable={VARIABLE_NAME}
		[not]
		[/not]
	[/store_locations]
	[while]
		[variable]
			name={VARIABLE_NAME}.length
			equals=0
		[/variable]
...

{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 ?

While technically equals= is faster than numerical_equals=, the amount of speed difference is imperceptible to humans.

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 ?

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.

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.
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]

At another point where NEAREST_HEX is used, {FILTER} is

Code: Select all

	[not]
		terrain=Xu,Qxu,Ql,Wo
	[/not]
	[not]
		[filter]
		[/filter]
	[/not]

(finding vacant hexes since find_vacant from unstore_unit does not analyse terrain for impassability!)

[silene]

{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 ?

I doubt there is any issue with this particular case. But there are some other cases (FormulaAI?) where I wouldn't be so sure.

While technically equals= is faster than numerical_equals=, the amount of speed difference is imperceptible to humans.

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 ?

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.

[solsword]

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]

At another point where NEAREST_HEX is used, {FILTER} is

Code: Select all

	[not]
		terrain=Xu,Qxu,Ql,Wo
	[/not]
	[not]
		[filter]
		[/filter]
	[/not]

(finding vacant hexes since find_vacant from unstore_unit does not analyse terrain for impassability!)

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:

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]

Do the speeds of these filters depend on {N} or $already_searched.length? I'd assume that it could go either way, depending on the underlying algorithms and data structures used. Of course, I'd also assume that for a problem size of hundreds (or even thousands) of hexes, there probably won't be an appreciable difference. But I could be wrong.

[silene]

If so, which are faster/slower) in the context of a location filter:

Code: Select all

[filter]
    [not]
    [/not]
[/filter]

That's cheap, relatively to WML interpretation cost.

Code: Select all

[not]
    x,y={X},{Y}
    radius={N}
[/not]

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.)

Code: Select all

[not]
    find_in=$already_searched
[/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.

To summarize, the first one has an almost negligible cost. The last two have not.

[Sapient]

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)

[silene]

In the case of store_locations, it would use algorithm B.

Sure, but that's not what I was replying to. Solsword was asking about "location filter", which I interpreted as meaning [filter_location].

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.

[Anonymissimus]

I have slow hardware and the slowdown is still acceptable I think. I hardly noticed anything when testing the macro.

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...

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.

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...

[silene]

I'd need access to system time and debug-output it, any way to do such a thing in wml or with wesnoth ?

You can use the "time" operation of [set_variable] to access a clock with millisecond resolution.

[Anonymissimus]

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 !

[solsword]

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.

[Sapient]

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.

[Anonymissimus]

1) For one thing, in the CASE#1 EVENT, you're using a suboptimal NEAREST_HEX algorithm (as I already discussed).

Is already improved according to suggestions in this thread.

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).

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).

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 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.

[Sapient]

Regarding point#1, I'd like to see your code just to be sure.

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).

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).

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.

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 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.

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.

I'll try to post up some code later if this doesn't make sense.