I'm working on a pathfinder for a MMORPG game, it's not mine; I'm RE it, now I need to create a pathfinder for monsters. But I figured that the client uses tiles for it's pathfinder (for players). Inside map files, there is a set of walkable and not walkable tiles. (Every coord XY is one tile). Now I wan't to implement the server side path finder, but the problem with these tiles is performance, some maps are 500x500 (250000 tiles). I need to reduce the number of tiles, so I guess I should convert them into navigations meshes, either triangles or bigger squares or rectangles. Is there a tool or an example code to do that? Thanks
Well I honestly think that the AStart or similar pathfinding algorithms should be able to work in such large scales, because they are mostly high performant.
But regarding large scale maps... probably this helps you a bit... its quite a good article : http://gram.cs.mcgill.ca/papers/lanctot-06-path-finding.pdf
Or even an other stack overflow question : https://stackoverflow.com/questions/37466738/pathfinding-on-large-map
And this here is the best article I have found : https://twvideo01.ubm-us.net/o1/vault/gdc2018/presentations/Alain_Benoit_HierarchicalDynamicPathfinding.pdf
I had same problem and I did precomputation.
I initially planned to brute force check all of the possible mappings between all coordinates however it is quite impossible since there are so many possible pathing.
I did some optimization with initial idea and now it works great.
My biggest map was 192x192 tiles and the software didn't have any problem to process it
The source code and the programming video are fully available. It is in C# but could give you a lot of ideas: