-added pathfinding

9 files changed, 211 insertions, 74 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 81c029d..565eef8 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,6 +3,7 @@ name = "roma"
 version = "0.1.0"
 dependencies = [
  "pancurses 0.11.0 (git+https://github.com/ihalila/pancurses)",
+ "pathfinding 0.2.4-pre (git+https://github.com/samueltardieu/pathfinding)",
  "rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -12,6 +13,16 @@ version = "0.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "either"
+version = "1.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "fixedbitset"
+version = "0.1.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "fuchsia-zircon"
 version = "0.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -33,6 +44,14 @@ version = "0.3.54"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "itertools"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "either 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "libc"
 version = "0.2.32"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -43,6 +62,14 @@ version = "0.3.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "matrixmultiply"
+version = "0.1.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rawpointer 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "ncurses"
 version = "5.86.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -53,6 +80,30 @@ dependencies = [
 ]
 
 [[package]]
+name = "ndarray"
+version = "0.10.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "itertools 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "matrixmultiply 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-complex 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "num-complex"
+version = "0.1.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "num-traits 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "num-traits"
+version = "0.1.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "pancurses"
 version = "0.11.0"
 source = "git+https://github.com/ihalila/pancurses#8f81661687a32a5b0a1cb65b1bb7b46c9206b593"
@@ -64,6 +115,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "pathfinding"
+version = "0.2.4-pre"
+source = "git+https://github.com/samueltardieu/pathfinding#ee5309b3571b7d2c8970f35918f0a40318e02573"
+dependencies = [
+ "fixedbitset 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "ndarray 0.10.12 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "pdcurses-sys"
 version = "0.5.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -86,15 +147,29 @@ dependencies = [
  "libc 0.2.32 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
+[[package]]
+name = "rawpointer"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [metadata]
 "checksum bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "aad18937a628ec6abcd26d1489012cc0e18c21798210f491af69ded9b881106d"
+"checksum either 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e311a7479512fbdf858fb54d91ec59f3b9f85bc0113659f46bba12b199d273ce"
+"checksum fixedbitset 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)" = "85cb8fec437468d86dc7c83ca7cfc933341d561873275f22dd5eedefa63a6478"
 "checksum fuchsia-zircon 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f6c0581a4e363262e52b87f59ee2afe3415361c6ec35e665924eb08afe8ff159"
 "checksum fuchsia-zircon-sys 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "43f3795b4bae048dc6123a6b972cadde2e676f9ded08aef6bb77f5f157684a82"
 "checksum gcc 0.3.54 (registry+https://github.com/rust-lang/crates.io-index)" = "5e33ec290da0d127825013597dbdfc28bee4964690c7ce1166cbc2a7bd08b1bb"
+"checksum itertools 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2c52051d3fd3b505796a0ee90f2e5ec43213808585e8adc4d0182492cf62751a"
 "checksum libc 0.2.32 (registry+https://github.com/rust-lang/crates.io-index)" = "56cce3130fd040c28df6f495c8492e5ec5808fb4c9093c310df02b0c8f030148"
 "checksum log 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "880f77541efa6e5cc74e76910c9884d9859683118839d6a1dc3b11e63512565b"
+"checksum matrixmultiply 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)" = "cac1a66eab356036af85ea093101a14223dc6e3f4c02a59b7d572e5b93270bf7"
 "checksum ncurses 5.86.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e404cc633e25a50d3427c4202313a33375c0a559902cecce1dd2893dd226feb0"
+"checksum ndarray 0.10.12 (registry+https://github.com/rust-lang/crates.io-index)" = "4081816658dbd5f219dc4ef1ec842496b7dc4987ad8d613c6eb8823a5f532ed8"
+"checksum num-complex 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "503e668405c5492d67cf662a81e05be40efe2e6bcf10f7794a07bd9865e704e6"
+"checksum num-traits 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "99843c856d68d8b4313b03a17e33c4bb42ae8f6610ea81b28abe076ac721b9b0"
 "checksum pancurses 0.11.0 (git+https://github.com/ihalila/pancurses)" = "<none>"
+"checksum pathfinding 0.2.4-pre (git+https://github.com/samueltardieu/pathfinding)" = "<none>"
 "checksum pdcurses-sys 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "923a29f049a83da029e6e96d2c1de8a9e3ca7c41ab1d2a9e3ab2c85a27725cf2"
 "checksum pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "3a8b4c6b8165cd1a1cd4b9b120978131389f64bdaf456435caa41e630edba903"
 "checksum rand 0.3.17 (registry+https://github.com/rust-lang/crates.io-index)" = "61efcbcd9fa8d8fbb07c84e34a8af18a1ff177b449689ad38a6e9457ecc7b2ae"
+"checksum rawpointer 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ebac11a9d2e11f2af219b8b8d833b76b1ea0e054aa0e8d8e9e4cbde353bdf019"
diff --git a/Cargo.toml b/Cargo.toml
index 54443f9..304a2cf 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -6,4 +6,4 @@ authors = ["Tom Barrett <tombarrett@siu.edu>"]
 [dependencies]
 pancurses = { git = "https://github.com/ihalila/pancurses" }
 rand = "0.3"
-
+pathfinding = { git = "https://github.com/samueltardieu/pathfinding" }
diff --git a/src/character.rs b/src/character.rs
index 4c7f7dc..c8101f5 100644
--- a/src/character.rs
+++ b/src/character.rs
@@ -1,36 +1,91 @@
 extern crate rand;
 use character::rand::Rng;
 
-use location::Location;
+extern crate pathfinding;
+use self::pathfinding::astar;
 
-pub struct Character{
-    pub symbol      : char,
-    pub color       : u8,
-    pub location    : Location,
-}
+use constants::Orders;
+use location::Location;
 
-impl Copy for Character {}
-impl Clone for Character {
-    fn clone(&self) -> Character {
-        *self
-    }
+#[derive(Clone)]
+pub struct Character {
+    pub symbol          : char,
+    pub color           : u8,
+    pub order           : u8,
+    pub location        : Location,
+    pub needs_path      : bool,
+    desired_location    : Option<Location>,
+    path                : Option<Vec<Location>>,
 }
 
 impl Character {
     pub fn new(symbol : char, color : u8, location : Location) -> Character {
         Character {
-            symbol      : symbol,
-            color       : color,
-            location    : location,
+            symbol              : symbol,
+            color               : color,
+            order               : Orders::Move as u8,
+            location            : location,
+            desired_location    : Some(Location(200,200)),
+            needs_path          : false,
+            path                : None,
         }
     }
 
-    pub fn action(&mut self, free_spaces : Vec<Location>) {
-        self.wander(free_spaces);
+    pub fn action(&mut self, free_spaces : Vec<(Location,usize)>) {
+        if self.order == Orders::Wander as u8 {
+            self.needs_path == false;
+            self.wander(free_spaces);
+        }
+        else if self.order == Orders::Move as u8 {
+            self.move_toward_desired(free_spaces);
+        }
     }
 
-    fn wander(&mut self, free_spaces : Vec<Location>) {
+    fn wander(&mut self, free_spaces : Vec<(Location, usize)>) {
         let direction = rand::thread_rng().gen_range(0, free_spaces.len());
-        self.location = free_spaces[direction];
+        self.location = free_spaces[direction].0;
+    }
+
+    fn move_toward_desired(&mut self, free_spaces : Vec<(Location, usize)>) {
+        let mut moved = false;
+        match self.path {
+            None => self.needs_path = true,
+            Some(ref mut calculated_path) => {
+                self.needs_path = false;
+                if calculated_path.len() > 0 {
+                    let next_location = calculated_path.pop().unwrap();
+                    for free_space in free_spaces {
+                        if next_location == free_space.0 {
+                            self.location = next_location;
+                            moved = true;
+                        }
+                    }
+                }
+                else {
+                    self.desired_location = None;
+                    self.order = Orders::Wander as u8;
+                }
+            }
+        }
+        if !moved {
+            self.path = None;
+        }
+    }
+
+    pub fn calculate_path(&mut self, impassable : Vec<(Location, usize)>) {
+        match self.desired_location {
+            None => (),
+            Some(target) => {
+                let location = self.location;
+                let result = astar(&location,
+                                       |l| l.neighbours(impassable.clone()),
+                                       |l| l.distance(&target),
+                                       |l| *l == target);
+                let mut result = result.expect("zz").0;
+                result.reverse();
+                result.pop();
+                self.path = Some(result);
+            }
+        }
     }
 }
diff --git a/src/constants.rs b/src/constants.rs
index 7219cd4..84e7653 100644
--- a/src/constants.rs
+++ b/src/constants.rs
@@ -1,4 +1,5 @@
 #[allow(dead_code)]
+
 pub enum Colors {
     None,
     Grass,
@@ -6,3 +7,9 @@ pub enum Colors {
     White,
     BlueUnit,
 }
+
+pub enum Orders {
+    Wait,
+    Move,
+    Wander,
+}
diff --git a/src/list.rs b/src/list.rs
index cf0607f..a429ab2 100644
--- a/src/list.rs
+++ b/src/list.rs
@@ -13,7 +13,7 @@ impl List {
     pub fn new(impassable_locations : Vec<Location>) -> List {
         let mut men = Vec::new();
         for i in 0..3 {
-            men.push(Character::new('@', Colors::BlueUnit as u8, Location{ x : 150, y : 150+i }));
+            men.push(Character::new('@', Colors::BlueUnit as u8, Location(150,150+i)));
         }
         List {
             men                     : men,
@@ -26,21 +26,26 @@ impl List {
             let location = self.men[i].location.clone();
             let free_locations = self.get_free_locations(location);
             self.men[i].action(free_locations);
+
+            if self.men[i].needs_path {
+                let impassable = self.get_all_impassable();
+                self.men[i].calculate_path(impassable);
+            }
         }
     }
 
-    fn get_free_locations(&mut self, location : Location) -> Vec<Location> {
-        let mut potential_locations = location.get_around();
+    fn get_free_locations(&mut self, location : Location) -> Vec<(Location, usize)> {
+        let mut potential_locations = location.neighbours(Vec::new());
 
         potential_locations.retain(|potential_location| {
             let mut keep = true;
             for man in self.men.iter() {
-                if potential_location == &man.location {
+                if potential_location.0 == man.location {
                     keep = false;
                 }
             }
             for impassable_location in self.impassable_locations.iter() {
-                if potential_location == impassable_location {
+                if potential_location.0 == *impassable_location {
                     keep = false;
                 }
             }
@@ -49,4 +54,15 @@ impl List {
 
         potential_locations
     }
+
+    fn get_all_impassable(&mut self) -> Vec<(Location, usize)> {
+        let mut impassable = Vec::new();
+        for man in self.men.iter() {
+            impassable.push((man.location, 1));
+        }
+        for impassable_location in self.impassable_locations.iter() {
+            impassable.push((*impassable_location,1));
+        }
+        impassable
+    }
 }
diff --git a/src/location.rs b/src/location.rs
index eb8110c..ca40700 100644
--- a/src/location.rs
+++ b/src/location.rs
@@ -1,40 +1,24 @@
-use std::cmp;
-
-pub struct Location {
-    pub x : i32, 
-    pub y : i32
-}
-
-impl Copy for Location {}
-impl Clone for Location {
-    fn clone(&self) -> Location {
-        *self
-    }
-}
-
-impl cmp::PartialEq for Location {
-    fn eq(&self, rhs : &Location) -> bool {
-        if self.x == rhs.x && self.y == rhs.y {
-            true
-        }
-        else {
-            false
-        }
-    }
-}
+#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, PartialOrd)]
+pub struct Location(pub i32, pub i32);
 
 impl Location {
-    pub fn get_around(self) -> Vec<Location> {
-        let mut around = Vec::new();
-        around.push(Location { x : self.x, y : self.y });
-        around.push(Location { x : self.x+1, y : self.y });
-        around.push(Location { x : self.x-1, y : self.y });
-        around.push(Location { x : self.x, y : self.y+1 });
-        around.push(Location { x : self.x, y : self.y-1 });
-        around.push(Location { x : self.x+1, y : self.y+1 });
-        around.push(Location { x : self.x-1, y : self.y-1 });
-        around.push(Location { x : self.x+1, y : self.y-1 });
-        around.push(Location { x : self.x-1, y : self.y+1 });
-        around
+    pub fn distance(&self, other: &Location) -> usize {
+        (((self.0 - other.0).pow(2) + (self.1 - other.1).pow(2)) as f64).sqrt() as usize
+    }
+    pub fn neighbours(self, impassable : Vec<(Location, usize)>) -> Vec<(Location, usize)> {
+        let mut nearby = vec![Location(self.0 + 1, self.1), Location(self.0 - 1, self.1),
+                              Location(self.0, self.1 + 1), Location(self.0, self.1 - 1),
+                              Location(self.0 + 1, self.1 + 1), Location(self.0 - 1, self.1 - 1),
+                              Location(self.0 + 1, self.1 - 1), Location(self.0 - 1, self.1 + 1)];
+        nearby.retain(|potential_location| {
+            let mut keep = true;
+            for location in impassable.iter() {
+                if *potential_location == location.0 {
+                    keep = false;
+                }
+            }
+            keep
+        });
+        nearby.into_iter().map(|p| (p, 1)).collect()
     }
 }
diff --git a/src/main.rs b/src/main.rs
index ac74781..7044467 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -36,7 +36,7 @@ fn main() {
     let mut map = Map::new();
     let mut view = View::new(main.get_max_yx(), &map.window);
 
-    let mut cursor = Character::new('X', Colors::White as u8, Location{ x : 150, y : 150});
+    let mut cursor = Character::new('X', Colors::White as u8, Location(150, 150));
 
     let mut list = List::new(map.impassable.to_vec());
 
@@ -44,10 +44,10 @@ fn main() {
         match main.getch() {
             Some(Input::Character(c)) => {
                 match c {
-                    'h' => cursor.location.y -= 1,
-                    'l' => cursor.location.y += 1,
-                    'k' => cursor.location.x -= 1,
-                    'j' => cursor.location.x += 1,
+                    'h' => cursor.location.1 -= 1,
+                    'l' => cursor.location.1 += 1,
+                    'k' => cursor.location.0 -= 1,
+                    'j' => cursor.location.0 += 1,
                     'q' => break,
                     _ => (),
                 }
@@ -64,7 +64,7 @@ fn main() {
         }
         map.draw(&cursor);
 
-        view.center(cursor, &map.window);
+        view.center(cursor.clone(), &map.window);
     }
 
 	endwin();
diff --git a/src/map.rs b/src/map.rs
index 59d53c7..a108929 100644
--- a/src/map.rs
+++ b/src/map.rs
@@ -34,20 +34,20 @@ impl Map {
         for (i, row) in map_data.iter().enumerate() {
             for (j, index) in row.chars().enumerate() {
                 match index {
-                    '0' | 'O' => impassable.push(Location{ x : i as i32, y : j as i32 }),
+                    '0' | 'O' => impassable.push(Location(i as i32, j as i32)),
                     _ => (),
                 }
             }
         }
 
         for y in 0..height {
-            impassable.push(Location{ x : 0 as i32, y : y as i32 });
-            impassable.push(Location{ x : width-1 as i32, y : y as i32} );
+            impassable.push(Location(0, y as i32));
+            impassable.push(Location(width-1 as i32, y as i32));
         }
 
         for x in 0..width {
-            impassable.push(Location{ x : x as i32, y : 0 as i32 });
-            impassable.push(Location{ x : x as i32, y : height-1 as i32 });
+            impassable.push(Location(x as i32, 0 as i32));
+            impassable.push(Location(x as i32, height-1));
         }
 
         Map {
@@ -61,7 +61,7 @@ impl Map {
 
     pub fn draw(&self, character : &Character) {
         self.window.attron(ColorPair(character.color));
-        self.window.mvaddch(character.location.x, character.location.y, character.symbol);
+        self.window.mvaddch(character.location.0, character.location.1, character.symbol);
     }
 
     pub fn fill(&mut self) {
diff --git a/src/view.rs b/src/view.rs
index c19ee63..d62454b 100644
--- a/src/view.rs
+++ b/src/view.rs
@@ -23,8 +23,8 @@ impl View {
     }
 
     pub fn center(&mut self, character : Character, map_window : &pancurses::Window) {
-        let c = character.location.x - self.width/2;
-        let r = character.location.y - self.height/2;
+        let c = character.location.0 - self.width/2;
+        let r = character.location.1 - self.height/2;
 
         let (hh, ww) = map_window.get_max_yx();