Pathfinding in large map (open world)

[Gugis]

What's the best pathfinding method for 2d open world game? At first I considered  A* algorythm, but it would require a huge grid and I'm talking about millions of tiles and it would take a long time to find a path. 

P.S. game is multiplayer so pathfinding will be proccessed in server side.

[mattstyles]

I'd love to be proved wrong but pathfinding over a large area, I think, is always going to be slow (whether it is too slow or not is a different concern).

Are you sure you need the pathfinding to be accurate over the huge distance between point A and point B?

For example, if no-one can see the unit moving, then the path does not need to be accurate, the unit simply needs to move from A to B in approximately the correct time.

[Gugis]

Pathfinding will be used for player movement and (linear) distances won't be huge. Player will be able to travel only to visible tiles. However obstacles can be large and you may need a very long bypass.

[b10b]

If using A* then super-sized locations can be resolved using multiple maps, each of varying levels of detail (e.g. World (32x32), Region (32x32) - making a total of 1,048,576 tiles).  Run the low detail route first (World) - this shows which Regions the player must travel through.  Then as the Player enters a new Region run the more detailed route.  That second high detail Route can be generated asynchronously as the Player is crossing the previous Region.  There is no guarantee that this multiple maps approach will yield the shortest route, but it'll be close enough (assuming no Region is totally unpassable).

[BliantFive]

On 4.4.2016 at 6:00 PM, b10b said:

If using A* then super-sized locations can be resolved using multiple maps, each of varying levels of detail (e.g. World (32x32), Region (32x32) - making a total of 1,048,576 tiles).  Run the low detail route first (World) - this shows which Regions the player must travel through.  Then as the Player enters a new Region run the more detailed route.  That second high detail Route can be generated asynchronously as the Player is crossing the previous Region.  There is no guarantee that this multiple maps approach will yield the shortest route, but it'll be close enough (assuming no Region is totally unpassable).

Thats actually a great idea. I will keep that in mind for later projects.

to OP:

Make sure you get that "assynchronous" part of this comment. As the Player "normaly" has to walk the distance, which takes time you dont need the process to be fully done at the start. You just need the route to the nearest region.

Most pathfinding engines let you limit the number of calculations done per tick, so there is no danger of the script blocking everything else. It just might take some time, which is easily hidden from the user.

[joshcamas]

You could also possibly generate a navmesh and export it as a file, and then whenever your playing the game you could load it. Of course this would require you to figure out how to do such a thing.  Navmeshes are how them big engines do it

EDIT: Whoops, I thought you where doing a 3D game! My mistake! What b10b said sounds great, listen to him! xD