diff options
| -rw-r--r-- | src/being.cpp | 9 | ||||
| -rw-r--r-- | src/being.h | 4 | ||||
| -rw-r--r-- | src/game.cpp | 27 | ||||
| -rw-r--r-- | src/game.h | 1 | ||||
| -rw-r--r-- | src/graphic/graphic.cpp | 28 | ||||
| -rw-r--r-- | src/map.cpp | 115 | ||||
| -rw-r--r-- | src/map.h | 5 |
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: @@ -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; } @@ -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); |