Implement a global map of entities

Implement a global map of entities, which allows referencing by either
position or ID and updating the positions of existent entities, and put
the character in there.

11 files changed, 448 insertions, 36 deletions

diff --git a/src/display/mod.rs b/src/display/mod.rs
index 664aaf319cc7..9e15a0d97d62 100644
--- a/src/display/mod.rs
+++ b/src/display/mod.rs
@@ -14,5 +14,17 @@ pub fn clear<T: Write>(out: &mut T) -> io::Result<()> {
 pub trait Draw: Positioned {
     /// Draw this entity, assuming the character is already at the correct
     /// position
-    fn do_draw<W: Write>(&self, out: &mut W) -> io::Result<()>;
+    fn do_draw(&self, out: &mut Write) -> io::Result<()>;
+}
+
+impl<T : Draw> Draw for &T {
+    fn do_draw(&self, out: &mut Write) -> io::Result<()> {
+        (**self).do_draw(out)
+    }
+}
+
+impl<T : Draw> Draw for Box<T> {
+    fn do_draw(&self, out: &mut Write) -> io::Result<()> {
+        (**self).do_draw(out)
+    }
 }
diff --git a/src/display/viewport.rs b/src/display/viewport.rs
index 24cc5272cb8e..780eb887143d 100644
--- a/src/display/viewport.rs
+++ b/src/display/viewport.rs
@@ -2,7 +2,6 @@ use super::BoxStyle;
 use super::Draw;
 use crate::display::draw_box::draw_box;
 use crate::display::utils::clone_times;
-use crate::display::utils::times;
 use crate::types::{BoundingBox, Position, Positioned};
 use std::fmt::{self, Debug};
 use std::io::{self, Write};
diff --git a/src/entities/character.rs b/src/entities/character.rs
index f436608ea5e7..fb5a89591c95 100644
--- a/src/entities/character.rs
+++ b/src/entities/character.rs
@@ -1,13 +1,13 @@
+use crate::display;
+use crate::entities::Entity;
+use crate::types::{Position, Speed};
 use proptest_derive::Arbitrary;
 use std::io::{self, Write};
 use termion::cursor;
 
-use crate::display;
-use crate::types::{Position, Speed};
-
 const DEFAULT_SPEED: Speed = Speed(100);
 
-#[derive(Debug, PartialEq, Eq, Arbitrary)]
+#[derive(Debug, PartialEq, Eq, Arbitrary, Clone)]
 pub struct Character {
     /// The position of the character, relative to the game
     pub position: Position,
@@ -26,13 +26,12 @@ impl Character {
 }
 
 positioned!(Character);
+positioned_mut!(Character);
+
+impl Entity for Character {}
 
 impl display::Draw for Character {
-    fn do_draw<W: Write>(&self, out: &mut W) -> io::Result<()> {
-        write!(
-            out,
-            "@{}",
-            cursor::Left(1),
-        )
+    fn do_draw(&self, out: &mut Write) -> io::Result<()> {
+        write!(out, "@{}", cursor::Left(1),)
     }
 }
diff --git a/src/entities/mod.rs b/src/entities/mod.rs
index 0320f2ddd9c1..a23b15eef34c 100644
--- a/src/entities/mod.rs
+++ b/src/entities/mod.rs
@@ -1,2 +1,16 @@
 pub mod character;
+use crate::display::Draw;
+use crate::types::{Positioned, PositionedMut};
 pub use character::Character;
+use downcast_rs::Downcast;
+use std::io::{self, Write};
+
+pub trait Entity: Positioned + PositionedMut + Draw + Downcast {}
+
+impl_downcast!(Entity);
+
+impl Draw for Box<dyn Entity> {
+    fn do_draw(&self, out: &mut Write) -> io::Result<()> {
+        (**self).do_draw(out)
+    }
+}
diff --git a/src/game.rs b/src/game.rs
index daa5fa575f68..90d94dc5f220 100644
--- a/src/game.rs
+++ b/src/game.rs
@@ -1,10 +1,14 @@
 use crate::display::{self, Viewport};
 use crate::entities::Character;
+use crate::entities::Entity;
 use crate::messages::message;
 use crate::settings::Settings;
 use crate::types::command::Command;
-use crate::types::Positioned;
-use crate::types::{BoundingBox, Dimensions, Position};
+use crate::types::entity_map::EntityID;
+use crate::types::entity_map::EntityMap;
+use crate::types::{
+    BoundingBox, Collision, Dimensions, Position, Positioned, PositionedMut,
+};
 use rand::rngs::SmallRng;
 use rand::SeedableRng;
 use std::io::{self, StdinLock, StdoutLock, Write};
@@ -16,6 +20,20 @@ type Stdout<'a> = RawTerminal<StdoutLock<'a>>;
 
 type Rng = SmallRng;
 
+type AnEntity<'a> = Box<dyn Entity>;
+
+impl<'a> Positioned for AnEntity<'a> {
+    fn position(&self) -> Position {
+        (**self).position()
+    }
+}
+
+impl<'a> PositionedMut for AnEntity<'a> {
+    fn set_position(&mut self, pos: Position) {
+        (**self).set_position(pos)
+    }
+}
+
 /// The full state of a running Game
 pub struct Game<'a> {
     settings: Settings,
@@ -25,8 +43,11 @@ pub struct Game<'a> {
     /// An iterator on keypresses from the user
     keys: Keys<StdinLock<'a>>,
 
-    /// The player character
-    character: Character,
+    /// The map of all the entities in the game
+    entities: EntityMap<AnEntity<'a>>,
+
+    /// The entity ID of the player character
+    character_entity_id: EntityID,
 
     /// The messages that have been said to the user, in forward time order
     messages: Vec<String>,
@@ -51,6 +72,7 @@ impl<'a> Game<'a> {
             Some(seed) => SmallRng::seed_from_u64(seed),
             None => SmallRng::from_entropy(),
         };
+        let mut entities: EntityMap<AnEntity<'a>> = EntityMap::new();
         Game {
             settings,
             rng,
@@ -61,19 +83,34 @@ impl<'a> Game<'a> {
                 stdout,
             ),
             keys: stdin.keys(),
-            character: Character::new(),
+            character_entity_id: entities.insert(Box::new(Character::new())),
             messages: Vec::new(),
+            entities,
         }
     }
 
-    /// Returns true if there's a collision in the game at the given Position
-    fn collision_at(&self, pos: Position) -> bool {
-        !pos.within(self.viewport.inner)
+    /// Returns a collision, if any, at the given Position in the game
+    fn collision_at(&self, pos: Position) -> Option<Collision> {
+        if !pos.within(self.viewport.inner) {
+            Some(Collision::Stop)
+        } else {
+            None
+        }
+    }
+
+    fn character(&self) -> &Character {
+        debug!("ents: {:?} cid: {:?}", self.entities.ids().map(|id| *id).collect::<Vec<u32>>(), self.character_entity_id);
+        (*self.entities.get(self.character_entity_id).unwrap())
+            .downcast_ref()
+            .unwrap()
     }
 
     /// Draw all the game entities to the screen
     fn draw_entities(&mut self) -> io::Result<()> {
-        self.viewport.draw(&self.character)
+        for entity in self.entities.entities() {
+            self.viewport.draw(entity)?;
+        }
+        Ok(())
     }
 
     /// Get a message from the global map based on the rng in this game
@@ -104,7 +141,6 @@ impl<'a> Game<'a> {
         self.viewport.init()?;
         self.draw_entities()?;
         self.say("global.welcome")?;
-        self.say("somethign else")?;
         self.flush()?;
         loop {
             let mut old_position = None;
@@ -116,10 +152,18 @@ impl<'a> Game<'a> {
                 }
 
                 Some(Move(direction)) => {
-                    let new_pos = self.character.position + direction;
-                    if !self.collision_at(new_pos) {
-                        old_position = Some(self.character.position);
-                        self.character.position = new_pos;
+                    use Collision::*;
+                    let new_pos = self.character().position + direction;
+                    match self.collision_at(new_pos) {
+                        None => {
+                            old_position = Some(self.character().position);
+                            self.entities.update_position(
+                                self.character_entity_id,
+                                new_pos,
+                            );
+                        }
+                        Some(Combat) => unimplemented!(),
+                        Some(Stop) => (),
                     }
                 }
 
@@ -131,12 +175,14 @@ impl<'a> Game<'a> {
             match old_position {
                 Some(old_pos) => {
                     self.viewport.clear(old_pos)?;
-                    self.viewport.draw(&self.character)?;
+                    self.viewport.draw(
+                        // TODO this clone feels unnecessary.
+                        &self.character().clone())?;
                 }
                 None => (),
             }
             self.flush()?;
-            debug!("{:?}", self.character);
+            debug!("{:?}", self.character());
         }
         Ok(())
     }
diff --git a/src/main.rs b/src/main.rs
index 6b0ae18181ef..8d7222106c52 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -13,9 +13,12 @@ extern crate clap;
 extern crate prettytable;
 #[macro_use]
 extern crate lazy_static;
+#[cfg(test)]
 #[macro_use]
 extern crate maplit;
-
+#[macro_use]
+extern crate downcast_rs;
+extern crate backtrace;
 
 mod display;
 mod game;
@@ -24,12 +27,14 @@ mod types;
 mod entities;
 mod messages;
 mod settings;
+mod util;
 
 use clap::App;
 use game::Game;
 use prettytable::format::consts::FORMAT_BOX_CHARS;
 use settings::Settings;
 
+use backtrace::Backtrace;
 use std::io::{self, StdinLock, StdoutLock};
 use std::panic;
 
@@ -43,7 +48,16 @@ fn init(
     w: u16,
     h: u16,
 ) {
-    panic::set_hook(Box::new(|info| error!("{}", info)));
+    panic::set_hook(if settings.logging.print_backtrace {
+        Box::new(|info| {
+            (error!("{}\n{:#?}", info, Backtrace::new()))
+        })
+    } else {
+        Box::new(|info| {
+            (error!("{}\n{:#?}", info, Backtrace::new()))
+        })
+    });
+
     let game = Game::new(settings, stdout, stdin, w, h);
     game.run().unwrap()
 }
diff --git a/src/settings.rs b/src/settings.rs
index 8444bf80eec8..1f205814d1dd 100644
--- a/src/settings.rs
+++ b/src/settings.rs
@@ -4,13 +4,16 @@ use log4rs::append::file::FileAppender;
 use log4rs::config::{Appender, Root};
 use log4rs::encode::pattern::PatternEncoder;
 
-#[derive(Debug, Deserialize)]
+#[derive(Debug, Deserialize, Clone)]
 pub struct Logging {
     #[serde(default = "Logging::default_level")]
     pub level: LevelFilter,
 
     #[serde(default = "Logging::default_file")]
     pub file: String,
+
+    #[serde(default = "Logging::default_print_backtrace")]
+    pub print_backtrace: bool,
 }
 
 impl Default for Logging {
@@ -18,6 +21,7 @@ impl Default for Logging {
         Logging {
             level: LevelFilter::Off,
             file: "debug.log".to_string(),
+            print_backtrace: true,
         }
     }
 }
@@ -44,9 +48,13 @@ impl Logging {
     fn default_file() -> String {
         Logging::default().file
     }
+
+    fn default_print_backtrace() -> bool {
+        Logging::default().print_backtrace
+    }
 }
 
-#[derive(Debug, Deserialize)]
+#[derive(Debug, Deserialize, Clone)]
 pub struct Settings {
     pub seed: Option<u64>,
     pub logging: Logging,
diff --git a/src/types/collision.rs b/src/types/collision.rs
new file mode 100644
index 000000000000..f41e30fc516a
--- /dev/null
+++ b/src/types/collision.rs
@@ -0,0 +1,8 @@
+/// Describes a kind of game collision
+pub enum Collision {
+    /// Stop moving - you can't move there!
+    Stop,
+
+    /// Moving into an entity at the given position indicates combat
+    Combat,
+}
diff --git a/src/types/entity_map.rs b/src/types/entity_map.rs
new file mode 100644
index 000000000000..2d9f033a79d4
--- /dev/null
+++ b/src/types/entity_map.rs
@@ -0,0 +1,242 @@
+use crate::types::Position;
+use crate::types::Positioned;
+use crate::types::PositionedMut;
+use std::collections::hash_map::HashMap;
+use std::collections::BTreeMap;
+use std::iter::FromIterator;
+
+pub type EntityID = u32;
+
+#[derive(Debug)]
+pub struct EntityMap<A> {
+    by_position: BTreeMap<Position, Vec<EntityID>>,
+    by_id: HashMap<EntityID, A>,
+    last_id: EntityID,
+}
+
+// impl<A: Debug> ArbitraryF1<A> for EntityMap<A> {
+//     type Parameters = ();
+//     fn lift1_with<AS>(base: AS, _: Self::Parameters) -> BoxedStrategy<Self>
+//     where
+//         AS: Strategy<Value = A> + 'static,
+//     {
+//         unimplemented!()
+//     }
+//     // type Strategy = strategy::Just<Self>;
+//     // fn arbitrary_with(params : Self::Parameters) -> Self::Strategy;
+// }
+
+// impl<A: Arbitrary> Arbitrary for EntityMap<A> {
+//     type Parameters = A::Parameters;
+//     type Strategy = BoxedStrategy<Self>;
+//     fn arbitrary_with(params: Self::Parameters) -> Self::Strategy {
+//         let a_strat: A::Strategy = Arbitrary::arbitrary_with(params);
+//         ArbitraryF1::lift1::<A::Strategy>(a_strat)
+//     }
+// }
+
+const BY_POS_INVARIANT: &'static str =
+    "Invariant: All references in EntityMap.by_position should point to existent references in by_id";
+
+impl<A> EntityMap<A> {
+    pub fn new() -> EntityMap<A> {
+        EntityMap {
+            by_position: BTreeMap::new(),
+            by_id: HashMap::new(),
+            last_id: 0,
+        }
+    }
+
+    pub fn len(&self) -> usize {
+        self.by_id.len()
+    }
+
+    /// Returns a list of all entities at the given position
+    pub fn at<'a>(&'a self, pos: Position) -> Vec<&'a A> {
+        // self.by_position.get(&pos).iter().flat_map(|eids| {
+        //     eids.iter()
+        //         .map(|eid| self.by_id.get(eid).expect(BY_POS_INVARIANT))
+        // })
+        // gross.
+        match self.by_position.get(&pos) {
+            None => Vec::new(),
+            Some(eids) => {
+                let mut res = Vec::new();
+                for eid in eids {
+                    res.push(self.by_id.get(eid).expect(BY_POS_INVARIANT));
+                }
+                res
+            }
+        }
+    }
+
+    /// Remove all entities at the given position
+    pub fn remove_all_at(&mut self, pos: Position) {
+        self.by_position.remove(&pos).map(|eids| {
+            eids.iter()
+                .map(|eid| self.by_id.remove(&eid).expect(BY_POS_INVARIANT));
+        });
+    }
+
+    pub fn get<'a>(&'a self, id: EntityID) -> Option<&'a A> {
+        self.by_id.get(&id)
+    }
+
+    pub fn entities<'a>(&'a self) -> impl Iterator<Item = &'a A> {
+        self.by_id.values()
+    }
+
+    pub fn entities_mut<'a>(&'a mut self) -> impl Iterator<Item = &'a mut A> {
+        self.by_id.values_mut()
+    }
+
+    pub fn ids(&self) -> impl Iterator<Item = &EntityID> {
+        self.by_id.keys()
+    }
+
+    fn next_id(&mut self) -> EntityID {
+        self.last_id += 1;
+        self.last_id
+    }
+}
+
+impl<A: Positioned> EntityMap<A> {
+    pub fn insert(&mut self, entity: A) -> EntityID {
+        let pos = entity.position();
+        let entity_id = self.next_id();
+        self.by_id.entry(entity_id).or_insert(entity);
+        self.by_position
+            .entry(pos)
+            .or_insert(Vec::new())
+            .push(entity_id);
+        entity_id
+    }
+}
+
+impl<A: Positioned> FromIterator<A> for EntityMap<A> {
+    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
+        let mut em = EntityMap::new();
+        for ent in iter {
+            em.insert(ent);
+        }
+        em
+    }
+}
+
+impl<A: PositionedMut> EntityMap<A> {
+    pub fn update_position(
+        &mut self,
+        entity_id: EntityID,
+        new_position: Position,
+    ) {
+        let mut old_pos = None;
+        if let Some(entity) = self.by_id.get_mut(&entity_id) {
+            if entity.position() == new_position {
+                return;
+            }
+            old_pos = Some(entity.position());
+            entity.set_position(new_position);
+        }
+        old_pos.map(|p| {
+            self.by_position
+                .get_mut(&p)
+                .map(|es| es.retain(|e| *e != entity_id));
+
+            self.by_position
+                .entry(new_position)
+                .or_insert(Vec::new())
+                .push(entity_id);
+        });
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::types::PositionedMut;
+    use proptest::prelude::*;
+    use proptest_derive::Arbitrary;
+
+    #[derive(Debug, Arbitrary, PartialEq, Eq, Clone)]
+    struct TestEntity {
+        position: Position,
+        name: String,
+    }
+
+    impl Positioned for TestEntity {
+        fn position(&self) -> Position {
+            self.position
+        }
+    }
+
+    impl PositionedMut for TestEntity {
+        fn set_position(&mut self, pos: Position) {
+            self.position = pos
+        }
+    }
+
+    fn gen_entity_map() -> BoxedStrategy<EntityMap<TestEntity>> {
+        any::<Vec<TestEntity>>()
+            .prop_map(|ents| {
+                ents.iter()
+                    .map(|e| e.clone())
+                    .collect::<EntityMap<TestEntity>>()
+            })
+            .boxed()
+    }
+
+    proptest! {
+        #![proptest_config(ProptestConfig::with_cases(10))]
+
+        #[test]
+        fn test_entity_map_len(items: Vec<TestEntity>) {
+            let mut map = EntityMap::new();
+            assert_eq!(map.len(), 0);
+            for ent in &items {
+                map.insert(ent);
+            }
+            assert_eq!(map.len(), items.len());
+        }
+
+        #[test]
+        fn test_entity_map_getset(
+            mut em in gen_entity_map(),
+            ent: TestEntity
+        ) {
+            em.insert(ent.clone());
+            assert!(em.at(ent.position).iter().any(|e| **e == ent))
+        }
+
+        #[test]
+        fn test_entity_map_set_iter_contains(
+            mut em in gen_entity_map(),
+            ent: TestEntity
+        ) {
+            em.insert(ent.clone());
+            assert!(em.entities().any(|e| *e == ent))
+        }
+
+        #[test]
+        fn test_update_position(
+            mut em in gen_entity_map(),
+            ent: TestEntity,
+            new_position: Position,
+        ) {
+            let original_position = ent.position();
+            let entity_id = em.insert(ent.clone());
+            em.update_position(entity_id, new_position);
+
+            if new_position != original_position {
+                assert_eq!(em.at(original_position).len(), 0);
+            }
+            assert_eq!(
+                em.get(entity_id).map(|e| e.position()),
+                Some(new_position)
+            );
+            assert_eq!(
+                em.at(new_position).iter().map(|e| e.name.clone()).collect::<Vec<_>>(),
+                vec![ent.name]
+            )
+        }
+    }
+}
diff --git a/src/types/mod.rs b/src/types/mod.rs
index ab66a50cc218..c0375a382fe2 100644
--- a/src/types/mod.rs
+++ b/src/types/mod.rs
@@ -1,7 +1,11 @@
 use std::cmp::Ordering;
 use std::ops;
+use std::rc::Rc;
+pub mod collision;
 pub mod command;
 pub mod direction;
+pub mod entity_map;
+pub use collision::Collision;
 pub use direction::Direction;
 pub use direction::Direction::{Down, Left, Right, Up};
 use proptest_derive::Arbitrary;
@@ -43,13 +47,16 @@ impl BoundingBox {
         }
     }
 
-    pub fn from_corners(top_left: Position, lower_right: Position) -> BoundingBox {
+    pub fn from_corners(
+        top_left: Position,
+        lower_right: Position,
+    ) -> BoundingBox {
         BoundingBox {
             position: top_left,
             dimensions: Dimensions {
                 w: (lower_right.x - top_left.x) as u16,
                 h: (lower_right.y - top_left.y) as u16,
-            }
+            },
         }
     }
 
@@ -70,7 +77,11 @@ impl BoundingBox {
     /// Moves the top right corner of the bounding box by the offset specified
     /// by the given position, keeping the lower right corner in place
     pub fn move_tr_corner(self, offset: Position) -> BoundingBox {
-        self + offset - Dimensions { w: offset.x as u16, h: offset.y as u16 }
+        self + offset
+            - Dimensions {
+                w: offset.x as u16,
+                h: offset.y as u16,
+            }
     }
 }
 
@@ -94,7 +105,7 @@ impl ops::Sub<Dimensions> for BoundingBox {
     }
 }
 
-#[derive(Clone, Copy, Debug, PartialEq, Eq, Arbitrary)]
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Arbitrary, Hash, Ord)]
 pub struct Position {
     /// x (horizontal) position
     #[proptest(strategy = "std::ops::Range::<i16>::from(0..100)")]
@@ -105,6 +116,10 @@ pub struct Position {
     pub y: i16,
 }
 
+pub fn pos(x: i16, y: i16) -> Position {
+    Position { x, y }
+}
+
 pub const ORIGIN: Position = Position { x: 0, y: 0 };
 pub const UNIT_POSITION: Position = Position { x: 1, y: 1 };
 
@@ -241,6 +256,47 @@ pub trait Positioned {
     }
 }
 
+pub trait PositionedMut: Positioned {
+    fn set_position(&mut self, pos: Position);
+}
+
+// impl<A, I> Positioned for A where A : Deref<Target = I>, I: Positioned {
+//     fn position(&self) -> Position {
+//         self.position()
+//     }
+// }
+
+impl<T: Positioned> Positioned for Box<T> {
+    fn position(&self) -> Position {
+        (**self).position()
+    }
+}
+
+impl<'a, T: Positioned> Positioned for &'a T {
+    fn position(&self) -> Position {
+        (**self).position()
+    }
+}
+
+impl<'a, T: Positioned> Positioned for &'a mut T {
+    fn position(&self) -> Position {
+        (**self).position()
+    }
+}
+
+impl<'a, T: Positioned> Positioned for Rc<T> {
+    fn position(&self) -> Position {
+        (**self).position()
+    }
+}
+
+impl<'a, T: PositionedMut> PositionedMut for &'a mut T {
+    fn set_position(&mut self, pos: Position) {
+        (**self).set_position(pos)
+    }
+}
+
+#[macro_export]
 macro_rules! positioned {
     ($name:ident) => {
         positioned!($name, position);
@@ -254,6 +310,20 @@ macro_rules! positioned {
     };
 }
 
+#[macro_export]
+macro_rules! positioned_mut {
+    ($name:ident) => {
+        positioned_mut!($name, position);
+    };
+    ($name:ident, $attr:ident) => {
+        impl crate::types::PositionedMut for $name {
+            fn set_position(&mut self, pos: Position) {
+                self.$attr = pos;
+            }
+        }
+    };
+}
+
 /// A number of ticks
 #[derive(Clone, Copy, Debug, PartialEq, Eq, Arbitrary)]
 pub struct Ticks(pub u16);
diff --git a/src/util/mod.rs b/src/util/mod.rs
new file mode 100644
index 000000000000..e69de29bb2d1
--- /dev/null
+++ b/src/util/mod.rs