Jump to content
  • Advertisement

pathfinding

Member
  • Content Count

    6
  • Joined

  • Last visited

Community Reputation

0 Neutral

About pathfinding

  • Rank
    Newbie

Personal Information

  • Interests
    Programming
  1. pathfinding

    Need pathfinding idea feedback

    Doesn't this seem more complicated than just using three separate array indexes? int[z][x][y] = new int[3][6000][6000]; seems way more straightforward and would end up being the same amount of tiles anyway. Why not just use this instead?
  2. pathfinding

    Need pathfinding idea feedback

    I still don't understand how that stores a coord pair of {x:1, y:2, z:3}. Could you show an example using those?
  3. pathfinding

    Need pathfinding idea feedback

    @Wyrframe Sorry man, I am messing up everything. I meant to say 20 million tiles, not 12. Also thank you for the help. So the map is around 6000x6000, but I'm not planning on storing the unwalkable tiles, so it makes it around 20 mil. However, the map has 3 levels. You're right, I mean z-index, not y-index, excuse me. You're correct, taking a ladder or staircase (or other object) up a level takes you to one z-index above where you were. Example: Current Tile: {x:1, y:2, z:0} *Go up ladder* Current Tile: {x:1, y:2, z:1} Could you explain how I might store a 3-layer map in a 2-d plane? I guess I haven't gotten to that part of mathematics lol, figured you always had to have each layer as a different index in a 3d array. Example: Tile[][][] map = new Tile[3][6000][6000]; And would ((long)x << 32) | y still work even with the 3 layers of tiles?
  4. pathfinding

    Need pathfinding idea feedback

    Thanks for clarifying what a portal is. It sounds like I can just assign a random object id to the seed, but also have the seed set as a custom object, for example, store the object interaction string within the seed/portal. If I want to "Climb-over", that would be set in the seed. The main() function is just an example of how I'd assign a portal/seed to a Tile, and how I might assign neighboring seeds/portals to a tile. My code is definitely wrong though, after looking at it again (I wrote it up in the forum's browser window, so no code-checking enabled). I also plan on the distance() calculation the A* path length from seed to seed, but that'll be a lot of work that I didn't have time to code right now. However, I understand that the distance should be the REAL path's distance from seed/port to seed/portal. So, ignoring the main() function mess, and assuming I'll use A* as my distance. Am I at least on the right track?
  5. pathfinding

    Need pathfinding idea feedback

    WOW @Wyrframe, after processing that fully, that makes much more sense than my idea! Should a portal be considered an NPC, Fence, Gate, Warp-gate, etc... ? I'm trying to think of how to code this in Java, which will let me serialize the object into a database. Just trying to come up with the structure. So far I have this: class Tile { private final int x, y, z, tileFlags; private Portal parentPortal; private int g, f, h; public Tile(int x, int y, int z, int tileFlags){ this.x = x; this.y = y; this.z = z; this.tileFlags = tileFlags; } public double distance(Tile t){ return Math.sqrt(Math.pow(x - t.getX(), 2) + Math.pow(y - t.getY(), 2) + Math.pow(z - t.getZ(), 2)); } public int getX(){return x;} public int getY(){return y;} public int getZ(){return z;} public int getFlags(){return tileFlags;} public Portal getParentPortal(){return parentPortal;} public void setParentPortal(Portal parentPortal){this.parentPortal = parentPortal;} } class Portal { private final int portalId; // Could be NPC id, or GameObject id private int area; private HashMap<Portal, Double> neighboringPortals = new HashMap<>(); public Portal(int portalId){ this.portalId = portalId; } public Portal(int portalId, int areaSize){ this.portalId = portalId; this.area = area; } public void addNeighbor(Portal portal, double distance){ neighboringPortals.add(portal, distance); } public void getNeighboringPortals(){ return neighboringPortals; } public int getAreaSize(){return area;} } public static void main(String... args){ Tile t = new Tile(220, 100, 3, 4355); t.setPortal(new Portal(5524)); Tile t2 = new Tile(384, 200, 3, 362); t2.setPortal(new Portal(5524)); Tile t3 = new Tile(265, 462, 3, 362); Tile t4 = new Tile(265, 462, 3, 362); Portal p = new Portal(624) t3.setPortal(p); t4.setPortal(p); t.addNeighbor(t2.getParentPortal(), t.distance(t2)); t.addNeighbor(t3.getParentPortal(), t.distance(t3)); t2.addNeighbor(t.getParentPortal(), t2.distance(t)); t2.addNeighbor(t3.getParentPortal(), t2.distance(t3)); t3.addNeighbor(t.getParentPortal(), t3.distance(t)); t3.addNeighbor(t2.getParentPortal(), t3.distance(t2)); } Look ok?
  6. 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.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!