Auto path

[Brambor]

Summary

Features "Player can record paths and automatically walk them again"

Purpose of change

Resolve #74433

Describe the solution

Listen with u.get_path_manager()->record_step to when the avatar moves in

void avatar_moves( const tripoint &old_abs_pos, avatar &u, const map &m )

Add the new_pos to std::vector<tripoint_abs_ms> recorded_path. If a cycle is detected, remove it.

Add an interface, where the player can manage their paths:

Known issues to fix / features to implement:

• [ ] Recording path across ramp doesn't work (stairs do work).
  • (Will be) fixed by #74762
• [x] When a problem occurs, it continues recording. I want to change this to fail fast.
  • Example of detectable unsolved problem: lift going more than 1 z-level.
  • 
  • [x] The latest version crashed on me, so I need to fix at least one crash.
  • [ ] (i) hover next to Walk the path button: Walk the first path from the list the player is standing on either end.

Will not fix:

• [ ] When naming start/end the string_popup is under the window (barely visible) but it does work.
  • Will not fix, unless somebody tells me how to easily do it without migrating string_input_popup to ImGui.

Further not-implemented improvements

• [x] I have a nice optimizations in my back pocket, described in the issue #74433

  • Look at one point at index i, count the distance from the new point dist = abs(z1-z2) + max(abs(x1-x2), abs(y1-y2)). The new point cannot be at indexes i-dist+1, ..., i+dist-1. So skip those in-loop checking.

dist optimization results

--- For the optimization, I ended up doing `max( tripoint_diff.abs().xyz() )` . The results are pretty amazing: 4 checks instead of 800 on this test path: https://github.com/CleverRaven/Cataclysm-DDA/assets/13402666/c6d2dc67-b2fd-40eb-9090-b5ccd76e660e Works reasonably in a spiral. I especially like how the number of checks decreases despite the number of tiles increasing when the character walks away from the spiral at the end: https://github.com/CleverRaven/Cataclysm-DDA/assets/13402666/7f44f12e-a91b-44aa-853c-497edd3e01f8 ---

• [x] Also, add QoL optimization to cut corners: going north and then west can be replaced by going north-west. In general: iterate over recorded_path from begin() to end() with tile, if the player is next to the tile, delete everything from tile to recorded_path.end(). This is similar to loop optimization but more aggressive.
• [ ] A checkbox to turn off cut-corner optimization.
• [ ] New button: Take an already recorded path the player is standing at either end of. Start recording (again) to edit this path as if recorded for the first time.
• [ ] New button: fix path. Something interrupted the walking (even if you did). You can snip the next tile of the path. This leaves two separate paths: from_start & till_end. Start recording until you reach any tile from till_end. Then glue them together (from_start ends at your feet, remove tiles from till_end from the snipped tile until the tile under your feet. Merge paths and that is your result.) - Not sure whether this works when the path has loops.
  • [ ] "Abort fix path" button. It stops everything and restores the original path before snipping.
• [ ] Remember the path and the direction the player was walking. The player can press "continue walking". They continue if they are on the same path (even at different tile of the path). Otherwise popup with info to the closest tile and the tile you left the path: popup( "You are no longer standing on the path you were walking. You left the path 3SW, closest tile is 1N." )
  • This is close to a special case of the next one. So don't do this.
• [ ] New button:
  1. Find paths under the player's feet (not start/end but any tile).
     • With the optimizations, this could be decently fast.
  2. The player selects a path.
  3. The player selects whether to go to the path start or the path end.
     • [ ] Edit paths without the need to walk them: Instead of walking, record the cursor position in look around. Such paths might need some fixing on first use.

Describe alternatives you've considered

Record keystrokes https://github.com/CleverRaven/Cataclysm-DDA/issues/74433#issuecomment-2171117437

Testing

I tried whatever I could think of. Should work on flat ground, with stairs, and ladders. Doesn't work with ramps, I will look into Travel To code when I have the time.

Additional context

[Brambor]

It is not ready for merge, but it is ready for review.

[anothersimulacrum]

I'm not sure this is a benefit. Like macros, this risks making it a player responsibility to make up for deficiencies in game systems and UX.

[Brambor]

@anothersimulacrum You are not the only one. @ GuardianDll pushed back too and warned me. I am totally fine with this not being merged. As stated on Discord, I made it for myself. Merging is just more convenient to me.

[Brambor]

TL;DR: I see the alternatives as either suboptimal or more work (for the player).

I disagree though, that Travel to, and such, could be improved to the level this would be completely obsolete. For me, Travel to would have to find the optimal* path between A and B and that is next to impossible in all cases. Small improvements just don't do it for me. I need to believe the path is optimal.

Just not being able to mark tiles as dangerous per-tile makes Travel to sub optimal. If that was implemented, then marking all dangerous tiles would be too much work. So let's consider only tiles I walked on already, I could have walked into a puddle I don't want to walk into again. Then I need to mark it off again. I could mark furniture_type = puddle to be blacklisted. That wouldn't work, since it sometimes is better or possible to only walk through puddle. So we would define cost for each tile ... ... ...

[Brambor]

Recording path across ramp doesn't work (stairs do work).

I just found out that Travel to doesn't work with ramps either: Commanding the character to Travel to to the tile below the cursor.

The moment you step down it cancels:

Edit: I think I fixed that, PR coming soon.

[github-actions[bot]]

Spell checker encountered unrecognized words in the in-game text added in this pull request. See below for details.

Click to expand

* Recorded path has no **lenght**. Path erased.

This alert is automatically generated. You can simply disregard if this is inaccurate, or (optionally) you can also add the new words to tools/spell_checker/dictionary.txt so they will not trigger an alert next time.

Hints for adding a new word to the dictionary

* If the word is normally in all lowercase, such as the noun `word` or the verb `does`, add it in its lower-case form; if the word is a proper noun, such as the surname `George`, add it in its initial-caps form; if the word is an acronym or has special letter case, such as the acronym `CDDA` or the unit `mW`, add it by preserving the case of all the letters. A word in the dictionary will also match its initial-caps form (if the word is in all lowercase) and all-uppercase form, so a word should be added to the dictionary in its normal letter case even if used in a different letter case in a sentence. * For a word to be added to the dictionary, it should either be a real, properly-spelled modern American English word, a foreign loan word (including romanized foreign names), or a foreign or made-up word that is used consistently and commonly enough in the game. Intentional misspelling (including eye dialect) of a word should not be added unless it has become a common terminology in the game, because while someone may have a legitimate use for it, another person may spell it that way accidentally.