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

  • \$\begingroup\$ There are lots of optimizations for unweighted grids; see this paper for some. Here's a demo of 800x800 running in a few milliseconds. That said, converting to navmesh will probably help a lot, but I don't have any references for you. I think people typically start with a navmesh instead of starting with tiles. \$\endgroup\$ – amitp Aug 10 '18 at 15:26

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.

Probably this helps you a bit : A-Star Algorithm Here the implementation Java Implementation

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

  • \$\begingroup\$ Thank you! I thought that it's expensive, but it's not. \$\endgroup\$ – Xyt Aug 16 '18 at 22:29
  • \$\begingroup\$ @Xyt No problem, glad that I could help somehow :) \$\endgroup\$ – genaray Aug 17 '18 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.