From 6e114371296d849132e538817a16877866fa84f3 Mon Sep 17 00:00:00 2001
From: Bjørn Lindeijer <bjorn@lindeijer.nl>
Date: Wed, 9 Feb 2005 18:57:27 +0000
Subject: More of a start on pathfinding, but still just a start.

---
 src/map.cpp | 37 ++++++++++++++++++++++++++++++++++++-
 src/map.h   | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 68 insertions(+), 1 deletion(-)

diff --git a/src/map.cpp b/src/map.cpp
index a9437f9f..d7ccb4d1 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -25,6 +25,7 @@
 #include "map.h"
 #include "log.h"
 #include "being.h"
+#include <queue>
 
 #include <stdio.h>
 #ifdef WIN32
@@ -78,9 +79,19 @@ Tile::Tile():
 {
 }
 
+Location::Location(int x, int y, Tile *tile):
+    x(x), y(y), tile(tile)
+{
+}
+
+bool Location::operator< (const Location &loc) const
+{
+   return tile->Fcost < loc.tile->Fcost; 
+}
 
 Map::Map():
-    width(0), height(0)
+    width(0), height(0),
+    onClosedList(1), onOpenList(2)
 {
     tiles = new Tile[width * height];
 }
@@ -193,9 +204,33 @@ int Map::getHeight()
 
 PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
 {
+    // Declare open list, a list with open tiles sorted on F cost
+    std::priority_queue<Location> openList;
+
     // Return when destination not walkable
     if (!getWalk(destX, destY)) return NULL;
 
+    // Reset starting square's G cost to 0
+    Tile *startTile = &tiles[startX + startY * width];
+    startTile->Gcost = 0;
+
+    // Add the start point to the open list
+    openList.push(Location(startX, startY, startTile));
+
+    // Keep trying new open tiles until no more tiles to try or target found
+    while (!openList.empty()) {
+        // Take the location with the lowest F cost from the open list, and
+        // add it to the closed list.
+        Location curr = openList.top();
+        openList.pop();
+        curr.tile->whichList = onClosedList;
+    }
+
+    // Two new values to indicate wether a tile is on the open or closed list,
+    // this way we don't have to clear all the values between each pathfinding.
+    onClosedList += 2;
+    onOpenList += 2;
+
     // No path found
     return NULL;
 }
diff --git a/src/map.h b/src/map.h
index be0364d7..38b880b7 100644
--- a/src/map.h
+++ b/src/map.h
@@ -30,9 +30,15 @@
 #define TILE_WALKABLE  1
 #define TILE_ANIMATED  2
 
+/**
+ * A tile on a tile map.
+ */
 class Tile
 {
     public:
+        /**
+         * Constructor.
+         */
         Tile();
 
         // Tile data
@@ -45,6 +51,29 @@ class Tile
         int parentX, parentY;
 };
 
+/**
+ * A location on a tile map. Used for pathfinding, open list.
+ */
+class Location
+{
+    public:
+        /**
+         * Constructor.
+         */
+        Location(int x, int y, Tile *tile);
+
+        /**
+         * Comparison operator.
+         */
+        bool operator< (const Location &loc) const;
+
+        int x, y;
+        Tile *tile;
+};
+
+/**
+ * A tile map.
+ */
 class Map
 {
     public:
@@ -106,6 +135,9 @@ class Map
     private:
         int width, height;
         Tile *tiles;
+
+        // Pathfinding members
+        int onClosedList, onOpenList;
 };
 
 extern Map tiledMap;
-- 
cgit v1.2.3-60-g2f50