New shorter and more flexible pathfinding implementation, which is hopefully

also more stable.

7 files changed, 159 insertions, 30 deletions

diff --git a/src/being.cpp b/src/being.cpp
index d8401673..8207d4a2 100644
--- a/src/being.cpp
+++ b/src/being.cpp
@@ -27,7 +27,7 @@
 
 Being *player_node = NULL;
 
-std::list<Being *> beings;
+std::list<Being*> beings;
 
 PATH_NODE::PATH_NODE(unsigned short x, unsigned short y):
     next(NULL)
@@ -36,13 +36,6 @@ PATH_NODE::PATH_NODE(unsigned short x, unsigned short y):
     this->y = y;
 }
 
-PATH_NODE *calculate_path(
-        unsigned short src_x, unsigned short src_y,
-        unsigned short dest_x, unsigned short dest_y)
-{
-    return find_path(1, src_x, src_y, dest_x, dest_y);
-}
-
 void empty() {
     std::list<Being *>::iterator i;
     for (i = beings.begin(); i != beings.end(); i++) {
diff --git a/src/being.h b/src/being.h
index ed6b4e31..84b693da 100644
--- a/src/being.h
+++ b/src/being.h
@@ -103,10 +103,6 @@ Being *find_node(unsigned int id);
 /** Remove a Being */
 void remove_node(unsigned int id);
 
-PATH_NODE *calculate_path(
-        unsigned short src_x, unsigned short src_y,
-        unsigned short dest_x, unsigned short dest_y);
-
 /** Find a NPC id based on its coordinates */
 unsigned int find_npc(unsigned short x, unsigned short y);
 
diff --git a/src/game.cpp b/src/game.cpp
index e4ec2d45..c68f8e67 100644
--- a/src/game.cpp
+++ b/src/game.cpp
@@ -47,6 +47,7 @@ volatile bool action_time = false;
 int current_npc, server_tick;
 extern unsigned char screen_mode;
 int fps = 0, frame = 0;
+int mouseX = 0, mouseY = 0;
 
 OkDialog *deathNotice = NULL;
 
@@ -265,14 +266,14 @@ void do_input()
             }
         } // End key down
 
-        if (event.button.type == SDL_MOUSEBUTTONDOWN)
+        if (event.type == SDL_MOUSEBUTTONDOWN)
         {
             if (event.button.button == 3)
             {
                 // We click the right button
                 // NPC Call
-                int npc_x = event.motion.x / 32 + camera_x;
-                int npc_y = event.motion.y / 32 + camera_y;
+                int npc_x = event.button.x / 32 + camera_x;
+                int npc_y = event.button.y / 32 + camera_y;
                 int id = find_npc(npc_x, npc_y);
                 if (id != 0)
                 {
@@ -283,7 +284,12 @@ void do_input()
                 }
 
             }
-
+        }
+        else if (event.type == SDL_MOUSEMOTION)
+        {
+            // Update the known mouse position
+            mouseX = event.motion.x;
+            mouseY = event.motion.y;
         }
 
         // Push input to GUI when not used
@@ -377,7 +383,6 @@ void do_input()
         }
 
     } // End if alive
-
 }
 
 int get_packet_length(short id) {
@@ -399,7 +404,7 @@ void do_parse() {
         while (in_size >= (len = get_packet_length(id = RFIFOW(0)))) {
             // Add infos to log file and dump the latest received packet
             char pkt_nfo[60];
-            sprintf(pkt_nfo,"In-buffer size: %i Packet id: %x Packet length: %i",in_size,RFIFOW(0),len);
+            sprintf(pkt_nfo,"In-buffer size: %i Packet id: %x Packet length: %i", in_size, RFIFOW(0), len);
             /*
             log_hex("Packet", "Packet_ID", RFIFOW(0));
             log_int("Packet", "Packet_length", get_length(RFIFOW(0)));
@@ -418,7 +423,7 @@ void do_parse() {
             fclose(file);
 //#endif 
             // Parse packet based on their id
-            switch(id) {
+            switch (id) {
                 // Received speech
                 case 0x008d:
                     temp = (char *)malloc(RFIFOW(2)-7);
@@ -549,9 +554,11 @@ void do_parse() {
                         being->job = RFIFOW(14);
                         add_node(being);
                     }
-                    being->setPath(calculate_path(get_src_x(RFIFOP(50)),
-                            get_src_y(RFIFOP(50)),get_dest_x(RFIFOP(50)),
-                            get_dest_y(RFIFOP(50))));
+                    being->setPath(tiledMap.findPath(
+                                get_src_x(RFIFOP(50)),
+                                get_src_y(RFIFOP(50)),
+                                get_dest_x(RFIFOP(50)),
+                                get_dest_y(RFIFOP(50))));
                     break;
                     // Being moving
                 case 0x01da:
diff --git a/src/game.h b/src/game.h
index 13e8c472..d15e6a83 100644
--- a/src/game.h
+++ b/src/game.h
@@ -62,6 +62,7 @@ extern char walk_status;
 extern unsigned short src_x, src_y, x, y;
 extern volatile int tick_time;
 extern int server_tick;
+extern int mouseX, mouseY;
 
 /**
  * Main game loop
diff --git a/src/graphic/graphic.cpp b/src/graphic/graphic.cpp
index bff5a29b..da18b109 100644
--- a/src/graphic/graphic.cpp
+++ b/src/graphic/graphic.cpp
@@ -118,7 +118,7 @@ int get_x_offset(Being *being) {
     if (being->action == WALK) {
         if (direction != NORTH && direction != SOUTH) {
             offset = being->frame + 1;
-            if (offset == 5)offset = 0;
+            if (offset == 5) offset = 0;
             offset *= 8;
             if (direction == WEST || direction == NW || direction == SW) {
                 offset = -offset;
@@ -486,6 +486,28 @@ void Engine::draw()
 #endif
         }
     }
+
+#ifdef __DEBUG
+    // Draw a debug path
+    PATH_NODE *debugPath = tiledMap.findPath(
+            player_node->x, player_node->y,
+            mouseX / 32 + camera_x, mouseY / 32 + camera_y);
+
+    while (debugPath)
+    {
+        SDL_Rect destRect;
+        destRect.x = (debugPath->x - camera_x) * 32 - offset_x + 12;
+        destRect.y = (debugPath->y - camera_y) * 32 - offset_y + 12;
+        destRect.w = 8;
+        destRect.h = 8;
+        SDL_FillRect(screen, &destRect, SDL_MapRGB(screen->format, 255, 0, 0));
+
+        // Move to the next node
+        PATH_NODE *temp = debugPath->next;
+        delete debugPath;
+        debugPath = temp;
+    }
+#endif
     
     // Draw player speech
     beingIterator = beings.begin();
@@ -526,8 +548,8 @@ void Engine::draw()
     gui->draw();
 
     std::stringstream debugStream;
-    debugStream << "[" << fps << " fps] ";// <<
-    //    (mouse_x / 32 + camera_x) << ", " << (mouse_y / 32 + camera_y);
+    debugStream << "[" << fps << " fps] " <<
+        (mouseX / 32 + camera_x) << ", " << (mouseY / 32 + camera_y);
     debugInfo->setCaption(debugStream.str());
     debugInfo->adjustSize();
 }
diff --git a/src/map.cpp b/src/map.cpp
index c4d9493b..597afa49 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -87,7 +87,7 @@ Location::Location(int x, int y, Tile *tile):
 
 bool Location::operator< (const Location &loc) const
 {
-   return tile->Fcost < loc.tile->Fcost; 
+   return tile->Fcost > loc.tile->Fcost; 
 }
 
 
@@ -194,6 +194,11 @@ int Map::getTile(int x, int y, int layer)
     return tiles[x + y * width].layers[layer];
 }
 
+Tile *Map::getTile(int x, int y)
+{
+    return &tiles[x + y * width];
+}
+
 int Map::getWidth()
 {
     return width;
@@ -212,22 +217,95 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
     // 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];
+    // Reset starting tile's G cost to 0
+    Tile *startTile = getTile(startX, startY);
     startTile->Gcost = 0;
 
     // Add the start point to the open list
     openList.push(Location(startX, startY, startTile));
 
+    bool foundPath = false;
+
     // Keep trying new open tiles until no more tiles to try or target found
-    while (!openList.empty()) {
+    while (!openList.empty() && !foundPath)
+    {
         // 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;
 
-
+        // Check the adjacent tiles
+        for (int dy = -1; dy <= 1; dy++)
+        {
+            for (int dx = -1; dx <= 1; dx++)
+            {
+                // Calculate location of tile to check
+                int x = curr.x + dx;
+                int y = curr.y + dy;
+
+                // Skip if if we're checking the same tile we're leaving
+                // from, or if the new location falls outside of the map
+                // boundaries
+                if ((dx == 0 && dy == 0) ||
+                        (x < 0 || y < 0 || x >= width || y >= height))
+                {
+                    continue;
+                }
+
+                Tile *newTile = getTile(x, y);
+
+                // Skip if the tile is on the closed list or is not walkable
+                if (newTile->whichList == onClosedList || !getWalk(x, y))
+                {
+                    continue;
+                }
+
+                // Calculate G cost for this route, 10 for moving straight and
+                // 14 for moving diagonal
+                int Gcost = curr.tile->Gcost + (dx == 0 || dy == 0) ? 10 : 14;
+
+                if (newTile->whichList != onOpenList)
+                {
+                    // Found a new tile (not on open nor on closed list)
+                    // Update Hcost of the new tile using Manhatten distance
+                    newTile->Hcost = 10 * (abs(x - destX) + abs(y - destY));
+
+                    // Set the current tile as the parent of the new tile
+                    newTile->parentX = curr.x;
+                    newTile->parentY = curr.y;
+
+                    // Update Gcost and Fcost of new tile
+                    newTile->Gcost = Gcost;
+                    newTile->Fcost = newTile->Gcost + newTile->Hcost;
+
+                    if (x != destX || y != destY) {
+                        // Add this tile to the open list
+                        newTile->whichList = onOpenList;
+                        openList.push(Location(x, y, newTile));
+                    }
+                    else {
+                        // Target location was found
+                        foundPath = true;
+                    }
+                }
+                else if (Gcost < newTile->Gcost)
+                {
+                    // Found a shorter route.
+                    // Update Gcost and Fcost of the new tile
+                    newTile->Gcost = Gcost;
+                    newTile->Fcost = newTile->Gcost + newTile->Hcost;
+
+                    // Set the current tile as the parent of the new tile
+                    newTile->parentX = curr.x;
+                    newTile->parentY = curr.y;
+
+                    // Add this tile to the open list (it's already
+                    // there, but this instance has a lower F score)
+                    openList.push(Location(x, y, newTile));
+                }
+            }
+        }
     }
 
     // Two new values to indicate wether a tile is on the open or closed list,
@@ -235,6 +313,33 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
     onClosedList += 2;
     onOpenList += 2;
 
+    // If a path has been found, iterate backwards using the parent locations
+    // to extract it.
+    if (foundPath) {
+        //printf("Found path from (%d, %d) to (%d, %d):\n",
+        //        startX, startY, destX, destY);
+        PATH_NODE *path = new PATH_NODE(destX, destY);
+        int pathX = destX;
+        int pathY = destY;
+
+        while (pathX != startX || pathY != startY)
+        {
+            // Find out the next parent
+            Tile *tile = getTile(pathX, pathY);
+            pathX = tile->parentX;
+            pathY = tile->parentY;
+
+            //printf("- (%d, %d)\n", pathX, pathY);
+
+            // Add the new path node to the start of the path list
+            PATH_NODE *pn = new PATH_NODE(pathX, pathY);
+            pn->next = path;
+            path = pn;
+        }
+
+        return path;
+    }
+
     // No path found
     return NULL;
 }
diff --git a/src/map.h b/src/map.h
index 38b880b7..c8757603 100644
--- a/src/map.h
+++ b/src/map.h
@@ -108,6 +108,11 @@ class Map
         int getTile(int x, int y, int layer);
 
         /**
+         * Get tile reference.
+         */
+        Tile *getTile(int x, int y);
+
+        /**
          * Set walkability flag for a tile
          */
         void setWalk(int x, int y, bool walkable);