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:

• [x] 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.
    • Migrating string_input_popup to ImGui needs migrating string_input_popup::*history which uses uilist so it needs its migration which is being done in #74341

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.
• [x] 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.
  • [ ] (i) hover next to the button: Continue recording the first path the player is standing at either end of. Temporarily swaps start and end until the recording is finished.
• [ ] 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.

Edit: Fixed in

• #74762

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

[db48x]

I really like the UI!

[Brambor]

I will continue with this on 2024-07-22. I just figured this could be improved:

I want (i) to show in detail what some buttons do. (i) doesn't show in ImGui demo ~with my version of ImGui. I should mark that regression separately~.

I would like it if a TAB would always switch focus from buttons to paths list. I will see if I can make the buttons unselectable. Like in the keybindings menu.

I dislike that when you browse paths with UP & DOWN, the bright blue is "hovered over" and light blue is "selected". This is confusing. I accidentally deleted the wrong path.

• Maybe related: #76033

Add a popup on deleting a path. With all the path's info.

The keybindings are what I figured could work. The menu could be opened with } by default.

[Brambor]

Added "Walk path from middle", see the Original Post.

[kevingranade]

Just to repeat what guardiandll and anothersimulacrum already told you, this isn't getting merged, but if you want to work on it in this PR that's fine.

[Brambor]

Just to repeat what guardiandll and anothersimulacrum already told you, this isn't getting merged, but if you want to work on it in this PR that's fine.

I thought my argument was accepted:

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

But ok, thanks for letting me know. I guess I don't need to polish it any further then.

[Brambor]

It is ready. I am leaving it in draft since it will not get merged. Then reviewers don't have to look at an open PR.

[Brambor]

Well, that's an option too...

[CoroNaut]

There may be a place for this when we finally get #70056. I would hate to move between far outposts by hand every time. This would make a world of difference on quality of life.

[Brambor]

There may be a place for this when we finally get #70056. I would hate to move between far outposts by hand every time. This would make a world of difference on quality of life.

Your usecase is already likely solved by overmap auto travel (or whatever is it called).

[CoroNaut]

My use case would be the ability to just open this window, select 'home' and the auto-travel makes the route. This is much better for quality of life than just opening the map, scrolling 20-100+ tiles, fumbling with a BUNCH of keypresses and using the fast scroll keybind, then selecting auto travel. Both ways... Auto travel is fantastic, but this specific window would save me thousands of keypresses within an IRL week, and 10,000+ keypresses in the long run.

This isn't even considering that once we get the vaguely defined official map, the key locations will be farther apart. Having to remember the coordinates of refuge center, then traveling to the other side of the map for stuff would get tedious fast.

[Brambor]

I feel like what you want is: A "Waypoints" menu.

• Open it on the map UI. (Or just mention it there, but also make it a default keybinding.)
• It may have a layout similar to this PR's UI. Add invlets.
• Unlike this PR, it has only destinations, not paths from A to B. To make them:
• • To make a destination, you don't have to walk and remember the path from A to B.
• • You just mark an Overmap tile on the map as a destination. Or better yet any tile within the overmap tile, not the middle of it (like the outside tile of the door).
• Selecting a destination, works like the overmap travel, not like this PR.

Now that you mention it, I like it too.

OR you could "jump to waypoints", then the travel becomes:

1. Open the map UI.
2. Open Waypoints.
3. Press an invlet / scroll / click etc. at the waypoint to select it.
   • the camera jumps to the waypoint on the map
4. Press W twice to start the travel.
   • The first previews the route, and the second walks the route.

[CoroNaut]

A waypoints UI would be absolutely amazing as an alternative to the PR. The auto travel is becoming robust enough that this would be reasonable to have.

[Brambor]

@CoroNaut Actually, Notes can already serve this purpose so there is no reason to add waypoints.

Setup:

1. Make a note. To filter nicely, you can add @ or something at the start not _ though, as that is part of colour tags.

Usage:

1. map
2. List notes
3. / Filter (this doesn't show in the vid as filter is still not in ImGui)
4. <string to find>
5. <CONFIRM> to confirm filter
6. <CONFIRM> to jump to note
7. WW mark route; walk marked route
8. <CONFIRM> to travel

If that is too many various keypresses, you can add a keybinding to the first three, like ctrl+T, then it becomes ctrl+T*3 <string to find> <CONFIRM>*2 WW <CONFIRM>

https://github.com/user-attachments/assets/c2f11923-05e8-4676-8227-216fb794853f

[Brambor]

Note: If this is used for your use case, you would need n! routes for n places. That is 24 routes for 4 places to travel from any one place to another.

[CoroNaut]

To clarify my use case a bit more, I suppose I was hoping to set up routes like a tree. My base would be the center, then I'd have like 3 nodes going out, 5 off of those, etc. Then I could just use those auto-paths to get back to my base or out to specific locations. The nodes are required to route around cities or dangerous locations. Then I would go Base->around Prescott-> down the highway-> along the forest -> lab. Then back. If I found myself far off my web of paths, I would make another node and link up.

If there was a sorting for the closest note in the notes window, I could just have the @ to identify my nodes as you suggest. I would filter, and it would just show my closest nodes. This would be the easiest solution for this specific use case. It would be a O(log(n)) number of keypresses for each node, rather than O(n) for scrolling across kilometers of the overmap. This would definitely be enough for me specifically. Your UI would be O(log(n)) keypresses to travel long distances for example. The hassle would be recording the paths in the first place, and having to open the UI after every stop.

However, it would be nicer to have something everyone can clearly see and use, like a separate UI, like the one you made. I suppose the best possible UI for my use case would be a way points UI that allows you to select any number of nodes, then use auto-travel to go between the nodes automatically. It would be auto-travel, but smarter. The user makes the path across the overmap all in one go, then just says "ok.., this node, this node, this node... GO!". And the UI just takes you from your location to all the nodes you selected one after the other until you're at your location.

[Brambor]

Does marking a zone on the map as dangerous not suffice? I think I understand what you want, but UX-wise to go to individual nodes to get to your destination will be too much of a hassle and would be suboptimal too. For overmap travel that is.

I would need concrete examples (in-game, real) to be swayed. I think the overmap travel with marking danger and using notes as waypoints should be enough.

On the programming side, a graph like you showed could be created. In setup, you would connect the nodes. And you would just select the destination when using it to travel and an algo (A*/Dijkstra) would find the nodes to go through... But I still need to see examples of when a graph is better than waypoints, which are sufficiently done with notes.

An example of overmap travel with marked danger.

[Brambor]

By deliberately looking for it, I found a bug in my optimization algorithm with a single ramp connecting two empty floors:

Let's say the character starts South to the upper staircase.

1. On the upper floor, start recording.
2. Walk onto the ramp. [North]
   • The ramp forces you to go z-1 immediately.
3. Walk off and back onto the ramp. [North, South]
   • (Walking back cuts the path.)
   • This forces you to go to z+1 immediately.
   • Walking up cuts the path.
   • You are now standing at a point where you got previously in step 2, but it forced you to go z-1, now it didn't.
4. Walk off the ramp. [North]

If you go back to the start and walk the path recorded, you will end up a floor below where you wanted to be:

1. Walk North onto the ramp.

   • This forces you to go z-1 immediately.

2. Walk North off the ramp.

Such ramp can be found in a mine:

It doesn't notify the player or anything. If you add some obstacles, the character just gets stuck and stops the auto-walking.

I didn't find a way to break it on the bridge:

Note: The algorithm remembers tripoints, I am writing North and South for ease of understanding.

• Fixing this would be an annoying addition, as the algorithm would have to consider forced movements or look at the map for ramps.
• Changing ramps is an option too. Make them not force the movement. This could lead to a different bag of snakes.
• At least a warning that this happened should be presented to the player.

[Brambor]

Or maybe the ramp is placed incorrectly? No, even if it is, I bet the bug can be reproduced similarly.

But maybe ramps should be changed... Isn't it weird you can enter a ramp from every tile and go up? Is it like a spiral ~staircase~ ramp? Or maybe it isn't worth modeling to such detail.

I don't get why we have ramps and stairs. Ramps are just stairs that allow vehicle movement, but force you to go to the different floor.

[Brambor]

But I still need to see examples of when a graph is better than waypoints, which are sufficiently done with notes.

Maybe, if we play in a dangerous world, it is worth marking individual safe nodes and safe paths between them, rather than marking all the dangers.

Also, travelling between safe nodes is always safe, if path doesn't exist, it reports it. Travelling on an unsafe map can be dangerous, if the path goes through a dangerous spot you didn't anticipate and the user should always check what path was suggested before accepting it.

However, in-game, I find the map to not be dangerous. You can travel by vehicle and back out off any encounter faster than the monsters catch up to you. And even travelling on foot, you can see the monsters sooner than they see you. So then you back off, mark area as dangerous and start auto travel again.

TL;DR: Cataclysm is too safe to warrant a safe node travel.

[CoroNaut]

An idea I got just now after reading your comment: It would be pretty cool if there was an underlying 'dangerous' map that could overlay on the regular map. If there are zombies/turrets/dangers in any way present, it could be marked on the map with yellow/red automatically and be ineligible for fast travel (if the overlay is turned on). This way, the current point to point auto travel would already have a decent sense of what areas to avoid.

IMO, having an auto-path is more about quality of life rather than actually avoiding dangerous areas. I would personally prioritize taking an inefficient path between nodes that has no chance to be interrupted. A path that passes nearby zombies that could trip safe mode is just annoying. The player automatically tries to go around dangerous areas, but offloading the thought and the keypresses needed to do that onto the game is what makes it a quality of life upgrade for me.

[Brambor]

Force pushing latest changes, I had to reopen and close for that.

[Brambor]

The naming popup was migrated to ImGui, so it works now! (It isn't behind the manager window.)

[Brambor]

This time I want to see if tests where an avatar moves pass. I changed the implementation regarding tests in the last commit.

I will close this again afterwards.

[Brambor]

All tests pass. That is nice.