Fast travel (Autodrive v2)

[eltank]

Is your feature request related to a problem? Please describe.

Players that settle down in a base often need to drive repeatedly to and from far-away locations, either for questing/trading or for looting interesting locations (e.g. labs). Traveling to a new location for the first time can be fun because you have to find a good path and deal with various perils and obstacles on the way. However subsequent trips are usually either boring (repetitive key presses) or annoying (having to constantly avoid wrecked cars and boulders). I think some automation would be helpful here and the current auto-drive feature doesn't cut it (very poor obstacle avoidance, can't drive off-road and can't follow custom paths).

Describe the solution you'd like

I'm planning to improve the existing auto-drive feature in the following ways:

Obstacle avoidance / autodrive improvements

The main idea here is to refactor the game engine a bit to allow simulating the position of the vehicle several [game] turns into the future, accounting for various amounts of steering at each turn. This can be used to compute a reachability graph containing all the positions that the vehicle can reach in the near future without colliding with anything. Dynamic programming A* can be used to collapse the multiple paths that reach the same spot and use search heuristics such as "don't drive away from the goal". This needs to be re-evaluated every turn, but the previously-selected optimal path should be cached and reused if it's still collision-free. Non-stationary obstacles (e.g. monsters) should be given a 1-tile buffer zone for the purposes of collision detection (for the immediate next turn only) since they can move into your path.

The current auto-drive algorithm uses as a waypoint the midpoint of the edge shared by the current and next OMT (overmap tile) in the path. This may be infeasible to reach due to an obstacle at or near that point. To fix this, the plan is to consider all points along that boundary that can be reached and try to pick something that gets as close as possible to the middle.

Another problem is that avoiding obstacles is difficult when travelling at high speed. The new algorithm will drop the speed to the minimum value when it's not able to find a path at high speed and try to raise it back up after clearing the current OMT. Future improvements may drop the speed less (e.g. binary exponential reduction until a path is found or the minimum is reached).

PR #49772 [merged on 7/31/2021]

• Precompute and cache reachability graph
• Drive along an approximate-best collision-free path to reach the next OMT
• Optimize for performance
• Try to leave extra room when navigating around obstacles
• Handle NPC drivers
• Support boats and aircraft (current z-level only)
• Support amphibious navigation
• Handle visibility issues
• Anticipate possible collisions due to moving creatures (and bail out)
• Travel faster than the minimum speed (1 tile/turn)
• Try to avoid dead ends by looking ahead one extra OMT

PR #50803 [merged on 8/17/2021]

• Frame skipping (speed up driving animation)

Deferred tasks:

• Handle z-level transitions via ramps
• Try to steer more than once per turn
• Try driving in reverse when starting out
• Try to avoid driving over loot
• Vehicle avoid zones, to protect loot piles and avoid pathfinding mistakes
• Parking zones
• Support for turning in place (for vehicles that can)
• Support rail vehicles
• (maybe) Ask NPC to drive you somewhere

Overmap pathfinding and UI improvements

This is aimed at letting you autodrive to any place that you can reach via manual driving. It should also let you avoid driving through places that are blocked (e.g. fields that are covered by trees, roads that are blocked by large wrecks) or are unsafe (e.g. overmap tiles with lots of monsters).

PR #50637 [merged on 8/9/2021]

• Allow pathfinding through field tiles and farm roads (but prefer paved roads)
• Take into account the vehicle's offroad driving coefficient
• Allow biking on forest trails
• Always allow pathing through the current OMT
• Handle player and vehicle being on separate OMTs

PR #50835 [merged on 8/21/2021]

• Make pathfinding work with bridges
• Prefer diagonal (faster) paths when pathing through air, lakes or fields
• Pick optimal paths using A* search

Deferred tasks:

• Prioritize pathfinding through OMTs that the player has visited before
• Allow toggling OMTs that should be avoided by autodrive pathfinding
• Allow toggling OMTs that are not normally considered drivable to allow pathfinding on them (e.g. empty parking lots or the road tiles in the military base, after you unblock the entrance)
• Autodrive -> Resume, to continue driving after stopping to deal with something
• "Travel to..." in vehicle menu, to reduce manual input needed to select frequent destinations
• Generate paths including z-level changes for flying vehicles
• (if necessary) Increase the overmap pathfinding distance and optimize performance; look into Jump Point Search

Recorded paths [scrapped]

This was the main point of the initial proposal, but now seems unnecessary. Autodrive v2 has already proved capable of handling "tricky" paths well enough and Vehicle Avoid Zones will let the player teach the system to avoid navigation mistakes. Designated Parking Zones as well as overmap UI changes to toggle OMT drivability should allow for plenty of path customization.

Tasks:

• Add "Record path" to vehicle driving menu. Record position, heading and speed at each game turn. Stop driving also stops recording
• Add "Replay path" to vehicle driving menu, replay a previously recorded route. Requires starting from the same starting position. Can be interrupted
• Serialize recorded paths to JSON
• Optimize the path representation for memory and disk space
• Change do_autodrive() to prioritize paths that follow the recorded path
• Change autodrive overmap pathfinding to consider (and prioritize) OMTs that have recorded paths on them
• Zone manager integration to allow viewing and deleting recorded paths

As an alternative to all of the above, it may be enough to simply use the Zone manager to add autodrive hints at the sub-map level (spots that pathfinding should prioritize routing through).

[Checked items have been implemented but not necessarily turned into PRs.]

Describe alternatives you've considered

Instant fast-travel (teleport player and vehicle to destination + advance time). Very easy to implement but there's no way that would be approved, right?
"Fast-travel by teleportation is pretty much off the table. if we do it, it’ll just be continuously auto-moving, possibly skipping some redraws to speed things up." -- Kevin Granade 2015

An earlier design was built entirely around recorded paths (see above), going all the way from the player base to some far away destination. Abandoned because of poor usability, versatility and discoverability.

Additional context

This will probably take weeks or months to do. If anyone wants to help implement any of this I am perfectly willing to collaborate.

Has this been suggested/attempted before? I tried a few searches but didn't find anything on github. I did find some stuff on discord but very old. [1] [2]

[Initial proposal on 6/23/2021, rewritten on 6/28/2021 as "v2" and further refined on 7/8/2021 as "Autodrive v2"]

[Saicchi]

How would you handle random events like hordes or the vehicle skidding in a replay? Stop the replay and ask the player to handle the situation?

[eltank]

How would you handle random events like hordes or the vehicle skidding in a replay? Stop the replay and ask the player to handle the situation?

With Phase 1 functionality the replay will stop if the vehicle goes off-course or is unable to maintain the recorded speed, which will happen if the vehicle hits anything, skids due to low driving skill, or runs out of fuel. If you see you're about to crash you can also interrupt with the skip-turn key. No way to resume, so you have to drive the rest of the way yourself, or go back to the starting point if it's closer and try again.

In Phase 2 either safe mode or collision detection should kick in before you hit anything. The player can either stop and deal with the problem or drive around it, then resume. Existing auto-drive code will be used to try to get back on track, which may fail.

[This answer is obsolete due to design changes on 6/28]

[PatrikLundell]

Note that unless your vehicle is completely symmetrical around the pivot point, a return path won't be identical unless you drive the whole distance in reverse gear. Thus, generation of a return path isn't trivial if you've got some tight spots along the path.
In fact, I suspect return paths won't be identical because of accelerations/deceleration probably not being identical.

My "standard" obstacle driving issue is bridges with vehicles forming an obstacle course where you have to move very precisely to get past without the swiveling causing the vehicle to swivel into either the railing or a blocking vehicle (often requiring a 30 degree angle movement so that you can move a tile sideways [eventually] while still having the vehicle oriented straight).

[Saicchi]

It might be easier to improve the auto-driving feature that already exists. Though I don't know much about AI driving.

[robotic-gamer]

some alternate solutions

• if being able to swap into npc followers becomes a thing, you'd just need to order them to travel were you want then swap to them.
• if alternate dimensions becomes a thing you could use it to travel faster like the nether in minecraft. or there could be a really "empty" dimension ideal for travelling long distances.
• being able to make aircraft could solve long distance travel
• making highways that are largely straight and wide would help in long distance travel

[eltank]

Note that unless your vehicle is completely symmetrical around the pivot point, a return path won't be identical unless you drive the whole distance in reverse gear. Thus, generation of a return path isn't trivial if you've got some tight spots along the path.
In fact, I suspect return paths won't be identical because of accelerations/deceleration probably not being identical.

Right, that's why it's further down the list in Phase 2. Driving in reverse could work but is unrealistic (you wouldn't / couldn't actually do that IRL) so I prefer to find an algorithm that generates a forward-driving route back to the starting point. If the vehicle is not perfectly symmetrical and the route involves "tight spots" then the auto-generated route may cause collisions, which is why collision detection is higher up in the list.
[This answer is obsolete due to design changes on 6/28]

It might be easier to improve the auto-driving feature that already exists.

It might be easy for someone other than me. If such a person is willing to do the work then by all means they should go for it.
After further consideration, I agree :)

[actual-nh]

I'm considering converting this to a discussion. Thoughts?

[eltank]

I'm considering converting this to a discussion. Thoughts?

I just need a place to collect feedback and report progress. If it's customary to put feature discussions in Discussions these days, then by all means feel free to move it there.

[pehamm]

Recording and replaying speed and acceleration would mean that you could run into issues if you load up additional materials in the car, as additional weight reduces possible acceleration. If you are too heavy, you may not replicate the path because you cannot not accelerate fast enough, if you are too light you may accelerate too fast and take sharper turns than intended, leading to offsets and crashes. Checking vehicle position at least periodically could alleviate this a bit, but then you deviate from the idea that you replicate the path using speed, acceleration and turn commands.

Getting this as a working feature would be an amazing QoL change, but I believe getting this right even as a basic implementation is incredibly complex.

[eltank]

Yes, any significant changes to the vehicle's handling properties, including acceleration and turning speed (which also depends on the player's speed stat) can cause the vehicle to go off-course when using the Phase 1 algorithm. This doesn't make the feature unusable, but it does limit its usability a fair bit.

This is supposed to be addressed in Phase 2. There's already code in the game for auto-driving to a specific map tile so the plan is to use that code, probably with some modifications (to get it to match a velocity vector i.e. position+speed+direction), to get back on track.

In any case, I expect to have a prototype version (first 2 tasks on the list) ready fairly soon. We'll see how well it works in practice.

[This answer is obsolete due to design changes on 6/28]

[PatrikLundell]

I agree with pehamm that a simple recording/replay probably won't work with any degree of reliability. Instead, a path probably would have to be recorded as a path the vehicle should strive to follow, and the recording process should probably also check the size of the space available to the path (i.e. width between fixed obstacles, room for turning at some maximum speed, etc. and generate a path flagged as either illegal or with a warning if sufficient room isn't available. It might be useful to have the usage of paths monitor obstacles to allow them to remove or add warning flags. It doesn't exactly seem trivial, as pehamm points out.
It would be useful to be able to resume/rejoin paths if you're sufficiently close to them (e.g. to resume to your destination after making a small detour to eliminate some threat or something that caused the auto pilot to switch over to manual, or simply have some paths to nearby facilities that you can then join up with to return home if you've taken a turn to a side road to go somewhere else).

[eltank]

a simple recording/replay probably won't work with any degree of reliability

As I said in my other reply, we'll find out how well it works after the prototype is done.

It would be useful to be able to resume/rejoin paths if you're sufficiently close to them

That's already on the task list ("Hop onto a recorded route from any position").

I had a new idea recently. I am contemplating changing the existing overmap auto-drive (which lets you drive to a destination from the map UI) to make use of one or more pre-recorded paths if they exist. So instead of having to record the whole route, you'd just need to record segments that get through areas that auto-drive can't handle (city streets littered with cars and off-road areas with boulders, shrubs, trees and ponds). I need to think about this more.

Edit: this idea has been expanded into a full design

[actual-nh]

A recursive process with waypoints: Try auto-driving to the destination. If this looks like it won't work, try auto-driving to the penultimate waypoint, and so on. Once you get (approximately?) to a waypoint, repeat the process.

This depends on being able to tell (from recorded and current information) whether auto-driving can work for getting from the current position to a given point.

[eltank]

I finished a proof-of-concept implementation (record and replay). Video demos below (only for the replay part).
However, I'm still not happy with the UI. I think it's very difficult for new players to figure out how to use this feature. The existing route selection on the overmap UI is much more intuitive, so I need to combine the new feature with the old UI.

Now that I've had a chance to mess with the autodrive code I think I can actually change it to avoid obstacles and to drive off-road. Recorded paths should only be needed for getting through tough spots, or maybe not needed at all.
I'll rewrite the design in the next few days. [done]

to_base.mp4

from_base.mp4

Also, yay for Github video uploads! Too bad the files have to be <10Mb.

[eltank]

Thanks to everyone who provided feedback so far! Please note that the design/plan has been changed completely, and the focus is now on fixing what's wrong with the current auto-drive feature.

[actual-nh]

Note, BTW, the very sensible D* idea - plan (if sufficient information is available) from the destination point backward, and keep some info from it so that, if you get diverted, you can use the stored information to quickly get going again. Your current point changes a lot more than the target point!

[eltank]

I'm not sure what you're referring to. Is this about following a pre-recorded path or finding the path to the next OMT? In the latter case there would not be a single destination point, but rather all the points along the nearest OMT edge would be valid destinations.

Since I'm planning to use simulation to predict the future during autodrive, I don't expect to get diverted from a predicted path except under very rare circumstances (e.g. player's speed stat drops a lot due to temperature and steering is slower), so in practice I should only have to run pathfinding once per OMT, then follow the optimal path to the next OMT edge, checking only for imminent collisions each turn (this can still happen due to moving obstacles). And if path diversions are rare, then the simple approach of re-running the whole algorithm from scratch when a diversion does occur shouldn't be an issue.

Thanks for reminding me of A* and its brethren. I've actually never used these algorithms before (that I can remember) so this'll be a good opportunity to play with them. I'll probably start with a simple but inefficient algorithm though (e.g. bounded BFS) and optimize later.

[actual-nh]

(Quite welcome.) Note the question on running simulations of whether to take care to keep randomness (e.g., direction of a zombie's stumbles) the same or allow it to vary.

[eltank]

Sorry, I should clarify what I mean by simulation. I don't mean to simulate everything that happens in the game since I think that's a bit too expensive. I just need to simulate what happens to the vehicle's pivot point in response to an autodrive action (steer left/right up to 3 times or just go forward, at the lowest possible speed), while keeping track of player/driver moves carried over from one turn to the next (which affects the amount of steering possible next turn). For the placement of the other vehicle parts w.r.t. the pivot point I can just precompute that once by rotating a copy of the vehicle in all possible directions (360/15 = 24 possibilities). For each possible orientation I can then precompute the set of "nearby" map tiles that the pivot point can occupy without causing any vpart to overlap with an obstacle (nearby = current OMT area plus a bit of padding). The pathfinding algorithm then needs to find a path that the pivot point can follow along these "safe" tiles in order to reach one of the "goal" tiles.

I don't intend to make auto-drive excel at moving around enemies/critters, mainly because it would introduce extra code complexity and runtime cost. I'll probably just treat them as 3x3 stationary obstacles for the purpose of pathfinding, and if they move in front of the vehicle collision detection should kick in and cancel auto-drive (if the player didn't cancel it already due to the "enemy spotted" prompt). Players should keep their common driving routes clear by killing or luring away enemies and scaring away or hunting wildlife.

[eltank]

I finished implementing the obstacle avoidance code, using A* as the pathfinding algorithm. I gave up on the idea of using "perfect simulation" for the vehicle's motion (it seemed too expensive) and implemented approximate simulation instead. As a result, the algorithm is very fast (can't even notice any delays) and uses very little memory. However it also bugs out half of the time (deviating from the predicted path, which cancels auto-drive).

In addition to fixing that bug I need to address some of the current limitations before creating a PR:

• always drives at the lowest possible speed (walk speed)
• steering is at most 15 degrees per turn
• doesn't detect collisions until after they happen

Anyway, here's a demo of the code in action. When it works correctly it's pretty impressive.

roadblock.mp4

I'll post a demo of longer-distance travel after I get the bug sorted.

[PatrikLundell]

Impressive! I'd say that driving is better than what I'm producing...

[eltank]

As soon as it gets merged into the main game I am going to use the shit out of it.

When everything that's been planned here is implemented and working properly there will be little reason to ever drive manually through explored and mostly clear areas.

Would the code work with helicopters/high speed things?

Helicopter support including takeoff and landing is on the project roadmap, but further away. If you don't mind doing the takeoff and landing manually I can probably add support for flying to a destination on the same z-level (>0) relatively easily (not in the first PR though).

Going at slightly higher speeds (up to 3x walk speed) when there are no obstacles in the way is in scope for the initial PR, though going at the maximum safe speed that the vehicle is capable of (or a lower user-specified limit) will have to wait for later due to the extra complexity of simulating deceleration over multiple turns and due to needing to take into account the effect of high speed on steering.

[Zeropol]

The videos are astounding ! I would have imagined such a result involve months of work. Astonishing, and seems more reliable than manual driving.

[JackReport]

Would the code work with helicopters/high speed things?

Helicopter support including takeoff and landing is on the project roadmap, but further away. If you don't mind doing the takeoff and landing manually I can probably add support for flying to a destination on the same z-level (>0) relatively easily (not in the first PR though).

Helicopters are still a bit wonky with collision detection, I don't mind doing the takeoff, just that if you go a distance it takes forever to travel/load and you have to hold down the period key, or do something that takes time like eating.(which risks a crash if you don't pay attention.)

The current autodrive freaks out and fails, even when there is no objects in the air to collide! A big thing about this game for me is removing tedium. I enjoyed helicopters a lot due to not having to constantly drive around because of that, this improvement will help me enjoy the game more, so thanks man!

[eltank]

@JackReport I ended up adding helicopter support in PR #49772, which is under review. There's a demo video there as well.

[eltank]

The second PR (#50637) which fixes a few issues, mainly offroad driving, is currently under review. Videos on the PR page.

[pehamm]

After playing around with this for a while, this is a total gamechanger. It is insane how much tedium this saves.

I have two questions/suggestions:

Any way to force the vehicle to use only streets would be nice. It is easy to clear out the main connecting streets so I can just send it out to a far-away point and ignore the game because I know it will take a path free of monsters. But with the new offroading, I have found that once the vehicle leaves the street, it becomes harder to predict which path it will take and leads to more disruptions because it tries to pass mass graves or similar densly packed areas. This could be a setting or just a heuristic to only path through streets if both start and end tiles are streets and they are connected via roads. Just a suggestion should this be easy to do.

A bit more involved, are successive waypoints something that is feasible? This would allow to more explicitly chart paths that avoid uncleared map extras which I as a player am aware of, but the game cannot. In terms of interface, the current system could be tweaked to start setting waypoints with "W", finishing by confirming the last one with "W" and clearing with "Esc". That could make things even simpler.

And thank for for the great work!

[schealex]

I also thought about that. A waypoint system would allow the player to further specify which route the car should take but let it find the path between waypoints on its own. On my current map for example i have a vast road network which is sometimes disconnected and or there are towns surrounded with forest. And i don't want to fast-travel through them. So for now i'm doing my travel from point a->b->c->d->e but it would be awesome if you could define that in one go to circumvent specific areas!

[eltank]

Any way to force the vehicle to use only streets would be nice. It is easy to clear out the main connecting streets so I can just send it out to a far-away point and ignore the game because I know it will take a path free of monsters. But with the new offroading, I have found that once the vehicle leaves the street, it becomes harder to predict which path it will take and leads to more disruptions because it tries to pass mass graves or similar densly packed areas.

I have two planned changes to address this.
First, the overmap pathfinding is still broken due to not implementing A* properly, so the per-tile weights I set in #50637 don't take effect they way they should. Once that's fixed the path will look better.

Second, another upcoming feature will keep track of which OMTs you have previously been on and prioritize those -- if the destination is a visited tile it'll try to path only through visited tiles (because those should be safe). I'm planning to add a UI layer on the overmap similar to "land use codes" (which BTW I haven't figured out why it's in the game) in which you can toggle safe tiles and dangerous tiles similar to how you can toggle explored tiles today.

Both of these will probably be ready this week, though maybe without the UI.

This [waypoints] would allow to more explicitly chart paths that avoid uncleared map extras

My plan for that is to allow marking tiles as dangerous. I'll see if I can automate it for map extras (as an improvement to auto-notes) but initially you may have to use the overmap UI to manually mark tiles to avoid. I agree that right now it's annoying when autodrive wants to take you over a "crater" map extra and if you don't notice you get irradiated. Although, for crater map extras you don't need to avoid the whole OMT, just the crater itself and eventually that'll be possible with Vehicle Avoid zones (another planned feature).

are successive waypoints something that is feasible?

Yes, but:

• I also want to allow the player to change the destination without introducing unwanted waypoints. Something like "Esc" to cancel could work, except now that just closes the map. It seems a new key would be needed and the list of keys in the overmap UI sidebar is already pretty long.
• Waypoints should not be necessary. Once fixed, autodrive should always give you the shortest safe path to your destination. If you want to stop somewhere else first, you could simply autodrive there. If the path autodrive picks isn't actually safe you'll be able to use the map UI to tell it which tiles to avoid.

Another way to look at it: waypoints provide temporary navigation hints for one trip, but marking tiles safe/unsafe provides persistent navigation hints for all future trips in that area.

[PatrikLundell]

I think waypoints would still be useful, because you'd otherwise have to designate a whole area around a dangerous tile as dangerous to avoid the danger from it. One example is a corpse pit, where you may want to pass sufficiently far away from it that you don't attract the zombies gathered around it. In this case, driving close will draw them further and further into the path for every time you pass by.
The worse case is mycus, where I never want to get close enough to get any spore into the reality bubble, and so need to make a wide berth, or the path will eventually go through the mess while simultaneously spreading it. This applies to triffids as well, but to a lesser extent.
A third example is a roadblock, where you want to pass sufficiently far away from it that the turrets can't fire at you, and you also have the issue of drawing the zombies around it into your path.
A fourth example is things like ant hives, where a huge area around the hive is crawling with ants, so you don't want to go through that area (although the fringes tend to have a lower ant density you still have the problem of drawing them more and more into the path for each passage).

All of these issues essentially boil down to dangerous tiles having a danger radius the size of which is dependent on the nature of the danger, so it might be easier to just set a few waypoints to ensure you go around.

[alex19EP]

hello @eltank thank you for your work.

I wanted to point out the enormous importance of your work, which you hardly thought about.

the fact is that this project significantly improves the ability of blind people to drive vehicles in a cataclysm.

I played cataclysm last summer and had a bike. even with legacy autodriving system, I managed to enjoy the game. I will be happy to check how pleasant it is to play now.

[eltank]

Hi @alex19EP, I am always in awe when I read testimonials from blind CDDA players, I think that's pretty amazing. I'm happy to hear that my changes are also making the game more accessible.

I have two features planned that you may like.

1. The ability to assign names to locations in the game and then ask autodrive to take you there via the vehicle driving menu (though I'm not sure how accessible the CDDA menus are in practice).
2. The ability to designate parking spots, so that the car (or bike) will always park in the same place when you return home. You would only need to struggle once to find a good parking spot and after that you'll nail the parking every time.

Another feature I'm planning, unrelated to autodrive, but which may also be of interest to you is a warning message that would be printed when a monster notices your character.

Hope you enjoy the game!

[schealex]

hey @eltank are you still working on this? I'm really enjoying the new features and i'm looking forward for the additional open tasks that still need implemenation :)

[eltank]

Taking a break at the moment, will likely do more work during winter vacation.

[ViachaclauSlepau]

Adding autoguidance will immediately add a new problem, a huge number of map files. My cards weigh 1 GB each and it takes an unbearably long time to load the game.