summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorBjørn Lindeijer <bjorn@lindeijer.nl>2005-02-13 00:15:33 +0000
committerBjørn Lindeijer <bjorn@lindeijer.nl>2005-02-13 00:15:33 +0000
commit85f211ea50df2d48c0400b2a267808f798b524fa (patch)
treedeb1a7ec15369e1b8b9def4a221548e87214d320 /src
parent4daa948c97c738ae102559635be3b89dc2b78dc4 (diff)
downloadmana-client-85f211ea50df2d48c0400b2a267808f798b524fa.tar.gz
mana-client-85f211ea50df2d48c0400b2a267808f798b524fa.tar.bz2
mana-client-85f211ea50df2d48c0400b2a267808f798b524fa.tar.xz
mana-client-85f211ea50df2d48c0400b2a267808f798b524fa.zip
New shorter and more flexible pathfinding implementation, which is hopefully
also more stable.
Diffstat (limited to 'src')
-rw-r--r--src/being.cpp9
-rw-r--r--src/being.h4
-rw-r--r--src/game.cpp27
-rw-r--r--src/game.h1
-rw-r--r--src/graphic/graphic.cpp28
-rw-r--r--src/map.cpp115
-rw-r--r--src/map.h5
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);