veloren_world/civ/airship_travel.rs
1use crate::{
2 sim::WorldSim,
3 site::{self, Site, plot::PlotKindMeta},
4 util::{DHashMap, DHashSet, seed_expan},
5};
6use common::{
7 store::{Id, Store},
8 terrain::CoordinateConversions,
9 util::Dir,
10};
11use rand::prelude::*;
12use rand_chacha::ChaChaRng;
13use std::{fs::OpenOptions, io::Write};
14use tracing::{debug, warn};
15use vek::*;
16
17const AIRSHIP_TRAVEL_DEBUG: bool = false;
18
19macro_rules! debug_airships {
20 ($($arg:tt)*) => {
21 if AIRSHIP_TRAVEL_DEBUG {
22 debug!($($arg)*);
23 }
24 }
25}
26
27/// A docking position (id, position). The docking position id is
28/// an index of all docking positions in the world.
29#[derive(Clone, Copy, Debug, Default, PartialEq)]
30pub struct AirshipDockingPosition(pub u32, pub Vec3<f32>);
31
32/// An airship can dock with its port or starboard side facing the dock.
33#[derive(Debug, Copy, Clone, PartialEq, Default)]
34pub enum AirshipDockingSide {
35 #[default]
36 Port,
37 Starboard,
38}
39
40/// An approach for the airship provides the data needed to fly to a docking
41/// position and stop at the docking position. The approach provides a target
42/// 'final' postion that is offset from the docking postion such that
43/// when the airship flys from the final position to the docking position, the
44/// airship will be naturally aligned with the direction of the docking
45/// position, and only very small orientation adjustments will be needed
46/// before docking. The approach final position is selected to minimize the
47/// change of direction when flying from the takeoff location to the target
48/// docking position.
49#[derive(Clone, Debug, PartialEq)]
50pub struct AirshipDockingApproach {
51 pub dock_pos: AirshipDockingPosition,
52 /// The position of the airship when docked.
53 /// This is different from dock_pos because the airship is offset to align
54 /// the ramp with the dock.
55 pub airship_pos: Vec3<f32>,
56 /// The direction the airship is facing when docked.
57 pub airship_direction: Dir,
58 /// Then center of the AirshipDock Plot.
59 pub dock_center: Vec2<f32>,
60 /// The height above terrain the airship cruises at.
61 pub height: f32,
62 /// A 3D position that is offset from the direct line between the dock sites
63 /// to allow for a transition to the direction the airship will be
64 /// facing when it is docked.
65 pub approach_initial_pos: Vec2<f32>,
66 /// Intermediate position from the initial position to smooth out the
67 /// directional changes.
68 pub approach_final_pos: Vec2<f32>,
69 /// There are ramps on both the port and starboard sides of the airship.
70 /// This gives the side that the airship will dock on.
71 pub side: AirshipDockingSide,
72 /// The site name where the airship will be docked at the end of the
73 /// approach.
74 pub site_id: Id<Site>,
75}
76
77/// A route that an airship flies round-trip between two sites.
78#[derive(Clone, Debug)]
79pub struct AirshipRoute {
80 /// site\[0\] is the home site, site\[1\] is the away site.
81 pub sites: [Id<site::Site>; 2],
82 /// approaches\[0\] is flying from the home site to the away site.
83 /// approaches\[1\] is flying from the away site to the home site.
84 pub approaches: [AirshipDockingApproach; 2],
85 /// The distance between the two sites.
86 pub distance: u32,
87}
88
89impl AirshipRoute {
90 fn new(
91 site1: Id<site::Site>,
92 site: Id<site::Site>,
93 approaches: [AirshipDockingApproach; 2],
94 distance: u32,
95 ) -> Self {
96 Self {
97 sites: [site1, site],
98 approaches,
99 distance,
100 }
101 }
102}
103
104/// Airship routes are identified by a unique serial number starting from zero.
105type AirshipRouteId = u32;
106
107/// Data for airship operations. This is generated world data.
108#[derive(Clone, Default)]
109pub struct Airships {
110 /// The airship routes between sites.
111 pub routes: DHashMap<AirshipRouteId, AirshipRoute>,
112}
113
114// Internal data structures
115
116/// The docking postions at an AirshipDock plot.
117/// The center is the center of the plot. The docking_positions
118/// are the positions where the airship can dock.
119#[derive(Clone, Debug)]
120struct AirshipDockPositions {
121 pub center: Vec2<f32>,
122 pub docking_positions: Vec<AirshipDockingPosition>,
123 pub site_id: Id<site::Site>,
124}
125
126impl AirshipDockPositions {
127 fn from_plot_meta(
128 first_id: u32,
129 center: Vec2<i32>,
130 docking_positions: &[Vec3<i32>],
131 site_id: Id<site::Site>,
132 ) -> Self {
133 let mut dock_pos_id = first_id;
134 Self {
135 center: center.map(|i| i as f32),
136 docking_positions: docking_positions
137 .iter()
138 .map(|pos: &Vec3<i32>| {
139 let docking_position =
140 AirshipDockingPosition(dock_pos_id, pos.map(|i| i as f32));
141 dock_pos_id += 1;
142 docking_position
143 })
144 .collect(),
145 site_id,
146 }
147 }
148}
149
150/// Used while generating the airship routes to connect the airship docks.
151/// Encapsulates the connection between two airship docks, including the angle
152/// and distance.
153#[derive(Clone, Debug)]
154struct AirRouteConnection<'a> {
155 pub dock1: &'a AirshipDockPositions,
156 pub dock2: &'a AirshipDockPositions,
157 pub angle: f32, // angle from dock1 to dock2, from dock2 the angle is -angle
158 pub distance: i64, // distance squared between dock1 and dock2
159}
160
161impl<'a> AirRouteConnection<'a> {
162 fn new(dock1: &'a AirshipDockPositions, dock2: &'a AirshipDockPositions) -> Self {
163 let angle = Airships::angle_between_vectors_ccw(
164 Airships::ROUTES_NORTH,
165 dock2.center - dock1.center,
166 );
167 let distance = dock1.center.distance_squared(dock2.center) as i64;
168 Self {
169 dock1,
170 dock2,
171 angle,
172 distance,
173 }
174 }
175}
176
177/// Dock connnections are a hash map (DHashMap) of DockConnectionHashKey to
178/// AirRouteConnection. The hash map is used internally during the generation of
179/// the airship routes.
180#[derive(Eq, PartialEq, Hash, Debug)]
181struct DockConnectionHashKey(Id<site::Site>, Id<site::Site>);
182
183/// Represents potential connections between two airship docks. Used during the
184/// generation of the airship routes.
185#[derive(Clone, Debug)]
186struct DockConnection<'a> {
187 pub dock: &'a AirshipDockPositions,
188 pub available_connections: usize,
189 pub connections: Vec<&'a AirRouteConnection<'a>>,
190}
191
192impl<'a> DockConnection<'a> {
193 fn new(dock: &'a AirshipDockPositions) -> Self {
194 Self {
195 dock,
196 available_connections: dock.docking_positions.len(),
197 connections: Vec::new(),
198 }
199 }
200
201 fn add_connection(&mut self, connection: &'a AirRouteConnection<'a>) {
202 self.connections.push(connection);
203 self.available_connections -= 1;
204 }
205}
206
207impl Airships {
208 /// The Z offset between the docking alignment point and the AirshipDock
209 /// plot docking position.
210 const AIRSHIP_TO_DOCK_Z_OFFSET: f32 = -3.0;
211 // the generated docking positions in world gen are a little low
212 const DEFAULT_DOCK_DURATION: f32 = 90.0;
213 /// The vector from the dock alignment point when the airship is docked on
214 /// the port side.
215 const DOCK_ALIGN_POS_PORT: Vec2<f32> =
216 Vec2::new(Airships::DOCK_ALIGN_X, -Airships::DOCK_ALIGN_Y);
217 /// The vector from the dock alignment point on the airship when the airship
218 /// is docked on the starboard side.
219 const DOCK_ALIGN_POS_STARBOARD: Vec2<f32> =
220 Vec2::new(-Airships::DOCK_ALIGN_X, -Airships::DOCK_ALIGN_Y);
221 /// The absolute offset from the airship's position to the docking alignment
222 /// point on the X axis. The airship is assumed to be facing positive Y.
223 const DOCK_ALIGN_X: f32 = 18.0;
224 /// The offset from the airship's position to the docking alignment point on
225 /// the Y axis. The airship is assumed to be facing positive Y.
226 /// This is positive if the docking alignment point is in front of the
227 /// airship's center position.
228 const DOCK_ALIGN_Y: f32 = 1.0;
229 const ROUTES_NORTH: Vec2<f32> = Vec2::new(0.0, 15000.0);
230 const STD_CRUISE_HEIGHT: f32 = 400.0;
231 const TAKEOFF_ASCENT_ALT: f32 = 150.0;
232
233 #[inline(always)]
234 pub fn docking_duration() -> f32 { Airships::DEFAULT_DOCK_DURATION }
235
236 #[inline(always)]
237 pub fn takeoff_ascent_height() -> f32 { Airships::TAKEOFF_ASCENT_ALT }
238
239 /// Get all the airship docking positions from the world sites.
240 fn all_airshipdock_positions(sites: &mut Store<Site>) -> Vec<AirshipDockPositions> {
241 let mut dock_pos_id = 0;
242 sites
243 .iter()
244 .flat_map(|(site_id, site)| {
245 site.plots().flat_map(move |plot| {
246 if let Some(PlotKindMeta::AirshipDock {
247 center,
248 docking_positions,
249 ..
250 }) = plot.kind().meta()
251 {
252 Some((center, docking_positions, site_id))
253 } else {
254 None
255 }
256 })
257 })
258 .map(|(center, docking_positions, site_id)| {
259 let positions = AirshipDockPositions::from_plot_meta(
260 dock_pos_id,
261 center,
262 docking_positions,
263 site_id,
264 );
265
266 dock_pos_id += positions.docking_positions.len() as u32;
267 positions
268 })
269 .collect::<Vec<_>>()
270 }
271
272 /// Generate the network of airship routes between all the sites with
273 /// airship docks. This is called only from the world generation code.
274 ///
275 /// After world sites are generated, the airship operations center creates a
276 /// network of airship routes between all the sites containing an
277 /// airship dock plot, and there are airships placed at each docking
278 /// position that will be used for an airship route. Each airship travels
279 /// between two sites. This is the airship's route (out and back). When
280 /// an airship is created, the ops center internally assigns the airship
281 /// a route based on the airship's home docking position and the airship
282 /// routing network. Since a route is between two sites, and therefore
283 /// between two docking positions, there are two airships flying in opposite
284 /// directions.
285 ///
286 /// Todo: On longer routes, it should be possible to determine the flight
287 /// time and add airships to the route to maintain a schedule. The
288 /// airships would be spawned midair so that they don't appear our of
289 /// nowhere near the ground.
290 ///
291 /// Airships are assigned a flying height based on the direction of
292 /// travel to deconflict as much as possible.
293 pub fn generate_airship_routes(
294 &mut self,
295 sites: &mut Store<Site>,
296 world_sim: &mut WorldSim,
297 seed: u32,
298 ) {
299 let all_docking_positions = Airships::all_airshipdock_positions(sites);
300 // Create a map of all possible dock to dock connections.
301 let mut rng = ChaChaRng::from_seed(seed_expan::rng_state(seed));
302 let mut routes = DHashMap::<DockConnectionHashKey, AirRouteConnection>::default();
303 all_docking_positions.iter().for_each(|from_dock| {
304 all_docking_positions
305 .iter()
306 .filter(|to_dock| to_dock.site_id != from_dock.site_id)
307 .for_each(|to_dock| {
308 routes.insert(
309 DockConnectionHashKey(from_dock.site_id, to_dock.site_id),
310 AirRouteConnection::new(from_dock, to_dock),
311 );
312 });
313 });
314
315 // Do four rounds of connections.
316 // In each round, attempt to connect each dock to another dock that has at least
317 // one connection remaining. Assign scores to each candidate route based
318 // on:
319 // 1. How close the candidate route angle is to the optimal angle. The optimal
320 // angle is calculated as follows:
321 // - 0 existing connections - any angle, all angles are equally good.
322 // - 1 existing connection - the angle for the vector opposite to the vector
323 // for the existing connection.
324 // - 2 existing connections - calculate the triangle formed by the first two
325 // route endpoints and the dock center. Find the centroid of the triangle
326 // and calculate the angle from the dock center to the centroid. The
327 // optimal angle is the angle opposite to the vector from the dock center
328 // to the centroid.
329 // - 3 existing connections - calculate the triangle formed by the first
330 // three connection endpoints. Find the centroid of the triangle and
331 // calculate the angle from the dock center to the centroid. The optimal
332 // angle is the angle opposite to the vector from the dock center to the
333 // centroid.
334 // 2. The distance from the dock center to the connection endpoint. Generally,
335 // the further the better, but the score function should be logarithmic to
336 // not favor so much amongst the longer distances.
337
338 let mut dock_connections = all_docking_positions
339 .iter()
340 .map(DockConnection::new)
341 .collect::<Vec<_>>();
342
343 // The simple angle score is how close a2 is to the opposite of a1. E.g. if a1
344 // is 0.0, the the best score is when a2 is PI.
345 let angle_score_fn = |a1: f32, a2: f32| {
346 let optimal_angle = (a1 + std::f32::consts::PI).rem_euclid(std::f32::consts::TAU);
347 let angle_diff = (optimal_angle - a2)
348 .abs()
349 .min(std::f32::consts::TAU - (optimal_angle - a2).abs());
350 1.0 - (angle_diff / std::f32::consts::PI)
351 };
352
353 // The centroid angle score function calculates the angle from the dock center
354 // to the given 'centroid' vector, then applies the angle score function
355 // with a1 being the centroid angle and a2 being the route angle.
356 let centroid_angle_score_fn =
357 |centroid: Vec2<f32>, dock_center: Vec2<f32>, rt: &AirRouteConnection| {
358 let centroid_dir = centroid - dock_center;
359 if centroid_dir.is_approx_zero() {
360 return 0.0;
361 }
362 let centroid_angle =
363 Airships::angle_between_vectors_ccw(Airships::ROUTES_NORTH, centroid_dir);
364 angle_score_fn(centroid_angle, rt.angle)
365 };
366
367 // The distance score function is logarithmic and favors long distances (but not
368 // by much). The lower cutoff is so that docks within 5000 blocks of
369 // each other are not connected unless there are no other options. The final
370 // division and subtraction are used to scale the score so that middle
371 // distances have a score of around 1.0.
372 let distance_score_fn = |distance: i64| {
373 // Note the distance argument is the square of the actual distance.
374 if distance > 25000000 {
375 (((distance - 24999000) / 1000) as f32).ln() / 8.0 - 0.5
376 } else {
377 0.0
378 }
379 };
380
381 // overall score function
382 let score_fn = |con: &DockConnection, rt: &AirRouteConnection| {
383 let mut angle_score = match con.connections.len() {
384 // Anything goes
385 0 => 1.0,
386 // Opposite angle
387 1 => angle_score_fn(con.connections[0].angle, rt.angle),
388 // Centroid angle of triangle formed by the first two connections and the dock
389 // center
390 2 => {
391 let centroid = (con.connections[0].dock2.center
392 + con.connections[1].dock2.center
393 + con.dock.center)
394 / 3.0;
395 centroid_angle_score_fn(centroid, con.dock.center, rt)
396 },
397 // Centroid angle of triangle formed by the first three connections
398 3 => {
399 let centroid = (con.connections[0].dock2.center
400 + con.connections[1].dock2.center
401 + con.connections[2].dock2.center)
402 / 3.0;
403 centroid_angle_score_fn(centroid, con.dock.center, rt)
404 },
405 _ => 0.0,
406 };
407 let distance_score = distance_score_fn(rt.distance);
408 // The 5.0 multiplier was established by trial and error. Without the
409 // multiplier, the routes tend to have a long distance bias. Giving
410 // the angle score more weight helps to balance the resulting route
411 // network.
412 angle_score *= 5.0;
413 (angle_score, distance_score, angle_score + distance_score)
414 };
415
416 for _ in 0..4 {
417 let mut best_trial: Option<(Vec<(Id<site::Site>, Id<site::Site>)>, f32)> = None;
418 // 100 loops to shuffle the dock connections and try different combinations is
419 // enough. Using 1000 loops doesn't improve the results.
420 for _ in 0..100 {
421 dock_connections.shuffle(&mut rng);
422 let candidates = dock_connections
423 .iter()
424 .filter(|con| con.available_connections > 0)
425 .collect::<Vec<_>>();
426 let mut trial = Vec::new();
427 let mut trial_score = 0f32;
428 for chunk in candidates.chunks(2) {
429 if let [con1, con2] = chunk {
430 let dock1_id = con1.dock.site_id;
431 let dock2_id = con2.dock.site_id;
432 let dock1_route = routes
433 .get(&DockConnectionHashKey(dock1_id, dock2_id))
434 .unwrap();
435 let dock2_route = routes
436 .get(&DockConnectionHashKey(dock2_id, dock1_id))
437 .unwrap();
438 let score1 = score_fn(con1, dock1_route);
439 let score2 = score_fn(con2, dock2_route);
440 trial_score += score1.2 + score2.2;
441 trial.push((dock1_id, dock2_id));
442 }
443 }
444 if let Some(current_best_trial) = best_trial.as_mut() {
445 if trial_score > current_best_trial.1 {
446 *current_best_trial = (trial, trial_score);
447 }
448 } else {
449 best_trial = Some((trial, trial_score));
450 }
451 }
452 if let Some(ref final_best_trial) = best_trial {
453 for (site1, site) in final_best_trial.0.iter() {
454 let dock1_route = routes.get(&DockConnectionHashKey(*site1, *site)).unwrap();
455 let dock2_route = routes.get(&DockConnectionHashKey(*site, *site1)).unwrap();
456 let con1 = dock_connections
457 .iter_mut()
458 .find(|con| con.dock.site_id == *site1)
459 .unwrap();
460 if con1.available_connections > 0 {
461 con1.add_connection(dock1_route);
462 }
463 let con2 = dock_connections
464 .iter_mut()
465 .find(|con| con.dock.site_id == *site)
466 .unwrap();
467 if con2.available_connections > 0 {
468 con2.add_connection(dock2_route);
469 }
470 }
471 }
472 }
473
474 // The dock connections are now set.
475 // At this point, we now have a network of airship routes between all the sites
476 // with airship docks, and we have a list of docking positions for each
477 // site. As airships are generated, they can be assigned a route based
478 // on their home docking position and the airship routing network.
479 // The number of airships per dock is determined by the number of connections at
480 // the dock. The docking positions used at the dock can be random. Each
481 // airship will have a route assigned that it will fly, out and back,
482 // round trip between two sites. This needs to remain constant so that
483 // travelers can know where the airship is going. The routes can be generated
484 // before the airships, and when an airship is generated, the appropriate route
485 // can be found by finding the docking position id for the docking position with
486 // the wpos closest to the airship position. When an airship is is loaded from
487 // saved RTSim data, the assigned routes will already be available. The airship
488 // routes will be persisted in the rtsim data.
489
490 let mut routes_added = DHashSet::<DockConnectionHashKey>::default();
491 // keep track of the docking positions that have been used on either end of the
492 // route.
493 let mut used_docking_positions = DHashSet::<u32>::default();
494
495 let mut random_dock_pos_fn =
496 |dock: &AirshipDockPositions, used_positions: &DHashSet<u32>| {
497 let mut dock_pos_index = rng.gen_range(0..dock.docking_positions.len());
498 let begin = dock_pos_index;
499 while used_positions.contains(&dock.docking_positions[dock_pos_index].0) {
500 dock_pos_index = (dock_pos_index + 1) % dock.docking_positions.len();
501 if dock_pos_index == begin {
502 return None;
503 }
504 }
505 Some(dock_pos_index)
506 };
507
508 let mut airship_route_id: u32 = 0;
509 dock_connections.iter().for_each(|con| {
510 con.connections.iter().for_each(|rt| {
511 if !routes_added
512 .contains(&DockConnectionHashKey(rt.dock1.site_id, rt.dock2.site_id))
513 {
514 if let Some(from_dock_pos_index) =
515 random_dock_pos_fn(rt.dock1, &used_docking_positions)
516 {
517 if let Some(to_dock_pos_index) =
518 random_dock_pos_fn(rt.dock2, &used_docking_positions)
519 {
520 let from_dock_pos_id =
521 rt.dock1.docking_positions[from_dock_pos_index].0;
522 let to_dock_pos_id = rt.dock2.docking_positions[to_dock_pos_index].0;
523 let approaches = Airships::airship_approaches_for_route(
524 world_sim,
525 rt,
526 from_dock_pos_id,
527 to_dock_pos_id,
528 );
529 let distance = rt.dock1.docking_positions[from_dock_pos_index]
530 .1
531 .xy()
532 .distance(rt.dock2.docking_positions[to_dock_pos_index].1.xy())
533 as u32;
534
535 self.routes.insert(
536 airship_route_id,
537 AirshipRoute::new(
538 rt.dock1.site_id,
539 rt.dock2.site_id,
540 approaches,
541 distance,
542 ),
543 );
544 airship_route_id += 1;
545
546 used_docking_positions.insert(from_dock_pos_id);
547 used_docking_positions.insert(to_dock_pos_id);
548 routes_added
549 .insert(DockConnectionHashKey(rt.dock1.site_id, rt.dock2.site_id));
550 routes_added
551 .insert(DockConnectionHashKey(rt.dock2.site_id, rt.dock1.site_id));
552 }
553 }
554 }
555 });
556 });
557 }
558
559 /// Given a docking position, find the airship route and approach index
560 /// where the approach endpoint is closest to the docking position.
561 /// Return the route id (u32) and the approach index (0 or 1).
562 pub fn airship_route_for_docking_pos(
563 &self,
564 docking_pos: Vec3<f32>,
565 ) -> Option<(AirshipRouteId, usize)> {
566 // Find the route where where either approach.dock_pos is equal (very close to)
567 // the given docking_pos.
568 if let Some((route_id, min_index, _)) = self
569 .routes
570 .iter()
571 .flat_map(|(rt_id, rt)| {
572 rt.approaches
573 .iter()
574 .enumerate()
575 .map(move |(index, approach)| {
576 let distance =
577 approach.dock_pos.1.xy().distance_squared(docking_pos.xy()) as i64;
578 (rt_id, index, distance)
579 })
580 })
581 .min_by_key(|(_, _, distance)| *distance)
582 {
583 Some((*route_id, min_index))
584 } else {
585 // It should be impossible to get here if
586 // should_spawn_airship_at_docking_position is working correctly.
587 warn!(
588 "No airship route has a docking postion near {:?}",
589 docking_pos
590 );
591 None
592 }
593 }
594
595 /// Given a airship dock docking position, determine if an airship should be
596 /// spawned at the docking position. Some airship docks will not have
597 /// the docking positions completely filled because some docks are not
598 /// connected to the maximum number of sites. E.g., if there are an odd
599 /// number of sites with airship docks. Another reason is the way the
600 /// routes are generated.
601 pub fn should_spawn_airship_at_docking_position(
602 &self,
603 docking_pos: &Vec3<i32>,
604 site_name: &str,
605 ) -> bool {
606 let use_docking_pos = self.routes.iter().any(|(_, rt)| {
607 rt.approaches.iter().any(|approach| {
608 approach
609 .dock_pos
610 .1
611 .xy()
612 .distance_squared(docking_pos.map(|i| i as f32).xy())
613 < 10.0
614 })
615 });
616 if !use_docking_pos {
617 debug_airships!(
618 "Skipping docking position {:?} for site {}",
619 docking_pos,
620 site_name
621 );
622 }
623 use_docking_pos
624 }
625
626 /// Get the position and direction for the airship to dock at the given
627 /// docking position. If use_starboard_boarding is None, the side for
628 /// boarding is randomly chosen. The center of the airship position with
629 /// respect to the docking position is an asymmetrical offset depending on
630 /// which side of the airship will be used for boarding and where the
631 /// captain is located on the airship. The returned position is the
632 /// position where the captain will be when the airship is docked
633 /// (because the captain NPC is the one that is positioned in the agent
634 /// or rtsim code).
635 pub fn airship_vec_for_docking_pos(
636 docking_pos: Vec3<f32>,
637 airship_dock_center: Vec2<f32>,
638 docking_side: Option<AirshipDockingSide>,
639 ) -> (Vec3<f32>, Dir) {
640 // choose a random side for docking if not specified
641 let dock_side = docking_side.unwrap_or_else(|| {
642 if thread_rng().gen::<bool>() {
643 AirshipDockingSide::Starboard
644 } else {
645 AirshipDockingSide::Port
646 }
647 });
648 // Get the vector from the dock alignment position on the airship to the
649 // captain's position and the rotation angle for the ship to dock on the
650 // specified side. The dock alignment position is where the airship
651 // should touch or come closest to the dock. The side_rotation is the
652 // angle the ship needs to rotate from to be perpendicular to the vector
653 // from the dock center to the docking position. For example, if the docking
654 // position is directly north (0 degrees, or aligned with the unit_y
655 // vector), the ship needs to rotate 90 degrees CCW to dock on the port
656 // side or 270 degrees CCW to dock on the starboard side.
657 let (dock_align_to_captain, side_rotation) = if dock_side == AirshipDockingSide::Starboard {
658 (
659 Airships::DOCK_ALIGN_POS_STARBOARD,
660 3.0 * std::f32::consts::FRAC_PI_2,
661 )
662 } else {
663 (Airships::DOCK_ALIGN_POS_PORT, std::f32::consts::FRAC_PI_2)
664 };
665 // get the vector from the dock center to the docking platform point where the
666 // airship should touch or come closest to.
667 let dock_pos_offset = (docking_pos - airship_dock_center).xy();
668 // The airship direction when docked is the dock_pos_offset rotated by the
669 // side_rotation angle.
670 let airship_dir =
671 Dir::from_unnormalized(dock_pos_offset.rotated_z(side_rotation).with_z(0.0))
672 .unwrap_or_default();
673 // The dock_align_to_captain vector is rotated by the angle between unit_y and
674 // the airship direction.
675 let ship_dock_rotation =
676 Airships::angle_between_vectors_ccw(Vec2::unit_y(), airship_dir.vec().xy());
677 let captain_offset = dock_align_to_captain
678 .rotated_z(ship_dock_rotation)
679 .with_z(Airships::AIRSHIP_TO_DOCK_Z_OFFSET);
680
681 // To get the location of the pilot when the ship is docked, add the
682 // captain_offset to the docking position.
683 (docking_pos + captain_offset, airship_dir)
684 }
685
686 // Get the docking approach for the given docking position.
687 fn docking_approach_for(
688 depart_center: Vec2<f32>,
689 dest_center: Vec2<f32>,
690 docking_pos: &AirshipDockingPosition,
691 depart_to_dest_angle: f32,
692 map_center: Vec2<f32>,
693 max_dims: Vec2<f32>,
694 site_id: Id<Site>,
695 ) -> AirshipDockingApproach {
696 let (airship_pos, airship_direction) = Airships::airship_vec_for_docking_pos(
697 docking_pos.1,
698 dest_center,
699 Some(AirshipDockingSide::Starboard),
700 );
701 // calculate port final point. It is a 500 block extension from the docking
702 // position in the direction of the docking direction.
703 let port_final_pos = docking_pos.1.xy() + airship_direction.to_vec().xy() * 500.0;
704 let starboard_final_pos = docking_pos.1.xy() - airship_direction.to_vec().xy() * 500.0;
705 // calculate the turn angle required to align with the port. The port final
706 // point is the origin. One vector is the reverse of the vector from the
707 // port final point to the departure center. The other vector is from
708 // the port final point to the docking position.
709 let port_final_angle =
710 (airship_pos.xy() - port_final_pos).angle_between(-(depart_center - port_final_pos));
711 // The starboard angle is calculated similarly.
712 let starboard_final_angle = (airship_pos.xy() - starboard_final_pos)
713 .angle_between(-(depart_center - starboard_final_pos));
714
715 // If the angles are approximately equal, it means the departure position and
716 // the docking position are on the same line (angle near zero) or are
717 // perpendicular to each other (angle near 90). If perpendicular, pick
718 // the side where the final approach point is furthest from the edge of the map.
719 // If on the same line, pick the side where the final approach point is closest
720 // to the departure position.
721 let side = if (port_final_angle - starboard_final_angle).abs() < 0.1 {
722 // equal angles
723 if port_final_angle < std::f32::consts::FRAC_PI_4 {
724 // same line
725 if port_final_pos.distance_squared(depart_center)
726 < starboard_final_pos.distance_squared(depart_center)
727 {
728 // dock on port side
729 AirshipDockingSide::Port
730 } else {
731 // dock on starboard side
732 AirshipDockingSide::Starboard
733 }
734 } else {
735 // perpendicular
736 // Use the final point closest to the center of the map.
737 if port_final_pos.distance_squared(map_center)
738 < starboard_final_pos.distance_squared(map_center)
739 {
740 // dock on port side
741 AirshipDockingSide::Port
742 } else {
743 // dock on starboard side
744 AirshipDockingSide::Starboard
745 }
746 }
747 } else {
748 // pick the side with the least turn angle.
749 if port_final_angle < starboard_final_angle {
750 // port side
751 AirshipDockingSide::Port
752 } else {
753 // starboard side
754 AirshipDockingSide::Starboard
755 }
756 };
757
758 let height = if depart_to_dest_angle < std::f32::consts::PI {
759 Airships::STD_CRUISE_HEIGHT
760 } else {
761 Airships::STD_CRUISE_HEIGHT + 100.0
762 };
763
764 let check_pos_fn = |pos: Vec2<f32>, what: &str| {
765 if pos.x < 0.0 || pos.y < 0.0 || pos.x > max_dims.x || pos.y > max_dims.y {
766 warn!("{} pos out of bounds: {:?}", what, pos);
767 }
768 };
769
770 let initial_pos_fn = |final_pos: Vec2<f32>| {
771 // Get the angle between a line (1) connecting the final_pos and the
772 // depart_center and line (2) from the final_pos to the docking
773 // position. divide the angle in half then rotate line 1 CCW by that
774 // angle + 270 degrees. The initial approach point is on this
775 // rotated line 1, 500 blocks from the final_pos.
776 let line1 = (depart_center - final_pos).normalized();
777 let angle = line1.angle_between((airship_pos.xy() - final_pos).normalized());
778 let initial_pos_line = line1.rotated_z(angle / 2.0 + 3.0 * std::f32::consts::FRAC_PI_2);
779 let initial_pos = final_pos + initial_pos_line * 500.0;
780 check_pos_fn(final_pos, "final_pos");
781 check_pos_fn(initial_pos, "initial_pos");
782 initial_pos
783 };
784
785 if side == AirshipDockingSide::Starboard {
786 AirshipDockingApproach {
787 dock_pos: *docking_pos,
788 airship_pos,
789 airship_direction,
790 dock_center: dest_center,
791 height,
792 approach_initial_pos: initial_pos_fn(starboard_final_pos),
793 approach_final_pos: starboard_final_pos,
794 side,
795 site_id,
796 }
797 } else {
798 // recalculate the actual airship position and direction for the port side.
799 let (airship_pos, airship_direction) = Airships::airship_vec_for_docking_pos(
800 docking_pos.1,
801 dest_center,
802 Some(AirshipDockingSide::Port),
803 );
804 AirshipDockingApproach {
805 dock_pos: *docking_pos,
806 airship_pos,
807 airship_direction,
808 dock_center: dest_center,
809 height,
810 approach_initial_pos: initial_pos_fn(port_final_pos),
811 approach_final_pos: port_final_pos,
812 side,
813 site_id,
814 }
815 }
816 }
817
818 /// Builds approaches for the given route connection.
819 /// Each docking position has two possible approaches, based on the
820 /// port and starboard sides of the airship. The approaches are aligned
821 /// with the docking position direction, which is always perpendicular
822 /// to the vector from the airship dock plot center to the docking position.
823 /// The airship can pivot around the z axis, but it does so slowly. To
824 /// ensure that the airship is oriented in the correct direction for
825 /// landing, and to make it more realistic, the airship approaches
826 /// the docking position pre-aligned with the landing direction. The
827 /// approach consists of two positions, the initial point where the
828 /// airship will turn toward the final point, at the final point it will
829 /// turn toward the docking position and will be aligned with the docking
830 /// direction.
831 fn airship_approaches_for_route(
832 world_sim: &mut WorldSim,
833 route: &AirRouteConnection,
834 dock1_position_id: u32,
835 dock2_position_id: u32,
836 ) -> [AirshipDockingApproach; 2] {
837 /* o Pick the docking side with the least rotation angle from the departure position.
838 If the angles are approximately equal, it means the departure position and
839 the docking position are on the same line (angle near zero) or are perpendicular to
840 each other (angle near 90). If perpendicular, pick the side where the final approach
841 point is furthest from the edge of the map. If on the same line, pick the side where
842 the final approach point is closest to the departure position.
843 o The cruising height above terrain is based on the angle between North and the
844 line between the docking positions.
845 */
846
847 let map_size_chunks = world_sim.get_size().map(|u| u as i32);
848 let max_dims = map_size_chunks.cpos_to_wpos().map(|u| u as f32);
849 let map_center = Vec2::new(max_dims.x / 2.0, max_dims.y / 2.0);
850
851 let dock1_positions = &route.dock1;
852 let dock2_positions = &route.dock2;
853 let dock1_center = dock1_positions.center;
854 let dock2_center = dock2_positions.center;
855 let docking_pos1 = dock1_positions
856 .docking_positions
857 .iter()
858 .find(|dp| dp.0 == dock1_position_id)
859 .unwrap();
860 let docking_pos2 = dock2_positions
861 .docking_positions
862 .iter()
863 .find(|dp| dp.0 == dock2_position_id)
864 .unwrap();
865 let dock1_to_dock2_angle = Airships::angle_between_vectors_ccw(
866 Airships::ROUTES_NORTH,
867 docking_pos2.1.xy() - docking_pos1.1.xy(),
868 );
869 let dock2_to_dock1_angle = std::f32::consts::TAU - dock1_to_dock2_angle;
870 debug_airships!(
871 "airship_approaches_for_route - dock1_pos:{:?}, dock2_pos:{:?}, \
872 dock1_to_dock2_angle:{}, dock2_to_dock1_angle:{}",
873 docking_pos1,
874 docking_pos2,
875 dock1_to_dock2_angle,
876 dock2_to_dock1_angle
877 );
878
879 [
880 Airships::docking_approach_for(
881 dock1_center,
882 dock2_center,
883 docking_pos2,
884 dock1_to_dock2_angle,
885 map_center,
886 max_dims,
887 dock2_positions.site_id,
888 ),
889 Airships::docking_approach_for(
890 dock2_center,
891 dock1_center,
892 docking_pos1,
893 dock2_to_dock1_angle,
894 map_center,
895 max_dims,
896 dock1_positions.site_id,
897 ),
898 ]
899 }
900
901 /// Returns the angle from vec v1 to vec v2 in the CCW direction.
902 fn angle_between_vectors_ccw(v1: Vec2<f32>, v2: Vec2<f32>) -> f32 {
903 let dot_product = v1.dot(v2);
904 let det = v1.x * v2.y - v1.y * v2.x; // determinant
905 let angle = det.atan2(dot_product); // atan2(det, dot_product) gives the CCW angle
906 if angle < 0.0 {
907 angle + std::f32::consts::TAU
908 } else {
909 angle
910 }
911 }
912
913 /// Returns the angle from vec v1 to vec v2 in the CW direction.
914 fn angle_between_vectors_cw(v1: Vec2<f32>, v2: Vec2<f32>) -> f32 {
915 let ccw_angle = Airships::angle_between_vectors_ccw(v1, v2);
916 std::f32::consts::TAU - ccw_angle
917 }
918}
919
920/// For debuging the airship routes. Writes the airship routes to a json file.
921fn write_airship_routes_log(file_path: &str, jsonstr: &str) -> std::io::Result<()> {
922 let mut file = OpenOptions::new()
923 .write(true)
924 .create(true)
925 .truncate(true)
926 .open(file_path)?;
927 file.write_all(jsonstr.as_bytes())?;
928 Ok(())
929}
930
931#[cfg(test)]
932mod tests {
933 use super::{AirshipDockingSide, Airships, approx::assert_relative_eq};
934 use vek::{Quaternion, Vec2, Vec3};
935
936 #[test]
937 fn basic_vec_test() {
938 let vec1 = Vec3::new(0.0f32, 10.0, 0.0);
939 let vec2 = Vec3::new(10.0, 0.0, 0.0);
940 let a12 = vec2.angle_between(vec1);
941 assert_relative_eq!(a12, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
942
943 let rotc2 = Quaternion::rotation_z(a12);
944 let vec3 = rotc2 * vec2;
945 assert!(vec3 == vec1);
946 }
947
948 #[test]
949 fn std_vec_angles_test() {
950 let refvec = Vec2::new(0.0f32, 10.0);
951
952 let vec1 = Vec2::new(0.0f32, 10.0);
953 let vec2 = Vec2::new(10.0f32, 0.0);
954 let vec3 = Vec2::new(0.0f32, -10.0);
955 let vec4 = Vec2::new(-10.0f32, 0.0);
956
957 let a1r = vec1.angle_between(refvec);
958 assert!(a1r == 0.0f32);
959
960 let a2r = vec2.angle_between(refvec);
961 assert_relative_eq!(a2r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
962
963 let a3r: f32 = vec3.angle_between(refvec);
964 assert_relative_eq!(a3r, std::f32::consts::PI, epsilon = 0.00001);
965
966 let a4r = vec4.angle_between(refvec);
967 assert_relative_eq!(a4r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
968 }
969
970 #[test]
971 fn vec_angles_test() {
972 let refvec = Vec3::new(0.0f32, 10.0, 0.0);
973
974 let vec1 = Vec3::new(0.0f32, 10.0, 0.0);
975 let vec2 = Vec3::new(10.0f32, 0.0, 0.0);
976 let vec3 = Vec3::new(0.0f32, -10.0, 0.0);
977 let vec4 = Vec3::new(-10.0f32, 0.0, 0.0);
978
979 let a1r = vec1.angle_between(refvec);
980 let a1r3 = Airships::angle_between_vectors_ccw(vec1.xy(), refvec.xy());
981 assert!(a1r == 0.0f32);
982 assert!(a1r3 == 0.0f32);
983
984 let a2r = vec2.angle_between(refvec);
985 let a2r3 = Airships::angle_between_vectors_ccw(vec2.xy(), refvec.xy());
986 assert_relative_eq!(a2r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
987 assert_relative_eq!(a2r3, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
988
989 let a3r: f32 = vec3.angle_between(refvec);
990 let a3r3 = Airships::angle_between_vectors_ccw(vec3.xy(), refvec.xy());
991 assert_relative_eq!(a3r, std::f32::consts::PI, epsilon = 0.00001);
992 assert_relative_eq!(a3r3, std::f32::consts::PI, epsilon = 0.00001);
993
994 let a4r = vec4.angle_between(refvec);
995 let a4r3 = Airships::angle_between_vectors_ccw(vec4.xy(), refvec.xy());
996 assert_relative_eq!(a4r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
997 assert_relative_eq!(a4r3, std::f32::consts::FRAC_PI_2 * 3.0, epsilon = 0.00001);
998 }
999
1000 #[test]
1001 fn airship_angles_test() {
1002 let refvec = Vec2::new(0.0f32, 37.0);
1003 let ovec = Vec2::new(-4.0f32, -14.0);
1004 let oveccw0 = Vec2::new(-4, -14);
1005 let oveccw90 = Vec2::new(-14, 4);
1006 let oveccw180 = Vec2::new(4, 14);
1007 let oveccw270 = Vec2::new(14, -4);
1008 let ovecccw0 = Vec2::new(-4, -14);
1009 let ovecccw90 = Vec2::new(14, -4);
1010 let ovecccw180 = Vec2::new(4, 14);
1011 let ovecccw270 = Vec2::new(-14, 4);
1012
1013 let vec1 = Vec2::new(0.0f32, 37.0);
1014 let vec2 = Vec2::new(37.0f32, 0.0);
1015 let vec3 = Vec2::new(0.0f32, -37.0);
1016 let vec4 = Vec2::new(-37.0f32, 0.0);
1017
1018 assert!(
1019 ovec.rotated_z(Airships::angle_between_vectors_cw(vec1, refvec))
1020 .map(|x| x.round() as i32)
1021 == oveccw0
1022 );
1023 assert!(
1024 ovec.rotated_z(Airships::angle_between_vectors_cw(vec2, refvec))
1025 .map(|x| x.round() as i32)
1026 == oveccw90
1027 );
1028 assert!(
1029 ovec.rotated_z(Airships::angle_between_vectors_cw(vec3, refvec))
1030 .map(|x| x.round() as i32)
1031 == oveccw180
1032 );
1033 assert!(
1034 ovec.rotated_z(Airships::angle_between_vectors_cw(vec4, refvec))
1035 .map(|x| x.round() as i32)
1036 == oveccw270
1037 );
1038
1039 assert!(
1040 ovec.rotated_z(Airships::angle_between_vectors_ccw(vec1, refvec))
1041 .map(|x| x.round() as i32)
1042 == ovecccw0
1043 );
1044 assert!(
1045 ovec.rotated_z(Airships::angle_between_vectors_ccw(vec2, refvec))
1046 .map(|x| x.round() as i32)
1047 == ovecccw90
1048 );
1049 assert!(
1050 ovec.rotated_z(Airships::angle_between_vectors_ccw(vec3, refvec))
1051 .map(|x| x.round() as i32)
1052 == ovecccw180
1053 );
1054 assert!(
1055 ovec.rotated_z(Airships::angle_between_vectors_ccw(vec4, refvec))
1056 .map(|x| x.round() as i32)
1057 == ovecccw270
1058 );
1059 }
1060
1061 #[test]
1062 fn airship_vec_test() {
1063 {
1064 let dock_pos = Vec3::new(10.0f32, 10.0, 0.0);
1065 let airship_dock_center = Vec2::new(0.0, 0.0);
1066 let mut left_tested = false;
1067 let mut right_tested = false;
1068 {
1069 for _ in 0..1000 {
1070 let (airship_pos, airship_dir) =
1071 Airships::airship_vec_for_docking_pos(dock_pos, airship_dock_center, None);
1072 if airship_pos.x > 23.0 {
1073 assert_relative_eq!(
1074 airship_pos,
1075 Vec3 {
1076 x: 23.435028,
1077 y: 22.020815,
1078 z: -3.0
1079 },
1080 epsilon = 0.00001
1081 );
1082 assert_relative_eq!(
1083 airship_dir.to_vec(),
1084 Vec3 {
1085 x: -0.70710677,
1086 y: 0.70710677,
1087 z: 0.0
1088 },
1089 epsilon = 0.00001
1090 );
1091 left_tested = true;
1092 } else {
1093 assert_relative_eq!(
1094 airship_pos,
1095 Vec3 {
1096 x: 22.020815,
1097 y: 23.435028,
1098 z: -3.0
1099 },
1100 epsilon = 0.00001
1101 );
1102 assert_relative_eq!(
1103 airship_dir.to_vec(),
1104 Vec3 {
1105 x: 0.70710677,
1106 y: -0.70710677,
1107 z: 0.0
1108 },
1109 epsilon = 0.00001
1110 );
1111 right_tested = true;
1112 }
1113 if left_tested && right_tested {
1114 break;
1115 }
1116 }
1117 }
1118 {
1119 let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
1120 dock_pos,
1121 airship_dock_center,
1122 Some(AirshipDockingSide::Port),
1123 );
1124 assert_relative_eq!(
1125 airship_pos,
1126 Vec3 {
1127 x: 23.435028,
1128 y: 22.020815,
1129 z: -3.0
1130 },
1131 epsilon = 0.00001
1132 );
1133 assert_relative_eq!(
1134 airship_dir.to_vec(),
1135 Vec3 {
1136 x: -0.70710677,
1137 y: 0.70710677,
1138 z: 0.0
1139 },
1140 epsilon = 0.00001
1141 );
1142 }
1143 {
1144 let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
1145 dock_pos,
1146 airship_dock_center,
1147 Some(AirshipDockingSide::Starboard),
1148 );
1149 assert_relative_eq!(
1150 airship_pos,
1151 Vec3 {
1152 x: 22.020815,
1153 y: 23.435028,
1154 z: -3.0
1155 },
1156 epsilon = 0.00001
1157 );
1158 assert_relative_eq!(
1159 airship_dir.to_vec(),
1160 Vec3 {
1161 x: 0.70710677,
1162 y: -0.70710677,
1163 z: 0.0
1164 },
1165 epsilon = 0.00001
1166 );
1167 }
1168 }
1169 {
1170 let dock_pos = Vec3::new(28874.0, 18561.0, 0.0);
1171 let airship_dock_center = Vec2::new(28911.0, 18561.0);
1172 {
1173 let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
1174 dock_pos,
1175 airship_dock_center,
1176 Some(AirshipDockingSide::Port),
1177 );
1178 assert_relative_eq!(
1179 airship_pos,
1180 Vec3 {
1181 x: 28856.0,
1182 y: 18562.0,
1183 z: -3.0
1184 },
1185 epsilon = 0.00001
1186 );
1187 assert_relative_eq!(
1188 airship_dir.to_vec(),
1189 Vec3 {
1190 x: 4.371139e-8,
1191 y: -1.0,
1192 z: 0.0
1193 },
1194 epsilon = 0.00001
1195 );
1196 }
1197 {
1198 let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
1199 dock_pos,
1200 airship_dock_center,
1201 Some(AirshipDockingSide::Starboard),
1202 );
1203 assert_relative_eq!(
1204 airship_pos,
1205 Vec3 {
1206 x: 28856.0,
1207 y: 18560.0,
1208 z: -3.0
1209 },
1210 epsilon = 0.00001
1211 );
1212 assert_relative_eq!(
1213 airship_dir.to_vec(),
1214 Vec3 {
1215 x: -1.1924881e-8,
1216 y: 1.0,
1217 z: 0.0
1218 },
1219 epsilon = 0.00001
1220 );
1221 }
1222 }
1223 }
1224
1225 #[test]
1226 fn angle_score_test() {
1227 let rt_angles = [
1228 0.0,
1229 std::f32::consts::FRAC_PI_2,
1230 std::f32::consts::PI,
1231 std::f32::consts::FRAC_PI_2 * 3.0,
1232 ];
1233 let con_angles = [
1234 0.0,
1235 std::f32::consts::FRAC_PI_2,
1236 std::f32::consts::PI,
1237 std::f32::consts::FRAC_PI_2 * 3.0,
1238 ];
1239 let scores = [
1240 [0.0, 2.5, 5.0, 2.5],
1241 [2.5, 0.0, 2.5, 5.0],
1242 [5.0, 2.5, 0.0, 2.5],
1243 [2.5, 5.0, 2.5, 0.0],
1244 ];
1245 let score_fn2 = |a1: f32, a2: f32| {
1246 let optimal_angle = (a1 + std::f32::consts::PI).rem_euclid(std::f32::consts::TAU);
1247 let angle_diff = (optimal_angle - a2)
1248 .abs()
1249 .min(std::f32::consts::TAU - (optimal_angle - a2).abs());
1250 (1.0 - (angle_diff / std::f32::consts::PI)) * 5.0
1251 };
1252 let mut i = 0;
1253 let mut j = 0;
1254 rt_angles.iter().for_each(|rt_angle| {
1255 j = 0;
1256 con_angles.iter().for_each(|con_angle| {
1257 let score = score_fn2(*con_angle, *rt_angle);
1258 assert_relative_eq!(score, scores[i][j], epsilon = 0.00001);
1259 j += 1;
1260 });
1261 i += 1;
1262 });
1263 }
1264
1265 #[test]
1266 fn distance_score_test() {
1267 let distances = [1, 1000, 5001, 6000, 15000, 30000, 48000];
1268 let scores = [
1269 0.0,
1270 0.0,
1271 -0.20026308,
1272 0.66321766,
1273 1.0257597,
1274 1.2102475,
1275 1.329906,
1276 ];
1277 let score_fn = |distance: i64| {
1278 if distance > 25000000 {
1279 (((distance - 24999000) / 1000) as f32).ln() / 8.0 - 0.5
1280 } else {
1281 0.0
1282 }
1283 };
1284 let mut i = 0;
1285 distances.iter().for_each(|distance| {
1286 let dist2 = *distance * *distance;
1287 let score = score_fn(dist2);
1288 assert_relative_eq!(score, scores[i], epsilon = 0.00001);
1289 i += 1;
1290 });
1291 }
1292}