Need pathfinding idea feedback Hello, I'm new to the forums, so this might not be in the correct section, but I think it is. I have an idea for a new pathfinder for a game I'm trying to traverse. The game is already established, so I'm not coding for the game, rather, I'm creating a program to navigate the game for me. Here's a description of the walking environment: The world is comprised of tiles Each tile has optional boundaries on each side. For example, a fence might be on the North-side of the tile, blocking us from traveling North. Players are able to move between tiles in all directions, if not blocked by an obstacle. For example, if traveling diagonally, you can reach the neighboring NE red tile by traveling either unblocked direction: Walkable: Walkable 2: Unwalkable: There are warp-nodes between tiles. An NPC can teleport you to a different tile on the other side of the map A game object can teleport you to a different tile on the other side of the map You character can teleport to a different tile on the other side of the map There are item/skill/quest requirements for accessing certain areas. There are 3 y-axis levels, so 3 times the amount of tiles to store. There are also around 12 million tiles in the game, which should work out to a few GB of data. So I know I can make these calculations in RAM. Each tile will be represented by a coordinate pair of {x, y, z}. I plan on using JavaScript to make this pathfinder a RESTful API in the future. JavaScript stores each integer as a 4-byte number, so (4 * 3 [coords per tile] * 20,000,000 = 240,000,000 bytes = 0.24 GB of tile data) However, 12 million tiles are a TON of tiles to find paths between, so I want to try and find a simple algorithm that solves all of these problems: Fast pathfinding calculation between two tiles (under a few milliseconds for REST) Can calculate shortest warp-node travel distance, meaning the pathfinder will calculate for teleporting Can compute area-specific requirements of travel My solution so far: In a database, store each tile in an "area", then traverse the areas to find the shortest path. Each area will be comprised of reachable tiles in any given area. Here is a visual representation of these areas (pink squares are fences/gates/doors separating the areas from each other. gray are unmovable boundaries): So, imagine that every area (colored and labeled differently above) holds those colored tiles in the database. If you want to get to, let's say, Area 5 (purple) from Area 1 (green) you'd have to pass through Area 4 (blue). You can model this path as a hierarchical structure. Each Area has a parent, and therefore some children. So, let's start an example REST query: GET /path Body contains {startTile: {x, y, z}, destTile: {x, y, z}} Server queries DB for the start tile's area. It returns Area 1, meaning that the start tile is in Area 1. Server queries DB for the destination tile's area. It returns Area 5, meaning that the destination tile is in Area 5. Let's assume Area 1 is our "main area", and that all areas lead back to it hierarchically. All the server needs to do is a const areasToTopLevelArea = []; for(Area parentArea = destArea.getParentArea(); parentArea; parentArea = parentArea.getParentArea()){ areasToTopLevelArea.push(parentArea); } if(areasToTopLevelArea.contains(startArea)) //get path, our destination area is above us else //find path to main area from startArea //check again if any areas match (they will ALWAYS meet at the top-level area, no matter what) Once we have our area-path, return a pre-computed (and stored) path from the DB between the areas. What do you all think? I'm pretty sure this covers all possible edge cases. For example, if the two areas we're traversing between are Area 5 and Area 6, then we need to traverse through Area 4. Luckily, Area 4 is the parent of both Area 5 and Area 6 making it easy for the algorithm to match on the first area (Area 6), and find the pre-computed path between Area 5 and Area 6 through Area 4. And of course, in the end, if the area is not reachable, do not store it. Meaning that any tile that is actually stored in the DB will be valid, and traversalable from anywhere in the game. Please let me know if I'm missing any logic here. I wanted to propose this idea before I start implementing it. https://ift.tt/eA8V8J

Hello, I'm new to the forums, so this might not be in the correct section, but I think it is. I have an idea for a new pathfinder for a game I'm trying to traverse. The game is already established, so I'm not coding for the game, rather, I'm creating a program to navigate the game for me. Here's a description of the walking environment: The world is comprised of tiles Each tile has optional boundaries on each side. For example, a fence might be on the North-side of the tile, blocking us from traveling North. Players are able to move between tiles in all directions, if not blocked by an obstacle. For example, if traveling diagonally, you can reach the neighboring NE red tile by traveling either unblocked direction: Walkable: Walkable 2: Unwalkable: There are warp-nodes between tiles. An NPC can teleport you to a different tile on the other side of the map A game object can teleport you to a different tile on the other side of the map You character can teleport to a different tile on the other side of the map There are item/skill/quest requirements for accessing certain areas. There are 3 y-axis levels, so 3 times the amount of tiles to store. There are also around 12 million tiles in the game, which should work out to a few GB of data. So I know I can make these calculations in RAM. Each tile will be represented by a coordinate pair of {x, y, z}. I plan on using JavaScript to make this pathfinder a RESTful API in the future. JavaScript stores each integer as a 4-byte number, so (4 * 3 [coords per tile] * 20,000,000 = 240,000,000 bytes = 0.24 GB of tile data) However, 12 million tiles are a TON of tiles to find paths between, so I want to try and find a simple algorithm that solves all of these problems: Fast pathfinding calculation between two tiles (under a few milliseconds for REST) Can calculate shortest warp-node travel distance, meaning the pathfinder will calculate for teleporting Can compute area-specific requirements of travel My solution so far: In a database, store each tile in an "area", then traverse the areas to find the shortest path. Each area will be comprised of reachable tiles in any given area. Here is a visual representation of these areas (pink squares are fences/gates/doors separating the areas from each other. gray are unmovable boundaries): So, imagine that every area (colored and labeled differently above) holds those colored tiles in the database. If you want to get to, let's say, Area 5 (purple) from Area 1 (green) you'd have to pass through Area 4 (blue). You can model this path as a hierarchical structure. Each Area has a parent, and therefore some children. So, let's start an example REST query: GET /path Body contains {startTile: {x, y, z}, destTile: {x, y, z}} Server queries DB for the start tile's area. It returns Area 1, meaning that the start tile is in Area 1. Server queries DB for the destination tile's area. It returns Area 5, meaning that the destination tile is in Area 5. Let's assume Area 1 is our "main area", and that all areas lead back to it hierarchically. All the server needs to do is a const areasToTopLevelArea = []; for(Area parentArea = destArea.getParentArea(); parentArea; parentArea = parentArea.getParentArea()){ areasToTopLevelArea.push(parentArea); } if(areasToTopLevelArea.contains(startArea)) //get path, our destination area is above us else //find path to main area from startArea //check again if any areas match (they will ALWAYS meet at the top-level area, no matter what) Once we have our area-path, return a pre-computed (and stored) path from the DB between the areas. What do you all think? I'm pretty sure this covers all possible edge cases. For example, if the two areas we're traversing between are Area 5 and Area 6, then we need to traverse through Area 4. Luckily, Area 4 is the parent of both Area 5 and Area 6 making it easy for the algorithm to match on the first area (Area 6), and find the pre-computed path between Area 5 and Area 6 through Area 4. And of course, in the end, if the area is not reachable, do not store it. Meaning that any tile that is actually stored in the DB will be valid, and traversalable from anywhere in the game. Please let me know if I'm missing any logic here. I wanted to propose this idea before I start implementing it.

from GameDev.net http://bit.ly/2LJGUiP