veloren_world/civ/
airship_travel.rs

1use crate::{
2    Index,
3    sim::WorldSim,
4    site::{self, Site, plot::PlotKindMeta},
5    util::{DHashMap, DHashSet, seed_expan},
6};
7use common::{
8    store::{Id, Store},
9    terrain::{MapSizeLg, TERRAIN_CHUNK_BLOCKS_LG},
10    util::Dir,
11};
12use delaunator::{Point, Triangulation, triangulate};
13use itertools::Itertools;
14use rand::{SeedableRng, prelude::*};
15use rand_chacha::ChaChaRng;
16use tracing::{error, warn};
17use vek::*;
18
19#[cfg(debug_assertions)] use tracing::debug;
20
21#[cfg(feature = "airship_maps")]
22use crate::civ::airship_route_map::*;
23
24#[cfg(debug_assertions)]
25macro_rules! debug_airships {
26    ($($arg:tt)*) => {
27        debug!($($arg)*);
28    }
29}
30
31#[cfg(not(debug_assertions))]
32macro_rules! debug_airships {
33    ($($arg:tt)*) => {};
34}
35
36/// A docking position (id, position). The docking position id is
37/// an index of all docking positions in the world.
38#[derive(Clone, Copy, Debug, Default, PartialEq)]
39pub struct AirshipDockingPosition(pub u32, pub Vec3<f32>);
40
41/// The AirshipDock Sites are always oriented along a cardinal direction.
42/// The docking platforms are likewise on the sides of the dock perpendicular
43/// to a cardinal axis.
44#[derive(Debug, Copy, Clone, Default, PartialEq, Eq, Hash)]
45pub enum AirshipDockPlatform {
46    #[default]
47    NorthPlatform,
48    EastPlatform,
49    SouthPlatform,
50    WestPlatform,
51}
52
53/// An airship can dock with its port or starboard side facing the dock.
54#[derive(Debug, Copy, Clone, PartialEq, Default)]
55pub enum AirshipDockingSide {
56    #[default]
57    Port,
58    Starboard,
59}
60
61impl AirshipDockingSide {
62    const EAST_REF_VEC: Vec2<f32> = Vec2 { x: 1.0, y: 0.0 };
63    const NORTH_REF_VEC: Vec2<f32> = Vec2 { x: 0.0, y: 1.0 };
64    const SOUTH_REF_VEC: Vec2<f32> = Vec2 { x: 0.0, y: -1.0 };
65    const WEST_REF_VEC: Vec2<f32> = Vec2 { x: -1.0, y: 0.0 };
66
67    /// When docking, the side to use depends on the angle the airship is
68    /// approaching the dock from, and the platform of the airship dock that
69    /// the airship is docking at.
70    /// For example, when docking at the North Platform:
71    ///
72    /// | From the          |  Docking Side |
73    /// |:----------------- |:--------------|
74    /// | West              |  Starboard    |
75    /// | Northwest         |  Starboard    |
76    /// | North             |  Starboard    |
77    /// | Northeast         |  Port         |
78    /// | East              |  Port         |
79    /// | Southeast         |  Port         |
80    /// | South             |  Port         |
81    /// | Southwest         |  Starboard    |
82    pub fn from_dir_to_platform(dir: &Vec2<f32>, platform: &AirshipDockPlatform) -> Self {
83        // get the reference vector and precompute whether to flip the angle based on
84        // the dir input.
85        let (ref_vec, negate_angle) = match platform {
86            AirshipDockPlatform::NorthPlatform => (&AirshipDockingSide::NORTH_REF_VEC, dir.x < 0.0),
87            AirshipDockPlatform::EastPlatform => (&AirshipDockingSide::EAST_REF_VEC, dir.y > 0.0),
88            AirshipDockPlatform::SouthPlatform => (&AirshipDockingSide::SOUTH_REF_VEC, dir.x > 0.0),
89            AirshipDockPlatform::WestPlatform => (&AirshipDockingSide::WEST_REF_VEC, dir.y < 0.0),
90        };
91        let mut angle = dir.angle_between(*ref_vec).to_degrees();
92        if negate_angle {
93            angle = -angle;
94        }
95        match angle as i32 {
96            -360..=0 => AirshipDockingSide::Port,
97            _ => AirshipDockingSide::Starboard,
98        }
99    }
100}
101
102/// Information needed for an airship to travel to and dock at an AirshipDock
103/// plot.
104#[derive(Clone, Copy, Debug, PartialEq)]
105pub struct AirshipDockingApproach {
106    /// The position of the airship when docked.
107    /// This is different from dock_pos because the airship is offset to align
108    /// the ramp with the dock.
109    pub airship_pos: Vec3<f32>,
110    /// The direction the airship is facing when docked.
111    pub airship_direction: Dir,
112    /// Then center of the AirshipDock Plot.
113    pub dock_center: Vec2<f32>,
114    /// The height above terrain the airship cruises at.
115    pub height: f32,
116    /// The end point of the cruise phase of flight.
117    pub approach_transition_pos: Vec3<f32>,
118    /// There are ramps on both the port and starboard sides of the airship.
119    /// This gives the side that the airship will dock on.
120    pub side: AirshipDockingSide,
121    /// The site name where the airship will be docked at the end of the
122    /// approach.
123    pub site_id: Id<Site>,
124}
125
126/// The docking postions at an AirshipDock plot.
127#[derive(Clone, Debug)]
128pub struct AirshipDockPositions {
129    /// The center of the AirshipDock plot. From the world generation code.
130    pub center: Vec2<f32>,
131    /// The docking positions for the airship, derived from the
132    /// positions calculated in the world generation code.
133    pub docking_positions: Vec<AirshipDockingPosition>,
134    /// The id of the Site where the AirshipDock is located.
135    pub site_id: Id<site::Site>,
136}
137
138/// One leg of an airship route.
139#[derive(Clone, Default, Debug)]
140pub struct AirshipRouteLeg {
141    /// The index of the destination in Airships::docking_positions.
142    pub dest_index: usize,
143    /// The assigned docking platform at the destination dock for this leg.
144    pub platform: AirshipDockPlatform,
145}
146
147/// Information needed for placing an airship in the world when the world is
148/// generated (each time the server starts).
149#[derive(Debug, Clone)]
150pub struct AirshipSpawningLocation {
151    pub pos: Vec2<f32>,
152    pub dir: Vec2<f32>,
153    pub height: f32,
154    pub route_index: usize,
155    pub leg_index: usize,
156}
157
158/// Data for airship operations. This is generated world data.
159#[derive(Clone, Default)]
160pub struct Airships {
161    pub airship_docks: Vec<AirshipDockPositions>,
162    pub routes: Vec<Vec<AirshipRouteLeg>>,
163    pub spawning_locations: Vec<AirshipSpawningLocation>,
164}
165
166// Internal data structures
167
168impl AirshipDockPositions {
169    fn from_plot_meta(
170        first_id: u32,
171        center: Vec2<i32>,
172        docking_positions: &[Vec3<i32>],
173        site_id: Id<site::Site>,
174    ) -> Self {
175        let mut dock_pos_id = first_id;
176        Self {
177            center: center.map(|i| i as f32),
178            docking_positions: docking_positions
179                .iter()
180                .map(|pos: &Vec3<i32>| {
181                    let docking_position =
182                        AirshipDockingPosition(dock_pos_id, pos.map(|i| i as f32));
183                    dock_pos_id += 1;
184                    docking_position
185                })
186                .collect(),
187            site_id,
188        }
189    }
190
191    /// Get the docking position that matches the given platform.
192    fn docking_position(&self, platform: AirshipDockPlatform) -> Vec3<f32> {
193        self.docking_positions
194            .iter()
195            .find_map(|&docking_position| {
196                // The docking position is the one that matches the platform.
197                // The platform is determined by the direction of the docking position
198                // relative to the center of the dock.
199                let docking_position_platform =
200                    AirshipDockPlatform::from_dir(docking_position.1.xy() - self.center);
201                if docking_position_platform == platform {
202                    Some(docking_position.1)
203                } else {
204                    None
205                }
206            })
207            .unwrap_or_else(|| {
208                // If no docking position is found, return the dock center.
209                self.center.with_z(1000.0)
210            })
211    }
212}
213
214// These are used in AirshipDockPlatform::choices_from_dir
215
216static SWEN_PLATFORMS: [AirshipDockPlatform; 4] = [
217    AirshipDockPlatform::SouthPlatform,
218    AirshipDockPlatform::WestPlatform,
219    AirshipDockPlatform::EastPlatform,
220    AirshipDockPlatform::NorthPlatform,
221];
222
223static SEWN_PLATFORMS: [AirshipDockPlatform; 4] = [
224    AirshipDockPlatform::SouthPlatform,
225    AirshipDockPlatform::EastPlatform,
226    AirshipDockPlatform::WestPlatform,
227    AirshipDockPlatform::NorthPlatform,
228];
229
230static WNSE_PLATFORMS: [AirshipDockPlatform; 4] = [
231    AirshipDockPlatform::WestPlatform,
232    AirshipDockPlatform::NorthPlatform,
233    AirshipDockPlatform::SouthPlatform,
234    AirshipDockPlatform::EastPlatform,
235];
236
237static WSNE_PLATFORMS: [AirshipDockPlatform; 4] = [
238    AirshipDockPlatform::WestPlatform,
239    AirshipDockPlatform::SouthPlatform,
240    AirshipDockPlatform::NorthPlatform,
241    AirshipDockPlatform::EastPlatform,
242];
243
244static NEWS_PLATFORMS: [AirshipDockPlatform; 4] = [
245    AirshipDockPlatform::NorthPlatform,
246    AirshipDockPlatform::EastPlatform,
247    AirshipDockPlatform::WestPlatform,
248    AirshipDockPlatform::SouthPlatform,
249];
250
251static NWES_PLATFORMS: [AirshipDockPlatform; 4] = [
252    AirshipDockPlatform::NorthPlatform,
253    AirshipDockPlatform::WestPlatform,
254    AirshipDockPlatform::EastPlatform,
255    AirshipDockPlatform::SouthPlatform,
256];
257
258static ESNW_PLATFORMS: [AirshipDockPlatform; 4] = [
259    AirshipDockPlatform::EastPlatform,
260    AirshipDockPlatform::SouthPlatform,
261    AirshipDockPlatform::NorthPlatform,
262    AirshipDockPlatform::WestPlatform,
263];
264
265static ENSW_PLATFORMS: [AirshipDockPlatform; 4] = [
266    AirshipDockPlatform::EastPlatform,
267    AirshipDockPlatform::NorthPlatform,
268    AirshipDockPlatform::SouthPlatform,
269    AirshipDockPlatform::WestPlatform,
270];
271
272/// The docking platforms used on each leg of the airship route segments is
273/// determined when the routes are generated. Route segments are continuous
274/// loops that are deconflicted by using only one docking platform for any given
275/// leg of a route segment. Since there are four docking platforms per airship
276/// dock, there are at most four route segments passing through a given airship
277/// dock. The docking platforms are also optimized so that on the incoming leg
278/// of a route segment, the airship uses the docking platform that is closest to
279/// the arrival direction (if possible), while still using only one docking
280/// platform per route segment leg.
281impl AirshipDockPlatform {
282    /// Get the preferred docking platform based on the direction vector.
283    pub fn from_dir(dir: Vec2<f32>) -> Self {
284        if let Some(dir) = dir.try_normalized() {
285            let mut angle = dir.angle_between(Vec2::unit_y()).to_degrees();
286            if dir.x < 0.0 {
287                angle = -angle;
288            }
289            match angle as i32 {
290                -360..=-135 => AirshipDockPlatform::SouthPlatform,
291                -134..=-45 => AirshipDockPlatform::WestPlatform,
292                -44..=45 => AirshipDockPlatform::NorthPlatform,
293                46..=135 => AirshipDockPlatform::EastPlatform,
294                136..=360 => AirshipDockPlatform::SouthPlatform,
295                _ => AirshipDockPlatform::NorthPlatform, // should never happen
296            }
297        } else {
298            AirshipDockPlatform::NorthPlatform // default value, should never happen
299        }
300    }
301
302    /// Get the platform choices in order of preference based on the direction
303    /// vector. The first choice is always the most direct plaform given the
304    /// approach direction. Then, the next two choices are the platforms for
305    /// the cardinal directions on each side of the approach direction, and
306    /// the last choice is the platform on the opposite side of the dock.
307    /// The return value is one of the ABCD_PLATFORMS arrays defined above.
308    pub fn choices_from_dir(dir: Vec2<f32>) -> &'static [AirshipDockPlatform] {
309        if let Some(dir) = dir.try_normalized() {
310            let mut angle = dir.angle_between(Vec2::unit_y()).to_degrees();
311            if dir.x < 0.0 {
312                angle = -angle;
313            }
314            // This code works similar to the Direction enum in the common crate.
315            // Angle between produces the smallest angle between two vectors,
316            // so when dir.x is negative, we force the angle to be negative.
317            // 0 or 360 is North. It is assumed that the angle ranges from -360 to 360
318            // degrees even though angles less than -180 or greater than 180
319            // should never be seen.
320            match angle as i32 {
321                -360..=-135 => {
322                    // primary is SouthPlatform
323                    // As a fallback (for when the south platform is already claimed),
324                    // if the direction is more towards the west, use the west platform,
325                    // and if the direction is more towards the east, use the east platform.
326                    // The north platform is always the last resort. All fallback blocks
327                    // below work similarly.
328                    if angle as i32 > -180 {
329                        &SWEN_PLATFORMS
330                    } else {
331                        &SEWN_PLATFORMS
332                    }
333                },
334                -134..=-45 => {
335                    // primary is WestPlatform
336                    if angle as i32 > -90 {
337                        &WNSE_PLATFORMS
338                    } else {
339                        &WSNE_PLATFORMS
340                    }
341                },
342                -44..=45 => {
343                    // primary is NorthPlatform
344                    if angle as i32 > 0 {
345                        &NEWS_PLATFORMS
346                    } else {
347                        &NWES_PLATFORMS
348                    }
349                },
350                46..=135 => {
351                    // primary is EastPlatform
352                    if angle as i32 > 90 {
353                        &ESNW_PLATFORMS
354                    } else {
355                        &ENSW_PLATFORMS
356                    }
357                },
358                136..=360 => {
359                    // primary is SouthPlatform
360                    if angle as i32 > 180 {
361                        &SWEN_PLATFORMS
362                    } else {
363                        &SEWN_PLATFORMS
364                    }
365                },
366                _ => &SEWN_PLATFORMS,
367            }
368        } else {
369            &SEWN_PLATFORMS
370        }
371    }
372
373    /// Get the direction vector that the airship would be facing when docked.
374    fn airship_dir_for_side(&self, side: AirshipDockingSide) -> Dir {
375        match self {
376            AirshipDockPlatform::NorthPlatform => match side {
377                AirshipDockingSide::Starboard => Dir::new(Vec2::unit_x().with_z(0.0)),
378                AirshipDockingSide::Port => Dir::new(-Vec2::unit_x().with_z(0.0)),
379            },
380            AirshipDockPlatform::EastPlatform => match side {
381                AirshipDockingSide::Starboard => Dir::new(-Vec2::unit_y().with_z(0.0)),
382                AirshipDockingSide::Port => Dir::new(Vec2::unit_y().with_z(0.0)),
383            },
384            AirshipDockPlatform::SouthPlatform => match side {
385                AirshipDockingSide::Starboard => Dir::new(-Vec2::unit_x().with_z(0.0)),
386                AirshipDockingSide::Port => Dir::new(Vec2::unit_x().with_z(0.0)),
387            },
388            AirshipDockPlatform::WestPlatform => match side {
389                AirshipDockingSide::Starboard => Dir::new(Vec2::unit_y().with_z(0.0)),
390                AirshipDockingSide::Port => Dir::new(-Vec2::unit_y().with_z(0.0)),
391            },
392        }
393    }
394}
395
396/// A node on the triangulation of the world docking sites, with
397/// data on the nodes that are connected to it.
398#[derive(Clone, Debug, Default, PartialEq)]
399pub struct DockNode {
400    /// An index into the array of all nodes in the graph.
401    pub node_id: usize,
402    /// True if the node is on the outer hull (convex hull) of the
403    /// triangulation.
404    pub on_hull: bool,
405    /// The nodes that are connected to this node.
406    pub connected: Vec<usize>,
407}
408
409impl Airships {
410    /// The nominal distance between airships when they are first spawned in the
411    /// world.
412    pub const AIRSHIP_SPACING: f32 = 5000.0;
413    /// The Z offset between the docking alignment point and the AirshipDock
414    /// plot docking position.
415    const AIRSHIP_TO_DOCK_Z_OFFSET: f32 = -3.0;
416    /// The cruising height varies by route index and there can be only four
417    /// routes.
418    pub const CRUISE_HEIGHTS: [f32; 4] = [400.0, 475.0, 550.0, 625.0];
419    // the generated docking positions in world gen are a little low
420    const DEFAULT_DOCK_DURATION: f32 = 60.0;
421    const DOCKING_TRANSITION_OFFSET: f32 = 175.0;
422    /// The vector from the dock alignment point when the airship is docked on
423    /// the port side.
424    const DOCK_ALIGN_POS_PORT: Vec2<f32> =
425        Vec2::new(Airships::DOCK_ALIGN_X, -Airships::DOCK_ALIGN_Y);
426    /// The vector from the dock alignment point on the airship when the airship
427    /// is docked on the starboard side.
428    const DOCK_ALIGN_POS_STARBOARD: Vec2<f32> =
429        Vec2::new(-Airships::DOCK_ALIGN_X, -Airships::DOCK_ALIGN_Y);
430    // TODO: These alignment offsets are specific to the airship model. If new
431    // models are added, a more generic way to determine the alignment offsets
432    // should be used.
433    /// The absolute offset from the airship's position to the docking alignment
434    /// point on the X axis. The airship is assumed to be facing positive Y.
435    const DOCK_ALIGN_X: f32 = 18.0;
436    /// The offset from the airship's position to the docking alignment point on
437    /// the Y axis. The airship is assumed to be facing positive Y.
438    /// This is positive if the docking alignment point is in front of the
439    /// airship's center position.
440    const DOCK_ALIGN_Y: f32 = 1.0;
441    /// The minimum distance from the docking position where the airship can be
442    /// initially placed in the world.
443    const MIN_SPAWN_POINT_DIST_FROM_DOCK: f32 = 300.0;
444    /// The algorithm that computes where to initially place airships in the
445    /// world (spawning locations) increments the candidate location of the
446    /// first airship on each route by this amount. This is just a prime number
447    /// that is small enough that the AIRSHIP_SPACING is not exceeded by the
448    /// expected number of iterations required to find a starting spawning
449    /// point such that all airships are not too close to docking positions
450    /// when spawned.
451    /// TODO: check that this still if a larger world map is used.
452    const SPAWN_TARGET_DIST_INCREMENT: f32 = 47.0;
453
454    #[inline(always)]
455    pub fn docking_duration() -> f32 { Airships::DEFAULT_DOCK_DURATION }
456
457    /// Get all the airship docking positions from the world sites.
458    fn all_airshipdock_positions(sites: &Store<Site>) -> Vec<AirshipDockPositions> {
459        let mut dock_pos_id = 0;
460        sites
461            .iter()
462            .flat_map(|(site_id, site)| {
463                site.plots().flat_map(move |plot| {
464                    if let Some(PlotKindMeta::AirshipDock {
465                        center,
466                        docking_positions,
467                        ..
468                    }) = plot.kind().meta()
469                    {
470                        Some((center, docking_positions, site_id))
471                    } else {
472                        None
473                    }
474                })
475            })
476            .map(|(center, docking_positions, site_id)| {
477                let positions = AirshipDockPositions::from_plot_meta(
478                    dock_pos_id,
479                    center,
480                    docking_positions,
481                    site_id,
482                );
483
484                dock_pos_id += positions.docking_positions.len() as u32;
485                positions
486            })
487            .collect::<Vec<_>>()
488    }
489
490    /// Convienence function that returns the next route leg accounting for wrap
491    /// around.
492    pub fn increment_route_leg(&self, route_index: usize, leg_index: usize) -> usize {
493        if route_index >= self.routes.len() {
494            error!("Invalid route index: {}", route_index);
495            return 0;
496        }
497        (leg_index + 1) % self.routes[route_index].len()
498    }
499
500    /// Convienence function that returns the previous route leg accounting for
501    /// wrap around.
502    pub fn decrement_route_leg(&self, route_index: usize, leg_index: usize) -> usize {
503        if route_index >= self.routes.len() {
504            error!("Invalid route index: {}", route_index);
505            return 0;
506        }
507        if leg_index > 0 {
508            leg_index - 1
509        } else {
510            self.routes[route_index].len() - 1
511        }
512    }
513
514    /// Convienence function returning the number of routes.
515    pub fn route_count(&self) -> usize { self.routes.len() }
516
517    /// Safe function to get the number of AirshipDock sites on a route.
518    pub fn docking_site_count_for_route(&self, route_index: usize) -> usize {
519        if route_index >= self.routes.len() {
520            error!("Invalid route index: {}", route_index);
521            return 0;
522        }
523        self.routes[route_index].len()
524    }
525
526    /// Assign the docking platforms for each leg of each route. Each route
527    /// consists of a series (Vec) of docking node indices on the docking
528    /// site graph. This function loops over the routes docking nodes and
529    /// assigns a docking platform based on the approach direction to each
530    /// dock node while making sure that no docking platform is used more
531    /// than once (globally, over all routes).
532    fn assign_docking_platforms(
533        route_segments: &[Vec<usize>],
534        dock_locations: &[Vec2<f32>],
535    ) -> Vec<Vec<AirshipRouteLeg>> {
536        let mut incoming_edges = DHashMap::default();
537        for segment in route_segments.iter() {
538            if segment.len() < 3 {
539                continue;
540            }
541            let mut prev_node_id = segment[0];
542            segment.iter().skip(1).for_each(|&node_id| {
543                incoming_edges
544                    .entry(node_id)
545                    .or_insert_with(Vec::new)
546                    .push(prev_node_id);
547                prev_node_id = node_id;
548            });
549        }
550
551        let mut leg_platforms = DHashMap::default();
552
553        incoming_edges.iter().for_each(|(node_id, edges)| {
554            let dock_location = dock_locations[*node_id];
555            let mut used_platforms = DHashSet::default();
556            for origin in edges {
557                let origin_location = dock_locations[*origin];
558                // Determine the platform to dock using the direction from the dock location
559                // to the origin location
560                let rev_approach_dir = origin_location - dock_location;
561                let docking_platforms = AirshipDockPlatform::choices_from_dir(rev_approach_dir);
562                let docking_platform = docking_platforms
563                    .iter()
564                    .find(|&platform| !used_platforms.contains(platform))
565                    .copied()
566                    .unwrap_or(AirshipDockPlatform::NorthPlatform);
567                leg_platforms.insert((*origin, *node_id), docking_platform);
568                used_platforms.insert(docking_platform);
569            }
570        });
571
572        #[cfg(debug_assertions)]
573        {
574            debug!("Route segments: {:?}", route_segments);
575            debug!("Leg platforms: {:?}", leg_platforms);
576        }
577
578        // The incoming edges control the docking platforms used for each leg of the
579        // route. The outgoing platform for leg i must match the incoming
580        // platform for leg i-1. For the first leg, get the 'from' platform from
581        // the last pair of nodes in the segment.
582        let mut routes = Vec::new();
583        route_segments.iter().for_each(|segment| {
584            assert!(
585                segment.len() > 2,
586                "Segments must have at least two nodes and they must wrap around."
587            );
588            let mut route_legs = Vec::new();
589            let leg_start = &segment[segment.len() - 2..];
590            for leg_index in 0..segment.len() - 1 {
591                let from_node = segment[leg_index];
592                let to_node = segment[leg_index + 1];
593                if leg_index == 0 {
594                    assert!(
595                        from_node == leg_start[1],
596                        "The 'previous' leg's 'to' node must match the current leg's 'from' node."
597                    );
598                }
599                let to_platform = leg_platforms.get(&(from_node, to_node)).copied().unwrap_or(
600                    AirshipDockPlatform::from_dir(
601                        dock_locations[from_node] - dock_locations[to_node],
602                    ),
603                );
604                route_legs.push(AirshipRouteLeg {
605                    dest_index: to_node,
606                    platform: to_platform,
607                });
608            }
609            routes.push(route_legs);
610        });
611        routes
612    }
613
614    /// For each route, calculate the location along the route where airships
615    /// should be initially located when the server starts. This attempts to
616    /// space airships evenly along the route while ensuring that no airship
617    /// is too close to a docking position. Each airship needs separation
618    /// from the docking position such that the airship can initially move
619    /// forward towards its target docking location when it first starts
620    /// flying because it will start in the cruise phase of flight.
621    pub fn calculate_spawning_locations(&mut self, all_dock_points: &[Point]) {
622        let mut spawning_locations = Vec::new();
623        let mut expected_airships_count = 0;
624        self.routes
625            .iter()
626            .enumerate()
627            .for_each(|(route_index, route)| {
628                // Get the route length in blocks.
629                let route_len_blocks = route.iter().enumerate().fold(0.0f64, |acc, (j, leg)| {
630                    let to_dock_point = &all_dock_points[leg.dest_index];
631                    let from_dock_point = if j > 0 {
632                        &all_dock_points[route[j - 1].dest_index]
633                    } else {
634                        &all_dock_points[route[route.len() - 1].dest_index]
635                    };
636                    let from_loc = Vec2::new(from_dock_point.x as f32, from_dock_point.y as f32);
637                    let to_loc = Vec2::new(to_dock_point.x as f32, to_dock_point.y as f32);
638                    acc + from_loc.distance(to_loc) as f64
639                });
640                // The minimum number of airships to spawn on this route is the number of
641                // docking sites. The maximum is where airships would be spaced
642                // out evenly with Airships::AIRSHIP_SPACING blocks between them.
643                let airship_count = route
644                    .len()
645                    .max((route_len_blocks / Airships::AIRSHIP_SPACING as f64) as usize);
646
647                // Keep track of the total number of airships expected to be spawned.
648                expected_airships_count += airship_count;
649
650                // The precise desired airship spacing.
651                let airship_spacing = (route_len_blocks / airship_count as f64) as f32;
652                debug_airships!(
653                    "Route {} length: {} blocks, avg: {}, expecting {} airships for {} docking \
654                     sites",
655                    route_index,
656                    route_len_blocks,
657                    route_len_blocks / route.len() as f64,
658                    airship_count,
659                    route.len()
660                );
661
662                // get the docking points on this route
663                let route_points = route
664                    .iter()
665                    .map(|leg| all_dock_points[leg.dest_index].clone())
666                    .collect::<Vec<_>>();
667
668                // Airships can't be spawned too close to the docking sites. The leg lengths and
669                // desired spacing between airships will probably cause spawning
670                // locations to violate the too close rule, so
671                // do some iterations where the initial spawning location is varied, and the
672                // spawning locations are corrected to be at least
673                // Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK blocks from docking sites.
674                // Keep track of the deviation from the ideal positions and then use the
675                // spawning locations that produce the least deviation.
676                let mut best_route_spawning_locations = Vec::new();
677                let mut best_route_deviations = f32::MAX;
678                #[cfg(debug_assertions)]
679                let mut best_route_iteration = 0;
680                // 50 iterations works for the test data, but it may need to be adjusted
681                for i in 0..50 {
682                    let mut route_spawning_locations = Vec::new();
683                    let mut prev_point = &route_points[route_points.len() - 1];
684                    let mut target_dist = -1.0;
685                    let mut airships_spawned = 0;
686                    let mut deviation = 0.0;
687                    route_points
688                        .iter()
689                        .enumerate()
690                        .for_each(|(leg_index, dock_point)| {
691                            let to_loc = Vec2::new(dock_point.x as f32, dock_point.y as f32);
692                            let from_loc = Vec2::new(prev_point.x as f32, prev_point.y as f32);
693                            let leg_dir = (to_loc - from_loc).normalized();
694                            let leg_len = from_loc.distance(to_loc);
695                            // target_dist is the distance from the 'from' docking position where
696                            // the airship should spawn. The maximum is
697                            // the length of the leg minus the minimum spawn distance from the dock.
698                            // The minimum is the minimum spawn distance from the dock.
699                            let max_target_dist =
700                                leg_len - Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK;
701                            // Each iteration, the initial target distance is incremented by a prime
702                            // number. If more than 50 iterations are
703                            // needed, SPAWN_TARGET_DIST_INCREMENT might need to be reduced
704                            // so that the initial target distance doesn't exceed the length of the
705                            // first leg of the route.
706                            if target_dist < 0.0 {
707                                target_dist = Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK
708                                    + i as f32 * Airships::SPAWN_TARGET_DIST_INCREMENT;
709                            }
710                            // When target_dist exceeds the leg length, it means the spawning
711                            // location is into the next leg.
712                            while target_dist <= leg_len {
713                                // Limit the actual spawn location and keep track of the deviation.
714                                let spawn_point_dist = if target_dist > max_target_dist {
715                                    deviation += target_dist - max_target_dist;
716                                    max_target_dist
717                                } else if target_dist < Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK {
718                                    deviation +=
719                                        Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK - target_dist;
720                                    Airships::MIN_SPAWN_POINT_DIST_FROM_DOCK
721                                } else {
722                                    target_dist
723                                };
724
725                                let spawn_loc = from_loc + leg_dir * spawn_point_dist;
726                                route_spawning_locations.push(AirshipSpawningLocation {
727                                    pos: Vec2::new(spawn_loc.x, spawn_loc.y),
728                                    dir: leg_dir,
729                                    height: Airships::CRUISE_HEIGHTS
730                                        [route_index % Airships::CRUISE_HEIGHTS.len()],
731                                    route_index,
732                                    leg_index,
733                                });
734                                airships_spawned += 1;
735                                target_dist += airship_spacing;
736                            }
737                            target_dist -= leg_len;
738                            assert!(
739                                target_dist > 0.0,
740                                "Target distance should not be zero or negative: {}",
741                                target_dist
742                            );
743                            prev_point = dock_point;
744                        });
745                    if deviation < best_route_deviations {
746                        best_route_deviations = deviation;
747                        best_route_spawning_locations = route_spawning_locations.clone();
748                        #[cfg(debug_assertions)]
749                        {
750                            best_route_iteration = i;
751                        }
752                    }
753                }
754                debug_airships!(
755                    "Route {}: {} airships, {} spawning locations, best deviation: {}, iteration: \
756                     {}",
757                    route_index,
758                    airship_count,
759                    best_route_spawning_locations.len(),
760                    best_route_deviations,
761                    best_route_iteration
762                );
763                spawning_locations.extend(best_route_spawning_locations);
764            });
765        debug_airships!(
766            "Set spawning locations for {} airships of {} expected",
767            spawning_locations.len(),
768            expected_airships_count
769        );
770        if spawning_locations.len() == expected_airships_count {
771            self.spawning_locations = spawning_locations;
772            debug_airships!("Spawning locations: {:?}", self.spawning_locations);
773        } else {
774            error!(
775                "Expected {} airships, but produced only {} spawning locations.",
776                expected_airships_count,
777                spawning_locations.len()
778            );
779        }
780    }
781
782    /// Generates the airship routes.
783    pub fn generate_airship_routes_inner(
784        &mut self,
785        map_size_lg: &MapSizeLg,
786        seed: u32,
787        _index: Option<&Index>,
788        _sampler: Option<&WorldSim>,
789        _map_image_path: Option<&str>,
790    ) {
791        let all_dock_points = self
792            .airship_docks
793            .iter()
794            .map(|dock| Point {
795                x: dock.center.x as f64,
796                y: dock.center.y as f64,
797            })
798            .collect::<Vec<_>>();
799        debug_airships!("all_dock_points: {:?}", all_dock_points);
800
801        // Run the delaunay triangulation on the docking points.
802        let triangulation = triangulate(&all_dock_points);
803
804        #[cfg(feature = "airship_maps")]
805        save_airship_routes_triangulation(
806            &triangulation,
807            &all_dock_points,
808            map_size_lg,
809            seed,
810            _index,
811            _sampler,
812            _map_image_path,
813        );
814
815        // Docking positions are specified in world coordinates, not chunks.
816        // Limit the max route leg length to 1000 chunks no matter the world size.
817        let blocks_per_chunk = 1 << TERRAIN_CHUNK_BLOCKS_LG;
818        let world_blocks = map_size_lg.chunks().map(|u| u as f32) * blocks_per_chunk as f32;
819        let max_route_leg_length = 1000.0 * world_blocks.x;
820
821        // eulerized_route_segments is fairly expensive as the number of docking sites
822        // grows. Limit the number of iterations according to world size.
823        // pow2     world size   iterations
824        // 10       1024         50
825        // 11       2048         22
826        // 12       4096         10
827        // 13       8192          2
828        // Doing a least squares fit on the iterations gives the formula:
829        // 3742931.0 * e.powf(-1.113823 * pow2)
830        // 3742931.0 * 2.71828f32.powf(-1.113823 * pow2)
831
832        let pow2 = map_size_lg.vec().x;
833        let max_iterations = (3742931.0 * std::f32::consts::E.powf(-1.113823 * pow2 as f32))
834            .clamp(1.0, 100.0)
835            .round() as usize;
836
837        if let Some((best_segments, _, _max_seg_len, _min_spread, _iteration)) = triangulation
838            .eulerized_route_segments(
839                &all_dock_points,
840                max_iterations,
841                max_route_leg_length as f64,
842                seed,
843            )
844        {
845            #[cfg(debug_assertions)]
846            {
847                debug!("Max segment length: {}", _max_seg_len);
848                debug!("Min spread: {}", _min_spread);
849                debug!("Iteration: {}", _iteration);
850                debug!("Segments count:");
851                best_segments.iter().enumerate().for_each(|segment| {
852                    debug!("  {} : {}", segment.0, segment.1.len());
853                });
854                debug!("Best segments: {:?}", best_segments);
855                #[cfg(feature = "airship_maps")]
856                if let Some(index) = _index
857                    && let Some(world_sim) = _sampler
858                {
859                    if let Err(e) = export_world_map(index, world_sim) {
860                        eprintln!("Failed to export world map: {:?}", e);
861                    }
862                }
863            }
864
865            self.routes = Airships::assign_docking_platforms(
866                &best_segments,
867                all_dock_points
868                    .iter()
869                    .map(|p| Vec2::new(p.x as f32, p.y as f32))
870                    .collect::<Vec<_>>()
871                    .as_slice(),
872            );
873
874            // Calculate the spawning locations for airships on the routes.
875            self.calculate_spawning_locations(&all_dock_points);
876
877            #[cfg(feature = "airship_maps")]
878            save_airship_route_segments(
879                &self.routes,
880                &all_dock_points,
881                &self.spawning_locations,
882                map_size_lg,
883                seed,
884                _index,
885                _sampler,
886                _map_image_path,
887            );
888        } else {
889            eprintln!("Error - cannot eulerize the dock points.");
890        }
891    }
892
893    pub fn generate_airship_routes(&mut self, world_sim: &mut WorldSim, index: &Index) {
894        self.airship_docks = Airships::all_airshipdock_positions(&index.sites);
895
896        self.generate_airship_routes_inner(
897            &world_sim.map_size_lg(),
898            index.seed,
899            Some(index),
900            Some(world_sim),
901            None,
902        );
903    }
904
905    /// Compute the transition point where the airship should stop the cruise
906    /// flight phase and start the docking phase.
907    /// ```text
908    ///  F : From position
909    ///  T : Transition point
910    ///  D : Docking position
911    ///  C : Center of the airship dock
912    ///  X : Airship dock
913    ///
914    ///                      F
915    ///                     ∙
916    ///                    ∙
917    ///                   ∙
918    ///                  ∙
919    ///                 ∙
920    ///                T
921    ///               ∙
922    ///              ∙
923    ///             D
924    ///
925    ///           XXXXX
926    ///         XX     XX
927    ///        X         X
928    ///        X    C    X
929    ///        X         X
930    ///         XX     XX
931    ///           XXXXX
932    /// ```
933    /// The transition point between cruise flight and docking is on a line
934    /// between the route leg starting point (F) and the docking position
935    /// (D), short of the docking position by
936    /// Airships::DOCKING_TRANSITION_OFFSET blocks.
937    ///
938    /// # Arguments
939    ///
940    /// * `dock_index` - The airship dock index in airship_docks.
941    /// * `route_index` - The index of the route (outer vector of
942    ///   airships.routes). This is used to determine the cruise height.
943    /// * `platform` - The platform on the airship dock where the airship is to
944    ///   dock.
945    /// * `from` - The position from which the airship is approaching the dock.
946    ///   I.e., the position of the dock for the previous route leg.
947    /// # Returns
948    /// The 2D position calculated with the Z coordinate set to the
949    /// docking_position.z + cruise height.
950    pub fn approach_transition_point(
951        &self,
952        dock_index: usize,
953        route_index: usize,
954        platform: AirshipDockPlatform,
955        from: Vec2<f32>,
956    ) -> Option<Vec3<f32>> {
957        if let Some(dock_pos) = self.airship_docks.get(dock_index) {
958            let docking_position = dock_pos.docking_position(platform);
959            let dir = (docking_position.xy() - from).normalized();
960            return Some(
961                (docking_position.xy() - dir * Airships::DOCKING_TRANSITION_OFFSET)
962                    .with_z(docking_position.z + Airships::CRUISE_HEIGHTS[route_index]),
963            );
964        }
965        warn!(
966            "Approach point invalid, no airship dock found for docking position index {}",
967            dock_index
968        );
969        None
970    }
971
972    fn vec3_relative_eq(a: &vek::Vec3<f32>, b: &vek::Vec3<f32>, epsilon: f32) -> bool {
973        (a.x - b.x).abs() < epsilon && (a.y - b.y).abs() < epsilon && (a.z - b.z).abs() < epsilon
974    }
975
976    pub fn approach_for_route_and_leg(
977        &self,
978        route_index: usize,
979        leg_index: usize,
980    ) -> AirshipDockingApproach {
981        // Get the docking positions for the route and leg.
982        let to_route_leg = &self.routes[route_index][leg_index];
983        let from_route_leg = if leg_index == 0 {
984            &self.routes[route_index][self.routes[route_index].len() - 1]
985        } else {
986            &self.routes[route_index][leg_index - 1]
987        };
988        let dest_dock_positions = &self.airship_docks[to_route_leg.dest_index];
989        let from_dock_positions = &self.airship_docks[from_route_leg.dest_index];
990
991        let docking_side = AirshipDockingSide::from_dir_to_platform(
992            &(dest_dock_positions.center - from_dock_positions.center),
993            &to_route_leg.platform,
994        );
995
996        let (airship_pos, airship_direction) = Airships::airship_vec_for_docking_pos(
997            dest_dock_positions.docking_position(to_route_leg.platform),
998            dest_dock_positions.center,
999            Some(docking_side),
1000        );
1001
1002        AirshipDockingApproach {
1003            airship_pos,
1004            airship_direction,
1005            dock_center: dest_dock_positions.center,
1006            height: Airships::CRUISE_HEIGHTS[route_index],
1007            approach_transition_pos: self
1008                .approach_transition_point(
1009                    to_route_leg.dest_index,
1010                    route_index,
1011                    to_route_leg.platform,
1012                    from_dock_positions.center,
1013                )
1014                .unwrap_or_else(|| {
1015                    warn!(
1016                        "Failed to calculate approach transition point for route {} leg {}",
1017                        route_index, leg_index
1018                    );
1019                    dest_dock_positions.docking_position(to_route_leg.platform)
1020                }),
1021            side: docking_side,
1022            site_id: dest_dock_positions.site_id,
1023        }
1024    }
1025
1026    pub fn airship_spawning_locations(&self) -> Vec<AirshipSpawningLocation> {
1027        self.spawning_locations.clone()
1028    }
1029
1030    /// Get the position a route leg originates from.
1031    pub fn route_leg_departure_location(&self, route_index: usize, leg_index: usize) -> Vec2<f32> {
1032        if route_index >= self.routes.len() || leg_index >= self.routes[route_index].len() {
1033            error!("Invalid index: rt {}, leg {}", route_index, leg_index);
1034            return Vec2::zero();
1035        }
1036
1037        let prev_leg = if leg_index == 0 {
1038            &self.routes[route_index][self.routes[route_index].len() - 1]
1039        } else {
1040            &self.routes[route_index][leg_index - 1]
1041        };
1042
1043        self.airship_docks[prev_leg.dest_index]
1044            .docking_position(prev_leg.platform)
1045            .xy()
1046    }
1047
1048    /// Get the position and direction for the airship to dock at the given
1049    /// docking position. If use_starboard_boarding is None, the side for
1050    /// boarding is randomly chosen. The center of the airship position with
1051    /// respect to the docking position is an asymmetrical offset depending on
1052    /// which side of the airship will be used for boarding and where the
1053    /// captain is located on the airship. The returned position is the
1054    /// position where the captain will be when the airship is docked
1055    /// (because the captain NPC is the one that is positioned in the agent
1056    /// or rtsim code).
1057    pub fn airship_vec_for_docking_pos(
1058        docking_pos: Vec3<f32>,
1059        airship_dock_center: Vec2<f32>,
1060        docking_side: Option<AirshipDockingSide>,
1061    ) -> (Vec3<f32>, Dir) {
1062        // choose a random side for docking if not specified
1063        let dock_side = docking_side.unwrap_or_else(|| {
1064            if rand::rng().random::<bool>() {
1065                AirshipDockingSide::Starboard
1066            } else {
1067                AirshipDockingSide::Port
1068            }
1069        });
1070        // Get the vector from the dock alignment position on the airship to the
1071        // captain's position and the rotation angle for the ship to dock on the
1072        // specified side. The dock alignment position is where the airship
1073        // should touch or come closest to the dock. The side_rotation is the
1074        // angle the ship needs to rotate from to be perpendicular to the vector
1075        // from the dock center to the docking position. For example, if the docking
1076        // position is directly north (0 degrees, or aligned with the unit_y
1077        // vector), the ship needs to rotate 90 degrees CCW to dock on the port
1078        // side or 270 degrees CCW to dock on the starboard side.
1079        let (dock_align_to_captain, side_rotation) = if dock_side == AirshipDockingSide::Starboard {
1080            (
1081                Airships::DOCK_ALIGN_POS_STARBOARD,
1082                3.0 * std::f32::consts::FRAC_PI_2,
1083            )
1084        } else {
1085            (Airships::DOCK_ALIGN_POS_PORT, std::f32::consts::FRAC_PI_2)
1086        };
1087        // get the vector from the dock center to the docking platform point where the
1088        // airship should touch or come closest to.
1089        let dock_pos_offset = (docking_pos - airship_dock_center).xy();
1090        // The airship direction when docked is the dock_pos_offset rotated by the
1091        // side_rotation angle.
1092        let airship_dir =
1093            Dir::from_unnormalized(dock_pos_offset.rotated_z(side_rotation).with_z(0.0))
1094                .unwrap_or_default();
1095        // The dock_align_to_captain vector is rotated by the angle between unit_y and
1096        // the airship direction.
1097        let ship_dock_rotation =
1098            Airships::angle_between_vectors_ccw(Vec2::unit_y(), airship_dir.vec().xy());
1099        let captain_offset = dock_align_to_captain
1100            .rotated_z(ship_dock_rotation)
1101            .with_z(Airships::AIRSHIP_TO_DOCK_Z_OFFSET);
1102
1103        // To get the location of the pilot when the ship is docked, add the
1104        // captain_offset to the docking position.
1105        (docking_pos + captain_offset, airship_dir)
1106    }
1107
1108    /// Returns the angle from vec v1 to vec v2 in the CCW direction.
1109    pub fn angle_between_vectors_ccw(v1: Vec2<f32>, v2: Vec2<f32>) -> f32 {
1110        let dot_product = v1.dot(v2);
1111        let det = v1.x * v2.y - v1.y * v2.x; // determinant
1112        let angle = det.atan2(dot_product); // atan2(det, dot_product) gives the CCW angle
1113        if angle < 0.0 {
1114            angle + std::f32::consts::TAU
1115        } else {
1116            angle
1117        }
1118    }
1119
1120    /// Returns the angle from vec v1 to vec v2 in the CW direction.
1121    pub fn angle_between_vectors_cw(v1: Vec2<f32>, v2: Vec2<f32>) -> f32 {
1122        let ccw_angle = Airships::angle_between_vectors_ccw(v1, v2);
1123        std::f32::consts::TAU - ccw_angle
1124    }
1125}
1126
1127#[cfg(debug_assertions)]
1128macro_rules! debug_airship_eulerization {
1129    ($($arg:tt)*) => {
1130        debug!($($arg)*);
1131    }
1132}
1133
1134#[cfg(not(debug_assertions))]
1135macro_rules! debug_airship_eulerization {
1136    ($($arg:tt)*) => {};
1137}
1138
1139/// A map of node index to DockNode, where DockNode contains a list of
1140/// nodes that the node is connected to.
1141type DockNodeGraph = DHashMap<usize, DockNode>;
1142
1143/// Extension functions for Triangulation (from the triangulate crate).
1144trait TriangulationExt {
1145    fn all_edges(&self) -> DHashSet<(usize, usize)>;
1146    fn is_hull_node(&self, index: usize) -> bool;
1147    fn node_connections(&self) -> DockNodeGraph;
1148    fn eulerized_route_segments(
1149        &self,
1150        all_dock_points: &[Point],
1151        iterations: usize,
1152        max_route_leg_length: f64,
1153        seed: u32,
1154    ) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)>;
1155}
1156
1157/// Find the first node in the graph where the DockNode has an odd number of
1158/// connections to other nodes.
1159fn first_odd_node(
1160    search_order: &[usize],
1161    start: usize,
1162    nodes: &DockNodeGraph,
1163) -> Option<(usize, usize)> {
1164    search_order
1165        .iter()
1166        .enumerate()
1167        .skip(start)
1168        .find_map(|(index, &node_index)| {
1169            if let Some(dock_node) = nodes.get(&node_index) {
1170                if dock_node.connected.len() % 2 == 1 {
1171                    Some((index, node_index))
1172                } else {
1173                    None
1174                }
1175            } else {
1176                None
1177            }
1178        })
1179}
1180
1181/// Removes an edge between two nodes in the tesselation graph.
1182fn remove_edge(edge: (usize, usize), nodes: &mut DockNodeGraph) {
1183    if let Some(dock_node) = nodes.get_mut(&edge.0) {
1184        // Remove the edge from node_id1 to node_id2.
1185        // The edge may be present more than once, just remove one instance.
1186        if let Some(index) = dock_node
1187            .connected
1188            .iter()
1189            .position(|&node_id| node_id == edge.1)
1190        {
1191            dock_node.connected.remove(index);
1192        }
1193    }
1194    if let Some(dock_node) = nodes.get_mut(&edge.1) {
1195        // Remove the edge from node_id2 to node_id1.
1196        // The edge may be present more than once, just remove one instance.
1197        if let Some(index) = dock_node
1198            .connected
1199            .iter()
1200            .position(|&node_id| node_id == edge.0)
1201        {
1202            dock_node.connected.remove(index);
1203        }
1204    }
1205}
1206
1207/// Adds an edge between two nodes in the tesselation graph.
1208fn add_edge(edge: (usize, usize), nodes: &mut DockNodeGraph) {
1209    if let Some(dock_node) = nodes.get_mut(&edge.0) {
1210        dock_node.connected.push(edge.1);
1211    }
1212    if let Some(dock_node) = nodes.get_mut(&edge.1) {
1213        dock_node.connected.push(edge.0);
1214    }
1215}
1216
1217/// Implementation of extension functions for the Triangulation struct.
1218impl TriangulationExt for Triangulation {
1219    /// Get the set of all edges in the triangulation.
1220    fn all_edges(&self) -> DHashSet<(usize, usize)> {
1221        let mut edges = DHashSet::default();
1222        for t in self.triangles.chunks(3) {
1223            let a = t[0];
1224            let b = t[1];
1225            let c = t[2];
1226            // The edges hashset must have edges specified in increasing order to avoid
1227            // duplicates.
1228            edges.insert(if a < b { (a, b) } else { (b, a) });
1229            edges.insert(if b < c { (b, c) } else { (c, b) });
1230            edges.insert(if a < c { (a, c) } else { (c, a) });
1231        }
1232        edges
1233    }
1234
1235    /// For all triangles in the tessellation, create a map of nodes to their
1236    /// connected nodes.
1237    fn node_connections(&self) -> DockNodeGraph {
1238        let mut connections = DHashMap::default();
1239
1240        self.triangles.chunks(3).for_each(|t| {
1241            for &node in t {
1242                let dock_node = connections.entry(node).or_insert_with(|| DockNode {
1243                    node_id: node,
1244                    on_hull: self.is_hull_node(node),
1245                    connected: Vec::default(),
1246                });
1247                for &connected_node in t {
1248                    if connected_node != node && !dock_node.connected.contains(&connected_node) {
1249                        dock_node.connected.push(connected_node);
1250                    }
1251                }
1252            }
1253        });
1254        for (_, dock_node) in connections.iter_mut() {
1255            dock_node.connected = dock_node.connected.to_vec();
1256        }
1257        connections
1258    }
1259
1260    /// True if the node is on the outer hull of the triangulation.
1261    fn is_hull_node(&self, index: usize) -> bool { self.hull.contains(&index) }
1262
1263    /// Calculates the best way to modify the triangulation so that
1264    /// all nodes have an even number of connections (all nodes have
1265    /// an even 'degree'). The steps are:
1266    ///
1267    /// 1. Remove very long edges (not important for eurelization, but this is a
1268    ///    goal of the airship routes design.
1269    /// 2. Remove the shortest edges from all nodes that have more than 8
1270    ///    connections to other nodes. This is because the airship docking sites
1271    ///    have at most 4 docking positions, and for deconfliction purposes, no
1272    ///    two "routes" can use the same docking position.
1273    /// 3. Add edges to the triangulation so that all nodes have an even number
1274    ///    of connections to other nodes. There are many combinations of added
1275    ///    edges that can make all nodes have an even number of connections. The
1276    ///    goal is to find a graph with the maximum number of 'routes'
1277    ///    (sub-graphs of connected nodes that form a closed loop), where the
1278    ///    routes are all the same length. Since this is a graph, the algorithm
1279    ///    is sensitive to the starting point. Several iterations are tried with
1280    ///    different starting points (node indices), and the best result is
1281    ///    returned.
1282    ///
1283    /// Returns a tuple with the following elements:
1284    ///  - best_route_segments (up to 4 routes, each route is a vector of node
1285    ///    indices)
1286    ///  - best_circuit (the full eulerian circuit)
1287    ///  - max_seg_len (the length of the longest route segment)
1288    ///  - min_spread (the standard deviation of the route segment lengths)
1289    ///  - best_iteration (for debugging, the iteration that produced the best
1290    ///    result)
1291    fn eulerized_route_segments(
1292        &self,
1293        all_dock_points: &[Point],
1294        iterations: usize,
1295        max_route_leg_length: f64,
1296        seed: u32,
1297    ) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)> {
1298        let mut edges_to_remove = DHashSet::default();
1299
1300        // There can be at most four incoming and four outgoing edges per node because
1301        // there are only four docking positions per docking site and for deconfliction
1302        // purposes, no two "routes" can use the same docking position. This means that
1303        // the maximum number of edges per node is 8. Remove the shortest edges from
1304        // nodes with more than 8 edges.
1305
1306        // The tessellation algorithm produces convex hull, and there can be edges
1307        // connecting outside nodes where the distance between the points is a
1308        // significant fraction of the hull diameter. We want to keep airship
1309        // route legs as short as possible, while not removing interior edges
1310        // that may already be fairly long due to the configuration of the
1311        // docking sites relative to the entire map. For the standard world map,
1312        // with 2^10 chunks (1024x1024), the hull diameter is about 1000 chunks.
1313        // Experimentally, the standard world map can have interior edges that are
1314        // around 800 chunks long. A world map with 2^12 chunks (4096x4096) can
1315        // have hull edges that are around 2000 chunks long, but interior edges
1316        // still have a max of around 800 chunks. For the larger world maps,
1317        // removing edges that are longer than 1000 chunks is a good heuristic.
1318
1319        // First, use these heuristics to remove excess edges from the node graph.
1320        // 1. remove edges that are longer than 1000 blocks.
1321        // 2. remove the shortest edges from nodes with more than 8 edges
1322
1323        let max_distance_squared = max_route_leg_length.powi(2);
1324
1325        let all_edges = self.all_edges();
1326        for edge in all_edges.iter() {
1327            let pt1 = &all_dock_points[edge.0];
1328            let pt2 = &all_dock_points[edge.1];
1329            let v1 = Vec2 { x: pt1.x, y: pt1.y };
1330            let v2 = Vec2 { x: pt2.x, y: pt2.y };
1331            // Remove the edge if the distance between the points is greater than
1332            // max_leg_length
1333            if v1.distance_squared(v2) > max_distance_squared {
1334                edges_to_remove.insert(*edge);
1335            }
1336        }
1337
1338        #[cfg(debug_assertions)]
1339        let long_edges = edges_to_remove.len();
1340
1341        debug_airship_eulerization!(
1342            "Found {} long edges to remove out of {} total edges",
1343            edges_to_remove.len(),
1344            all_edges.len()
1345        );
1346
1347        let node_connections = self.node_connections();
1348        node_connections.iter().for_each(|(&node_id, node)| {
1349            if node.connected.len() > 8 {
1350                let excess_edges_count = node.connected.len() - 8;
1351                // Find the shortest edge and remove it
1352                let mut connected_node_info = node
1353                    .connected
1354                    .iter()
1355                    .map(|&connected_node_id| {
1356                        let pt1 = &all_dock_points[node_id];
1357                        let pt2 = &all_dock_points[connected_node_id];
1358                        let v1 = Vec2 { x: pt1.x, y: pt1.y };
1359                        let v2 = Vec2 { x: pt2.x, y: pt2.y };
1360                        (connected_node_id, v1.distance_squared(v2) as i64)
1361                    })
1362                    .collect::<Vec<_>>();
1363                connected_node_info.sort_by(|a, b| a.1.cmp(&b.1));
1364                let mut excess_edges_remaining = excess_edges_count;
1365                let mut remove_index = 0;
1366                while excess_edges_remaining > 0 && remove_index < connected_node_info.len() {
1367                    let (connected_node_id, _) = connected_node_info[remove_index];
1368                    let edge = if node_id < connected_node_id {
1369                        (node_id, connected_node_id)
1370                    } else {
1371                        (connected_node_id, node_id)
1372                    };
1373                    if !edges_to_remove.contains(&edge) {
1374                        edges_to_remove.insert(edge);
1375                        excess_edges_remaining -= 1;
1376                    }
1377                    remove_index += 1;
1378                }
1379            }
1380        });
1381
1382        let mut mutable_node_connections = node_connections.clone();
1383
1384        debug_airship_eulerization!(
1385            "Removing {} long edges and {} excess edges for a total of {} removed edges out of a \
1386             total of {} edges",
1387            long_edges,
1388            edges_to_remove.len() - long_edges,
1389            edges_to_remove.len(),
1390            all_edges.len(),
1391        );
1392
1393        for edge in edges_to_remove {
1394            remove_edge(edge, &mut mutable_node_connections);
1395        }
1396
1397        #[cfg(debug_assertions)]
1398        {
1399            // count the number of nodes with an odd connected count
1400            let odd_connected_count0 = mutable_node_connections
1401                .iter()
1402                .filter(|(_, node)| node.connected.len() % 2 == 1)
1403                .count();
1404            let total_connections1 = mutable_node_connections
1405                .iter()
1406                .map(|(_, node)| node.connected.len())
1407                .sum::<usize>();
1408            debug_airship_eulerization!(
1409                "After Removing, odd connected count: {} in {} nodes, total connections: {}",
1410                odd_connected_count0,
1411                mutable_node_connections.len(),
1412                total_connections1
1413            );
1414        }
1415
1416        // Now eurlerize the node graph by adding edges to connect nodes with an odd
1417        // number of connections. Eurlerization means that every node will have
1418        // an even number of degrees (edges), which is a requirement for
1419        // creating a Eulerian Circuit.
1420
1421        // Get the keys (node ids, which is the same as the node's index in the
1422        // all_dock_points vector) of nodes with an odd number of edges.
1423        let mut odd_keys: Vec<usize> = mutable_node_connections
1424            .iter()
1425            .filter(|(_, node)| node.connected.len() % 2 == 1)
1426            .map(|(node_id, _)| *node_id)
1427            .collect();
1428
1429        let mut rng = ChaChaRng::from_seed(seed_expan::rng_state(seed));
1430
1431        // There will always be an even number of odd nodes in a connected graph (one
1432        // where all nodes are reachable from any other node). The goal is to
1433        // pair the odd nodes, adding edges between each pair such that the
1434        // added edges are as short as possible. After adding edges, the graph
1435        // will have an even number of edges for each node.
1436
1437        // The starting node index for finding pairs is arbitrary, and starting from
1438        // different nodes will yield different Eulerian circuits.
1439
1440        // Do a number of iterations and find the best results. The criteria is
1441        // 1. The number of route groups (the outer Vec in best_route_segments) This
1442        //    will be a maximum of 4 because there are at most 4 docking positions per
1443        //    docking site. More is better.
1444        // 2. The 'spread' of the lengths of the inner Vecs in best_route_segments. The
1445        //    calculated spread is the standard deviation of the lengths. Smaller is
1446        //    better (more uniform lengths of the route groups.)
1447        let mut best_circuit = Vec::new();
1448        let mut best_route_segments = Vec::new();
1449        let mut best_max_seg_len = 0;
1450        let mut best_min_spread = f32::MAX;
1451        let mut best_iteration = 0;
1452
1453        for i in 0..iterations {
1454            // Deterministically randomize the node order to search for the best route
1455            // segments.
1456            let mut eulerized_node_connections = mutable_node_connections.clone();
1457
1458            let mut odd_connected_count = odd_keys.len();
1459            assert!(
1460                odd_connected_count.is_multiple_of(2),
1461                "Odd connected count should be even, got {}",
1462                odd_connected_count
1463            );
1464            assert!(
1465                odd_keys.len()
1466                    == eulerized_node_connections
1467                        .iter()
1468                        .filter(|(_, node)| node.connected.len() % 2 == 1)
1469                        .count()
1470            );
1471
1472            // It's possible that the graphs starts with no odd nodes after removing edges
1473            // above.
1474            if odd_connected_count > 0 {
1475                odd_keys.shuffle(&mut rng);
1476
1477                // The edges to be added. An edge is a tuple of two node ids/indices.
1478                let mut edges_to_add = DHashSet::default();
1479                // Each odd node will be paired with only one other odd node.
1480                // Keep track of which nodes have been paired already.
1481                let mut paired_odd_nodes = DHashSet::default();
1482
1483                for node_key in odd_keys.iter() {
1484                    // Skip nodes that are already paired.
1485                    if paired_odd_nodes.contains(node_key) {
1486                        continue;
1487                    }
1488                    if let Some(node) = mutable_node_connections.get(node_key) {
1489                        // find the closest node other than nodes that are already connected to
1490                        // this one.
1491                        let mut closest_node_id = None;
1492                        let mut closest_distance = f64::MAX;
1493                        for candidate_key in odd_keys.iter() {
1494                            // Skip nodes that are already paired.
1495                            if paired_odd_nodes.contains(candidate_key) {
1496                                continue;
1497                            }
1498                            if let Some(candidate_node) =
1499                                mutable_node_connections.get(candidate_key)
1500                            {
1501                                // Skip the node itself and nodes that are already connected to this
1502                                // node.
1503                                if *candidate_key != *node_key
1504                                    && !node.connected.contains(candidate_key)
1505                                    && !candidate_node.connected.contains(node_key)
1506                                {
1507                                    // make sure the edge is specified in increasing node index
1508                                    // order to
1509                                    // avoid duplicates.
1510                                    let edge_to_add = if *node_key < *candidate_key {
1511                                        (*node_key, *candidate_key)
1512                                    } else {
1513                                        (*candidate_key, *node_key)
1514                                    };
1515                                    // Skip the edge if it is already in the edges_to_add set.
1516                                    if !edges_to_add.contains(&edge_to_add) {
1517                                        let pt1 = &all_dock_points[*node_key];
1518                                        let pt2 = &all_dock_points[*candidate_key];
1519                                        let v1 = Vec2 { x: pt1.x, y: pt1.y };
1520                                        let v2 = Vec2 { x: pt2.x, y: pt2.y };
1521                                        let distance = v1.distance_squared(v2);
1522                                        if distance < closest_distance {
1523                                            closest_distance = distance;
1524                                            closest_node_id = Some(*candidate_key);
1525                                        }
1526                                    }
1527                                }
1528                            }
1529                        }
1530                        // It's possible that the only odd nodes remaining are already connected to
1531                        // this node, but we still need to pair them. In
1532                        // this case, the connections become bidirectional,
1533                        // but that's okay for Eulerization and airships will still only follow each
1534                        // other in one direction.
1535                        if closest_node_id.is_none() {
1536                            // If no suitable node was found, repeat the search but allow
1537                            // connecting to nodes that are already connected to this one.
1538                            for candidate_key in odd_keys.iter() {
1539                                // Skip nodes that are already paired.
1540                                if paired_odd_nodes.contains(candidate_key) {
1541                                    continue;
1542                                }
1543                                // Skip the node itself
1544                                if *candidate_key != *node_key {
1545                                    // make sure the edge is specified in increasing node index
1546                                    // order to
1547                                    // avoid duplicates.
1548                                    let edge_to_add = if *node_key < *candidate_key {
1549                                        (*node_key, *candidate_key)
1550                                    } else {
1551                                        (*candidate_key, *node_key)
1552                                    };
1553                                    // Skip the edge if it is already in the edges_to_add set.
1554                                    if !edges_to_add.contains(&edge_to_add) {
1555                                        let pt1 = &all_dock_points[*node_key];
1556                                        let pt2 = &all_dock_points[*candidate_key];
1557                                        let v1 = Vec2 { x: pt1.x, y: pt1.y };
1558                                        let v2 = Vec2 { x: pt2.x, y: pt2.y };
1559                                        let distance = v1.distance_squared(v2);
1560                                        if distance < closest_distance {
1561                                            closest_distance = distance;
1562                                            closest_node_id = Some(*candidate_key);
1563                                        }
1564                                    }
1565                                }
1566                            }
1567                        }
1568                        // If a closest node was found that is not already paired, add the edge.
1569                        // Note that this should not fail since we are guaranteed to have
1570                        // an even number of odd nodes.
1571                        if let Some(close_node_id) = closest_node_id {
1572                            // add the edge between node_id and closest_node_id
1573                            let edge_to_add = if *node_key < close_node_id {
1574                                (*node_key, close_node_id)
1575                            } else {
1576                                (close_node_id, *node_key)
1577                            };
1578                            edges_to_add.insert(edge_to_add);
1579                            paired_odd_nodes.insert(*node_key);
1580                            paired_odd_nodes.insert(close_node_id);
1581                        } else {
1582                            error!("Cannot pair all odd nodes, this should not happen.");
1583                        }
1584                    }
1585                    if edges_to_add.len() == odd_connected_count / 2 {
1586                        // If we have paired all odd nodes, break out of the loop.
1587                        // The break is necessary because the outer loop iterates over
1588                        // all odd keys but we only need make 1/2 that many pairs of nodes.
1589                        break;
1590                    }
1591                }
1592                for edge in edges_to_add {
1593                    add_edge(edge, &mut eulerized_node_connections);
1594                }
1595                // count the number of nodes with an odd connected count
1596                odd_connected_count = eulerized_node_connections
1597                    .iter()
1598                    .filter(|(_, node)| node.connected.len() % 2 == 1)
1599                    .count();
1600
1601                #[cfg(debug_assertions)]
1602                {
1603                    let total_connections = eulerized_node_connections
1604                        .iter()
1605                        .map(|(_, node)| node.connected.len())
1606                        .sum::<usize>();
1607                    debug_airship_eulerization!(
1608                        "Outer Iteration: {}, After Adding, odd connected count: {} in {} nodes, \
1609                         total connections: {}",
1610                        i,
1611                        odd_connected_count,
1612                        eulerized_node_connections.len(),
1613                        total_connections
1614                    );
1615                }
1616            }
1617
1618            // If all nodes have an even number of edges, proceed with finding the best
1619            // Eulerian circuit for the given node configuration.
1620            if odd_connected_count == 0 {
1621                // Find the best Eulerian circuit for the current node connections
1622                if let Some((route_segments, circuit, max_seg_len, min_spread, _)) =
1623                    find_best_eulerian_circuit(&eulerized_node_connections)
1624                {
1625                    #[cfg(debug_assertions)]
1626                    {
1627                        debug_airship_eulerization!("Outer Iteration: {}", i);
1628                        debug_airship_eulerization!("Max segment length: {}", max_seg_len);
1629                        debug_airship_eulerization!("Min spread: {}", min_spread);
1630                        debug_airship_eulerization!("Segments count:");
1631                        route_segments.iter().enumerate().for_each(|segment| {
1632                            debug_airship_eulerization!("  {} : {}", segment.0, segment.1.len());
1633                        });
1634                    }
1635                    // A Eulerian circuit was found, apply the goal criteria to find the best
1636                    // circuit.
1637                    if max_seg_len > best_max_seg_len
1638                        || (max_seg_len == best_max_seg_len && min_spread < best_min_spread)
1639                    {
1640                        best_circuit = circuit;
1641                        best_route_segments = route_segments;
1642                        best_max_seg_len = max_seg_len;
1643                        best_min_spread = min_spread;
1644                        best_iteration = i;
1645                    }
1646                }
1647            } else {
1648                debug_airship_eulerization!(
1649                    "Error, this should not happen: iteration {}, odd connected count: {} of {} \
1650                     nodes, total connections: {}, SKIPPING iteration",
1651                    i,
1652                    odd_connected_count,
1653                    eulerized_node_connections.len(),
1654                    eulerized_node_connections
1655                        .iter()
1656                        .map(|(_, node)| node.connected.len())
1657                        .sum::<usize>()
1658                );
1659                error!(
1660                    "Eulerian circuit not found on iteration {}. Odd connected count is not zero, \
1661                     this should not happen",
1662                    i
1663                );
1664            }
1665        }
1666        #[cfg(debug_assertions)]
1667        {
1668            debug_airship_eulerization!("Max segment length: {}", best_max_seg_len);
1669            debug_airship_eulerization!("Min spread: {}", best_min_spread);
1670            debug_airship_eulerization!("Iteration: {}", best_iteration);
1671            debug_airship_eulerization!("Segments count:");
1672            best_route_segments.iter().enumerate().for_each(|segment| {
1673                debug_airship_eulerization!("  {} : {}", segment.0, segment.1.len());
1674            });
1675        }
1676
1677        if best_route_segments.is_empty() {
1678            return None;
1679        }
1680        Some((
1681            best_route_segments,
1682            best_circuit,
1683            best_max_seg_len,
1684            best_min_spread,
1685            best_iteration,
1686        ))
1687    }
1688}
1689
1690/// Find the best Eulerian circuit for the given graph of dock nodes.
1691/// Try each node as the starting point for a circuit.
1692/// The best circuit is the one with the longest routes (sub-segments
1693/// of the circuit), and where the route lengths are equal as possible.
1694fn find_best_eulerian_circuit(
1695    graph: &DockNodeGraph,
1696) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)> {
1697    let mut best_circuit = Vec::new();
1698    let mut best_route_segments = Vec::new();
1699    let mut best_max_seg_len = 0;
1700    let mut best_min_spread = f32::MAX;
1701    let mut best_iteration = 0;
1702
1703    let graph_keys = graph.keys().copied().collect::<Vec<_>>();
1704
1705    // Repeat for each node as the starting point.
1706    for (i, &start_vertex) in graph_keys.iter().enumerate() {
1707        let mut graph = graph.clone();
1708        let mut circuit = Vec::new();
1709        let mut stack = Vec::new();
1710        let mut circuit_nodes = DHashSet::default();
1711
1712        let mut current_vertex = start_vertex;
1713
1714        // The algorithm for finding a Eulerian Circuit (Hierholzer's algorithm).
1715        while !stack.is_empty() || !graph[&current_vertex].connected.is_empty() {
1716            if graph[&current_vertex].connected.is_empty() {
1717                circuit.push(current_vertex);
1718                circuit_nodes.insert(current_vertex);
1719                current_vertex = stack.pop()?;
1720            } else {
1721                stack.push(current_vertex);
1722                if let Some(&next_vertex) = graph
1723                    .get(&current_vertex)?
1724                    .connected
1725                    .iter()
1726                    .find(|&vertex| !circuit_nodes.contains(vertex))
1727                    .or(graph.get(&current_vertex)?.connected.first())
1728                {
1729                    remove_edge((current_vertex, next_vertex), &mut graph);
1730                    current_vertex = next_vertex;
1731                } else {
1732                    return None;
1733                }
1734            }
1735        }
1736        circuit.push(current_vertex);
1737        circuit.reverse();
1738
1739        if let Some((route_segments, max_seg_len, min_spread)) =
1740            best_eulerian_circuit_segments(&graph, &circuit)
1741            && (max_seg_len > best_max_seg_len
1742                || (max_seg_len == best_max_seg_len && min_spread < best_min_spread))
1743        {
1744            best_circuit = circuit.clone();
1745            best_route_segments = route_segments;
1746            best_max_seg_len = max_seg_len;
1747            best_min_spread = min_spread;
1748            best_iteration = i;
1749        }
1750    }
1751    if best_route_segments.is_empty() {
1752        return None;
1753    }
1754    Some((
1755        best_route_segments,
1756        best_circuit,
1757        best_max_seg_len,
1758        best_min_spread,
1759        best_iteration,
1760    ))
1761}
1762
1763/// Get the optimal grouping of Eulerian Circuit nodes and edges such that a
1764/// maximum number of sub-circuits are created, and the length of each
1765/// sub-circuit is as similar as possible.
1766///
1767/// The Airship dock nodes are connected in a Eulerian Circuit, where each edge
1768/// of the tessellation is traversed exactly once. The circuit is a closed loop,
1769/// so the first and last node are the same. The single circuit can be broken
1770/// into multiple segments, each being also a closed loop. This is desirable for
1771/// airship routes, to limit the number of airships associated with each "route"
1772/// where a route is a closed circuit of docking sites. Since each edge is flown
1773/// in only one direction, the maximum number of possible closed loop segments
1774/// is equal to the maximum number of edges connected to any node, divided by 2.
1775fn best_eulerian_circuit_segments(
1776    graph: &DockNodeGraph,
1777    circuit: &[usize],
1778) -> Option<(Vec<Vec<usize>>, usize, f32)> {
1779    // get the node_connections keys, which are node ids.
1780    // Sort the nodes (node ids) by the number of connections to other nodes.
1781    let sorted_node_ids: Vec<usize> = graph
1782        .keys()
1783        .copied()
1784        .sorted_by_key(|&node_id| graph[&node_id].connected.len())
1785        .rev()
1786        .collect();
1787
1788    let mut max_segments_count = 0;
1789    let mut min_segments_len_spread = f32::MAX;
1790    let mut best_segments = Vec::new();
1791
1792    // For each node_id in the sorted node ids,
1793    // break the circuit into circular segments that start and end with that
1794    // node_id. The best set of segments is the one with the most segments and
1795    // where the length of the segments differ the least.
1796    sorted_node_ids.iter().for_each(|&node_id| {
1797        let mut segments = Vec::new();
1798        let mut current_segment = Vec::new();
1799        let circuit_len = circuit.len();
1800        let mut starting_index = usize::MAX;
1801        let mut end_index = usize::MAX;
1802        let mut prev_value = usize::MAX;
1803
1804        for (index, &value) in circuit.iter().cycle().enumerate() {
1805            if value == node_id {
1806                if starting_index == usize::MAX {
1807                    starting_index = index;
1808                    if starting_index > 0 {
1809                        end_index = index + circuit_len - 1;
1810                    } else {
1811                        end_index = index + circuit_len - 2;
1812                    }
1813                }
1814                if !current_segment.is_empty() {
1815                    current_segment.push(value);
1816                    segments.push(current_segment);
1817                    current_segment = Vec::new();
1818                }
1819            }
1820            if starting_index < usize::MAX {
1821                if value != prev_value {
1822                    current_segment.push(value);
1823                }
1824                prev_value = value;
1825            }
1826
1827            // Stop cycling once we've looped back to the value before the starting index
1828            if index == end_index {
1829                break;
1830            }
1831        }
1832
1833        // Add the last segment
1834        if !current_segment.is_empty() {
1835            current_segment.push(node_id);
1836            segments.push(current_segment);
1837        }
1838
1839        let avg_segment_length = segments.iter().map(|segment| segment.len()).sum::<usize>() as f32
1840            / segments.len() as f32;
1841
1842        // We want similar segment lengths, so calculate the spread as the
1843        // standard deviation of the segment lengths.
1844        let seg_lengths_spread = segments
1845            .iter()
1846            .map(|segment| (segment.len() as f32 - avg_segment_length).powi(2))
1847            .sum::<f32>()
1848            .sqrt()
1849            / segments.len() as f32;
1850
1851        // First take the longest segment count, then if the segment count is the same
1852        // as the longest so far, take the one with the least length spread.
1853        if segments.len() > max_segments_count {
1854            max_segments_count = segments.len();
1855            min_segments_len_spread = seg_lengths_spread;
1856            best_segments = segments;
1857        } else if segments.len() == max_segments_count
1858            && seg_lengths_spread < min_segments_len_spread
1859        {
1860            min_segments_len_spread = seg_lengths_spread;
1861            best_segments = segments;
1862        }
1863    });
1864    if best_segments.is_empty() {
1865        return None;
1866    }
1867    Some((best_segments, max_segments_count, min_segments_len_spread))
1868}
1869
1870// ------------------------------------------------
1871// All code below this is for testing purposes only
1872// ------------------------------------------------
1873
1874// Public so it could be used in other modules' tests.
1875#[cfg(test)]
1876pub fn airships_from_test_data() -> Airships {
1877    let mut store = Store::<Site>::default();
1878    let dummy_site = Site::default();
1879    let dummy_site_id = store.insert(dummy_site);
1880
1881    let docks = vec![
1882        AirshipDockPositions {
1883            center: Vec2 {
1884                x: 26688.0,
1885                y: 4758.0,
1886            },
1887            docking_positions: vec![
1888                AirshipDockingPosition(0, Vec3 {
1889                    x: 26707.0,
1890                    y: 4758.0,
1891                    z: 213.0,
1892                }),
1893                AirshipDockingPosition(1, Vec3 {
1894                    x: 26688.0,
1895                    y: 4777.0,
1896                    z: 213.0,
1897                }),
1898                AirshipDockingPosition(2, Vec3 {
1899                    x: 26669.0,
1900                    y: 4758.0,
1901                    z: 213.0,
1902                }),
1903                AirshipDockingPosition(3, Vec3 {
1904                    x: 26688.0,
1905                    y: 4739.0,
1906                    z: 213.0,
1907                }),
1908            ],
1909            site_id: dummy_site_id,
1910        },
1911        AirshipDockPositions {
1912            center: Vec2 {
1913                x: 24574.0,
1914                y: 26108.0,
1915            },
1916            docking_positions: vec![
1917                AirshipDockingPosition(4, Vec3 {
1918                    x: 24593.0,
1919                    y: 26108.0,
1920                    z: 214.0,
1921                }),
1922                AirshipDockingPosition(5, Vec3 {
1923                    x: 24574.0,
1924                    y: 26127.0,
1925                    z: 214.0,
1926                }),
1927                AirshipDockingPosition(6, Vec3 {
1928                    x: 24555.0,
1929                    y: 26108.0,
1930                    z: 214.0,
1931                }),
1932                AirshipDockingPosition(7, Vec3 {
1933                    x: 24574.0,
1934                    y: 26089.0,
1935                    z: 214.0,
1936                }),
1937            ],
1938            site_id: dummy_site_id,
1939        },
1940        AirshipDockPositions {
1941            center: Vec2 {
1942                x: 24253.0,
1943                y: 20715.0,
1944            },
1945            docking_positions: vec![
1946                AirshipDockingPosition(8, Vec3 {
1947                    x: 24272.0,
1948                    y: 20715.0,
1949                    z: 515.0,
1950                }),
1951                AirshipDockingPosition(9, Vec3 {
1952                    x: 24253.0,
1953                    y: 20734.0,
1954                    z: 515.0,
1955                }),
1956                AirshipDockingPosition(10, Vec3 {
1957                    x: 24234.0,
1958                    y: 20715.0,
1959                    z: 515.0,
1960                }),
1961                AirshipDockingPosition(11, Vec3 {
1962                    x: 24253.0,
1963                    y: 20696.0,
1964                    z: 515.0,
1965                }),
1966            ],
1967            site_id: dummy_site_id,
1968        },
1969        AirshipDockPositions {
1970            center: Vec2 {
1971                x: 20809.0,
1972                y: 6555.0,
1973            },
1974            docking_positions: vec![
1975                AirshipDockingPosition(12, Vec3 {
1976                    x: 20828.0,
1977                    y: 6555.0,
1978                    z: 216.0,
1979                }),
1980                AirshipDockingPosition(13, Vec3 {
1981                    x: 20809.0,
1982                    y: 6574.0,
1983                    z: 216.0,
1984                }),
1985                AirshipDockingPosition(14, Vec3 {
1986                    x: 20790.0,
1987                    y: 6555.0,
1988                    z: 216.0,
1989                }),
1990                AirshipDockingPosition(15, Vec3 {
1991                    x: 20809.0,
1992                    y: 6536.0,
1993                    z: 216.0,
1994                }),
1995            ],
1996            site_id: dummy_site_id,
1997        },
1998        AirshipDockPositions {
1999            center: Vec2 {
2000                x: 16492.0,
2001                y: 1061.0,
2002            },
2003            docking_positions: vec![
2004                AirshipDockingPosition(16, Vec3 {
2005                    x: 16511.0,
2006                    y: 1061.0,
2007                    z: 211.0,
2008                }),
2009                AirshipDockingPosition(17, Vec3 {
2010                    x: 16492.0,
2011                    y: 1080.0,
2012                    z: 211.0,
2013                }),
2014                AirshipDockingPosition(18, Vec3 {
2015                    x: 16473.0,
2016                    y: 1061.0,
2017                    z: 211.0,
2018                }),
2019                AirshipDockingPosition(19, Vec3 {
2020                    x: 16492.0,
2021                    y: 1042.0,
2022                    z: 211.0,
2023                }),
2024            ],
2025            site_id: dummy_site_id,
2026        },
2027        AirshipDockPositions {
2028            center: Vec2 {
2029                x: 18452.0,
2030                y: 11236.0,
2031            },
2032            docking_positions: vec![
2033                AirshipDockingPosition(20, Vec3 {
2034                    x: 18471.0,
2035                    y: 11236.0,
2036                    z: 421.0,
2037                }),
2038                AirshipDockingPosition(21, Vec3 {
2039                    x: 18452.0,
2040                    y: 11255.0,
2041                    z: 421.0,
2042                }),
2043                AirshipDockingPosition(22, Vec3 {
2044                    x: 18433.0,
2045                    y: 11236.0,
2046                    z: 421.0,
2047                }),
2048                AirshipDockingPosition(23, Vec3 {
2049                    x: 18452.0,
2050                    y: 11217.0,
2051                    z: 421.0,
2052                }),
2053            ],
2054            site_id: dummy_site_id,
2055        },
2056        AirshipDockPositions {
2057            center: Vec2 {
2058                x: 21870.0,
2059                y: 8530.0,
2060            },
2061            docking_positions: vec![
2062                AirshipDockingPosition(24, Vec3 {
2063                    x: 21889.0,
2064                    y: 8530.0,
2065                    z: 216.0,
2066                }),
2067                AirshipDockingPosition(25, Vec3 {
2068                    x: 21870.0,
2069                    y: 8549.0,
2070                    z: 216.0,
2071                }),
2072                AirshipDockingPosition(26, Vec3 {
2073                    x: 21851.0,
2074                    y: 8530.0,
2075                    z: 216.0,
2076                }),
2077                AirshipDockingPosition(27, Vec3 {
2078                    x: 21870.0,
2079                    y: 8511.0,
2080                    z: 216.0,
2081                }),
2082            ],
2083            site_id: dummy_site_id,
2084        },
2085        AirshipDockPositions {
2086            center: Vec2 {
2087                x: 22577.0,
2088                y: 15197.0,
2089            },
2090            docking_positions: vec![
2091                AirshipDockingPosition(28, Vec3 {
2092                    x: 22605.0,
2093                    y: 15197.0,
2094                    z: 277.0,
2095                }),
2096                AirshipDockingPosition(29, Vec3 {
2097                    x: 22577.0,
2098                    y: 15225.0,
2099                    z: 277.0,
2100                }),
2101                AirshipDockingPosition(30, Vec3 {
2102                    x: 22549.0,
2103                    y: 15197.0,
2104                    z: 277.0,
2105                }),
2106                AirshipDockingPosition(31, Vec3 {
2107                    x: 22577.0,
2108                    y: 15169.0,
2109                    z: 277.0,
2110                }),
2111            ],
2112            site_id: dummy_site_id,
2113        },
2114        AirshipDockPositions {
2115            center: Vec2 {
2116                x: 5477.0,
2117                y: 15207.0,
2118            },
2119            docking_positions: vec![
2120                AirshipDockingPosition(32, Vec3 {
2121                    x: 5514.0,
2122                    y: 15207.0,
2123                    z: 1675.0,
2124                }),
2125                AirshipDockingPosition(33, Vec3 {
2126                    x: 5477.0,
2127                    y: 15244.0,
2128                    z: 1675.0,
2129                }),
2130                AirshipDockingPosition(34, Vec3 {
2131                    x: 5440.0,
2132                    y: 15207.0,
2133                    z: 1675.0,
2134                }),
2135                AirshipDockingPosition(35, Vec3 {
2136                    x: 5477.0,
2137                    y: 15170.0,
2138                    z: 1675.0,
2139                }),
2140            ],
2141            site_id: dummy_site_id,
2142        },
2143        AirshipDockPositions {
2144            center: Vec2 {
2145                x: 23884.0,
2146                y: 24302.0,
2147            },
2148            docking_positions: vec![
2149                AirshipDockingPosition(36, Vec3 {
2150                    x: 23903.0,
2151                    y: 24302.0,
2152                    z: 214.0,
2153                }),
2154                AirshipDockingPosition(37, Vec3 {
2155                    x: 23884.0,
2156                    y: 24321.0,
2157                    z: 214.0,
2158                }),
2159                AirshipDockingPosition(38, Vec3 {
2160                    x: 23865.0,
2161                    y: 24302.0,
2162                    z: 214.0,
2163                }),
2164                AirshipDockingPosition(39, Vec3 {
2165                    x: 23884.0,
2166                    y: 24283.0,
2167                    z: 214.0,
2168                }),
2169            ],
2170            site_id: dummy_site_id,
2171        },
2172        AirshipDockPositions {
2173            center: Vec2 {
2174                x: 13373.0,
2175                y: 2313.0,
2176            },
2177            docking_positions: vec![
2178                AirshipDockingPosition(40, Vec3 {
2179                    x: 13392.0,
2180                    y: 2313.0,
2181                    z: 259.0,
2182                }),
2183                AirshipDockingPosition(41, Vec3 {
2184                    x: 13373.0,
2185                    y: 2332.0,
2186                    z: 259.0,
2187                }),
2188                AirshipDockingPosition(42, Vec3 {
2189                    x: 13354.0,
2190                    y: 2313.0,
2191                    z: 259.0,
2192                }),
2193                AirshipDockingPosition(43, Vec3 {
2194                    x: 13373.0,
2195                    y: 2294.0,
2196                    z: 259.0,
2197                }),
2198            ],
2199            site_id: dummy_site_id,
2200        },
2201        AirshipDockPositions {
2202            center: Vec2 {
2203                x: 20141.0,
2204                y: 31861.0,
2205            },
2206            docking_positions: vec![
2207                AirshipDockingPosition(44, Vec3 {
2208                    x: 20160.0,
2209                    y: 31861.0,
2210                    z: 215.0,
2211                }),
2212                AirshipDockingPosition(45, Vec3 {
2213                    x: 20141.0,
2214                    y: 31880.0,
2215                    z: 215.0,
2216                }),
2217                AirshipDockingPosition(46, Vec3 {
2218                    x: 20122.0,
2219                    y: 31861.0,
2220                    z: 215.0,
2221                }),
2222                AirshipDockingPosition(47, Vec3 {
2223                    x: 20141.0,
2224                    y: 31842.0,
2225                    z: 215.0,
2226                }),
2227            ],
2228            site_id: dummy_site_id,
2229        },
2230        AirshipDockPositions {
2231            center: Vec2 {
2232                x: 29713.0,
2233                y: 24533.0,
2234            },
2235            docking_positions: vec![
2236                AirshipDockingPosition(48, Vec3 {
2237                    x: 29732.0,
2238                    y: 24533.0,
2239                    z: 214.0,
2240                }),
2241                AirshipDockingPosition(49, Vec3 {
2242                    x: 29713.0,
2243                    y: 24552.0,
2244                    z: 214.0,
2245                }),
2246                AirshipDockingPosition(50, Vec3 {
2247                    x: 29694.0,
2248                    y: 24533.0,
2249                    z: 214.0,
2250                }),
2251                AirshipDockingPosition(51, Vec3 {
2252                    x: 29713.0,
2253                    y: 24514.0,
2254                    z: 214.0,
2255                }),
2256            ],
2257            site_id: dummy_site_id,
2258        },
2259        AirshipDockPositions {
2260            center: Vec2 {
2261                x: 18992.0,
2262                y: 17120.0,
2263            },
2264            docking_positions: vec![
2265                AirshipDockingPosition(52, Vec3 {
2266                    x: 19011.0,
2267                    y: 17120.0,
2268                    z: 435.0,
2269                }),
2270                AirshipDockingPosition(53, Vec3 {
2271                    x: 18992.0,
2272                    y: 17139.0,
2273                    z: 435.0,
2274                }),
2275                AirshipDockingPosition(54, Vec3 {
2276                    x: 18973.0,
2277                    y: 17120.0,
2278                    z: 435.0,
2279                }),
2280                AirshipDockingPosition(55, Vec3 {
2281                    x: 18992.0,
2282                    y: 17101.0,
2283                    z: 435.0,
2284                }),
2285            ],
2286            site_id: dummy_site_id,
2287        },
2288        AirshipDockPositions {
2289            center: Vec2 {
2290                x: 7705.0,
2291                y: 12533.0,
2292            },
2293            docking_positions: vec![
2294                AirshipDockingPosition(56, Vec3 {
2295                    x: 7742.0,
2296                    y: 12533.0,
2297                    z: 1911.0,
2298                }),
2299                AirshipDockingPosition(57, Vec3 {
2300                    x: 7705.0,
2301                    y: 12570.0,
2302                    z: 1911.0,
2303                }),
2304                AirshipDockingPosition(58, Vec3 {
2305                    x: 7668.0,
2306                    y: 12533.0,
2307                    z: 1911.0,
2308                }),
2309                AirshipDockingPosition(59, Vec3 {
2310                    x: 7705.0,
2311                    y: 12496.0,
2312                    z: 1911.0,
2313                }),
2314            ],
2315            site_id: dummy_site_id,
2316        },
2317        AirshipDockPositions {
2318            center: Vec2 {
2319                x: 30365.0,
2320                y: 12987.0,
2321            },
2322            docking_positions: vec![
2323                AirshipDockingPosition(60, Vec3 {
2324                    x: 30393.0,
2325                    y: 12987.0,
2326                    z: 244.0,
2327                }),
2328                AirshipDockingPosition(61, Vec3 {
2329                    x: 30365.0,
2330                    y: 13015.0,
2331                    z: 244.0,
2332                }),
2333                AirshipDockingPosition(62, Vec3 {
2334                    x: 30337.0,
2335                    y: 12987.0,
2336                    z: 244.0,
2337                }),
2338                AirshipDockingPosition(63, Vec3 {
2339                    x: 30365.0,
2340                    y: 12959.0,
2341                    z: 244.0,
2342                }),
2343            ],
2344            site_id: dummy_site_id,
2345        },
2346        AirshipDockPositions {
2347            center: Vec2 {
2348                x: 10142.0,
2349                y: 19190.0,
2350            },
2351            docking_positions: vec![
2352                AirshipDockingPosition(64, Vec3 {
2353                    x: 10170.0,
2354                    y: 19190.0,
2355                    z: 1141.0,
2356                }),
2357                AirshipDockingPosition(65, Vec3 {
2358                    x: 10142.0,
2359                    y: 19218.0,
2360                    z: 1141.0,
2361                }),
2362                AirshipDockingPosition(66, Vec3 {
2363                    x: 10114.0,
2364                    y: 19190.0,
2365                    z: 1141.0,
2366                }),
2367                AirshipDockingPosition(67, Vec3 {
2368                    x: 10142.0,
2369                    y: 19162.0,
2370                    z: 1141.0,
2371                }),
2372            ],
2373            site_id: dummy_site_id,
2374        },
2375        AirshipDockPositions {
2376            center: Vec2 {
2377                x: 13716.0,
2378                y: 17505.0,
2379            },
2380            docking_positions: vec![
2381                AirshipDockingPosition(68, Vec3 {
2382                    x: 13753.0,
2383                    y: 17505.0,
2384                    z: 1420.0,
2385                }),
2386                AirshipDockingPosition(69, Vec3 {
2387                    x: 13716.0,
2388                    y: 17542.0,
2389                    z: 1420.0,
2390                }),
2391                AirshipDockingPosition(70, Vec3 {
2392                    x: 13679.0,
2393                    y: 17505.0,
2394                    z: 1420.0,
2395                }),
2396                AirshipDockingPosition(71, Vec3 {
2397                    x: 13716.0,
2398                    y: 17468.0,
2399                    z: 1420.0,
2400                }),
2401            ],
2402            site_id: dummy_site_id,
2403        },
2404        AirshipDockPositions {
2405            center: Vec2 {
2406                x: 9383.0,
2407                y: 17145.0,
2408            },
2409            docking_positions: vec![
2410                AirshipDockingPosition(72, Vec3 {
2411                    x: 9411.0,
2412                    y: 17145.0,
2413                    z: 909.0,
2414                }),
2415                AirshipDockingPosition(73, Vec3 {
2416                    x: 9383.0,
2417                    y: 17173.0,
2418                    z: 909.0,
2419                }),
2420                AirshipDockingPosition(74, Vec3 {
2421                    x: 9355.0,
2422                    y: 17145.0,
2423                    z: 909.0,
2424                }),
2425                AirshipDockingPosition(75, Vec3 {
2426                    x: 9383.0,
2427                    y: 17117.0,
2428                    z: 909.0,
2429                }),
2430            ],
2431            site_id: dummy_site_id,
2432        },
2433        AirshipDockPositions {
2434            center: Vec2 {
2435                x: 24424.0,
2436                y: 7800.0,
2437            },
2438            docking_positions: vec![
2439                AirshipDockingPosition(76, Vec3 {
2440                    x: 24443.0,
2441                    y: 7800.0,
2442                    z: 329.0,
2443                }),
2444                AirshipDockingPosition(77, Vec3 {
2445                    x: 24424.0,
2446                    y: 7819.0,
2447                    z: 329.0,
2448                }),
2449                AirshipDockingPosition(78, Vec3 {
2450                    x: 24405.0,
2451                    y: 7800.0,
2452                    z: 329.0,
2453                }),
2454                AirshipDockingPosition(79, Vec3 {
2455                    x: 24424.0,
2456                    y: 7781.0,
2457                    z: 329.0,
2458                }),
2459            ],
2460            site_id: dummy_site_id,
2461        },
2462        AirshipDockPositions {
2463            center: Vec2 {
2464                x: 7528.0,
2465                y: 28426.0,
2466            },
2467            docking_positions: vec![
2468                AirshipDockingPosition(80, Vec3 {
2469                    x: 7547.0,
2470                    y: 28426.0,
2471                    z: 218.0,
2472                }),
2473                AirshipDockingPosition(81, Vec3 {
2474                    x: 7528.0,
2475                    y: 28445.0,
2476                    z: 218.0,
2477                }),
2478                AirshipDockingPosition(82, Vec3 {
2479                    x: 7509.0,
2480                    y: 28426.0,
2481                    z: 218.0,
2482                }),
2483                AirshipDockingPosition(83, Vec3 {
2484                    x: 7528.0,
2485                    y: 28407.0,
2486                    z: 218.0,
2487                }),
2488            ],
2489            site_id: dummy_site_id,
2490        },
2491        AirshipDockPositions {
2492            center: Vec2 {
2493                x: 9942.0,
2494                y: 30936.0,
2495            },
2496            docking_positions: vec![
2497                AirshipDockingPosition(84, Vec3 {
2498                    x: 9961.0,
2499                    y: 30936.0,
2500                    z: 185.0,
2501                }),
2502                AirshipDockingPosition(85, Vec3 {
2503                    x: 9942.0,
2504                    y: 30955.0,
2505                    z: 185.0,
2506                }),
2507                AirshipDockingPosition(86, Vec3 {
2508                    x: 9923.0,
2509                    y: 30936.0,
2510                    z: 185.0,
2511                }),
2512                AirshipDockingPosition(87, Vec3 {
2513                    x: 9942.0,
2514                    y: 30917.0,
2515                    z: 185.0,
2516                }),
2517            ],
2518            site_id: dummy_site_id,
2519        },
2520        AirshipDockPositions {
2521            center: Vec2 {
2522                x: 27915.0,
2523                y: 18559.0,
2524            },
2525            docking_positions: vec![
2526                AirshipDockingPosition(88, Vec3 {
2527                    x: 27934.0,
2528                    y: 18559.0,
2529                    z: 498.0,
2530                }),
2531                AirshipDockingPosition(89, Vec3 {
2532                    x: 27915.0,
2533                    y: 18578.0,
2534                    z: 498.0,
2535                }),
2536                AirshipDockingPosition(90, Vec3 {
2537                    x: 27896.0,
2538                    y: 18559.0,
2539                    z: 498.0,
2540                }),
2541                AirshipDockingPosition(91, Vec3 {
2542                    x: 27915.0,
2543                    y: 18540.0,
2544                    z: 498.0,
2545                }),
2546            ],
2547            site_id: dummy_site_id,
2548        },
2549        AirshipDockPositions {
2550            center: Vec2 {
2551                x: 3688.0,
2552                y: 29168.0,
2553            },
2554            docking_positions: vec![
2555                AirshipDockingPosition(92, Vec3 {
2556                    x: 3711.0,
2557                    y: 29168.0,
2558                    z: 198.0,
2559                }),
2560                AirshipDockingPosition(93, Vec3 {
2561                    x: 3688.0,
2562                    y: 29191.0,
2563                    z: 198.0,
2564                }),
2565                AirshipDockingPosition(94, Vec3 {
2566                    x: 3665.0,
2567                    y: 29168.0,
2568                    z: 198.0,
2569                }),
2570                AirshipDockingPosition(95, Vec3 {
2571                    x: 3688.0,
2572                    y: 29145.0,
2573                    z: 198.0,
2574                }),
2575            ],
2576            site_id: dummy_site_id,
2577        },
2578        AirshipDockPositions {
2579            center: Vec2 {
2580                x: 15864.0,
2581                y: 15584.0,
2582            },
2583            docking_positions: vec![
2584                AirshipDockingPosition(96, Vec3 {
2585                    x: 15892.0,
2586                    y: 15584.0,
2587                    z: 419.0,
2588                }),
2589                AirshipDockingPosition(97, Vec3 {
2590                    x: 15864.0,
2591                    y: 15612.0,
2592                    z: 419.0,
2593                }),
2594                AirshipDockingPosition(98, Vec3 {
2595                    x: 15836.0,
2596                    y: 15584.0,
2597                    z: 419.0,
2598                }),
2599                AirshipDockingPosition(99, Vec3 {
2600                    x: 15864.0,
2601                    y: 15556.0,
2602                    z: 419.0,
2603                }),
2604            ],
2605            site_id: dummy_site_id,
2606        },
2607        AirshipDockPositions {
2608            center: Vec2 {
2609                x: 9975.0,
2610                y: 24289.0,
2611            },
2612            docking_positions: vec![
2613                AirshipDockingPosition(100, Vec3 {
2614                    x: 10012.0,
2615                    y: 24289.0,
2616                    z: 755.0,
2617                }),
2618                AirshipDockingPosition(101, Vec3 {
2619                    x: 9975.0,
2620                    y: 24326.0,
2621                    z: 755.0,
2622                }),
2623                AirshipDockingPosition(102, Vec3 {
2624                    x: 9938.0,
2625                    y: 24289.0,
2626                    z: 755.0,
2627                }),
2628                AirshipDockingPosition(103, Vec3 {
2629                    x: 9975.0,
2630                    y: 24252.0,
2631                    z: 755.0,
2632                }),
2633            ],
2634            site_id: dummy_site_id,
2635        },
2636        AirshipDockPositions {
2637            center: Vec2 {
2638                x: 479.0,
2639                y: 18279.0,
2640            },
2641            docking_positions: vec![
2642                AirshipDockingPosition(104, Vec3 {
2643                    x: 516.0,
2644                    y: 18279.0,
2645                    z: 449.0,
2646                }),
2647                AirshipDockingPosition(105, Vec3 {
2648                    x: 479.0,
2649                    y: 18316.0,
2650                    z: 449.0,
2651                }),
2652                AirshipDockingPosition(106, Vec3 {
2653                    x: 442.0,
2654                    y: 18279.0,
2655                    z: 449.0,
2656                }),
2657                AirshipDockingPosition(107, Vec3 {
2658                    x: 479.0,
2659                    y: 18242.0,
2660                    z: 449.0,
2661                }),
2662            ],
2663            site_id: dummy_site_id,
2664        },
2665        AirshipDockPositions {
2666            center: Vec2 {
2667                x: 26543.0,
2668                y: 17175.0,
2669            },
2670            docking_positions: vec![
2671                AirshipDockingPosition(108, Vec3 {
2672                    x: 26566.0,
2673                    y: 17175.0,
2674                    z: 362.0,
2675                }),
2676                AirshipDockingPosition(109, Vec3 {
2677                    x: 26543.0,
2678                    y: 17198.0,
2679                    z: 362.0,
2680                }),
2681                AirshipDockingPosition(110, Vec3 {
2682                    x: 26520.0,
2683                    y: 17175.0,
2684                    z: 362.0,
2685                }),
2686                AirshipDockingPosition(111, Vec3 {
2687                    x: 26543.0,
2688                    y: 17152.0,
2689                    z: 362.0,
2690                }),
2691            ],
2692            site_id: dummy_site_id,
2693        },
2694    ];
2695
2696    let routes = vec![
2697        vec![
2698            AirshipRouteLeg {
2699                dest_index: 13,
2700                platform: AirshipDockPlatform::SouthPlatform,
2701            },
2702            AirshipRouteLeg {
2703                dest_index: 24,
2704                platform: AirshipDockPlatform::EastPlatform,
2705            },
2706            AirshipRouteLeg {
2707                dest_index: 17,
2708                platform: AirshipDockPlatform::EastPlatform,
2709            },
2710            AirshipRouteLeg {
2711                dest_index: 13,
2712                platform: AirshipDockPlatform::WestPlatform,
2713            },
2714            AirshipRouteLeg {
2715                dest_index: 9,
2716                platform: AirshipDockPlatform::SouthPlatform,
2717            },
2718            AirshipRouteLeg {
2719                dest_index: 2,
2720                platform: AirshipDockPlatform::NorthPlatform,
2721            },
2722            AirshipRouteLeg {
2723                dest_index: 13,
2724                platform: AirshipDockPlatform::EastPlatform,
2725            },
2726            AirshipRouteLeg {
2727                dest_index: 7,
2728                platform: AirshipDockPlatform::WestPlatform,
2729            },
2730            AirshipRouteLeg {
2731                dest_index: 2,
2732                platform: AirshipDockPlatform::SouthPlatform,
2733            },
2734            AirshipRouteLeg {
2735                dest_index: 22,
2736                platform: AirshipDockPlatform::WestPlatform,
2737            },
2738            AirshipRouteLeg {
2739                dest_index: 27,
2740                platform: AirshipDockPlatform::NorthPlatform,
2741            },
2742            AirshipRouteLeg {
2743                dest_index: 2,
2744                platform: AirshipDockPlatform::EastPlatform,
2745            },
2746            AirshipRouteLeg {
2747                dest_index: 12,
2748                platform: AirshipDockPlatform::WestPlatform,
2749            },
2750            AirshipRouteLeg {
2751                dest_index: 22,
2752                platform: AirshipDockPlatform::NorthPlatform,
2753            },
2754            AirshipRouteLeg {
2755                dest_index: 15,
2756                platform: AirshipDockPlatform::NorthPlatform,
2757            },
2758            AirshipRouteLeg {
2759                dest_index: 19,
2760                platform: AirshipDockPlatform::EastPlatform,
2761            },
2762            AirshipRouteLeg {
2763                dest_index: 6,
2764                platform: AirshipDockPlatform::EastPlatform,
2765            },
2766            AirshipRouteLeg {
2767                dest_index: 5,
2768                platform: AirshipDockPlatform::EastPlatform,
2769            },
2770        ],
2771        vec![
2772            AirshipRouteLeg {
2773                dest_index: 24,
2774                platform: AirshipDockPlatform::SouthPlatform,
2775            },
2776            AirshipRouteLeg {
2777                dest_index: 14,
2778                platform: AirshipDockPlatform::EastPlatform,
2779            },
2780            AirshipRouteLeg {
2781                dest_index: 18,
2782                platform: AirshipDockPlatform::SouthPlatform,
2783            },
2784            AirshipRouteLeg {
2785                dest_index: 16,
2786                platform: AirshipDockPlatform::SouthPlatform,
2787            },
2788            AirshipRouteLeg {
2789                dest_index: 17,
2790                platform: AirshipDockPlatform::WestPlatform,
2791            },
2792            AirshipRouteLeg {
2793                dest_index: 18,
2794                platform: AirshipDockPlatform::EastPlatform,
2795            },
2796            AirshipRouteLeg {
2797                dest_index: 8,
2798                platform: AirshipDockPlatform::EastPlatform,
2799            },
2800            AirshipRouteLeg {
2801                dest_index: 16,
2802                platform: AirshipDockPlatform::WestPlatform,
2803            },
2804            AirshipRouteLeg {
2805                dest_index: 26,
2806                platform: AirshipDockPlatform::EastPlatform,
2807            },
2808            AirshipRouteLeg {
2809                dest_index: 25,
2810                platform: AirshipDockPlatform::WestPlatform,
2811            },
2812            AirshipRouteLeg {
2813                dest_index: 13,
2814                platform: AirshipDockPlatform::NorthPlatform,
2815            },
2816            AirshipRouteLeg {
2817                dest_index: 11,
2818                platform: AirshipDockPlatform::SouthPlatform,
2819            },
2820            AirshipRouteLeg {
2821                dest_index: 1,
2822                platform: AirshipDockPlatform::NorthPlatform,
2823            },
2824            AirshipRouteLeg {
2825                dest_index: 9,
2826                platform: AirshipDockPlatform::NorthPlatform,
2827            },
2828            AirshipRouteLeg {
2829                dest_index: 25,
2830                platform: AirshipDockPlatform::EastPlatform,
2831            },
2832            AirshipRouteLeg {
2833                dest_index: 17,
2834                platform: AirshipDockPlatform::NorthPlatform,
2835            },
2836            AirshipRouteLeg {
2837                dest_index: 14,
2838                platform: AirshipDockPlatform::NorthPlatform,
2839            },
2840            AirshipRouteLeg {
2841                dest_index: 5,
2842                platform: AirshipDockPlatform::WestPlatform,
2843            },
2844        ],
2845        vec![
2846            AirshipRouteLeg {
2847                dest_index: 10,
2848                platform: AirshipDockPlatform::NorthPlatform,
2849            },
2850            AirshipRouteLeg {
2851                dest_index: 14,
2852                platform: AirshipDockPlatform::SouthPlatform,
2853            },
2854            AirshipRouteLeg {
2855                dest_index: 8,
2856                platform: AirshipDockPlatform::SouthPlatform,
2857            },
2858            AirshipRouteLeg {
2859                dest_index: 26,
2860                platform: AirshipDockPlatform::SouthPlatform,
2861            },
2862            AirshipRouteLeg {
2863                dest_index: 14,
2864                platform: AirshipDockPlatform::WestPlatform,
2865            },
2866            AirshipRouteLeg {
2867                dest_index: 16,
2868                platform: AirshipDockPlatform::EastPlatform,
2869            },
2870            AirshipRouteLeg {
2871                dest_index: 25,
2872                platform: AirshipDockPlatform::SouthPlatform,
2873            },
2874            AirshipRouteLeg {
2875                dest_index: 23,
2876                platform: AirshipDockPlatform::EastPlatform,
2877            },
2878            AirshipRouteLeg {
2879                dest_index: 20,
2880                platform: AirshipDockPlatform::WestPlatform,
2881            },
2882            AirshipRouteLeg {
2883                dest_index: 21,
2884                platform: AirshipDockPlatform::SouthPlatform,
2885            },
2886            AirshipRouteLeg {
2887                dest_index: 11,
2888                platform: AirshipDockPlatform::WestPlatform,
2889            },
2890            AirshipRouteLeg {
2891                dest_index: 9,
2892                platform: AirshipDockPlatform::WestPlatform,
2893            },
2894            AirshipRouteLeg {
2895                dest_index: 12,
2896                platform: AirshipDockPlatform::SouthPlatform,
2897            },
2898            AirshipRouteLeg {
2899                dest_index: 1,
2900                platform: AirshipDockPlatform::EastPlatform,
2901            },
2902            AirshipRouteLeg {
2903                dest_index: 7,
2904                platform: AirshipDockPlatform::NorthPlatform,
2905            },
2906            AirshipRouteLeg {
2907                dest_index: 27,
2908                platform: AirshipDockPlatform::WestPlatform,
2909            },
2910            AirshipRouteLeg {
2911                dest_index: 15,
2912                platform: AirshipDockPlatform::WestPlatform,
2913            },
2914            AirshipRouteLeg {
2915                dest_index: 7,
2916                platform: AirshipDockPlatform::EastPlatform,
2917            },
2918            AirshipRouteLeg {
2919                dest_index: 19,
2920                platform: AirshipDockPlatform::NorthPlatform,
2921            },
2922            AirshipRouteLeg {
2923                dest_index: 3,
2924                platform: AirshipDockPlatform::EastPlatform,
2925            },
2926            AirshipRouteLeg {
2927                dest_index: 5,
2928                platform: AirshipDockPlatform::SouthPlatform,
2929            },
2930        ],
2931        vec![
2932            AirshipRouteLeg {
2933                dest_index: 4,
2934                platform: AirshipDockPlatform::NorthPlatform,
2935            },
2936            AirshipRouteLeg {
2937                dest_index: 10,
2938                platform: AirshipDockPlatform::EastPlatform,
2939            },
2940            AirshipRouteLeg {
2941                dest_index: 3,
2942                platform: AirshipDockPlatform::WestPlatform,
2943            },
2944            AirshipRouteLeg {
2945                dest_index: 4,
2946                platform: AirshipDockPlatform::EastPlatform,
2947            },
2948            AirshipRouteLeg {
2949                dest_index: 0,
2950                platform: AirshipDockPlatform::WestPlatform,
2951            },
2952            AirshipRouteLeg {
2953                dest_index: 15,
2954                platform: AirshipDockPlatform::SouthPlatform,
2955            },
2956            AirshipRouteLeg {
2957                dest_index: 12,
2958                platform: AirshipDockPlatform::EastPlatform,
2959            },
2960            AirshipRouteLeg {
2961                dest_index: 11,
2962                platform: AirshipDockPlatform::EastPlatform,
2963            },
2964            AirshipRouteLeg {
2965                dest_index: 25,
2966                platform: AirshipDockPlatform::NorthPlatform,
2967            },
2968            AirshipRouteLeg {
2969                dest_index: 21,
2970                platform: AirshipDockPlatform::EastPlatform,
2971            },
2972            AirshipRouteLeg {
2973                dest_index: 23,
2974                platform: AirshipDockPlatform::NorthPlatform,
2975            },
2976            AirshipRouteLeg {
2977                dest_index: 26,
2978                platform: AirshipDockPlatform::NorthPlatform,
2979            },
2980            AirshipRouteLeg {
2981                dest_index: 10,
2982                platform: AirshipDockPlatform::WestPlatform,
2983            },
2984            AirshipRouteLeg {
2985                dest_index: 19,
2986                platform: AirshipDockPlatform::WestPlatform,
2987            },
2988            AirshipRouteLeg {
2989                dest_index: 0,
2990                platform: AirshipDockPlatform::NorthPlatform,
2991            },
2992            AirshipRouteLeg {
2993                dest_index: 3,
2994                platform: AirshipDockPlatform::SouthPlatform,
2995            },
2996            AirshipRouteLeg {
2997                dest_index: 6,
2998                platform: AirshipDockPlatform::SouthPlatform,
2999            },
3000            AirshipRouteLeg {
3001                dest_index: 7,
3002                platform: AirshipDockPlatform::SouthPlatform,
3003            },
3004            AirshipRouteLeg {
3005                dest_index: 5,
3006                platform: AirshipDockPlatform::NorthPlatform,
3007            },
3008        ],
3009    ];
3010
3011    Airships {
3012        airship_docks: docks,
3013        routes,
3014        ..Default::default()
3015    }
3016}
3017
3018#[cfg(test)]
3019mod tests {
3020    use super::{
3021        AirshipDockPlatform, AirshipDockingSide, Airships, DockNode, TriangulationExt,
3022        airships_from_test_data, approx::assert_relative_eq, find_best_eulerian_circuit,
3023        remove_edge,
3024    };
3025    use crate::util::{DHashMap, DHashSet};
3026    use delaunator::{Point, triangulate};
3027    use vek::{Quaternion, Vec2, Vec3};
3028
3029    #[test]
3030    fn basic_vec_test() {
3031        let vec1 = Vec3::new(0.0f32, 10.0, 0.0);
3032        let vec2 = Vec3::new(10.0, 0.0, 0.0);
3033        let a12 = vec2.angle_between(vec1);
3034        assert_relative_eq!(a12, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3035
3036        let rotc2 = Quaternion::rotation_z(a12);
3037        let vec3 = rotc2 * vec2;
3038        assert!(vec3 == vec1);
3039    }
3040
3041    #[test]
3042    fn std_vec_angles_test() {
3043        let refvec = Vec2::new(0.0f32, 10.0);
3044
3045        let vec1 = Vec2::new(0.0f32, 10.0);
3046        let vec2 = Vec2::new(10.0f32, 0.0);
3047        let vec3 = Vec2::new(0.0f32, -10.0);
3048        let vec4 = Vec2::new(-10.0f32, 0.0);
3049
3050        let a1r = vec1.angle_between(refvec);
3051        assert!(a1r == 0.0f32);
3052
3053        let a2r = vec2.angle_between(refvec);
3054        assert_relative_eq!(a2r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3055
3056        let a3r: f32 = vec3.angle_between(refvec);
3057        assert_relative_eq!(a3r, std::f32::consts::PI, epsilon = 0.00001);
3058
3059        let a4r = vec4.angle_between(refvec);
3060        assert_relative_eq!(a4r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3061    }
3062
3063    #[test]
3064    fn vec_angles_test() {
3065        let refvec = Vec3::new(0.0f32, 10.0, 0.0);
3066
3067        let vec1 = Vec3::new(0.0f32, 10.0, 0.0);
3068        let vec2 = Vec3::new(10.0f32, 0.0, 0.0);
3069        let vec3 = Vec3::new(0.0f32, -10.0, 0.0);
3070        let vec4 = Vec3::new(-10.0f32, 0.0, 0.0);
3071
3072        let a1r = vec1.angle_between(refvec);
3073        let a1r3 = Airships::angle_between_vectors_ccw(vec1.xy(), refvec.xy());
3074        assert!(a1r == 0.0f32);
3075        assert!(a1r3 == 0.0f32);
3076
3077        let a2r = vec2.angle_between(refvec);
3078        let a2r3 = Airships::angle_between_vectors_ccw(vec2.xy(), refvec.xy());
3079        assert_relative_eq!(a2r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3080        assert_relative_eq!(a2r3, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3081
3082        let a3r: f32 = vec3.angle_between(refvec);
3083        let a3r3 = Airships::angle_between_vectors_ccw(vec3.xy(), refvec.xy());
3084        assert_relative_eq!(a3r, std::f32::consts::PI, epsilon = 0.00001);
3085        assert_relative_eq!(a3r3, std::f32::consts::PI, epsilon = 0.00001);
3086
3087        let a4r = vec4.angle_between(refvec);
3088        let a4r3 = Airships::angle_between_vectors_ccw(vec4.xy(), refvec.xy());
3089        assert_relative_eq!(a4r, std::f32::consts::FRAC_PI_2, epsilon = 0.00001);
3090        assert_relative_eq!(a4r3, std::f32::consts::FRAC_PI_2 * 3.0, epsilon = 0.00001);
3091    }
3092
3093    #[test]
3094    fn airship_angles_test() {
3095        let refvec = Vec2::new(0.0f32, 37.0);
3096        let ovec = Vec2::new(-4.0f32, -14.0);
3097        let oveccw0 = Vec2::new(-4, -14);
3098        let oveccw90 = Vec2::new(-14, 4);
3099        let oveccw180 = Vec2::new(4, 14);
3100        let oveccw270 = Vec2::new(14, -4);
3101        let ovecccw0 = Vec2::new(-4, -14);
3102        let ovecccw90 = Vec2::new(14, -4);
3103        let ovecccw180 = Vec2::new(4, 14);
3104        let ovecccw270 = Vec2::new(-14, 4);
3105
3106        let vec1 = Vec2::new(0.0f32, 37.0);
3107        let vec2 = Vec2::new(37.0f32, 0.0);
3108        let vec3 = Vec2::new(0.0f32, -37.0);
3109        let vec4 = Vec2::new(-37.0f32, 0.0);
3110
3111        assert!(
3112            ovec.rotated_z(Airships::angle_between_vectors_cw(vec1, refvec))
3113                .map(|x| x.round() as i32)
3114                == oveccw0
3115        );
3116        assert!(
3117            ovec.rotated_z(Airships::angle_between_vectors_cw(vec2, refvec))
3118                .map(|x| x.round() as i32)
3119                == oveccw90
3120        );
3121        assert!(
3122            ovec.rotated_z(Airships::angle_between_vectors_cw(vec3, refvec))
3123                .map(|x| x.round() as i32)
3124                == oveccw180
3125        );
3126        assert!(
3127            ovec.rotated_z(Airships::angle_between_vectors_cw(vec4, refvec))
3128                .map(|x| x.round() as i32)
3129                == oveccw270
3130        );
3131
3132        assert!(
3133            ovec.rotated_z(Airships::angle_between_vectors_ccw(vec1, refvec))
3134                .map(|x| x.round() as i32)
3135                == ovecccw0
3136        );
3137        assert!(
3138            ovec.rotated_z(Airships::angle_between_vectors_ccw(vec2, refvec))
3139                .map(|x| x.round() as i32)
3140                == ovecccw90
3141        );
3142        assert!(
3143            ovec.rotated_z(Airships::angle_between_vectors_ccw(vec3, refvec))
3144                .map(|x| x.round() as i32)
3145                == ovecccw180
3146        );
3147        assert!(
3148            ovec.rotated_z(Airships::angle_between_vectors_ccw(vec4, refvec))
3149                .map(|x| x.round() as i32)
3150                == ovecccw270
3151        );
3152    }
3153
3154    #[test]
3155    fn airship_vec_test() {
3156        {
3157            let dock_pos = Vec3::new(10.0f32, 10.0, 0.0);
3158            let airship_dock_center = Vec2::new(0.0, 0.0);
3159            let mut left_tested = false;
3160            let mut right_tested = false;
3161            {
3162                for _ in 0..1000 {
3163                    let (airship_pos, airship_dir) =
3164                        Airships::airship_vec_for_docking_pos(dock_pos, airship_dock_center, None);
3165                    if airship_pos.x > 23.0 {
3166                        assert_relative_eq!(
3167                            airship_pos,
3168                            Vec3 {
3169                                x: 23.435028,
3170                                y: 22.020815,
3171                                z: -3.0
3172                            },
3173                            epsilon = 0.00001
3174                        );
3175                        assert_relative_eq!(
3176                            airship_dir.to_vec(),
3177                            Vec3 {
3178                                x: -0.70710677,
3179                                y: 0.70710677,
3180                                z: 0.0
3181                            },
3182                            epsilon = 0.00001
3183                        );
3184                        left_tested = true;
3185                    } else {
3186                        assert_relative_eq!(
3187                            airship_pos,
3188                            Vec3 {
3189                                x: 22.020815,
3190                                y: 23.435028,
3191                                z: -3.0
3192                            },
3193                            epsilon = 0.00001
3194                        );
3195                        assert_relative_eq!(
3196                            airship_dir.to_vec(),
3197                            Vec3 {
3198                                x: 0.70710677,
3199                                y: -0.70710677,
3200                                z: 0.0
3201                            },
3202                            epsilon = 0.00001
3203                        );
3204                        right_tested = true;
3205                    }
3206                    if left_tested && right_tested {
3207                        break;
3208                    }
3209                }
3210            }
3211            {
3212                let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
3213                    dock_pos,
3214                    airship_dock_center,
3215                    Some(AirshipDockingSide::Port),
3216                );
3217                assert_relative_eq!(
3218                    airship_pos,
3219                    Vec3 {
3220                        x: 23.435028,
3221                        y: 22.020815,
3222                        z: -3.0
3223                    },
3224                    epsilon = 0.00001
3225                );
3226                assert_relative_eq!(
3227                    airship_dir.to_vec(),
3228                    Vec3 {
3229                        x: -0.70710677,
3230                        y: 0.70710677,
3231                        z: 0.0
3232                    },
3233                    epsilon = 0.00001
3234                );
3235            }
3236            {
3237                let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
3238                    dock_pos,
3239                    airship_dock_center,
3240                    Some(AirshipDockingSide::Starboard),
3241                );
3242                assert_relative_eq!(
3243                    airship_pos,
3244                    Vec3 {
3245                        x: 22.020815,
3246                        y: 23.435028,
3247                        z: -3.0
3248                    },
3249                    epsilon = 0.00001
3250                );
3251                assert_relative_eq!(
3252                    airship_dir.to_vec(),
3253                    Vec3 {
3254                        x: 0.70710677,
3255                        y: -0.70710677,
3256                        z: 0.0
3257                    },
3258                    epsilon = 0.00001
3259                );
3260            }
3261        }
3262        {
3263            let dock_pos = Vec3::new(28874.0, 18561.0, 0.0);
3264            let airship_dock_center = Vec2::new(28911.0, 18561.0);
3265            {
3266                let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
3267                    dock_pos,
3268                    airship_dock_center,
3269                    Some(AirshipDockingSide::Port),
3270                );
3271                assert_relative_eq!(
3272                    airship_pos,
3273                    Vec3 {
3274                        x: 28856.0,
3275                        y: 18562.0,
3276                        z: -3.0
3277                    },
3278                    epsilon = 0.00001
3279                );
3280                assert_relative_eq!(
3281                    airship_dir.to_vec(),
3282                    Vec3 {
3283                        x: 4.371139e-8,
3284                        y: -1.0,
3285                        z: 0.0
3286                    },
3287                    epsilon = 0.00001
3288                );
3289            }
3290            {
3291                let (airship_pos, airship_dir) = Airships::airship_vec_for_docking_pos(
3292                    dock_pos,
3293                    airship_dock_center,
3294                    Some(AirshipDockingSide::Starboard),
3295                );
3296                assert_relative_eq!(
3297                    airship_pos,
3298                    Vec3 {
3299                        x: 28856.0,
3300                        y: 18560.0,
3301                        z: -3.0
3302                    },
3303                    epsilon = 0.00001
3304                );
3305                assert_relative_eq!(
3306                    airship_dir.to_vec(),
3307                    Vec3 {
3308                        x: -1.1924881e-8,
3309                        y: 1.0,
3310                        z: 0.0
3311                    },
3312                    epsilon = 0.00001
3313                );
3314            }
3315        }
3316    }
3317
3318    #[test]
3319    fn angle_score_test() {
3320        let rt_angles = [
3321            0.0,
3322            std::f32::consts::FRAC_PI_2,
3323            std::f32::consts::PI,
3324            std::f32::consts::FRAC_PI_2 * 3.0,
3325        ];
3326        let con_angles = [
3327            0.0,
3328            std::f32::consts::FRAC_PI_2,
3329            std::f32::consts::PI,
3330            std::f32::consts::FRAC_PI_2 * 3.0,
3331        ];
3332        let scores = [
3333            [0.0, 2.5, 5.0, 2.5],
3334            [2.5, 0.0, 2.5, 5.0],
3335            [5.0, 2.5, 0.0, 2.5],
3336            [2.5, 5.0, 2.5, 0.0],
3337        ];
3338        let score_fn2 = |a1: f32, a2: f32| {
3339            let optimal_angle = (a1 + std::f32::consts::PI).rem_euclid(std::f32::consts::TAU);
3340            let angle_diff = (optimal_angle - a2)
3341                .abs()
3342                .min(std::f32::consts::TAU - (optimal_angle - a2).abs());
3343            (1.0 - (angle_diff / std::f32::consts::PI)) * 5.0
3344        };
3345        let mut i = 0;
3346        let mut j = 0;
3347        rt_angles.iter().for_each(|rt_angle| {
3348            j = 0;
3349            con_angles.iter().for_each(|con_angle| {
3350                let score = score_fn2(*con_angle, *rt_angle);
3351                assert_relative_eq!(score, scores[i][j], epsilon = 0.00001);
3352                j += 1;
3353            });
3354            i += 1;
3355        });
3356    }
3357
3358    #[test]
3359    fn best_eulerian_circuit_test() {
3360        let node_connections: DHashMap<usize, DockNode> = DHashMap::from_iter([
3361            (0, DockNode {
3362                node_id: 0,
3363                on_hull: false,
3364                connected: Vec::from_iter([23, 29, 26, 14, 19, 4]),
3365            }),
3366            (28, DockNode {
3367                node_id: 28,
3368                on_hull: false,
3369                connected: Vec::from_iter([23, 15, 25, 20, 21, 22]),
3370            }),
3371            (25, DockNode {
3372                node_id: 25,
3373                on_hull: false,
3374                connected: Vec::from_iter([23, 11, 28, 21]),
3375            }),
3376            (22, DockNode {
3377                node_id: 22,
3378                on_hull: false,
3379                connected: Vec::from_iter([23, 28, 27, 9, 3, 15]),
3380            }),
3381            (19, DockNode {
3382                node_id: 19,
3383                on_hull: false,
3384                connected: Vec::from_iter([0, 6, 29, 18, 2, 4]),
3385            }),
3386            (16, DockNode {
3387                node_id: 16,
3388                on_hull: false,
3389                connected: Vec::from_iter([10, 12, 20, 21]),
3390            }),
3391            (13, DockNode {
3392                node_id: 13,
3393                on_hull: true,
3394                connected: Vec::from_iter([7, 26, 9, 27, 3, 18]),
3395            }),
3396            (10, DockNode {
3397                node_id: 10,
3398                on_hull: false,
3399                connected: Vec::from_iter([24, 29, 11, 2, 16, 21]),
3400            }),
3401            (7, DockNode {
3402                node_id: 7,
3403                on_hull: true,
3404                connected: Vec::from_iter([26, 1, 13, 11]),
3405            }),
3406            (4, DockNode {
3407                node_id: 4,
3408                on_hull: false,
3409                connected: Vec::from_iter([0, 6, 14, 19]),
3410            }),
3411            (1, DockNode {
3412                node_id: 1,
3413                on_hull: true,
3414                connected: Vec::from_iter([7, 26, 8, 17]),
3415            }),
3416            (29, DockNode {
3417                node_id: 29,
3418                on_hull: false,
3419                connected: Vec::from_iter([0, 10, 24, 23, 19, 2]),
3420            }),
3421            (26, DockNode {
3422                node_id: 26,
3423                on_hull: false,
3424                connected: Vec::from_iter([0, 23, 14, 1, 27, 5, 7, 13]),
3425            }),
3426            (23, DockNode {
3427                node_id: 23,
3428                on_hull: false,
3429                connected: Vec::from_iter([0, 29, 25, 22, 28, 24, 11, 26]),
3430            }),
3431            (20, DockNode {
3432                node_id: 20,
3433                on_hull: true,
3434                connected: Vec::from_iter([18, 28, 12, 15, 16, 21]),
3435            }),
3436            (17, DockNode {
3437                node_id: 17,
3438                on_hull: false,
3439                connected: Vec::from_iter([5, 6, 8, 1]),
3440            }),
3441            (14, DockNode {
3442                node_id: 14,
3443                on_hull: false,
3444                connected: Vec::from_iter([0, 5, 26, 4]),
3445            }),
3446            (11, DockNode {
3447                node_id: 11,
3448                on_hull: false,
3449                connected: Vec::from_iter([10, 24, 23, 25, 21, 7]),
3450            }),
3451            (8, DockNode {
3452                node_id: 8,
3453                on_hull: true,
3454                connected: Vec::from_iter([18, 6, 1, 17]),
3455            }),
3456            (5, DockNode {
3457                node_id: 5,
3458                on_hull: false,
3459                connected: Vec::from_iter([6, 26, 14, 17]),
3460            }),
3461            (2, DockNode {
3462                node_id: 2,
3463                on_hull: false,
3464                connected: Vec::from_iter([10, 29, 12, 19]),
3465            }),
3466            (27, DockNode {
3467                node_id: 27,
3468                on_hull: false,
3469                connected: Vec::from_iter([26, 9, 13, 22]),
3470            }),
3471            (24, DockNode {
3472                node_id: 24,
3473                on_hull: false,
3474                connected: Vec::from_iter([10, 29, 11, 23]),
3475            }),
3476            (21, DockNode {
3477                node_id: 21,
3478                on_hull: false,
3479                connected: Vec::from_iter([10, 11, 25, 28, 20, 16]),
3480            }),
3481            (18, DockNode {
3482                node_id: 18,
3483                on_hull: true,
3484                connected: Vec::from_iter([6, 12, 8, 19, 20, 13]),
3485            }),
3486            (15, DockNode {
3487                node_id: 15,
3488                on_hull: true,
3489                connected: Vec::from_iter([28, 20, 3, 22]),
3490            }),
3491            (12, DockNode {
3492                node_id: 12,
3493                on_hull: false,
3494                connected: Vec::from_iter([18, 2, 16, 20]),
3495            }),
3496            (9, DockNode {
3497                node_id: 9,
3498                on_hull: false,
3499                connected: Vec::from_iter([13, 27, 3, 22]),
3500            }),
3501            (6, DockNode {
3502                node_id: 6,
3503                on_hull: false,
3504                connected: Vec::from_iter([4, 8, 5, 18, 19, 17]),
3505            }),
3506            (3, DockNode {
3507                node_id: 3,
3508                on_hull: true,
3509                connected: Vec::from_iter([13, 9, 15, 22]),
3510            }),
3511        ]);
3512
3513        let (best_segments, circuit, max_seg_len, min_spread, iteration) =
3514            find_best_eulerian_circuit(&node_connections)
3515                .expect("a circuit should have been found");
3516        assert_eq!(max_seg_len, 4);
3517        assert_relative_eq!(min_spread, 1.0606601, epsilon = 0.0000001);
3518        assert_eq!(iteration, 6);
3519        let expected_segments = vec![
3520            vec![26, 0, 23, 29, 0, 14, 5, 6, 4, 0, 19, 6, 8, 18, 6, 17, 5, 26],
3521            vec![
3522                26, 23, 25, 11, 10, 24, 29, 10, 2, 29, 19, 18, 12, 2, 19, 4, 14, 26,
3523            ],
3524            vec![
3525                26, 1, 8, 17, 1, 7, 11, 24, 23, 22, 28, 23, 11, 21, 10, 16, 12, 20, 18, 13, 26,
3526            ],
3527            vec![
3528                26, 27, 9, 13, 27, 22, 9, 3, 15, 28, 25, 21, 28, 20, 16, 21, 20, 15, 22, 3, 13, 7,
3529                26,
3530            ],
3531        ];
3532        assert_eq!(best_segments, expected_segments);
3533        let expected_circuit = vec![
3534            13, 7, 26, 0, 23, 29, 0, 14, 5, 6, 4, 0, 19, 6, 8, 18, 6, 17, 5, 26, 23, 25, 11, 10,
3535            24, 29, 10, 2, 29, 19, 18, 12, 2, 19, 4, 14, 26, 1, 8, 17, 1, 7, 11, 24, 23, 22, 28,
3536            23, 11, 21, 10, 16, 12, 20, 18, 13, 26, 27, 9, 13, 27, 22, 9, 3, 15, 28, 25, 21, 28,
3537            20, 16, 21, 20, 15, 22, 3, 13,
3538        ];
3539        assert_eq!(circuit, expected_circuit);
3540    }
3541
3542    fn large_map_docking_locations() -> Vec<Vec2<f32>> {
3543        [
3544            [384, 113],
3545            [713, 67],
3546            [1351, 17],
3547            [3146, 64],
3548            [720, 248],
3549            [775, 204],
3550            [829, 166],
3551            [1391, 161],
3552            [1812, 156],
3553            [3022, 204],
3554            [3094, 193],
3555            [781, 529],
3556            [860, 289],
3557            [889, 371],
3558            [892, 488],
3559            [975, 408],
3560            [1039, 509],
3561            [1050, 449],
3562            [1167, 379],
3563            [1359, 457],
3564            [1425, 382],
3565            [1468, 424],
3566            [1493, 363],
3567            [1752, 322],
3568            [1814, 452],
3569            [2139, 469],
3570            [2179, 343],
3571            [2283, 333],
3572            [2428, 299],
3573            [2499, 504],
3574            [2567, 498],
3575            [3110, 363],
3576            [3126, 503],
3577            [3248, 330],
3578            [3343, 491],
3579            [96, 837],
3580            [98, 752],
3581            [149, 884],
3582            [258, 679],
3583            [349, 873],
3584            [350, 676],
3585            [431, 983],
3586            [541, 842],
3587            [686, 640],
3588            [923, 728],
3589            [941, 537],
3590            [951, 654],
3591            [991, 575],
3592            [999, 955],
3593            [1164, 767],
3594            [1238, 669],
3595            [1250, 923],
3596            [1266, 808],
3597            [1343, 878],
3598            [1535, 711],
3599            [1633, 773],
3600            [1684, 705],
3601            [1690, 833],
3602            [1694, 982],
3603            [1742, 774],
3604            [1781, 821],
3605            [1833, 558],
3606            [1854, 623],
3607            [2169, 815],
3608            [2189, 966],
3609            [2232, 691],
3610            [2243, 778],
3611            [2266, 934],
3612            [2354, 742],
3613            [2423, 753],
3614            [2423, 999],
3615            [2438, 637],
3616            [2491, 758],
3617            [2497, 636],
3618            [2507, 855],
3619            [3066, 909],
3620            [3088, 568],
3621            [3124, 687],
3622            [3198, 681],
3623            [3241, 901],
3624            [3260, 603],
3625            [3276, 704],
3626            [3314, 652],
3627            [3329, 744],
3628            [3374, 888],
3629            [3513, 999],
3630            [3609, 708],
3631            [3864, 934],
3632            [3959, 933],
3633            [3959, 1000],
3634            [167, 1135],
3635            [229, 1072],
3636            [333, 1198],
3637            [349, 1481],
3638            [399, 1165],
3639            [473, 1350],
3640            [510, 1032],
3641            [523, 1481],
3642            [535, 1294],
3643            [552, 1080],
3644            [587, 1388],
3645            [789, 1103],
3646            [816, 1284],
3647            [886, 1183],
3648            [905, 1338],
3649            [1022, 1158],
3650            [1161, 1359],
3651            [1187, 1457],
3652            [1197, 1289],
3653            [1231, 1067],
3654            [1311, 1352],
3655            [1331, 1076],
3656            [1340, 1504],
3657            [1367, 1415],
3658            [1414, 1384],
3659            [1424, 1091],
3660            [1447, 1018],
3661            [1642, 1383],
3662            [1733, 1237],
3663            [1740, 1066],
3664            [1751, 1128],
3665            [1797, 1171],
3666            [1802, 1060],
3667            [1960, 1495],
3668            [1977, 1081],
3669            [2305, 1064],
3670            [2372, 1117],
3671            [2411, 1480],
3672            [2688, 1320],
3673            [2745, 1359],
3674            [2819, 1162],
3675            [2860, 1268],
3676            [2868, 1088],
3677            [2934, 1481],
3678            [2991, 1388],
3679            [3078, 1447],
3680            [3166, 1267],
3681            [3222, 1374],
3682            [3234, 1234],
3683            [3244, 1057],
3684            [3256, 1437],
3685            [3302, 1274],
3686            [3354, 1165],
3687            [3389, 1340],
3688            [3416, 1406],
3689            [3451, 1122],
3690            [3594, 1205],
3691            [3681, 1435],
3692            [3838, 1265],
3693            [3892, 1181],
3694            [3911, 1243],
3695            [200, 1663],
3696            [328, 1843],
3697            [363, 1630],
3698            [445, 1640],
3699            [505, 1756],
3700            [537, 1594],
3701            [560, 1779],
3702            [654, 1594],
3703            [713, 1559],
3704            [769, 1912],
3705            [970, 1782],
3706            [988, 1705],
3707            [1361, 1595],
3708            [1370, 1949],
3709            [1480, 1695],
3710            [1695, 1531],
3711            [1881, 1703],
3712            [2315, 1979],
3713            [2411, 1536],
3714            [2508, 1990],
3715            [2679, 1737],
3716            [2731, 1704],
3717            [2734, 1956],
3718            [2739, 1606],
3719            [2770, 1781],
3720            [2778, 1879],
3721            [2781, 1664],
3722            [2841, 1716],
3723            [2858, 1647],
3724            [2858, 1826],
3725            [2898, 1715],
3726            [2935, 1554],
3727            [3051, 1837],
3728            [3060, 1965],
3729            [3185, 1918],
3730            [3251, 1869],
3731            [3442, 1856],
3732            [3447, 1543],
3733            [3534, 1951],
3734            [3590, 1878],
3735            [3611, 1960],
3736            [3635, 1584],
3737            [3649, 1781],
3738            [3656, 1850],
3739            [3668, 1912],
3740            [3750, 1906],
3741            [3762, 1826],
3742            [3831, 1971],
3743            [3841, 1876],
3744            [3888, 1806],
3745            [3960, 1818],
3746            [177, 2260],
3747            [239, 2026],
3748            [358, 2364],
3749            [471, 2327],
3750            [528, 2100],
3751            [536, 2198],
3752            [588, 2244],
3753            [648, 2180],
3754            [665, 2038],
3755            [693, 2366],
3756            [852, 2410],
3757            [898, 2293],
3758            [969, 2205],
3759            [1095, 2322],
3760            [1198, 2217],
3761            [1267, 2284],
3762            [1278, 2220],
3763            [1339, 2114],
3764            [1419, 2203],
3765            [1470, 2049],
3766            [1487, 2108],
3767            [1959, 2257],
3768            [2087, 2061],
3769            [2226, 2048],
3770            [2231, 2319],
3771            [2385, 2251],
3772            [2417, 2039],
3773            [2598, 2035],
3774            [2686, 2071],
3775            [2715, 2204],
3776            [2778, 2188],
3777            [2900, 2128],
3778            [2910, 2007],
3779            [2988, 2087],
3780            [3002, 2435],
3781            [3082, 2433],
3782            [3115, 2006],
3783            [3167, 2143],
3784            [3170, 2361],
3785            [3360, 2433],
3786            [3472, 2370],
3787            [3514, 2022],
3788            [3599, 2045],
3789            [3662, 2365],
3790            [3676, 2172],
3791            [3838, 2208],
3792            [3921, 2060],
3793            [87, 2628],
3794            [239, 2604],
3795            [270, 2668],
3796            [327, 2726],
3797            [371, 2781],
3798            [419, 2583],
3799            [546, 2574],
3800            [620, 2776],
3801            [979, 2850],
3802            [1052, 2762],
3803            [1095, 2825],
3804            [1486, 2601],
3805            [1587, 2701],
3806            [1620, 2599],
3807            [1633, 2492],
3808            [1948, 2809],
3809            [2156, 2852],
3810            [2464, 2605],
3811            [2544, 2777],
3812            [2645, 2605],
3813            [2743, 2466],
3814            [2836, 2785],
3815            [2981, 2635],
3816            [3029, 2699],
3817            [3162, 2733],
3818            [3389, 2769],
3819            [3484, 2776],
3820            [3561, 2795],
3821            [3631, 2549],
3822            [3669, 2474],
3823            [3732, 2625],
3824            [33, 3129],
3825            [97, 3152],
3826            [191, 3289],
3827            [449, 2938],
3828            [450, 3000],
3829            [590, 3142],
3830            [654, 3065],
3831            [744, 3093],
3832            [870, 3042],
3833            [875, 2904],
3834            [921, 3103],
3835            [1018, 3034],
3836            [1040, 3135],
3837            [1079, 3238],
3838            [1122, 3316],
3839            [1136, 2996],
3840            [1237, 3366],
3841            [1294, 3127],
3842            [1360, 3297],
3843            [1366, 3043],
3844            [1368, 2985],
3845            [1381, 3128],
3846            [1464, 3089],
3847            [1514, 2965],
3848            [1529, 3046],
3849            [1901, 3052],
3850            [1954, 3272],
3851            [2117, 3121],
3852            [2182, 3381],
3853            [2225, 3212],
3854            [2241, 3142],
3855            [2250, 2949],
3856            [2340, 3333],
3857            [2395, 3195],
3858            [2496, 3383],
3859            [2521, 3162],
3860            [2604, 2959],
3861            [2635, 3287],
3862            [2644, 3021],
3863            [2657, 3140],
3864            [2716, 3367],
3865            [2726, 3184],
3866            [2734, 3264],
3867            [2799, 3300],
3868            [2866, 3361],
3869            [2907, 2893],
3870            [2938, 3362],
3871            [3058, 2982],
3872            [3187, 3076],
3873            [3357, 3200],
3874            [3467, 3300],
3875            [3511, 3359],
3876            [3522, 3105],
3877            [3538, 2997],
3878            [3791, 3348],
3879            [3866, 3261],
3880            [3947, 3223],
3881            [33, 3807],
3882            [109, 3828],
3883            [390, 3472],
3884            [468, 3510],
3885            [534, 3508],
3886            [563, 3659],
3887            [665, 3830],
3888            [668, 3732],
3889            [742, 3770],
3890            [896, 3818],
3891            [934, 3475],
3892            [1255, 3871],
3893            [1309, 3477],
3894            [1318, 3812],
3895            [1425, 3417],
3896            [1443, 3950],
3897            [1479, 3638],
3898            [1492, 3546],
3899            [1498, 3940],
3900            [1533, 3593],
3901            [1584, 3448],
3902            [1605, 3691],
3903            [1632, 3831],
3904            [1798, 3826],
3905            [1992, 3612],
3906            [2101, 3713],
3907            [2157, 3496],
3908            [2204, 3796],
3909            [2314, 3835],
3910            [2350, 3650],
3911            [2446, 3697],
3912            [2474, 3624],
3913            [2516, 3528],
3914            [2607, 3551],
3915            [2644, 3929],
3916            [2714, 3603],
3917            [2760, 3707],
3918            [2797, 3658],
3919            [2940, 3520],
3920            [2955, 3687],
3921            [2971, 3446],
3922            [3081, 3427],
3923            [3082, 3828],
3924            [3124, 3475],
3925            [3149, 3624],
3926            [3174, 3539],
3927            [3341, 3897],
3928            [3371, 3841],
3929            [3663, 3786],
3930            [3740, 3468],
3931            [3783, 3575],
3932            [3886, 3584],
3933            [3948, 3547],
3934        ]
3935        .iter()
3936        .map(|&[x, y]| Vec2::new(x as f32, y as f32))
3937        .collect()
3938    }
3939
3940    fn large_map_docking_points() -> Vec<Point> {
3941        large_map_docking_locations()
3942            .iter()
3943            .map(|&loc| Point {
3944                x: loc.x as f64,
3945                y: loc.y as f64,
3946            })
3947            .collect()
3948    }
3949
3950    #[test]
3951    fn large_map_graph_remove_edges_compare_test() {
3952        let all_dock_points1 = large_map_docking_points();
3953        let triangulation1 = triangulate(&all_dock_points1);
3954        let node_connections1 = triangulation1.node_connections();
3955
3956        let all_dock_points2 = large_map_docking_points();
3957        let triangulation2 = triangulate(&all_dock_points2);
3958        let node_connections2 = triangulation2.node_connections();
3959
3960        assert_eq!(
3961            all_dock_points1, all_dock_points2,
3962            "Dock points should be the same."
3963        );
3964        assert_eq!(
3965            node_connections1, node_connections2,
3966            "Node connections should be equal before removing edges."
3967        );
3968
3969        let max_distance_squared = 1000.0f64.powi(2);
3970
3971        let mut edges_to_remove1 = Vec::new();
3972        node_connections1.iter().for_each(|(node_id, node)| {
3973            for &connected_node_id in &node.connected {
3974                let pt1 = &all_dock_points1[*node_id];
3975                let pt2 = &all_dock_points1[connected_node_id];
3976                let v1 = Vec2 { x: pt1.x, y: pt1.y };
3977                let v2 = Vec2 { x: pt2.x, y: pt2.y };
3978                // Remove the edge if the distance is greater than 1000.0
3979                if v1.distance_squared(v2) > max_distance_squared {
3980                    edges_to_remove1.push((*node_id, connected_node_id));
3981                }
3982            }
3983        });
3984        let edges_to_remove1b = edges_to_remove1.clone();
3985
3986        let mut edges_to_remove1c = DHashSet::default();
3987        edges_to_remove1b
3988            .iter()
3989            .for_each(|&(node_id, connected_node_id)| {
3990                edges_to_remove1c.insert(if node_id < connected_node_id {
3991                    (node_id, connected_node_id)
3992                } else {
3993                    (connected_node_id, node_id)
3994                });
3995            });
3996
3997        let mut edges_to_remove2 = DHashSet::default();
3998        let all_edges2 = triangulation2.all_edges();
3999        for edge in all_edges2.iter() {
4000            let pt1 = &all_dock_points2[edge.0];
4001            let pt2 = &all_dock_points2[edge.1];
4002            let v1 = Vec2 { x: pt1.x, y: pt1.y };
4003            let v2 = Vec2 { x: pt2.x, y: pt2.y };
4004            // Remove the edge if the distance between the points is greater than
4005            // max_leg_length
4006            if v1.distance_squared(v2) > max_distance_squared {
4007                edges_to_remove2.insert(*edge);
4008            }
4009        }
4010
4011        assert_eq!(
4012            edges_to_remove1c, edges_to_remove2,
4013            "Edges to remove should be the same in hashset form."
4014        );
4015
4016        let mut mutable_node_connections1 = node_connections1.clone();
4017        for (node_id, connected_node_id) in edges_to_remove1 {
4018            remove_edge((node_id, connected_node_id), &mut mutable_node_connections1);
4019        }
4020
4021        let mut mutable_node_connections1b = node_connections1.clone();
4022        for edge in edges_to_remove1c {
4023            remove_edge(edge, &mut mutable_node_connections1b);
4024        }
4025
4026        assert_eq!(
4027            mutable_node_connections1, mutable_node_connections1b,
4028            "Node connections1 should be the same for either Vec or HashSet remove edges."
4029        );
4030
4031        let mut mutable_node_connections2 = node_connections2.clone();
4032        for edge in edges_to_remove2 {
4033            remove_edge(edge, &mut mutable_node_connections2);
4034        }
4035
4036        assert_eq!(
4037            mutable_node_connections1, mutable_node_connections2,
4038            "Node connections should be equal after removing edges."
4039        );
4040
4041        assert_eq!(
4042            mutable_node_connections1, mutable_node_connections2,
4043            "Node connections should be equal after removing edges."
4044        );
4045    }
4046
4047    #[test]
4048    fn docking_position_from_platform_test() {
4049        let airships = airships_from_test_data();
4050        let platforms = [
4051            AirshipDockPlatform::NorthPlatform,
4052            AirshipDockPlatform::EastPlatform,
4053            AirshipDockPlatform::SouthPlatform,
4054            AirshipDockPlatform::WestPlatform,
4055        ];
4056        let expected = [
4057            Vec3 {
4058                x: 26688.0,
4059                y: 4777.0,
4060                z: 213.0,
4061            },
4062            Vec3 {
4063                x: 26707.0,
4064                y: 4758.0,
4065                z: 213.0,
4066            },
4067            Vec3 {
4068                x: 26688.0,
4069                y: 4739.0,
4070                z: 213.0,
4071            },
4072            Vec3 {
4073                x: 26669.0,
4074                y: 4758.0,
4075                z: 213.0,
4076            },
4077            Vec3 {
4078                x: 24574.0,
4079                y: 26127.0,
4080                z: 214.0,
4081            },
4082            Vec3 {
4083                x: 24593.0,
4084                y: 26108.0,
4085                z: 214.0,
4086            },
4087            Vec3 {
4088                x: 24574.0,
4089                y: 26089.0,
4090                z: 214.0,
4091            },
4092            Vec3 {
4093                x: 24555.0,
4094                y: 26108.0,
4095                z: 214.0,
4096            },
4097            Vec3 {
4098                x: 24253.0,
4099                y: 20734.0,
4100                z: 515.0,
4101            },
4102            Vec3 {
4103                x: 24272.0,
4104                y: 20715.0,
4105                z: 515.0,
4106            },
4107            Vec3 {
4108                x: 24253.0,
4109                y: 20696.0,
4110                z: 515.0,
4111            },
4112            Vec3 {
4113                x: 24234.0,
4114                y: 20715.0,
4115                z: 515.0,
4116            },
4117            Vec3 {
4118                x: 20809.0,
4119                y: 6574.0,
4120                z: 216.0,
4121            },
4122            Vec3 {
4123                x: 20828.0,
4124                y: 6555.0,
4125                z: 216.0,
4126            },
4127            Vec3 {
4128                x: 20809.0,
4129                y: 6536.0,
4130                z: 216.0,
4131            },
4132            Vec3 {
4133                x: 20790.0,
4134                y: 6555.0,
4135                z: 216.0,
4136            },
4137            Vec3 {
4138                x: 16492.0,
4139                y: 1080.0,
4140                z: 211.0,
4141            },
4142            Vec3 {
4143                x: 16511.0,
4144                y: 1061.0,
4145                z: 211.0,
4146            },
4147            Vec3 {
4148                x: 16492.0,
4149                y: 1042.0,
4150                z: 211.0,
4151            },
4152            Vec3 {
4153                x: 16473.0,
4154                y: 1061.0,
4155                z: 211.0,
4156            },
4157            Vec3 {
4158                x: 18452.0,
4159                y: 11255.0,
4160                z: 421.0,
4161            },
4162            Vec3 {
4163                x: 18471.0,
4164                y: 11236.0,
4165                z: 421.0,
4166            },
4167            Vec3 {
4168                x: 18452.0,
4169                y: 11217.0,
4170                z: 421.0,
4171            },
4172            Vec3 {
4173                x: 18433.0,
4174                y: 11236.0,
4175                z: 421.0,
4176            },
4177            Vec3 {
4178                x: 21870.0,
4179                y: 8549.0,
4180                z: 216.0,
4181            },
4182            Vec3 {
4183                x: 21889.0,
4184                y: 8530.0,
4185                z: 216.0,
4186            },
4187            Vec3 {
4188                x: 21870.0,
4189                y: 8511.0,
4190                z: 216.0,
4191            },
4192            Vec3 {
4193                x: 21851.0,
4194                y: 8530.0,
4195                z: 216.0,
4196            },
4197            Vec3 {
4198                x: 22577.0,
4199                y: 15225.0,
4200                z: 277.0,
4201            },
4202            Vec3 {
4203                x: 22605.0,
4204                y: 15197.0,
4205                z: 277.0,
4206            },
4207            Vec3 {
4208                x: 22577.0,
4209                y: 15169.0,
4210                z: 277.0,
4211            },
4212            Vec3 {
4213                x: 22549.0,
4214                y: 15197.0,
4215                z: 277.0,
4216            },
4217            Vec3 {
4218                x: 5477.0,
4219                y: 15244.0,
4220                z: 1675.0,
4221            },
4222            Vec3 {
4223                x: 5514.0,
4224                y: 15207.0,
4225                z: 1675.0,
4226            },
4227            Vec3 {
4228                x: 5477.0,
4229                y: 15170.0,
4230                z: 1675.0,
4231            },
4232            Vec3 {
4233                x: 5440.0,
4234                y: 15207.0,
4235                z: 1675.0,
4236            },
4237            Vec3 {
4238                x: 23884.0,
4239                y: 24321.0,
4240                z: 214.0,
4241            },
4242            Vec3 {
4243                x: 23903.0,
4244                y: 24302.0,
4245                z: 214.0,
4246            },
4247            Vec3 {
4248                x: 23884.0,
4249                y: 24283.0,
4250                z: 214.0,
4251            },
4252            Vec3 {
4253                x: 23865.0,
4254                y: 24302.0,
4255                z: 214.0,
4256            },
4257            Vec3 {
4258                x: 13373.0,
4259                y: 2332.0,
4260                z: 259.0,
4261            },
4262            Vec3 {
4263                x: 13392.0,
4264                y: 2313.0,
4265                z: 259.0,
4266            },
4267            Vec3 {
4268                x: 13373.0,
4269                y: 2294.0,
4270                z: 259.0,
4271            },
4272            Vec3 {
4273                x: 13354.0,
4274                y: 2313.0,
4275                z: 259.0,
4276            },
4277            Vec3 {
4278                x: 20141.0,
4279                y: 31880.0,
4280                z: 215.0,
4281            },
4282            Vec3 {
4283                x: 20160.0,
4284                y: 31861.0,
4285                z: 215.0,
4286            },
4287            Vec3 {
4288                x: 20141.0,
4289                y: 31842.0,
4290                z: 215.0,
4291            },
4292            Vec3 {
4293                x: 20122.0,
4294                y: 31861.0,
4295                z: 215.0,
4296            },
4297            Vec3 {
4298                x: 29713.0,
4299                y: 24552.0,
4300                z: 214.0,
4301            },
4302            Vec3 {
4303                x: 29732.0,
4304                y: 24533.0,
4305                z: 214.0,
4306            },
4307            Vec3 {
4308                x: 29713.0,
4309                y: 24514.0,
4310                z: 214.0,
4311            },
4312            Vec3 {
4313                x: 29694.0,
4314                y: 24533.0,
4315                z: 214.0,
4316            },
4317            Vec3 {
4318                x: 18992.0,
4319                y: 17139.0,
4320                z: 435.0,
4321            },
4322            Vec3 {
4323                x: 19011.0,
4324                y: 17120.0,
4325                z: 435.0,
4326            },
4327            Vec3 {
4328                x: 18992.0,
4329                y: 17101.0,
4330                z: 435.0,
4331            },
4332            Vec3 {
4333                x: 18973.0,
4334                y: 17120.0,
4335                z: 435.0,
4336            },
4337            Vec3 {
4338                x: 7705.0,
4339                y: 12570.0,
4340                z: 1911.0,
4341            },
4342            Vec3 {
4343                x: 7742.0,
4344                y: 12533.0,
4345                z: 1911.0,
4346            },
4347            Vec3 {
4348                x: 7705.0,
4349                y: 12496.0,
4350                z: 1911.0,
4351            },
4352            Vec3 {
4353                x: 7668.0,
4354                y: 12533.0,
4355                z: 1911.0,
4356            },
4357            Vec3 {
4358                x: 30365.0,
4359                y: 13015.0,
4360                z: 244.0,
4361            },
4362            Vec3 {
4363                x: 30393.0,
4364                y: 12987.0,
4365                z: 244.0,
4366            },
4367            Vec3 {
4368                x: 30365.0,
4369                y: 12959.0,
4370                z: 244.0,
4371            },
4372            Vec3 {
4373                x: 30337.0,
4374                y: 12987.0,
4375                z: 244.0,
4376            },
4377            Vec3 {
4378                x: 10142.0,
4379                y: 19218.0,
4380                z: 1141.0,
4381            },
4382            Vec3 {
4383                x: 10170.0,
4384                y: 19190.0,
4385                z: 1141.0,
4386            },
4387            Vec3 {
4388                x: 10142.0,
4389                y: 19162.0,
4390                z: 1141.0,
4391            },
4392            Vec3 {
4393                x: 10114.0,
4394                y: 19190.0,
4395                z: 1141.0,
4396            },
4397            Vec3 {
4398                x: 13716.0,
4399                y: 17542.0,
4400                z: 1420.0,
4401            },
4402            Vec3 {
4403                x: 13753.0,
4404                y: 17505.0,
4405                z: 1420.0,
4406            },
4407            Vec3 {
4408                x: 13716.0,
4409                y: 17468.0,
4410                z: 1420.0,
4411            },
4412            Vec3 {
4413                x: 13679.0,
4414                y: 17505.0,
4415                z: 1420.0,
4416            },
4417            Vec3 {
4418                x: 9383.0,
4419                y: 17173.0,
4420                z: 909.0,
4421            },
4422            Vec3 {
4423                x: 9411.0,
4424                y: 17145.0,
4425                z: 909.0,
4426            },
4427            Vec3 {
4428                x: 9383.0,
4429                y: 17117.0,
4430                z: 909.0,
4431            },
4432            Vec3 {
4433                x: 9355.0,
4434                y: 17145.0,
4435                z: 909.0,
4436            },
4437            Vec3 {
4438                x: 24424.0,
4439                y: 7819.0,
4440                z: 329.0,
4441            },
4442            Vec3 {
4443                x: 24443.0,
4444                y: 7800.0,
4445                z: 329.0,
4446            },
4447            Vec3 {
4448                x: 24424.0,
4449                y: 7781.0,
4450                z: 329.0,
4451            },
4452            Vec3 {
4453                x: 24405.0,
4454                y: 7800.0,
4455                z: 329.0,
4456            },
4457            Vec3 {
4458                x: 7528.0,
4459                y: 28445.0,
4460                z: 218.0,
4461            },
4462            Vec3 {
4463                x: 7547.0,
4464                y: 28426.0,
4465                z: 218.0,
4466            },
4467            Vec3 {
4468                x: 7528.0,
4469                y: 28407.0,
4470                z: 218.0,
4471            },
4472            Vec3 {
4473                x: 7509.0,
4474                y: 28426.0,
4475                z: 218.0,
4476            },
4477            Vec3 {
4478                x: 9942.0,
4479                y: 30955.0,
4480                z: 185.0,
4481            },
4482            Vec3 {
4483                x: 9961.0,
4484                y: 30936.0,
4485                z: 185.0,
4486            },
4487            Vec3 {
4488                x: 9942.0,
4489                y: 30917.0,
4490                z: 185.0,
4491            },
4492            Vec3 {
4493                x: 9923.0,
4494                y: 30936.0,
4495                z: 185.0,
4496            },
4497            Vec3 {
4498                x: 27915.0,
4499                y: 18578.0,
4500                z: 498.0,
4501            },
4502            Vec3 {
4503                x: 27934.0,
4504                y: 18559.0,
4505                z: 498.0,
4506            },
4507            Vec3 {
4508                x: 27915.0,
4509                y: 18540.0,
4510                z: 498.0,
4511            },
4512            Vec3 {
4513                x: 27896.0,
4514                y: 18559.0,
4515                z: 498.0,
4516            },
4517            Vec3 {
4518                x: 3688.0,
4519                y: 29191.0,
4520                z: 198.0,
4521            },
4522            Vec3 {
4523                x: 3711.0,
4524                y: 29168.0,
4525                z: 198.0,
4526            },
4527            Vec3 {
4528                x: 3688.0,
4529                y: 29145.0,
4530                z: 198.0,
4531            },
4532            Vec3 {
4533                x: 3665.0,
4534                y: 29168.0,
4535                z: 198.0,
4536            },
4537            Vec3 {
4538                x: 15864.0,
4539                y: 15612.0,
4540                z: 419.0,
4541            },
4542            Vec3 {
4543                x: 15892.0,
4544                y: 15584.0,
4545                z: 419.0,
4546            },
4547            Vec3 {
4548                x: 15864.0,
4549                y: 15556.0,
4550                z: 419.0,
4551            },
4552            Vec3 {
4553                x: 15836.0,
4554                y: 15584.0,
4555                z: 419.0,
4556            },
4557            Vec3 {
4558                x: 9975.0,
4559                y: 24326.0,
4560                z: 755.0,
4561            },
4562            Vec3 {
4563                x: 10012.0,
4564                y: 24289.0,
4565                z: 755.0,
4566            },
4567            Vec3 {
4568                x: 9975.0,
4569                y: 24252.0,
4570                z: 755.0,
4571            },
4572            Vec3 {
4573                x: 9938.0,
4574                y: 24289.0,
4575                z: 755.0,
4576            },
4577            Vec3 {
4578                x: 479.0,
4579                y: 18316.0,
4580                z: 449.0,
4581            },
4582            Vec3 {
4583                x: 516.0,
4584                y: 18279.0,
4585                z: 449.0,
4586            },
4587            Vec3 {
4588                x: 479.0,
4589                y: 18242.0,
4590                z: 449.0,
4591            },
4592            Vec3 {
4593                x: 442.0,
4594                y: 18279.0,
4595                z: 449.0,
4596            },
4597            Vec3 {
4598                x: 26543.0,
4599                y: 17198.0,
4600                z: 362.0,
4601            },
4602            Vec3 {
4603                x: 26566.0,
4604                y: 17175.0,
4605                z: 362.0,
4606            },
4607            Vec3 {
4608                x: 26543.0,
4609                y: 17152.0,
4610                z: 362.0,
4611            },
4612            Vec3 {
4613                x: 26520.0,
4614                y: 17175.0,
4615                z: 362.0,
4616            },
4617        ];
4618
4619        for (i, dock_pos) in airships.airship_docks.iter().enumerate() {
4620            for platform in platforms {
4621                let docking_position = dock_pos.docking_position(platform);
4622                assert_eq!(docking_position, expected[i * 4 + platform as usize]);
4623            }
4624        }
4625    }
4626
4627    #[test]
4628    fn docking_transition_point_test() {
4629        let expected = [
4630            Vec3 {
4631                x: 26567.24,
4632                y: 4903.6567,
4633                z: 613.0,
4634            },
4635            Vec3 {
4636                x: 26725.146,
4637                y: 4948.012,
4638                z: 613.0,
4639            },
4640            Vec3 {
4641                x: 26825.607,
4642                y: 4668.8833,
4643                z: 613.0,
4644            },
4645            Vec3 {
4646                x: 26515.738,
4647                y: 4746.166,
4648                z: 613.0,
4649            },
4650            Vec3 {
4651                x: 26586.238,
4652                y: 4884.6543,
4653                z: 613.0,
4654            },
4655            Vec3 {
4656                x: 26744.012,
4657                y: 4929.0415,
4658                z: 613.0,
4659            },
4660            Vec3 {
4661                x: 26844.652,
4662                y: 4649.9404,
4663                z: 613.0,
4664            },
4665            Vec3 {
4666                x: 26534.713,
4667                y: 4727.306,
4668                z: 613.0,
4669            },
4670            Vec3 {
4671                x: 26567.326,
4672                y: 4865.7383,
4673                z: 613.0,
4674            },
4675            Vec3 {
4676                x: 26725.098,
4677                y: 4910.0225,
4678                z: 613.0,
4679            },
4680            Vec3 {
4681                x: 26826.025,
4682                y: 4631.4175,
4683                z: 613.0,
4684            },
4685            Vec3 {
4686                x: 26515.695,
4687                y: 4708.404,
4688                z: 613.0,
4689            },
4690            Vec3 {
4691                x: 26548.328,
4692                y: 4884.74,
4693                z: 613.0,
4694            },
4695            Vec3 {
4696                x: 26706.232,
4697                y: 4928.993,
4698                z: 613.0,
4699            },
4700            Vec3 {
4701                x: 26806.979,
4702                y: 4650.3584,
4703                z: 613.0,
4704            },
4705            Vec3 {
4706                x: 26496.72,
4707                y: 4727.2637,
4708                z: 613.0,
4709            },
4710            Vec3 {
4711                x: 21752.715,
4712                y: 8678.882,
4713                z: 766.0,
4714            },
4715            Vec3 {
4716                x: 21941.81,
4717                y: 8708.588,
4718                z: 766.0,
4719            },
4720            Vec3 {
4721                x: 22007.69,
4722                y: 8440.988,
4723                z: 766.0,
4724            },
4725            Vec3 {
4726                x: 21707.01,
4727                y: 8485.287,
4728                z: 766.0,
4729            },
4730            Vec3 {
4731                x: 21771.709,
4732                y: 8659.877,
4733                z: 766.0,
4734            },
4735            Vec3 {
4736                x: 21960.66,
4737                y: 8689.655,
4738                z: 766.0,
4739            },
4740            Vec3 {
4741                x: 22026.715,
4742                y: 8422.0205,
4743                z: 766.0,
4744            },
4745            Vec3 {
4746                x: 21725.943,
4747                y: 8466.458,
4748                z: 766.0,
4749            },
4750            Vec3 {
4751                x: 21752.816,
4752                y: 8640.974,
4753                z: 766.0,
4754            },
4755            Vec3 {
4756                x: 21941.717,
4757                y: 8670.63,
4758                z: 766.0,
4759            },
4760            Vec3 {
4761                x: 22007.924,
4762                y: 8403.286,
4763                z: 766.0,
4764            },
4765            Vec3 {
4766                x: 21706.914,
4767                y: 8447.533,
4768                z: 766.0,
4769            },
4770            Vec3 {
4771                x: 21733.822,
4772                y: 8659.979,
4773                z: 766.0,
4774            },
4775            Vec3 {
4776                x: 21922.867,
4777                y: 8689.562,
4778                z: 766.0,
4779            },
4780            Vec3 {
4781                x: 21988.898,
4782                y: 8422.254,
4783                z: 766.0,
4784            },
4785            Vec3 {
4786                x: 21687.98,
4787                y: 8466.362,
4788                z: 766.0,
4789            },
4790            Vec3 {
4791                x: 29544.33,
4792                y: 24598.639,
4793                z: 614.0,
4794            },
4795            Vec3 {
4796                x: 29773.992,
4797                y: 24716.027,
4798                z: 614.0,
4799            },
4800            Vec3 {
4801                x: 29734.61,
4802                y: 24378.34,
4803                z: 614.0,
4804            },
4805            Vec3 {
4806                x: 29578.096,
4807                y: 24440.527,
4808                z: 614.0,
4809            },
4810            Vec3 {
4811                x: 29563.35,
4812                y: 24579.71,
4813                z: 614.0,
4814            },
4815            Vec3 {
4816                x: 29792.535,
4817                y: 24697.197,
4818                z: 614.0,
4819            },
4820            Vec3 {
4821                x: 29753.492,
4822                y: 24359.324,
4823                z: 614.0,
4824            },
4825            Vec3 {
4826                x: 29597.02,
4827                y: 24421.621,
4828                z: 614.0,
4829            },
4830            Vec3 {
4831                x: 29544.385,
4832                y: 24560.84,
4833                z: 614.0,
4834            },
4835            Vec3 {
4836                x: 29773.744,
4837                y: 24678.12,
4838                z: 614.0,
4839            },
4840            Vec3 {
4841                x: 29734.64,
4842                y: 24340.344,
4843                z: 614.0,
4844            },
4845            Vec3 {
4846                x: 29578.012,
4847                y: 24402.63,
4848                z: 614.0,
4849            },
4850            Vec3 {
4851                x: 29525.365,
4852                y: 24579.768,
4853                z: 614.0,
4854            },
4855            Vec3 {
4856                x: 29755.2,
4857                y: 24696.95,
4858                z: 614.0,
4859            },
4860            Vec3 {
4861                x: 29715.758,
4862                y: 24359.357,
4863                z: 614.0,
4864            },
4865            Vec3 {
4866                x: 29559.088,
4867                y: 24421.537,
4868                z: 614.0,
4869            },
4870            Vec3 {
4871                x: 9292.779,
4872                y: 17322.951,
4873                z: 1459.0,
4874            },
4875            Vec3 {
4876                x: 9528.595,
4877                y: 17270.094,
4878                z: 1459.0,
4879            },
4880            Vec3 {
4881                x: 9524.052,
4882                y: 17069.418,
4883                z: 1459.0,
4884            },
4885            Vec3 {
4886                x: 9299.091,
4887                y: 17019.428,
4888                z: 1459.0,
4889            },
4890            Vec3 {
4891                x: 9320.701,
4892                y: 17294.904,
4893                z: 1459.0,
4894            },
4895            Vec3 {
4896                x: 9556.46,
4897                y: 17242.295,
4898                z: 1459.0,
4899            },
4900            Vec3 {
4901                x: 9552.073,
4902                y: 17041.447,
4903                z: 1459.0,
4904            },
4905            Vec3 {
4906                x: 9326.793,
4907                y: 16991.592,
4908                z: 1459.0,
4909            },
4910            Vec3 {
4911                x: 9293.017,
4912                y: 17267.094,
4913                z: 1459.0,
4914            },
4915            Vec3 {
4916                x: 9528.434,
4917                y: 17214.336,
4918                z: 1459.0,
4919            },
4920            Vec3 {
4921                x: 9524.213,
4922                y: 17013.637,
4923                z: 1459.0,
4924            },
4925            Vec3 {
4926                x: 9298.88,
4927                y: 16963.543,
4928                z: 1459.0,
4929            },
4930            Vec3 {
4931                x: 9265.096,
4932                y: 17295.14,
4933                z: 1459.0,
4934            },
4935            Vec3 {
4936                x: 9500.567,
4937                y: 17242.135,
4938                z: 1459.0,
4939            },
4940            Vec3 {
4941                x: 9496.191,
4942                y: 17041.607,
4943                z: 1459.0,
4944            },
4945            Vec3 {
4946                x: 9271.179,
4947                y: 16991.38,
4948                z: 1459.0,
4949            },
4950            Vec3 {
4951                x: 15745.189,
4952                y: 15740.487,
4953                z: 819.0,
4954            },
4955            Vec3 {
4956                x: 15986.825,
4957                y: 15736.656,
4958                z: 819.0,
4959            },
4960            Vec3 {
4961                x: 15992.56,
4962                y: 15493.267,
4963                z: 819.0,
4964            },
4965            Vec3 {
4966                x: 15739.27,
4967                y: 15489.251,
4968                z: 819.0,
4969            },
4970            Vec3 {
4971                x: 15773.181,
4972                y: 15712.4795,
4973                z: 819.0,
4974            },
4975            Vec3 {
4976                x: 16014.62,
4977                y: 15708.857,
4978                z: 819.0,
4979            },
4980            Vec3 {
4981                x: 16020.567,
4982                y: 15465.275,
4983                z: 819.0,
4984            },
4985            Vec3 {
4986                x: 15767.052,
4987                y: 15461.473,
4988                z: 819.0,
4989            },
4990            Vec3 {
4991                x: 15745.397,
4992                y: 15684.68,
4993                z: 819.0,
4994            },
4995            Vec3 {
4996                x: 15986.621,
4997                y: 15680.855,
4998                z: 819.0,
4999            },
5000            Vec3 {
5001                x: 15992.771,
5002                y: 15437.497,
5003                z: 819.0,
5004            },
5005            Vec3 {
5006                x: 15739.049,
5007                y: 15433.476,
5008                z: 819.0,
5009            },
5010            Vec3 {
5011                x: 15717.407,
5012                y: 15712.688,
5013                z: 819.0,
5014            },
5015            Vec3 {
5016                x: 15958.826,
5017                y: 15708.654,
5018                z: 819.0,
5019            },
5020            Vec3 {
5021                x: 15964.763,
5022                y: 15465.488,
5023                z: 819.0,
5024            },
5025            Vec3 {
5026                x: 15711.268,
5027                y: 15461.253,
5028                z: 819.0,
5029            },
5030        ];
5031
5032        let airships = airships_from_test_data();
5033        let platforms = [
5034            AirshipDockPlatform::NorthPlatform,
5035            AirshipDockPlatform::EastPlatform,
5036            AirshipDockPlatform::SouthPlatform,
5037            AirshipDockPlatform::WestPlatform,
5038        ];
5039        let from_positions = [
5040            Vec2::new(0.0, 32768.0),
5041            Vec2::new(32768.0, 32768.0),
5042            Vec2::new(32768.0, 0.0),
5043            Vec2::new(0.0, 0.0),
5044        ];
5045        for dock_index in (0..airships.airship_docks.len()).step_by(6) {
5046            for platform in platforms.iter() {
5047                for (i, from_pos) in from_positions.iter().enumerate() {
5048                    let transition_point = airships
5049                        .approach_transition_point(dock_index, dock_index % 4, *platform, *from_pos)
5050                        .unwrap();
5051                    assert_eq!(
5052                        transition_point,
5053                        expected[dock_index / 6 * 16 + *platform as usize * 4 + i]
5054                    );
5055                }
5056            }
5057        }
5058    }
5059
5060    #[test]
5061    fn docking_side_for_platform_test() {
5062        // Approximately: 0, 22, 45, 67, 90, 112, 135, 157, 180, 202, 225, 247, 270,
5063        // 292, 315, 337 degrees
5064        let dirs = [
5065            Vec2::new(0.0, 100.0) - Vec2::zero(),
5066            Vec2::new(100.0, 100.0) - Vec2::zero(),
5067            Vec2::new(100.0, 0.0) - Vec2::zero(),
5068            Vec2::new(100.0, -100.0) - Vec2::zero(),
5069            Vec2::new(0.0, -100.0) - Vec2::zero(),
5070            Vec2::new(-100.0, -100.0) - Vec2::zero(),
5071            Vec2::new(-100.0, 0.0) - Vec2::zero(),
5072            Vec2::new(-100.0, 100.0) - Vec2::zero(),
5073        ];
5074        let expected = [
5075            AirshipDockingSide::Port,
5076            AirshipDockingSide::Starboard,
5077            AirshipDockingSide::Starboard,
5078            AirshipDockingSide::Starboard,
5079            AirshipDockingSide::Starboard,
5080            AirshipDockingSide::Port,
5081            AirshipDockingSide::Port,
5082            AirshipDockingSide::Port,
5083            AirshipDockingSide::Port,
5084            AirshipDockingSide::Port,
5085            AirshipDockingSide::Port,
5086            AirshipDockingSide::Starboard,
5087            AirshipDockingSide::Starboard,
5088            AirshipDockingSide::Starboard,
5089            AirshipDockingSide::Starboard,
5090            AirshipDockingSide::Port,
5091            AirshipDockingSide::Starboard,
5092            AirshipDockingSide::Port,
5093            AirshipDockingSide::Port,
5094            AirshipDockingSide::Port,
5095            AirshipDockingSide::Port,
5096            AirshipDockingSide::Starboard,
5097            AirshipDockingSide::Starboard,
5098            AirshipDockingSide::Starboard,
5099            AirshipDockingSide::Starboard,
5100            AirshipDockingSide::Starboard,
5101            AirshipDockingSide::Starboard,
5102            AirshipDockingSide::Port,
5103            AirshipDockingSide::Port,
5104            AirshipDockingSide::Port,
5105            AirshipDockingSide::Port,
5106            AirshipDockingSide::Starboard,
5107        ];
5108        for platform in [
5109            AirshipDockPlatform::NorthPlatform,
5110            AirshipDockPlatform::EastPlatform,
5111            AirshipDockPlatform::SouthPlatform,
5112            AirshipDockPlatform::WestPlatform,
5113        ]
5114        .iter()
5115        {
5116            for (i, dir) in dirs.iter().enumerate() {
5117                let side = AirshipDockingSide::from_dir_to_platform(dir, platform);
5118                assert_eq!(side, expected[*platform as usize * 8 + i]);
5119            }
5120        }
5121    }
5122
5123    #[test]
5124    fn airship_spawning_locations_test() {
5125        let mut airships = airships_from_test_data();
5126        let all_dock_points = airships
5127            .airship_docks
5128            .iter()
5129            .map(|dock| Point {
5130                x: dock.center.x as f64,
5131                y: dock.center.y as f64,
5132            })
5133            .collect::<Vec<_>>();
5134
5135        airships.calculate_spawning_locations(&all_dock_points);
5136    }
5137}