Jump to content
  • Advertisement
pathfinding

Need pathfinding idea feedback

Recommended Posts

Posted (edited)

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:
        walkable1.PNG.375061bc8b10b479c44245dabfe6a152.PNG
         
      • Walkable 2:
        walkable2.PNG.4d2cecd123374d6bf66f98e51c57aee0.PNG
         
      • Unwalkable:
        unwalkablePNG.PNG.593875ef8151feee4c520d42b7bfcaca.PNG
  • 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):

idea.thumb.png.a4f50408dd62bde5dac2cb7020001fe4.png

 

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:

  1. GET /path
    1. Body contains
      {startTile: {x, y, z}, destTile: {x, y, z}}

       

  2. Server queries DB for the start tile's area. It returns Area 1, meaning that the start tile is in Area 1.
  3. Server queries DB for the destination tile's area. It returns Area 5, meaning that the destination tile is in Area 5.
  4. 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)

     

  5. 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.

Edited by pathfinding

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

And if a little part of your map wants to look like this, instead?

image.png.58e618e255e8708241e2721cfacfbcdf.png

 

  • A graph is not necessarily heirarchial.
  • Not all tiles within an area are an equal distance from all portals between any two given areas.
  • An optimal path between two adjacent areas (say, the question mark in area 1 to an arbitrary tile in area 4) might route through any number of areas, not just those two. Heck, there are paths that start and end in area 1, which have optimal routes that go through area 4 on your own map.

 

If you know that you will hand-designate all (or most) portals between areas, it may be more useful to assign tiles to neighbourhoods based on those portals; e.g. each portal gets an ID, and each tile is assigned its closest portal (a la Voronoi) as its neighbourhood ID. Then...

  • You know that all routes that begin and end within the same neighbourhood will go through no other neighbourhoods, because by definition the tiles within a neighbourhood at at least one tile closer together than they could be reached via any path through another neighbourhood.
  • You can pre-calculate the shortest path between the portals of every neighbourhood pair, and store distance that in a simple sparse matrix, because there will be no duplication of "area" adjacencies (like you have multiple ways to get from area 1 to area 4).
  • You end up with a representation of spatial complexity of your environment; a graph that doesn't encode the "enclosedness", but instead encodes the disconnectedness of your environment. If any of the neighbourhoods you generate are too large for your tastes, you can scatter random neighbourhood seeds into them, to generate smaller, better-connected regions.
  • Local pathfinding is then used to solve the route between a tile in a neighbourhood A, and a tile in the same neighbourhood A, or any adjacent neighbourhood B. You know they will be trivially reachable, and will be by definition closer to eachother via their neighbourhood portals than to any other portal.

image.png.9db537eb661cc102b74d6016056ed2ba.png

Edited by Wyrframe
fixed the yellow/orange boundary

Share this post


Link to post
Share on other sites

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?

Edited by pathfinding

Share this post


Link to post
Share on other sites

A portal is just a seed position for subdividing your world into well-connected segments. Any traversable tile can be a seed position for the voronoi-esque algorithm, but picking bottlenecks (like doorways) will give the best results. You could just randomly pattern your world with seed positions, if you like.

I've no idea what you're trying to accomplish in that main() function. You're using the same portal ID for two different seeds, you're manually configuring neighbours, there's no tilemap mentioned that these coordinates and seeds exist within... and you can't just use cartesian distance between seeds. You have to determine the length of the shortest path between them, which requires the tilemap they exist within.

Share this post


Link to post
Share on other sites
54 minutes ago, Wyrframe said:

A portal is just a seed position for subdividing your world into well-connected segments. Any traversable tile can be a seed position for the voronoi-esque algorithm, but picking bottlenecks (like doorways) will give the best results. You could just randomly pattern your world with seed positions, if you like.

I've no idea what you're trying to accomplish in that main() function. You're using the same portal ID for two different seeds, you're manually configuring neighbours, there's no tilemap mentioned that these coordinates and seeds exist within... and you can't just use cartesian distance between seeds. You have to determine the length of the shortest path between them, which requires the tilemap they exist within.

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?

Share this post


Link to post
Share on other sites

Honestly, if your map is certain to be less than 2M tiles in width and height (or, specifically, 2^31-1), I'd just make the portal ID a 64-bit `long` and make the portal's ID be its coordinates: ((long)x << 32) | y. No chance of collision, and you can determine where the seed tile was based on just its ID.

You've said your map is ~12 million tiles... which is only about 3500^2 tiles. That's basically zero. You've mentioned having Z-levels (although you called them Y-layers)... but how are they connected? If only with "staircase" tiles, they may as well be teleporters within a single 2D map.

Why do you need to store a tile's position within the tile? Its position within the dataset is its coordinates. You only need to communicate a tile's position when talking about a tile; the tile itself doesn't care what its coordinates are, since they are constant, immutable, and inferrable from the location of that tile within its container. If you need a 32-bit field to store what is in or on the tile, that's ~45MB of data to store the whole map. Again, basically rounds down to zero.

 

Calculating the neighbourhood field is going to be more computationally expensive than the pathfinding pass you'll do to generate the area-connectivity graph, especially since the neighbour-distance pathfinding can be done massively in parallel. Work on the voronoi field first.

Edited by Wyrframe

Share this post


Link to post
Share on other sites

@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?

Edited by pathfinding

Share this post


Link to post
Share on other sites

You have to admit that it seems pretty addictive, see if you finish it soon, a good project. I would put more difficulty in the maps.

Share this post


Link to post
Share on other sites
On 5/17/2019 at 2:17 AM, pathfinding said:

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.

Same way as a C compiler stores the 3D array in linear memory address space.

Starting with 2D, assume width=2 (in x direction), and height=3 (in y direction), ie

width = 2
height = 3
content = (2 columns x and 3 rows y, values A..F)
    x->    0 1
           ---
    y   0| A B
    |   1| C D
    v   2| E F

in linear array, with x minor D=[A, B, C, D, E, F], access with D[x + y * width]
in linear array, with y minor D=[A, C, E, B, D, F], access with D[y + x * height]

You pick one of the axes as major, and the other one is then minor. Increasing the minor axis 'jumps' one position, increasing the major axis 'jumps' <length minor> positions.

Extending to 3D or higher dimensions is simply extending this scheme, like D[x + y * width + z * (width*height)].

 

EDIT: "Teleporting" in the simplest form means you make a [6000][3*6000] map, going down increases y by 6000, going up decreases y by 6000.

More sophisticated is if you have a list with stair jump locations
 

up   (100, 200) -> (400, 500)
down (400, 500) -> (100, 200)

When the player is at (100, 200), and wants to go 'up', set the player position to (400, 500), and so on.

As long as you can't walk from (100, 200) to (400, 500) without taking a stairs, it seems like two different floors to the player.

Edited by Alberth

Share this post


Link to post
Share on other sites
On 5/18/2019 at 9:18 AM, Alberth said:

Same way as a C compiler stores the 3D array in linear memory address space.

Starting with 2D, assume width=2 (in x direction), and height=3 (in y direction), ie


width = 2
height = 3
content = (2 columns x and 3 rows y, values A..F)
    x->    0 1
           ---
    y   0| A B
    |   1| C D
    v   2| E F

in linear array, with x minor D=[A, B, C, D, E, F], access with D[x + y * width]
in linear array, with y minor D=[A, C, E, B, D, F], access with D[y + x * height]

You pick one of the axes as major, and the other one is then minor. Increasing the minor axis 'jumps' one position, increasing the major axis 'jumps' <length minor> positions.

Extending to 3D or higher dimensions is simply extending this scheme, like D[x + y * width + z * (width*height)].

 

EDIT: "Teleporting" in the simplest form means you make a [6000][3*6000] map, going down increases y by 6000, going up decreases y by 6000.

More sophisticated is if you have a list with stair jump locations
 


up   (100, 200) -> (400, 500)
down (400, 500) -> (100, 200)

When the player is at (100, 200), and wants to go 'up', set the player position to (400, 500), and so on.

As long as you can't walk from (100, 200) to (400, 500) without taking a stairs, it seems like two different floors to the player.

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?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • 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!