Consider quest dependencies

[Lotus815]

Current Situation

Many quests have preconditions to get asked
https://wiki.openstreetmap.org/wiki/StreetComplete/Quests
Many quest answers release the preconditions for other quests to get asked.
The newly released quests will not get asked immediately.
Quests which got asked in a Streetcomplete session and release other quests to be asked, will only get asked after downloading and analyzing Openstreetmap data again. Basically this happens after cache timeout or manual cache delete.

Example: Missing house numbers
Quest No1: What kind of building is this?
Quest No2: What is the house number of this building? [requires Quest No1 data]
Quest No3: What street does the (house) number […] belong to? [requires Quest No1 and No2 data]
Short: To map a place, I need to walk it three times in a row. And I need to download and parse all data inbetween each walk.
This is very annoying for a power-user of Streetcomplete.

Requirement

Quests which depend on preconditions, shall be immediately asked once the preconditions are fulfilled. Those quests shall be asked without additional user interaction.

Proposed Solution

Assumptions / Preconditions

• Streetcomplete has the Openstreetmap key/value dataset downloaded
• Streetcomplete locally knows the changed key/value dataset due to user input by quests

Formal documentation of relationships

For each quest, all used input and output keys need to be documented. Values of the keys are not interesting.

E.g. based on https://wiki.openstreetmap.org/wiki/StreetComplete/Quests

Quest No1: What kind of building is this?
Input: building, man_made, historic, military, power, location
Output: building, man_made

Quest No2: What is the house number of this building? [requires Quest No1 data]
Input: building
Output: addr:housenumber, addr:housename, addr:conscriptionnumber, noaddress

Quest No3: What street does the (house) number […] belong to? [requires Quest No2 data]
Input: addr:housenumber, addr:street, addr:place, addr:block_number, addr:streetnumber
Output: addr:street, addr:place

Partial parse related quests

After a quest is answered, trigger partial parse of related quests on the changed key/value dataset.
Related quests are quests which have at least one input key of any key of the output keys of the answered quest.
Partial parse means: not parse all quests like after downloading the key/value dataset from Openstreetmap server.

Option 1: Parse only dataset of changed object

Trigger partial parse only on the changed key/value dataset of the changed object.

Option 2: Parse whole dataset

Trigger partial parse only on the whole key/value dataset.
Pro: May be easier initial development
Con: CPU load, user interaction

Further enhancements

Static check for possible deadlocks of the quests

Based on the formal documentation of the relationship between the quests, possible deadlocks can be detected by a static check.
Deadlock means in this case, quests which depend on each other and may never get asked.
The quest relations must be a tree structure and must not reference in a loop.
Those structural problems of the quests can be assessed.

Quests-in-row for quests related to same object

Immediately display "next quest" for the object after the user answers a quest for the identical object. The user must not interact with Streetcomplete to get the "next quest" dialogue for the identical object asked. Note: May be generic requirement to show also for unrelated quests which complete keys for the identical object, e.g. for streets: surface, sidewalk, lit in a row. FIFO list of quest for object may be a generic structure.

For example, below quests can be asked without additional user interaction once first quest is answered:

Quest No1: What kind of building is this?
Quest No2: What is the house number of this building?
Quest No3: What street does the (house) number […] belong to?

[matkoniecz]

See #1510 for what was discussed already

[westnordost]

Well, the easier technical solution rather than creating and maintaining complex dependency chains of quests is to just keep all OSM data downloaded in a bounding box. Though, this will lead to a lot of data being persisted in the local storage.

[rhhsm]

Much could already be improved if non-dependent quests on an object would be loaded at the same time. I don't understand, for instance, why I have to visit a new shop at least twice, once to survey its name, and then its opening hours. Surely a shop doesn't need a name to have opening hours. (Residential) roads usually also need several visits. Quests on steps are a good example of how I'd prefer it: surface, lit and all steps-specific quests can be answered in one visit.

[smichel17]

a lot of data being persisted in the local storage

How much is a lot?

[westnordost]

As much as is being downloaded.

[smichel17]

I was thinking along the lines of — we already cache map tiles; how much space would osm data for an area take up compared to that?

[westnordost]

I don't know.

[Lotus815]

See #1510 for what was discussed already

Thanks for the references. Boundary conditions are different today and blocking preconditions are resolved beginning from release v26.

Well, the easier technical solution rather than creating and maintaining complex dependency chains of quests is to just keep all OSM data downloaded in a bounding box.

This will not answer how to find the new quests based on added information. This is what the initial post is about.

According to initial post, the proposal involves neither creating nor maintaining complex dependency chains. Only metadata is maintained locally to each quest in the individual quest definition. Based on this, the follow-up quests can be easily found via an appropriate data structure available in the programming language, e.g. dictionary (I have no know-how in Kotlin).

Though, this will lead to a lot of data being persisted in the local storage.

A lot of data can be purged. Only a minority of it is interesting. Those are only all the objects for which quests are found after initial parsing. Only for those objects, follow-up quests can be found.

Why to you close and tag the issue wontfix? We have a serious problem in Streetcomplete functionality. Software is all about solving problems. If software doesn't solve problems, it is useless. It is a waste of time to go mapping with the current Streetcomplete, as long as you need to visit the same place multiple times. To put it with the project wording: Valuable Surveyors: Surveyor time is valuable. If I would be able to contribute in Kotlin, I would branch SC by myself after discussion.

Maybe some of the developers can at least provide an impact analysis, what need to be refactored?

[westnordost]

Sure, I can do that. I closed this because I will not implement it. Someone else can have a try. Also, note that most of what you suggested already works, only for a few quests it does not. See the OsmQuestGiver class.

What would need to be done would be the following:

1. On download, instead of discarding downloaded data that did not lead to the creation of at least one quest, persist all downloaded OSM data in the database
2. Implement some caching that takes care of discarding old downloaded data not used by any quest anymore so that data usage doesn't grow endlessly - similar to how it is done now with the map tiles. I.e. probably just additionally record when an element has last been downloaded/updated
3. Keep around a persisted data structure that sorts the downloaded elements into a raster / quadtree for fast spatial access of this data (i.e. loading all elements from database that are within a given bounding box / tile rect). Could be a table with the following columns: element id, element type, x, y. x and y would be the tile number at f.e. zoom 16.
4. the OsmQuestGiver would need to be refactored so that in updateQuests, if questType.isApplicableTo returns null (or always), all the elements for the tile in which the passed in element resides are loaded from database and instead questType.getApplicableElements is called - for each quest type. If the applicable elements for a quest type contain the passed in element, a quest of that quest type can be created.

Needless to say, this is hugely inefficient. So after that basic functionality is there, it is imperative to concern oneself with how to make it less inefficient. Ideas:

• keep the map data for the current tile (though, which is the "current" tile?) in memory
• maybe don't call getApplicableElements for each questType for the whole map data for each solved quest but instead add a second optional parameter to isApplicableTo: mapData. More implementation effort though. Not exactly sure what would be the best approach.

[smichel17]

Perhaps this is due to my own (intentional: #1889 (comment)) ignorance of osm, but quest dependencies do not seem particularly complicated to me. Certainly less complicated than the analysis just above.

1. Add a new type of quest, PendingHouseNumberQuest. Its query is like the house number quest but without the building type constraint. isApplicableTo(element) returns true.
2. In updateQuests, add an additional check to filter out any PendingHouseNumberQuests. (ie, they should never be shown)
3. When a building type quest is completed, run this pseudocode:

   if (element has a PendingHouseNumberQuest) {
       if (selected building type is eligible for the house number quest) {
           convert PendingHouseNumberQuest to a regular house number quest
       } else {
           delete PendingHouseNumberQuest and associated data
       }
   }
   

   I don't know this part of the code well enough to say exactly where it would need to happen; perhaps this is the complex part.

This way, there is no special caching required (data is stored and deleted through the normal mechanisms), and no special data structures needed to filter elements in a given tile — you just need to check the single element that has been changed. I can see this getting complex with anything more complicated than this scenario, where the decision about whether to show a quest is dependent only on the value of one other tag. However, as @westnordost noted, there are actually only a few quests for which this is needed.

Actually, I will go further: I think this is the only quest with this type of relationship that is impactful enough to be worth implementing this type of behavior. So, I think it's an acceptable trade-off to implement a single "quest dependency" as a special case, rather than create an abstraction for it. As long as the number of places where we need to check for the special case remains small (here: just two?), I think the benefit outweighs the less clean code.

edit: I've now looked at AddHouseNumberQuest and am starting to understand the problem better. Anyone replying to this, hold off on that for a little…

[smichel17]

I've run out of time that I can justify looking in to this right now; it is a bigger project than I thought. For anyone else interested in understanding this, here is a complete list of the specific files/functions I needed to look at to understand how this area of the code works, overall:

• OsmQuestGiver: updateQuests() and recreateQuests()
• OsmElementUpdateController: update()
  • OsmInChangesetsUploader: upload() and updateElement()
  • SplitWaysUploader: updateElement()
• AddHouseNumber quest: isApplicableTo() and the general form (not details) of applyAnswerTo() and getApplicableElements()
  • For applyAnswerTo(): HousenumberAnswer
  • For getApplicableElements(): OsmApiQuestDownloader: parts of download()

I still think it is possible to write a special case for house numbers as a "dependency", in a relatively self-contained way. It would use basically the same code path as way splitting. It would involve a check for quest type (instead of ignoring that info) in OsmInChangesetsUploader.updateElement().

[matkoniecz]

The main problem here is that each such hack is relatively easy. But after you add 10 or 20 or 100 such hacks you end with bizarre bugs where you change one thing, adjust 25 hacks but because hack number 12 also needed to be adjusted you end with bizarre bug happening for completely unclear reason.

And StreetComplete already has some bizarre, hard to reproduce bugs happening for unclear reasons, bugs caused by upstream issues like #1236 and so on.

[smichel17]

#1236, while bizarre, is not hard to reproduce (it happens when you put a time picker in a dialog). It also has totally separate circumstances; it happens when interacting with two separate third-party components (dialog and time picker), whereas my proposal here interacts with none — it is entirely self contained.

But after you add 10 or 20 or 100 such hacks

I totally understand this, and already addressed it: I am not proposing adding any other "such" hacks (ie, hacks of the same type). Yes, this approach could be used for roof shape and other per-country-disabled quests, but I don't think it should, because they are not as important as the house number quest. Given that, I think that adding a "proper" abstraction to serve this single quest would be more likely to cause bugs than what I am proposing. Creating a huge abstraction to cover what may be a 20-30 LoC edge case is not a good trade-off.

Plus, it's a very tame hack. In my opinion, storing the information, "element E will be eligible for quest Q if tag T is added to it with a value of X, Y, or Z" is a pretty reasonable approach (ie, not a hack), as a lighter-weight alternative to caching all of the relevant OSM data needed to re-run getApplicableElements from scratch. Same for passing the quest that was completed into the update function. The hacky part is storing the information as a normal quest rather than creating a proper abstraction. Actually, I was originally going to propose doing that (a PossibleQuest class); I changed my mind for similar reasons to the previous paragraph.