sim/mechanics/
walking.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use serde::{Deserialize, Serialize};
4
5use abstutil::{deserialize_multimap, serialize_multimap, FixedMap, IndexableKey, MultiMap};
6use geom::{Distance, Duration, Line, PolyLine, Speed, Time};
7use map_model::{
8    BuildingID, DrivingSide, IntersectionID, Map, ParkingLotID, Path, PathConstraints, PathStep,
9    RoadID, TransitRouteID, Traversable,
10};
11
12use crate::sim::Ctx;
13use crate::{
14    pedestrian_body_radius, AgentID, AgentProperties, Command, CommutersVehiclesCounts,
15    CreatePedestrian, DistanceInterval, DrawPedCrowdInput, DrawPedestrianInput, Event, Intent,
16    IntersectionSimState, ParkedCar, ParkingSpot, PedCrowdLocation, PedestrianID, PersonID,
17    Problem, Scheduler, SidewalkPOI, SidewalkSpot, TimeInterval, TransitSimState, TripID,
18    TripManager, UnzoomedAgent,
19};
20
21const TIME_TO_START_BIKING: Duration = Duration::const_seconds(30.0);
22const TIME_TO_FINISH_BIKING: Duration = Duration::const_seconds(45.0);
23
24/// Simulates pedestrians. Unlike vehicles, pedestrians can move bidirectionally on sidewalks and
25/// just "ghost" through each other. There's no queueing or slowdown when many people are
26/// overlapping. They're simply grouped together into a DrawPedCrowdInput for rendering.
27#[derive(Serialize, Deserialize, Clone)]
28pub(crate) struct WalkingSimState {
29    peds: FixedMap<PedestrianID, Pedestrian>,
30    #[serde(
31        serialize_with = "serialize_multimap",
32        deserialize_with = "deserialize_multimap"
33    )]
34    peds_per_traversable: MultiMap<Traversable, PedestrianID>,
35    events: Vec<Event>,
36}
37
38impl WalkingSimState {
39    pub fn new() -> WalkingSimState {
40        WalkingSimState {
41            peds: FixedMap::new(),
42            peds_per_traversable: MultiMap::new(),
43            events: Vec::new(),
44        }
45    }
46
47    pub fn spawn_ped(
48        &mut self,
49        now: Time,
50        params: CreatePedestrian,
51        map: &Map,
52        scheduler: &mut Scheduler,
53    ) {
54        let start_lane = params.start.sidewalk_pos.lane();
55        assert_eq!(params.path.current_step().as_lane(), start_lane);
56        assert_eq!(
57            params.path.last_step().as_lane(),
58            params.goal.sidewalk_pos.lane()
59        );
60
61        let mut ped = Pedestrian {
62            id: params.id,
63            // Temporary bogus thing
64            state: PedState::Crossing {
65                dist_int: DistanceInterval::new_walking(Distance::ZERO, Distance::meters(1.0)),
66                time_int: TimeInterval::new(
67                    Time::START_OF_DAY,
68                    Time::START_OF_DAY + Duration::seconds(1.0),
69                ),
70                steep_uphill: false,
71            },
72            speed: params.speed,
73            total_blocked_time: Duration::ZERO,
74            started_at: now,
75            path: params.path,
76            start: params.start.clone(),
77            goal: params.goal,
78            trip: params.trip,
79            person: params.person,
80        };
81        ped.state = match params.start.connection {
82            SidewalkPOI::Building(b) | SidewalkPOI::ParkingSpot(ParkingSpot::Offstreet(b, _)) => {
83                PedState::LeavingBuilding(
84                    b,
85                    TimeInterval::new(now, now + map.get_b(b).driveway_geom.length() / ped.speed),
86                )
87            }
88            SidewalkPOI::ParkingSpot(ParkingSpot::Lot(pl, _)) => PedState::LeavingParkingLot(
89                pl,
90                TimeInterval::new(now, now + map.get_pl(pl).sidewalk_line.length() / ped.speed),
91            ),
92            SidewalkPOI::BikeRack(driving_pos) => PedState::FinishingBiking(
93                params.start.clone(),
94                Line::must_new(driving_pos.pt(map), params.start.sidewalk_pos.pt(map)),
95                TimeInterval::new(now, now + TIME_TO_FINISH_BIKING),
96            ),
97            _ => ped.crossing_state(
98                &self.peds_per_traversable,
99                params.start.sidewalk_pos.dist_along(),
100                now,
101                map,
102                &mut self.events,
103            ),
104        };
105
106        scheduler.push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
107        self.peds.insert(ped.id, ped);
108        self.peds_per_traversable.insert(
109            Traversable::Lane(params.start.sidewalk_pos.lane()),
110            params.id,
111        );
112    }
113
114    pub fn get_draw_ped(
115        &self,
116        id: PedestrianID,
117        now: Time,
118        map: &Map,
119    ) -> Option<DrawPedestrianInput> {
120        self.peds.get(&id).map(|p| p.get_draw_ped(now, map))
121    }
122
123    pub fn get_all_draw_peds(&self, now: Time, map: &Map) -> Vec<DrawPedestrianInput> {
124        self.peds
125            .values()
126            .map(|p| p.get_draw_ped(now, map))
127            .collect()
128    }
129
130    pub fn update_ped(
131        &mut self,
132        id: PedestrianID,
133        now: Time,
134        ctx: &mut Ctx,
135        trips: &mut TripManager,
136        transit: &mut TransitSimState,
137    ) {
138        let ped = self.peds.get_mut(&id).unwrap();
139        match ped.state {
140            PedState::Crossing { ref dist_int, .. } => {
141                if ped.path.is_last_step() {
142                    match ped.goal.connection {
143                        SidewalkPOI::ParkingSpot(spot) => {
144                            if let ParkingSpot::Lot(pl, _) = spot {
145                                ped.state = PedState::EnteringParkingLot(
146                                    pl,
147                                    TimeInterval::new(
148                                        now,
149                                        now + ctx.map.get_pl(pl).sidewalk_line.length() / ped.speed,
150                                    ),
151                                );
152                                ctx.scheduler
153                                    .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
154                            } else {
155                                self.peds_per_traversable
156                                    .remove(ped.path.current_step().as_traversable(), ped.id);
157                                trips.ped_reached_parking_spot(
158                                    now,
159                                    ped.id,
160                                    spot,
161                                    ped.total_blocked_time,
162                                    ped.path.total_length(),
163                                    ctx,
164                                );
165                                self.peds.remove(&id);
166                            }
167                        }
168                        SidewalkPOI::Building(b) => {
169                            ped.state = PedState::EnteringBuilding(
170                                b,
171                                TimeInterval::new(
172                                    now,
173                                    now + ctx.map.get_b(b).driveway_geom.length() / ped.speed,
174                                ),
175                            );
176                            ctx.scheduler
177                                .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
178                        }
179                        SidewalkPOI::TransitStop(stop) => {
180                            if let Some(route) = trips.ped_reached_bus_stop(
181                                now,
182                                ped.id,
183                                stop,
184                                ped.total_blocked_time,
185                                ped.path.total_length(),
186                                ctx,
187                                transit,
188                            ) {
189                                ped.state = PedState::WaitingForBus(route, now);
190                            } else {
191                                self.peds_per_traversable
192                                    .remove(ped.path.current_step().as_traversable(), ped.id);
193                                self.peds.remove(&id);
194                            }
195                        }
196                        SidewalkPOI::Border(i) => {
197                            self.peds_per_traversable
198                                .remove(ped.path.current_step().as_traversable(), ped.id);
199                            trips.ped_reached_border(
200                                now,
201                                ped.id,
202                                i,
203                                ped.total_blocked_time,
204                                ped.path.total_length(),
205                                ctx,
206                            );
207                            self.peds.remove(&id);
208                        }
209                        SidewalkPOI::BikeRack(driving_pos) => {
210                            let pt1 = ped.goal.sidewalk_pos.pt(ctx.map);
211                            let pt2 = driving_pos.pt(ctx.map);
212                            ped.state = PedState::StartingToBike(
213                                ped.goal.clone(),
214                                Line::must_new(pt1, pt2),
215                                TimeInterval::new(now, now + TIME_TO_START_BIKING),
216                            );
217                            ctx.scheduler
218                                .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
219                        }
220                        SidewalkPOI::SuddenlyAppear => unreachable!(),
221                        SidewalkPOI::DeferredParkingSpot => unreachable!(),
222                    }
223                } else {
224                    if let PathStep::Turn(t) | PathStep::ContraflowTurn(t) = ped.path.current_step()
225                    {
226                        ctx.intersections.turn_finished(
227                            now,
228                            AgentID::Pedestrian(ped.id),
229                            t,
230                            ctx.scheduler,
231                            ctx.map,
232                            false,
233                        );
234                    }
235
236                    let dist = dist_int.end;
237                    if ped.maybe_transition(
238                        now,
239                        ctx.map,
240                        ctx.intersections,
241                        &mut self.peds_per_traversable,
242                        &mut self.events,
243                        ctx.scheduler,
244                    ) {
245                        ctx.scheduler
246                            .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
247                    } else {
248                        // Must've failed because we can't turn yet. Don't schedule a retry here.
249                        ped.state = PedState::WaitingToTurn(dist, now);
250                    }
251                }
252            }
253            PedState::WaitingToTurn(_, blocked_since) => {
254                if ped.maybe_transition(
255                    now,
256                    ctx.map,
257                    ctx.intersections,
258                    &mut self.peds_per_traversable,
259                    &mut self.events,
260                    ctx.scheduler,
261                ) {
262                    ctx.scheduler
263                        .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
264                    ped.total_blocked_time += now - blocked_since;
265                    self.events.push(Event::IntersectionDelayMeasured(
266                        ped.trip,
267                        ped.path.current_step().as_turn(),
268                        AgentID::Pedestrian(id),
269                        now - blocked_since,
270                    ));
271                }
272            }
273            PedState::LeavingBuilding(b, _) => {
274                ped.state = ped.crossing_state(
275                    &self.peds_per_traversable,
276                    ctx.map.get_b(b).sidewalk_pos.dist_along(),
277                    now,
278                    ctx.map,
279                    &mut self.events,
280                );
281                ctx.scheduler
282                    .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
283            }
284            PedState::EnteringBuilding(bldg, _) => {
285                self.peds_per_traversable
286                    .remove(ped.path.current_step().as_traversable(), ped.id);
287                trips.ped_reached_building(
288                    now,
289                    ped.id,
290                    bldg,
291                    ped.total_blocked_time,
292                    ped.path.total_length(),
293                    ctx,
294                );
295                self.peds.remove(&id);
296            }
297            PedState::LeavingParkingLot(pl, _) => {
298                ped.state = ped.crossing_state(
299                    &self.peds_per_traversable,
300                    ctx.map.get_pl(pl).sidewalk_pos.dist_along(),
301                    now,
302                    ctx.map,
303                    &mut self.events,
304                );
305                ctx.scheduler
306                    .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
307            }
308            PedState::EnteringParkingLot(_, _) => {
309                self.peds_per_traversable
310                    .remove(ped.path.current_step().as_traversable(), ped.id);
311                trips.ped_reached_parking_spot(
312                    now,
313                    ped.id,
314                    match ped.goal.connection {
315                        SidewalkPOI::ParkingSpot(spot) => spot,
316                        _ => unreachable!(),
317                    },
318                    ped.total_blocked_time,
319                    ped.path.total_length(),
320                    ctx,
321                );
322                self.peds.remove(&id);
323            }
324            PedState::StartingToBike(ref spot, _, _) => {
325                self.peds_per_traversable
326                    .remove(ped.path.current_step().as_traversable(), ped.id);
327                trips.ped_ready_to_bike(
328                    now,
329                    ped.id,
330                    spot.clone(),
331                    ped.total_blocked_time,
332                    ped.path.total_length(),
333                    ctx,
334                );
335                self.peds.remove(&id);
336            }
337            PedState::FinishingBiking(ref spot, _, _) => {
338                ped.state = ped.crossing_state(
339                    &self.peds_per_traversable,
340                    spot.sidewalk_pos.dist_along(),
341                    now,
342                    ctx.map,
343                    &mut self.events,
344                );
345                ctx.scheduler
346                    .push(ped.state.get_end_time(), Command::UpdatePed(ped.id));
347            }
348            PedState::WaitingForBus(_, _) => unreachable!(),
349        }
350    }
351
352    pub fn ped_boarded_bus(&mut self, now: Time, id: PedestrianID) {
353        let mut ped = self.peds.remove(&id).unwrap();
354        match ped.state {
355            PedState::WaitingForBus(_, blocked_since) => {
356                self.peds_per_traversable
357                    .remove(ped.path.current_step().as_traversable(), id);
358                ped.total_blocked_time += now - blocked_since;
359            }
360            _ => unreachable!(),
361        };
362    }
363
364    /// Abruptly remove a pedestrian from the simulation. They may be in any arbitrary state, like
365    /// in the middle of a turn.
366    pub fn delete_ped(&mut self, id: PedestrianID, ctx: &mut Ctx) {
367        let ped = self.peds.remove(&id).unwrap();
368        self.peds_per_traversable
369            .remove(ped.path.current_step().as_traversable(), id);
370        ctx.scheduler.cancel(Command::UpdatePed(id));
371
372        if let PathStep::Turn(t) | PathStep::ContraflowTurn(t) = ped.path.current_step() {
373            ctx.intersections
374                .agent_deleted_mid_turn(AgentID::Pedestrian(id), t);
375        }
376        if let Some(PathStep::Turn(t)) | Some(PathStep::ContraflowTurn(t)) =
377            ped.path.maybe_next_step()
378        {
379            ctx.intersections.cancel_request(AgentID::Pedestrian(id), t);
380        }
381    }
382
383    pub fn debug_ped_json(&self, id: PedestrianID) -> String {
384        if let Some(ped) = self.peds.get(&id) {
385            abstutil::to_json(ped)
386        } else {
387            format!("{} doesn't exist", id)
388        }
389    }
390
391    pub fn agent_properties(&self, map: &Map, id: PedestrianID, now: Time) -> AgentProperties {
392        let p = &self.peds[&id];
393
394        let time_spent_waiting = p.state.time_spent_waiting(now);
395        // TODO Incorporate this somewhere
396        /*if let PedState::WaitingForBus(r, _) = p.state {
397            extra.push(format!("Waiting for bus {}", map.get_tr(r).name));
398        }*/
399
400        let current_state_dist = match p.state {
401            PedState::Crossing {
402                ref dist_int,
403                ref time_int,
404                ..
405            } => time_int.percent(now) * dist_int.length(),
406            // We're at the beginning of our trip and are only walking along a driveway or biking
407            // connection
408            PedState::LeavingBuilding(_, _)
409            | PedState::LeavingParkingLot(_, _)
410            | PedState::FinishingBiking(_, _, _) => Distance::ZERO,
411            // In all of these cases, we haven't shifted the PathStep that led us to this state yet
412            PedState::WaitingToTurn(_, _)
413            | PedState::EnteringBuilding(_, _)
414            | PedState::EnteringParkingLot(_, _)
415            | PedState::StartingToBike(_, _, _)
416            | PedState::WaitingForBus(_, _) => {
417                p.path.dist_crossed_from_step(map, &p.path.current_step())
418            }
419        };
420
421        AgentProperties {
422            total_time: now - p.started_at,
423            waiting_here: time_spent_waiting,
424            total_waiting: p.total_blocked_time + time_spent_waiting,
425            dist_crossed: p.path.crossed_so_far() + current_state_dist,
426            total_dist: p.path.total_length(),
427        }
428    }
429
430    pub fn trace_route(&self, now: Time, id: PedestrianID, map: &Map) -> Option<PolyLine> {
431        let p = self.peds.get(&id)?;
432        let dist = (p.get_dist_along(now, map) + pedestrian_body_radius()).min(
433            p.path
434                .current_step()
435                .as_traversable()
436                .get_polyline(map)
437                .length(),
438        );
439        p.path.trace_from_start(map, dist)
440    }
441
442    pub fn get_path(&self, id: PedestrianID) -> Option<&Path> {
443        let p = self.peds.get(&id)?;
444        Some(&p.path)
445    }
446
447    pub fn get_unzoomed_agents(&self, now: Time, map: &Map) -> Vec<UnzoomedAgent> {
448        let mut peds = Vec::new();
449
450        for ped in self.peds.values() {
451            peds.push(UnzoomedAgent {
452                id: AgentID::Pedestrian(ped.id),
453                pos: ped.get_draw_ped(now, map).pos,
454                person: Some(ped.person),
455                parking: false,
456            });
457        }
458
459        peds
460    }
461
462    pub fn get_draw_peds_on(
463        &self,
464        now: Time,
465        on: Traversable,
466        map: &Map,
467    ) -> (Vec<DrawPedestrianInput>, Vec<DrawPedCrowdInput>) {
468        // Classify into direction-based groups or by building/parking lot driveway.
469        let mut forwards: Vec<(PedestrianID, Distance)> = Vec::new();
470        let mut backwards: Vec<(PedestrianID, Distance)> = Vec::new();
471        let mut bldg_driveway: MultiMap<BuildingID, (PedestrianID, Distance)> = MultiMap::new();
472        let mut lot_driveway: MultiMap<ParkingLotID, (PedestrianID, Distance)> = MultiMap::new();
473
474        for id in self.peds_per_traversable.get(on) {
475            let ped = &self.peds[id];
476            let dist = ped.get_dist_along(now, map);
477
478            match ped.state {
479                PedState::Crossing { ref dist_int, .. } => {
480                    if dist_int.start < dist_int.end {
481                        forwards.push((*id, dist));
482                    } else {
483                        backwards.push((*id, dist));
484                    }
485                }
486                PedState::WaitingToTurn(dist, _) => {
487                    if dist == Distance::ZERO {
488                        backwards.push((*id, dist));
489                    } else {
490                        forwards.push((*id, dist));
491                    }
492                }
493                PedState::LeavingBuilding(b, ref int) => {
494                    let len = map.get_b(b).driveway_geom.length();
495                    bldg_driveway.insert(b, (*id, int.percent(now) * len));
496                }
497                PedState::EnteringBuilding(b, ref int) => {
498                    let len = map.get_b(b).driveway_geom.length();
499                    bldg_driveway.insert(b, (*id, (1.0 - int.percent(now)) * len));
500                }
501                PedState::LeavingParkingLot(pl, ref int) => {
502                    let len = map.get_pl(pl).sidewalk_line.length();
503                    lot_driveway.insert(pl, (*id, int.percent(now) * len));
504                }
505                PedState::EnteringParkingLot(pl, ref int) => {
506                    let len = map.get_pl(pl).sidewalk_line.length();
507                    lot_driveway.insert(pl, (*id, (1.0 - int.percent(now)) * len));
508                }
509                PedState::StartingToBike(_, _, _)
510                | PedState::FinishingBiking(_, _, _)
511                | PedState::WaitingForBus(_, _) => {
512                    // The backwards half of the sidewalk is closer to the road.
513                    backwards.push((*id, dist));
514                }
515            }
516        }
517
518        let mut crowds: Vec<DrawPedCrowdInput> = Vec::new();
519        let mut loners: Vec<DrawPedestrianInput> = Vec::new();
520
521        // For each group, sort by distance along. Attempt to bundle into intervals.
522        for (mut group, location, on_len) in vec![
523            (
524                forwards,
525                PedCrowdLocation::Sidewalk(on, false),
526                on.get_polyline(map).length(),
527            ),
528            (
529                backwards,
530                PedCrowdLocation::Sidewalk(on, true),
531                on.get_polyline(map).length(),
532            ),
533        ]
534        .into_iter()
535        .chain(bldg_driveway.consume().into_iter().map(|(b, set)| {
536            (
537                set.into_iter().collect::<Vec<_>>(),
538                PedCrowdLocation::BldgDriveway(b),
539                map.get_b(b).driveway_geom.length(),
540            )
541        }))
542        .chain(lot_driveway.consume().into_iter().map(|(pl, set)| {
543            (
544                set.into_iter().collect::<Vec<_>>(),
545                PedCrowdLocation::LotDriveway(pl),
546                map.get_pl(pl).sidewalk_line.length(),
547            )
548        })) {
549            if group.is_empty() {
550                continue;
551            }
552            group.sort_by_key(|(_, dist)| *dist);
553            let (individs, these_crowds) = find_crowds(group, location);
554            for id in individs {
555                loners.push(self.peds[&id].get_draw_ped(now, map));
556            }
557            for mut crowd in these_crowds {
558                // Clamp the distance intervals.
559                if crowd.low < Distance::ZERO {
560                    crowd.low = Distance::ZERO;
561                }
562                if crowd.high > on_len {
563                    crowd.high = on_len;
564                }
565                crowds.push(crowd);
566            }
567        }
568
569        (loners, crowds)
570    }
571
572    pub fn collect_events(&mut self) -> Vec<Event> {
573        std::mem::take(&mut self.events)
574    }
575
576    pub fn find_trips_to_parking(&self, evicted_cars: Vec<ParkedCar>) -> Vec<(AgentID, TripID)> {
577        let goals: BTreeSet<SidewalkPOI> = evicted_cars
578            .into_iter()
579            .map(|p| SidewalkPOI::ParkingSpot(p.spot))
580            .collect();
581        let mut affected = Vec::new();
582        for ped in self.peds.values() {
583            if goals.contains(&ped.goal.connection) {
584                affected.push((AgentID::Pedestrian(ped.id), ped.trip));
585            }
586        }
587        affected
588    }
589
590    pub fn all_waiting_people(&self, now: Time, delays: &mut BTreeMap<PersonID, Duration>) {
591        for p in self.peds.values() {
592            let delay = p.state.time_spent_waiting(now);
593            if delay > Duration::ZERO {
594                delays.insert(p.person, delay);
595            }
596        }
597    }
598
599    pub fn populate_commuter_counts(&self, cnts: &mut CommutersVehiclesCounts) {
600        for p in self.peds.values() {
601            match p.goal.connection {
602                SidewalkPOI::ParkingSpot(_) | SidewalkPOI::DeferredParkingSpot => {
603                    cnts.walking_to_from_car += 1;
604                }
605                SidewalkPOI::TransitStop(_) => {
606                    cnts.walking_to_from_transit += 1;
607                }
608                SidewalkPOI::BikeRack(_) => {
609                    cnts.walking_to_from_bike += 1;
610                }
611                _ => match p.start.connection {
612                    SidewalkPOI::ParkingSpot(_) | SidewalkPOI::DeferredParkingSpot => {
613                        cnts.walking_to_from_car += 1;
614                    }
615                    SidewalkPOI::TransitStop(_) => {
616                        cnts.walking_to_from_transit += 1;
617                    }
618                    SidewalkPOI::BikeRack(_) => {
619                        cnts.walking_to_from_bike += 1;
620                    }
621                    _ => {
622                        cnts.walking_commuters += 1;
623                    }
624                },
625            }
626        }
627    }
628
629    pub fn get_pedestrian_density(
630        &self,
631        map: &Map,
632    ) -> (BTreeMap<RoadID, f64>, BTreeMap<IntersectionID, f64>) {
633        let mut roads = BTreeMap::new();
634        let mut intersections = BTreeMap::new();
635        for (traversable, peds) in self.peds_per_traversable.borrow() {
636            if peds.is_empty() {
637                continue;
638            }
639            let density = (peds.len() as f64) / area(map, *traversable);
640            match traversable {
641                Traversable::Lane(l) => {
642                    let entry = roads.entry(l.road).or_insert(0.0);
643                    if *entry < density {
644                        *entry = density;
645                    }
646                }
647                Traversable::Turn(t) => {
648                    let entry = intersections.entry(t.parent).or_insert(0.0);
649                    if *entry < density {
650                        *entry = density;
651                    }
652                }
653            }
654        }
655        (roads, intersections)
656    }
657}
658
659#[derive(Serialize, Deserialize, Clone)]
660struct Pedestrian {
661    id: PedestrianID,
662    state: PedState,
663    speed: Speed,
664    total_blocked_time: Duration,
665    // TODO organize analytics better.
666    started_at: Time,
667
668    path: Path,
669    start: SidewalkSpot,
670    goal: SidewalkSpot,
671    trip: TripID,
672    person: PersonID,
673}
674
675impl Pedestrian {
676    fn crossing_state(
677        &self,
678        peds_per_traversable: &MultiMap<Traversable, PedestrianID>,
679        start_dist: Distance,
680        start_time: Time,
681        map: &Map,
682        events: &mut Vec<Event>,
683    ) -> PedState {
684        let end_dist = if self.path.is_last_step() {
685            self.goal.sidewalk_pos.dist_along()
686        } else {
687            // TODO PathStep should have a end_dist... or end_pos
688            match self.path.current_step() {
689                PathStep::Lane(l) => map.get_l(l).length(),
690                PathStep::ContraflowLane(_) => Distance::ZERO,
691                PathStep::Turn(t) => map.get_t(t).geom.length(),
692                PathStep::ContraflowTurn(_) => Distance::ZERO,
693            }
694        };
695
696        let speed_penalty = crowdedness_penalty(
697            map,
698            self.path.current_step().as_traversable(),
699            peds_per_traversable,
700        );
701        if speed_penalty != 1.0 {
702            events.push(Event::ProblemEncountered(
703                self.trip,
704                Problem::PedestrianOvercrowding(self.path.current_step().as_traversable()),
705            ));
706        }
707
708        let dist_int = DistanceInterval::new_walking(start_dist, end_dist);
709        let (speed, percent_incline) = self.path.current_step().max_speed_and_incline_along(
710            Some(self.speed),
711            PathConstraints::Pedestrian,
712            map,
713        );
714        let time_int = TimeInterval::new(
715            start_time,
716            start_time + dist_int.length() / (speed_penalty * speed),
717        );
718        PedState::Crossing {
719            dist_int,
720            time_int,
721            steep_uphill: percent_incline >= 0.08,
722        }
723    }
724
725    fn get_dist_along(&self, now: Time, map: &Map) -> Distance {
726        match self.state {
727            PedState::Crossing {
728                ref dist_int,
729                ref time_int,
730                ..
731            } => dist_int.lerp(time_int.percent(now)),
732            PedState::WaitingToTurn(dist, _) => dist,
733            PedState::LeavingBuilding(b, _) | PedState::EnteringBuilding(b, _) => {
734                map.get_b(b).sidewalk_pos.dist_along()
735            }
736            PedState::LeavingParkingLot(pl, _) | PedState::EnteringParkingLot(pl, _) => {
737                map.get_pl(pl).sidewalk_pos.dist_along()
738            }
739            PedState::StartingToBike(ref spot, _, _) => spot.sidewalk_pos.dist_along(),
740            PedState::FinishingBiking(ref spot, _, _) => spot.sidewalk_pos.dist_along(),
741            PedState::WaitingForBus(_, _) => self.goal.sidewalk_pos.dist_along(),
742        }
743    }
744
745    fn get_draw_ped(&self, now: Time, map: &Map) -> DrawPedestrianInput {
746        let on = self.path.current_step().as_traversable();
747        let err = format!("at {}, {}'s position is broken", now, self.id);
748        let angle_offset = if map.get_config().driving_side == DrivingSide::Right {
749            90.0
750        } else {
751            270.0
752        };
753        let project_away = match on {
754            Traversable::Lane(l) => map.get_l(l).width / 2.0 - pedestrian_body_radius(),
755            // Width of a crossing is fuzzy, but this could likely be improved
756            Traversable::Turn(_) => pedestrian_body_radius(),
757        };
758        let mut intent = None;
759
760        let (pos, facing) = match self.state {
761            PedState::Crossing {
762                ref dist_int,
763                ref time_int,
764                steep_uphill,
765            } => {
766                let percent = if now > time_int.end {
767                    1.0
768                } else {
769                    time_int.percent(now)
770                };
771                let (pos, orig_angle) = on
772                    .get_polyline(map)
773                    .dist_along(dist_int.lerp(percent))
774                    .expect(&err);
775                let facing = if dist_int.start < dist_int.end {
776                    orig_angle
777                } else {
778                    orig_angle.opposite()
779                };
780                if steep_uphill {
781                    intent = Some(Intent::SteepUphill);
782                }
783                (
784                    pos.project_away(project_away, facing.rotate_degs(angle_offset)),
785                    facing,
786                )
787            }
788            PedState::WaitingToTurn(dist, _) => {
789                let (pos, orig_angle) = on.get_polyline(map).dist_along(dist).expect(&err);
790                let facing = if dist == Distance::ZERO {
791                    orig_angle.opposite()
792                } else {
793                    orig_angle
794                };
795                (
796                    pos.project_away(project_away, facing.rotate_degs(angle_offset)),
797                    facing,
798                )
799            }
800            PedState::LeavingBuilding(b, ref time_int) => {
801                let pl = &map.get_b(b).driveway_geom;
802                // If we're on some tiny line and percent_along fails, just fall back to to some
803                // point on the line instead of crashing.
804                if let Ok(pair) = pl.dist_along(time_int.percent(now) * pl.length()) {
805                    pair
806                } else {
807                    (pl.first_pt(), pl.first_line().angle())
808                }
809            }
810            PedState::EnteringBuilding(b, ref time_int) => {
811                let pl = &map.get_b(b).driveway_geom;
812                if let Ok((pt, angle)) = pl.dist_along((1.0 - time_int.percent(now)) * pl.length())
813                {
814                    (pt, angle.opposite())
815                } else {
816                    (pl.first_pt(), pl.first_line().angle().opposite())
817                }
818            }
819            PedState::LeavingParkingLot(pl, ref time_int) => {
820                let line = &map.get_pl(pl).sidewalk_line;
821                (
822                    line.percent_along(time_int.percent(now))
823                        .unwrap_or_else(|_| line.pt1()),
824                    line.angle(),
825                )
826            }
827            PedState::EnteringParkingLot(pl, ref time_int) => {
828                let line = &map.get_pl(pl).sidewalk_line;
829                (
830                    line.reversed()
831                        .percent_along(time_int.percent(now))
832                        .unwrap_or_else(|_| line.pt1()),
833                    line.angle().opposite(),
834                )
835            }
836            PedState::StartingToBike(_, ref line, ref time_int) => (
837                line.percent_along(time_int.percent(now))
838                    .unwrap_or_else(|_| line.pt1()),
839                line.angle(),
840            ),
841            PedState::FinishingBiking(_, ref line, ref time_int) => (
842                line.percent_along(time_int.percent(now))
843                    .unwrap_or_else(|_| line.pt1()),
844                line.angle(),
845            ),
846            PedState::WaitingForBus(_, _) => {
847                let (pt, angle) = self.goal.sidewalk_pos.pt_and_angle(map);
848                // Stand on the far side of the sidewalk (by the bus stop), facing the road
849                (
850                    pt.project_away(project_away, angle.rotate_degs(angle_offset)),
851                    angle.rotate_degs(-angle_offset),
852                )
853            }
854        };
855
856        DrawPedestrianInput {
857            id: self.id,
858            pos,
859            facing,
860            waiting_for_turn: match self.state {
861                PedState::WaitingToTurn(_, _) => Some(self.path.next_step().as_turn()),
862                _ => None,
863            },
864            intent,
865            preparing_bike: matches!(
866                self.state,
867                PedState::StartingToBike(_, _, _) | PedState::FinishingBiking(_, _, _)
868            ),
869            waiting_for_bus: matches!(self.state, PedState::WaitingForBus(_, _)),
870            on,
871            person: self.person,
872        }
873    }
874
875    // True if we successfully continued to the next step of our path
876    fn maybe_transition(
877        &mut self,
878        now: Time,
879        map: &Map,
880        intersections: &mut IntersectionSimState,
881        peds_per_traversable: &mut MultiMap<Traversable, PedestrianID>,
882        events: &mut Vec<Event>,
883        scheduler: &mut Scheduler,
884    ) -> bool {
885        if let PathStep::Turn(t) | PathStep::ContraflowTurn(t) = self.path.next_step() {
886            if !intersections.maybe_start_turn(
887                AgentID::Pedestrian(self.id),
888                t,
889                PathStep::Turn(t).max_speed_along(
890                    Some(self.speed),
891                    PathConstraints::Pedestrian,
892                    map,
893                ),
894                now,
895                map,
896                scheduler,
897                None,
898            ) {
899                return false;
900            }
901        }
902
903        peds_per_traversable.remove(self.path.current_step().as_traversable(), self.id);
904        self.path.shift(map);
905        let start_dist = match self.path.current_step() {
906            PathStep::Lane(_) => Distance::ZERO,
907            PathStep::ContraflowLane(l) => map.get_l(l).length(),
908            PathStep::Turn(_) => Distance::ZERO,
909            PathStep::ContraflowTurn(t) => map.get_t(t).geom.length(),
910        };
911        self.state = self.crossing_state(peds_per_traversable, start_dist, now, map, events);
912        peds_per_traversable.insert(self.path.current_step().as_traversable(), self.id);
913        events.push(Event::AgentEntersTraversable(
914            AgentID::Pedestrian(self.id),
915            Some(self.trip),
916            self.path.current_step().as_traversable(),
917            None,
918        ));
919        true
920    }
921}
922
923#[derive(Serialize, Deserialize, Debug, Clone)]
924enum PedState {
925    Crossing {
926        dist_int: DistanceInterval,
927        time_int: TimeInterval,
928        steep_uphill: bool,
929    },
930    /// The Distance is either 0 or the current traversable's length. The Time is blocked_since.
931    WaitingToTurn(Distance, Time),
932    LeavingBuilding(BuildingID, TimeInterval),
933    EnteringBuilding(BuildingID, TimeInterval),
934    LeavingParkingLot(ParkingLotID, TimeInterval),
935    EnteringParkingLot(ParkingLotID, TimeInterval),
936    StartingToBike(SidewalkSpot, Line, TimeInterval),
937    FinishingBiking(SidewalkSpot, Line, TimeInterval),
938    WaitingForBus(TransitRouteID, Time),
939}
940
941impl PedState {
942    fn get_end_time(&self) -> Time {
943        match self {
944            PedState::Crossing { ref time_int, .. } => time_int.end,
945            PedState::WaitingToTurn(_, _) => unreachable!(),
946            PedState::LeavingBuilding(_, ref time_int) => time_int.end,
947            PedState::EnteringBuilding(_, ref time_int) => time_int.end,
948            PedState::LeavingParkingLot(_, ref time_int) => time_int.end,
949            PedState::EnteringParkingLot(_, ref time_int) => time_int.end,
950            PedState::StartingToBike(_, _, ref time_int) => time_int.end,
951            PedState::FinishingBiking(_, _, ref time_int) => time_int.end,
952            PedState::WaitingForBus(_, _) => unreachable!(),
953        }
954    }
955
956    fn time_spent_waiting(&self, now: Time) -> Duration {
957        match self {
958            PedState::WaitingToTurn(_, blocked_since)
959            | PedState::WaitingForBus(_, blocked_since) => now - *blocked_since,
960            _ => Duration::ZERO,
961        }
962    }
963}
964
965// The crowds returned here may have low/high values extending up to radius past the real geometry.
966fn find_crowds(
967    input: Vec<(PedestrianID, Distance)>,
968    location: PedCrowdLocation,
969) -> (Vec<PedestrianID>, Vec<DrawPedCrowdInput>) {
970    let mut loners = Vec::new();
971    let mut crowds = Vec::new();
972    let radius = pedestrian_body_radius();
973
974    let mut current_crowd = DrawPedCrowdInput {
975        low: input[0].1 - radius,
976        high: input[0].1 + radius,
977        members: vec![input[0].0],
978        location: location.clone(),
979    };
980    for (id, dist) in input.into_iter().skip(1) {
981        // If the pedestrian circles would overlap at all,
982        if dist - radius <= current_crowd.high {
983            current_crowd.members.push(id);
984            current_crowd.high = dist + radius;
985        } else {
986            if current_crowd.members.len() == 1 {
987                loners.push(current_crowd.members[0]);
988            } else {
989                crowds.push(current_crowd);
990            }
991            // Reset current_crowd
992            current_crowd = DrawPedCrowdInput {
993                low: dist - radius,
994                high: dist + radius,
995                members: vec![id],
996                location: location.clone(),
997            };
998        }
999    }
1000    // Handle the last bit
1001    if current_crowd.members.len() == 1 {
1002        loners.push(current_crowd.members[0]);
1003    } else {
1004        crowds.push(current_crowd);
1005    }
1006
1007    (loners, crowds)
1008}
1009
1010impl IndexableKey for PedestrianID {
1011    fn index(&self) -> usize {
1012        self.0
1013    }
1014}
1015
1016/// Returns a number in (0, 1] to multiply speed by to account for current crowdedness.
1017///
1018/// We could get really fancy here and slow people down only when they're part of a crowd, or
1019/// passing people going the opposite direction. But start simple -- keep a fixed speed for the
1020/// entire time on a sidewalk, and base the decision on how many people are there when entering the
1021/// sidewalk.
1022fn crowdedness_penalty(
1023    map: &Map,
1024    traversable: Traversable,
1025    peds_per_traversable: &MultiMap<Traversable, PedestrianID>,
1026) -> f64 {
1027    let num_people = peds_per_traversable.get(traversable).len();
1028    // Assume everyone's equally spread out
1029    let people_per_sq_m = (num_people as f64) / area(map, traversable);
1030    // Based on eyeballing images from
1031    // https://www.gkstill.com/Support/crowd-density/CrowdDensity-1.html, let's use a fixed
1032    // threshold of 1.5 people per square meter as "crowded" and slow them down by half.
1033    if people_per_sq_m < 1.5 {
1034        // Plenty of room, no penalty
1035        return 1.0;
1036    }
1037    0.5
1038}
1039
1040// In m^2
1041fn area(map: &Map, traversable: Traversable) -> f64 {
1042    // The length of the sidewalk or crosswalk
1043    let len = traversable.get_polyline(map).length();
1044    // The width of the space
1045    let width = match traversable {
1046        // Sidewalk
1047        Traversable::Lane(l) => map.get_l(l).width,
1048        // For crosswalks, the thinner of the two sidewalks being connected
1049        Traversable::Turn(t) => map.get_l(t.src).width.min(map.get_l(t.dst).width),
1050    };
1051    width.inner_meters() * len.inner_meters()
1052}