[event] name=sighted behavior

[solsword]

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

If by this you're referring to your suggestion of excluding hexes already searched, didn't we just establish that that would actually be *slower* than the alternative in most cases? This was because the exclusion relies on running another location filter with a radius, which isn't implemented in O(1) time, while the filter for matching (which we know fails on all spaces checked so far) is going to be O(1) in most cases (like my example of [filter][not][/not][/filter], or any simple terrain filter). If I've got something wrong here, please correct me. If I'm missing something else that you brought up, could you take the time to point it out in my code (which I think is nearly identical to Anonymissus'):

Code: Select all

#define FIND_NEARBY FILTER X Y LIMIT
    # Does a search for a nearby location that matches the given filter.
    # Basically just looks for such a location with increasing radius until it
    # finds at least one. This is sadly inefficient, but implementing BFS in
    # WML is... difficult. Once LIMIT is reached, the entire map is searched.
    # This macro creates the 'nearby_locations' and 'nearby_distance'
    # variables, which can be used to access a list of locations found and the
    # distance to those locations, respectively. They should eventually be
    # cleared, which can be accomplished using the CLEANUP_SEARCH macro.
    [clear_variable]
        name=nearby_locations
    [/clear_variable]
    [set_variable]
        name=nearby_distance
        value=0
    [/set_variable]
    [while]
        [not]
            [variable]
                name=nearby_locations.length
                greater_than=0
            [/variable]
        [/not]
        [and]
            [variable]
                name=nearby_distance
                less_than={LIMIT}
            [/variable]
        [/and]
        [do]
            {DEBUG "Searching depth $nearby_distance around ({X}, {Y})..."}
            [store_locations]
                variable=nearby_locations
                {FILTER}
                [and]
                    x,y={X},{Y}
                    radius=$nearby_distance
                [/and]
            [/store_locations]
            {DEBUG "...found $nearby_locations.length locations."}
            [set_variable]
                name=nearby_distance
                add=1
            [/set_variable]
        [/do]
    [/while]
    [if]
        [variable]
            name=nearby_locations.length
            equals=0
        [/variable]
        [then]
            [store_locations]
                variable=nearby_locations
                {FILTER}
            [/store_locations]
        [/then]
    [/if]
#enddef

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.

The only problem that I can see here is that if you're trying to be *really* accurate in emulating sighted events, you only want to fire your faux-sighted event for units spotted by the moving unit. Of course, the existing code for the faux-sighted event fails on this count in several ways as well. Considering the following examples:

1. You want to fire an event when the first Spearman is sighted. However, the player has one Spearman on their team. According to the wiki, a real name=sighted event ignores the already-known spearman, because name=sighted only fires when *new* units come into view. Anonymissus' code fails here if, for example, you move another unit next to the spearman. There's no point at which shroud gets removed, but the faux-sighted fires anyways. Sapient's version (just using [filter_vision] across all units, as I understand it) fails here whenever any unit gets moved. To work around this, you could make your filter more specific than "Spearman", but I'm not sure that that will *always* be the case. Of course, you could just revise the definition of "sighted" somehow.

2. You move a unit such that as it moves, it reveals an enemy unit, but once it is done moving, it isn't within range of that unit. In this case, Sapient's code works, but Anonymissus' code fails.

Note that in most cases, I suspect Sapient's version (filtering vision over all units) will be faster than Anonymissus' (and it accurately takes into account unit move costs which is great). However, if there are *a lot* of units on the map, it could be slower.

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.

On point 3, I agree with Sapient. It seems like the store_unit would run a *lot* slower than store_location, because the store_unit has to evaluate the location filter for each unit (unless it caches filter results?).

[Sapient]

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

If by this you're referring to your suggestion of excluding hexes already searched, didn't we just establish that that would actually be *slower* than the alternative in most cases? This was because the exclusion relies on running another location filter with a radius, which isn't implemented in O(1) time, while the filter for matching (which we know fails on all spaces checked so far) is going to be O(1) in most cases (like my example of [filter][not][/not][/filter], or any simple terrain filter). If I've got something wrong here, please correct me. If I'm missing something else that you brought up, could you take the time to point it out in my code (which I think is nearly identical to Anonymissus'):

I still disagree somewhat with silene's Big-O analysis and I think the [not]x,y,radius=a,b,c[/not] would be beneficial in the general case where {FILTER} is unknown, since it allows us to eliminate the re-processing of arbitrarily complex filters.

See the developer irclog from 2009-09-30 for an in-depth discussion:

irclog:

00:05 <Sapient> I am trying to figure out how silene calculated O((n^2+t)*log(n)) for terrain_filter::get_locations()
00:05 <Sapient> http://www.wesnoth.org/forum/viewtopic. ... 44#p387344
00:05 <Shadow_Master> due to a lack of proper book training, I have no clue about algorithm complexity stuff
00:06 <Sapient> there are a couple of obvious inefficiencies, like the converting sets into vectors, and the way empty filter containing [not] is handled using set difference instead of a negation of the universal set
00:07 <Sapient> but that first issue would be difficult to fix without making a lot of code use sets of location instead of vectors of location
00:08 <Sapient> and the second issue seemed like premature optimization since creating a collection of all x,y wasn't likely to be a bottleneck
00:09 <Sapient> but I do think my overall approach was a very sensible one with respect to efficienc
00:11 <Sapient> so I was surprised to be ranked so poorly on the O-notation
00:11 <Sapient> Crab seems like a scholar so maybe he could tell me
00:12 * Crab_ has to read the whole post before that
00:12 * Crab_ is reading..
00:20 <Sapient> in the case of getlocations (x,y,radius=a,b,c), the algorithm should only test the filter upon x,y (O(1)) and then grow the result by a quantity of c, without further computations required
00:23 <Crab_> growing the result by radius C is not that simple
00:24 <Crab_> see get_tiles_radius in src/pathutils.cpp
00:24 <Sapient> yeah, I wasn't sure if he was including get_tiles_radius as part of the computational complexity
00:24 <Crab_> it means testing O(c^2) hexes, and each test is logarithmic.
00:25 <Sapient> I agree that get_tiles_radius does look more complex than optimal
00:25 <Crab_> yes, since the topology of the map is well-known, it can be simpler..
00:29 <Sapient> but no terrain filter is being applied upon those c^2 hexes, so if the terrain filter is considered the only expensive operation then the big-O of get_tiles_radius is irrelevant
00:30 <Sapient> it also uses a caching mechanism to prevent redundant filtering when [filter_radius] is involved
00:30 <Crab_> yes, if that radius is the last operation (no further terrain filters on result) it should be not relevant to terrain_filter's complexity.
00:34 <Crab_> but, why we consider 'terrain filter' to be the only expensive operation ?
00:35 <Crab_> shouldn't we try to count O() of operations on location sets instead ?
00:39 <Sapient> sure, but map sizes are limited so there will always be an upper bound on location set operation
00:39 <Sapient> whereas the complexity of a location filter SLF is hypothetically infinite
00:40 <Crab_> it depends on what you consider the 'input' to slf - e.g. '1 MAP' or 'N*M locations'
00:42 <Crab_> and, for example, if we switch the implementation to terrain_filter to use something else from std::vector and std::set for it's operations - for example, if we use a content-addressable-table representing the entire map, the complexity will change.
00:43 <Crab_> since, for example, then it'd be possible to check "is the hex present in table?" in O(1), instead of O(log(n)) for std::set.
00:46 <Sapient> I'm definitely in favor of improving the efficiency of our location operations, where reasonable to do so, even though it's only a hypothetical bottleneck at this point
00:46 <Crab_> are SLFs really a bottleneck now ?
00:47 <Sapient> I haven't measured performance myself in Wesnoth, but Mordante did tell me that terrain filtering should be considered expensive
00:48 <Crab_> I've seen this only once, in a very specific circumstances (ai 'avoid' aspect with a long SLF, multiplied by the number of times ai recalculates it's move maps - it's done after each move/attack ) )
00:48 <Sapient> slowness was based on observed issues with TerrainWML
00:49 <Crab_> was it profiled ?
00:50 <mordante> mog did some profiling and optimizations
00:50 <mordante> but there are just a lot of rules to parse
00:50 <Crab_> sometimes profiling wields unexpected bottlenecks... I.e. I once spotted that 5-10% ai turn tume was spent just getting 'is the unit slowed now?' status thing (which, at that time, required std::string constructions and std::map lookups)
00:51 <Crab_> mordante: is there any graphs/results of that profiling posted ?
00:51 <Sapient> SLF can contain SUF, and SUF can contain [filter_wml] which writes the entire unit into a config for comparison
00:51 <mordante> no
00:52 <Crab_> than doing that graphs on some often-used and suspected-for-inefficiency SLFs is a good thing to start.
00:53 <mordante> don't expect me to look into it any time soon, have enough to do with the gui
00:53 <Crab_> I can do it and post the graphs, if someone posts me the WML snippets to be tested
00:54 <Sapient> TerrainWML doesn't use SLF, it uses terrain pattern matching strings, which are also used by SLF
00:55 <Crab_> Sapient: then, we can try to take that getlocations (x,y,radius=a,b,c) thing and see what contributes to its run time.
00:55 <Sapient> Mordante advised me that parsing the terrain pattern matching strings should be considered a fairly expensive operation, and to cache the result for reuse
00:56 <mordante> the wildcard matching is expensive at least that was the bottleneck
00:58 <Sapient> so it seemed wise to treat SLF as arbitrarily complex and eliminate unnecessary calls to matches_filter_internal
00:59 <Sapient> although in practice, I've never experienced slowness due to SLF processing
00:59 <Sapient> with the AI changes it might be the first time
00:59 <Crab_> Sapient: yes, a viable approach. but, then, you should measure complexity in number of SLF calls
01:00 <Shadow_Master> I haven't noticed SLF to be slow in event filters
01:00 <Shadow_Master> (... or maybe I just have too much processor power)
01:01 <Crab_> Sapient: no, it was just a very specific combination of several different things - like unnecessarily very long SLF (related to map specifics), unnecessarily large number of evaluations per turn (related to ai implementation issues)
01:03 <Crab_> I fixes some of those things since then, so that particular slowness disappeared
01:04 <Sapient> ah, ok
01:04 <Crab_> wesbot: log 38101
01:04 <wesbot> crab * r38101 : changes to targeting phase to discard avoided locations earlier
01:04 <wesbot> URL: http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=38101

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.

The only problem that I can see here is that if you're trying to be *really* accurate in emulating sighted events, you only want to fire your faux-sighted event for units spotted by the moving unit. Of course, the existing code for the faux-sighted event fails on this count in several ways as well. Considering the following examples:

1. You want to fire an event when the first Spearman is sighted. However, the player has one Spearman on their team. According to the wiki, a real name=sighted event ignores the already-known spearman, because name=sighted only fires when *new* units come into view. Anonymissus' code fails here if, for example, you move another unit next to the spearman. There's no point at which shroud gets removed, but the faux-sighted fires anyways. Sapient's version (just using [filter_vision] across all units, as I understand it) fails here whenever any unit gets moved. To work around this, you could make your filter more specific than "Spearman", but I'm not sure that that will *always* be the case. Of course, you could just revise the definition of "sighted" somehow.

Ok, I wasn't aware that the sighted event supports that behavior you are describing.
In any case, in the (rare) event that you needed such behavior, you could set a flag on all the already-visible spearmen (such as unit.variables.already_seen) and then add a [filter_wml] against it. I think that situation would be rare enough that it'd be hard to justify adding its complexity to the main macro.

store_unit has to evaluate the location filter for each unit (unless it caches filter results?).

When considering units, store_unit (or any standard unit filter) does not cache anything from one unit to the next one. (Except maybe visibility information for adjacent units, but I wouldn't worry about that.)

[solsword]

I still disagree somewhat with silene's Big-O analysis and I think the [not]x,y,radius=a,b,c[/not] would be beneficial in the general case where {FILTER} is unknown, since it allows us to eliminate the re-processing of arbitrarily complex filters.

Eh. I'm betting that the {FILTER} is fast, I guess. I think this one could go either way, though. In the cases that I've actually used this, {FILTER} either includes presence or absence of a unit from the filtered space (which should be faster than either a [not]find_in or a whole new [not][filter_location] with a radius) or the terrain of the space. Given the comments from IRC below, maybe that terrain filter is slow enough (it's *V*, so basically pretty bad in terms of wildcards) that doing the [not] with a radius or find_in is worth it... In any case, I think the [not]find_in approach is better than the [not]radius approach: [not]find_in is O(n) where n is the number of tiles searched so far, but we know that there will be n hits (one per tile) and approximately 1.5*n misses (one per new tile) which is going to be cheaper than re-constructing a tileset for radius r-1 for each of the n tiles in filter + the 1.5*n tiles outside of it (assuming, as I think people have been indicating, that the [not] clause with a radius results in the construction of that radius for each tile considered by the outer clause). Now, if the [not] radius clause were O(1), then it would always beat whatever {FILTER} was and you'd want to use that.

Ok, I wasn't aware that the sighted event supports that behavior you are describing.
In any case, in the (rare) event that you needed such behavior, you could set a flag on all the already-visible spearmen (such as unit.variables.already_seen) and then add a [filter_wml] against it. I think that situation would be rare enough that it'd be hard to justify adding its complexity to the main macro.

Based on the wiki description, I think it does... but of course that could well be wrong. However, you're right that it's almost never needed... but that's one of the reasons that I still use name=sighted for that half of the macro. As far as I can tell, name=sighted works fine for the case of units spotted when shroud gets removed (which makes sense, since it seems easy to program that way). And all other cases are covered by the simpler of the two moveto events. Of course, even the simpler of the moveto events suffers the problem that I described (triggering on the already-visible spearman), and like you, I don't feel the need to correct for it. Just thought I'd point it out while we're considering the guts of name=sighted.

When considering units, store_unit (or any standard unit filter) does not cache anything from one unit to the next one. (Except maybe visibility information for adjacent units, but I wouldn't worry about that.)

...yeah, I really didn't think that it did. One of these days I'll get around to contributing to the Wesnoth codebase and get in the habit of looking these things up instead of making wild guesses or silly qualifications.

[Anonymissimus]

...I'm definitely not claiming to have understood all of this super high level discussion so far

This

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.

at least makes perfectly sense. I have a solution in mind and I'll try it. I think I'm still using store_unit because in an earlier version I needed the unit variable anyway since I didn't use [primary_unit] for the event to be fired.

The only problem that I can see here is that if you're trying to be *really* accurate in emulating sighted events, you only want to fire your faux-sighted event for units spotted by the moving unit. Of course, the existing code for the faux-sighted event fails on this count in several ways as well. Considering the following examples:

1. You want to fire an event when the first Spearman is sighted. However, the player has one Spearman on their team. According to the wiki, a real name=sighted event ignores the already-known spearman, because name=sighted only fires when *new* units come into view. Anonymissus' code fails here if, for example, you move another unit next to the spearman. There's no point at which shroud gets removed, but the faux-sighted fires anyways. Sapient's version (just using [filter_vision] across all units, as I understand it) fails here whenever any unit gets moved. To work around this, you could make your filter more specific than "Spearman", but I'm not sure that that will *always* be the case. Of course, you could just revise the definition of "sighted" somehow.

FILTER=(
side=2
type=Spearman)
then. That's "revise the definition of "sighted" somehow", yes.

2. You move a unit such that as it moves, it reveals an enemy unit, but once it is done moving, it isn't within range of that unit. In this case, Sapient's code works, but Anonymissus' code fails.

If I understand you, you are wrong. The calculation of the visibility area is based on max_moves of the player's unit that has just moved.
Where is "Sapient's code" btw ? [ironic][event]name=sighted[filter]id=Sapient's code seems buggy...[/ironic]

Let me try again to explain why filter_vision is (unfortunately) no option for case #2 (the player=viewing side=side 1) moves; example:
1. Delay shroud is on.
2. The unit to be spotted has id=A.
3. A unit of the player (id=B) moves in such a way that when the move ends, A would be in B's visibility area, but, because of delay shroud, A is still not visible. Let's say A is three hexes away from B now, and B has max_moves=4 and movement costs 1 for all terrain types, for example.
4. The move has ended; since the event is a name=moveto, the event fires. [filter_vision]side=1 whether A is visible now won't return A since it's still invisible, [fire_event] for the child event won't be called.
(I don't understand what the term "filter on the vision of all units" shall mean btw, what is "all units", all on the map ? That doesn't make sense to me.)
5. The player chooses "update shroud now", or disables "delay shroud", leading to shroud update. A becomes visible. [event] name=sighted is supposed to fire exactly now, but the replacement event still doesn't since it's based on name=moveto!
6. The replacement event would, or could, fire the next time that side 1 moves a unit now, but that's too late for me.
---------------------------------------------
-In step 4, it might also be possible to [filter_vision]side=2 whether B is visible for side 2. But let's say A has max_moves=1. Thus B is (probably) invisible for side 2, [fire_event], again, isn't called.
-Let's say that in step 3, the unit that would come into B's visibility area as the result of B's move isn't A, but unit C (id=C, side=2) instead. [filter_vision]side=2 might now call [fire_event] (if B is visible from C's=side 2's point of view now), but the unit to be spotted is A, not C. That's why I'd want to [filter_vision]id=A which is impossible according to reference wml.
But, since side 2's units can have completely different max_moves/movement costs/visibility areas, [filter_vision]side=2 is probably a bad idea at all.
-Let's say that delay shroud had been off (leave out step 1), and the shroud is updated before the moveto event is called. (Is that correct ? The order might also be vice versa...) YES, then [filter]id=A[filter_vision]side=1 returns A.

However, I know that, from the game engine's point of view, (visibility area of B)=(visibility area of all other side 1 units)=(visibility area of side 1), Sapient. So by saying "B's visibility area" I generally mean that area that side 1 could see if fog was on, delay shroud off and B the only unit of side 1 - the movement area of B with respect to B's movement_costs and B's max_moves (and impassable terrain types...).

[solsword]

at least makes perfectly sense. I have a solution in mind and I'll try it. I think I'm still using store_unit because in an earlier version I needed the unit variable anyway since I didn't use [primary_unit] for the event to be fired.

Yeah, what Sapient said was that even though/if you need the unit, it's faster to do a location filter with an SUF inside it and then [store_unit] using the x and y returned by the filter rather than vice versa. Using the SLF inside the SUF re-evaluates the SLF once for each unit on the map (and on all recall lists), although that of course depends on the order of things. But at best, it evaluates the SLF once for each unit matching the SUF. Putting the SUF inside the SLF, you have the SUF evaluated once for each hex found in the SLF, but since the SUF is fast, while the SLF is slow, this in general gives better performance. I guess if you had a *really* complex SUF, it might be better to do it the other way, but I don't think that that's ever going to come up (since almost any key you put in an SUF makes it pretty fast). Maybe if all you had in there was a [filter_wml]... But in that case you're still betting that running the SLF for *every* unit on the map, and then the SUF only on matching units, is faster than running the SUF on every hex of the SLF (heck, probably only on every unit within the SLF, since I don't think you can construct an SUF that takes a long time before noticing that *there's no unit* on the space that it's trying to filter and returning pretty quickly. If you did, it probably wouldn't be a useful SUF anyways).

If I understand you, you are wrong. The calculation of the visibility area is based on max_moves of the player's unit that has just moved.
Where is "Sapient's code" btw ? [ironic][event]name=sighted[filter]id=Sapient's code seems buggy...[/ironic]

"Sapient's code" is hypothetical... he suggested using [filter_vision] (implicitly over all units in the map, run alongside whatever other filter you specify) instead of your movement-based search. And you're right that delay_shroud will screw that up big-time. I had forgotten about that. Still, your code is vulnerable to the problem that I brought up (#2). I just fiddled with it and realized that the problem never occurs unless some terrain is involved. Since you ignore terrain except for impassibility, the problem is a lot less severe... but it could still happen. Consider this picture:

An example of a move that's problematic for the moveto replacement for name=sighted.

If a unit with 4 moves moves from the dirt patch highlighted in the north to the village highlighted in the south, they get to see the mushroom forest hex along the way (because it's within their max_moves of a point that they passed). Actually, I haven't checked this, but since the player could force that vision by stopping the unit mid-move and continuing, it's a bug if the engine doesn't expose that space for a continuous move. In any case, since the now-visible space isn't within movement range from either the source or the destination, it's never checked in your name=sighted version.

Note that this example comes up reasonably often in underground scenarios, especially when flying units are involved. If you take terrain into account, it also comes up all the time in other maps, when a unit like a horseman moves past a fork in a road through forest or something like that.

So basically, neither version works in both cases. There might be a way to patch Sapient's version by adding an end-of-turn filter or something like that, to catch any units that fell through the cracks of delay_shroud, but it would be odd to have the vision event fire at the end of turn instead of when the unit was revealed (if the player updated shroud mid-turn). It might even cause bugs, or at least cause the player to waste some movement without knowing about a new objective or something like that.

Again, I don't see any problem with continuing to use name=sighted events for this part of the job, because as far as I can tell, they work fine (I have done some basic experiments, but not anything super-intense).

[Sapient]

Also, Delay Shroud and Update Shroud instructions don't even appear in the replay/savefile, which means that relying on this behavior to trigger the sighted event can cause replay/savegame corruption and also OOS in MP.

(That's a C++ bug that you really can't workaround easily though).

I guess there's no way to truly resolve this problem without adding Delay Shroud and Update Shroud instructions to the replay, then teaching the replay_controller about it... but I'm not sure how many lines of code it would require. I'm not actively working on this area of the code right now.

[solsword]

Could the moveto event trigger be delayed until shroud updates? After all, the effect of delay shroud is to allow the player to explore *possible* moves without making *real* moves, giving them the ability to take things back. Of course, this might mess with some existing campaigns... the same issue I mentioned above where you move a unit onto a trigger, but then don't realize until the end of your turn.

Of course, you could store these potential moves in the order that they are made and then replay them one-by-one, stopping (and thus undoing further moves) when any event fires. This replay would occur any time that shroud updates (such as when you attack a unit). The downside is that this would take potentially quite a bit of code... but it does make Sapient's version of the moveto replacement for sighted work, and it gives players even more freedom when delay_shroud is turned on (i.e. they won't trigger events).

[Soliton]

I guess there's no way to truly resolve this problem without adding Delay Shroud and Update Shroud instructions to the replay, then teaching the replay_controller about it...

Probably easier and more robust to not implicitly fire sighted events when replaying and instead record an explicit fire_event command in the replay. There is a somewhat similar issue with ai turn events that will not fire in replays at all since there is no ai involved and thus should also be recorded explicitly in the replay.

[Anonymissimus]

Yeah, what Sapient said was that even though/if you need the unit, it's faster to do a location filter with an SUF inside it and then [store_unit] using the x and y returned by the filter rather than vice versa. Using the SLF inside the SUF re-evaluates the SLF once for each unit on the map (and on all recall lists), although that of course depends on the order of things. But at best, it evaluates the SLF once for each unit matching the SUF. Putting the SUF inside the SLF, you have the SUF evaluated once for each hex found in the SLF, but since the SUF is fast, while the SLF is slow, this in general gives better performance.

Delay is now only roughly 20ms, and seems to work as good as the other version. Thx.

If a unit with 4 moves moves from the dirt patch highlighted in the north to the village highlighted in the south, they get to see the mushroom forest hex along the way (because it's within their max_moves of a point that they passed). Actually, I haven't checked this, but since the player could force that vision by stopping the unit mid-move and continuing, it's a bug if the engine doesn't expose that space for a continuous move. In any case, since the now-visible space isn't within movement range from either the source or the destination, it's never checked in your name=sighted version.

Ah, understood the issue. Yes, that case isn't covered by the moveto replacement, and the game engine behaves the way you think. But still, the problem that name=sighted doesn't fire reliably is too important for me. As I said somewhere above - I've played a scenario that was broken because of a lacking name=sighted event execution. Afaik, sighted events have never been working reliably since I've discovered wesnoth in 1.4.x. There are two in HttT The lost general...

Also, Delay Shroud and Update Shroud instructions don't even appear in the replay/savefile, which means that relying on this behavior to trigger the sighted event can cause replay/savegame corruption and also OOS in MP.

Could be the reason why such a lot of my replays are corrupt although it is said to have been fixed in 1.5.x - even if there aren't any sighted events in that scenarios.

I've made a small test for the [not]find_in=$already_searched_locations and [not]radius=$previous_radius approaches that may improve the FIND_NEARBY algorythm. Sad to say, I can't messure any sensible speed improvement...

[solsword]

Ah, understood the issue. Yes, that case isn't covered by the moveto replacement, and the game engine behaves the way you think. But still, the problem that name=sighted doesn't fire reliably is too important for me. As I said somewhere above - I've played a scenario that was broken because of a lacking name=sighted event execution. Afaik, sighted events have never been working reliably since I've discovered wesnoth in 1.4.x. There are two in HttT The lost general...

I remain skeptical (of sighted being more broken than we know it is). We know that sighted events don't fire during enemy turns, which is a bug. However, the simpler of the two moveto events is a workaround for that. As far as I've ever heard, not firing on enemy turns might well be the only bug in the behavior of sighted. A quick look at the code supports this theory a bit:

Code: Select all

	/**
	 * Returns true if some shroud is cleared.
	 * seen_units will return new units that have been seen by this unit.
	 * If known_units is NULL, seen_units can be NULL and will not be changed.
	 */
	bool clear_shroud_unit(const map_location &loc, int side,
			const std::set<map_location>* known_units = NULL,
			std::set<map_location>* seen_units = NULL,
			std::set<map_location>* petrified_units = NULL)

and then what seems to be the function for updating shroud when coming out of delay shroud:

Code: Select all

void apply_shroud_changes(undo_list &undos, int side)
{
	team &tm = (*resources::teams)[side - 1];
	// No need to do this if the team isn't using fog or shroud.
	if (!tm.uses_shroud() && !tm.uses_fog())
		return;

	game_display &disp = *resources::screen;
	unit_map &units = *resources::units;

	/*
	   This function works thusly:
	   1. run through the list of undo_actions
	   2. for each one, play back the unit's move
	   3. for each location along the route, clear any "shrouded" hexes that the unit can see
	      and record sighted events
	   4. render shroud/fog cleared.
	   5. pump all events
	   6. call clear_shroud to update the fog of war for each unit
	   7. fix up associated display stuff (done in a similar way to turn_info::undo())
	*/

Unless there's some other edge case that I haven't tested or thought of, I think it's reasonable to assume that [event] name=sighted works for all cases when shroud is being removed (i.e. all sighted events triggered during your turn) and the simple moveto event covers all other cases.

Thanks a lot for testing the times, though. It's one thing to debate about how these things work in theory, and another to hear concrete evidence about how they work in practice. Based on the 20ms time, I'm doing something else wrong with my macros that use search that cause a perceptible slowdown.

[Anonymissimus]

Thanks a lot for testing the times, though. It's one thing to debate about how these things work in theory, and another to hear concrete evidence about how they work in practice. Based on the 20ms time, I'm doing something else wrong with my macros that use search that cause a perceptible slowdown.

I was referring to case #2 of the moveto replacement, not the FIND_NEARBY algorithm. The code (not copied, just written out of memory)

Code: Select all

[store_locations]
    [filter]
        {FILTER}
    [filter]
    [and]
        x=$x1
        y=$y1
        radius=...
    [/and]
    variable=...
[/store_locations]

used to calculate whether the unit to be spotted has become visible works a lot faster than the version starting with [store_unit] - as Sapient had suggested.

--------------------------------------------------
Although my beginner C++ knowledge allows me to understand parts of that code , I'd never dare to assume something from it because it "looks ok". You've quoted the starts of some method definitions, their existance alone doesn't mean anything, and the description only says what these methods are supposed to do. I'd need to trigger a faulty sighted event and then debug through that code in an IDE, comparing the values of every variable to what I think it should be, than I might be able to say anything. But I don't even have a clue about "subversion" or what you developers are using there to access the source...

/edit
Tried to reproduce the bug with the lacking name=sighted event using the same savegame - without success. That is, the event always fired the way it should. But I know for sure that the bug had happened during playing. It's just that there must've been some special circumstances I don't know of - if the bug name=sighted not firing in case #2 is deterministic at all...
/edit2
Could repeat it a few times now. But finding out the exact circumstances takes too much time since I'm not going to use name=sighted anyway. Delay shroud update is involved for sure, probably undo and probably more than one unit revealed at once.
/ahem, OK
Here's one way how to fool a name=sighted event in case #2. Seems to work always this way on 1.6.4. Attached is a savegame from the campaign Brave Wings, unfortunately you'll probably need to download that first.
1. Load the savegame
2. Activate "delay shroud update". Note that you can select "update shroud now" without revealing any units at this point.
3. Move the Armageddon Drake on 26,4 to 27,5. I have debug-created this drake on this position, without moving any units in the scenario before.
4. Select "update shroud now" or deactive "delay shroud update." The enemy leader is revealed which should fire an activation code for his side but doesn't.
Note that the event did fire on other trials, displayed some messages and such.

[Sapient]

There are other, more insidious bugs with the "sighted" event... do a search for it on the bug tracker if you're curious. For one thing, there is a fake unit involved when the game is doing the animation for moving a unit. The sighted event can be fired while this fake unit is on the gamemap and any modifications to it will therefore be lost when the fake unit is replaced with the real unit.

I guess there's no way to truly resolve this problem without adding Delay Shroud and Update Shroud instructions to the replay, then teaching the replay_controller about it...

Probably easier and more robust to not implicitly fire sighted events when replaying and instead record an explicit fire_event command in the replay. There is a somewhat similar issue with ai turn events that will not fire in replays at all since there is no ai involved and thus should also be recorded explicitly in the replay.

No, I'm afraid that approach wouldn't account for [filter_vision]. And if we go down that road, of documenting in the replay every time a unit goes in or out of vision for a particular side, then eventually we would have to add a record for every location as well because zookeeper is also requesting a way to filter visibility of locations. Maybe there's a way to improve on it a bit by eliminating records intelligently, but I think it's the wrong approach.

[Anonymissimus]

Yeah, what Sapient said was that even though/if you need the unit, it's faster to do a location filter with an SUF inside it and then [store_unit] using the x and y returned by the filter rather than vice versa. Using the SLF inside the SUF re-evaluates the SLF once for each unit on the map (and on all recall lists), although that of course depends on the order of things. But at best, it evaluates the SLF once for each unit matching the SUF. Putting the SUF inside the SLF, you have the SUF evaluated once for each hex found in the SLF, but since the SUF is fast, while the SLF is slow, this in general gives better performance. I guess if you had a *really* complex SUF, it might be better to do it the other way, but I don't think that that's ever going to come up (since almost any key you put in an SUF makes it pretty fast).

I have the impression that [store_unit][filter][filter_location] checks the filters [filter] and [filter_location] individually, while logically only unit locations with units on it that match the previous unit filter need to be checked. That's what I had in mind when writing that code, and it somewhat surprises me that [store_locations][filter] works a lot better, while complexity of the filters is the same. Mostly, the unit filter is quite restrictive (id=...), so doesn't the location filter only need to be executed once ?
Keeping the thread alive.

/edit
Just seen http://gna.org/bugs/?11286. I must note that the last time I've played that campaign (sceptre of fire) on 1.6.4 the sighted event for the galleon also didn't fire. (I think it hardly ever fired in that campaign.) Fortunately, I could remove the Galleon by attacking it to be able to move onto that hex.
Since a lot of the problems seem to be caused by delay shroud: Could my suggestion to simply ignore delay shroud for this aspect be accepted, if sighted events become working again then ? That means, a sighted event then fires whenever the unit to be spotted comes or would come into visibility range, shroud is forced to update and the event executed.