-added pathfinding

7 files changed, 135 insertions, 73 deletions

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();