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:

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.

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?

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?

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

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.

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.

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?