0
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\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, 2018 at 15:26

2 Answers 2

0
\$\begingroup\$

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

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

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:

\$\endgroup\$
1
  • \$\begingroup\$ You might want to stop spamming your web site to avoid being flagged as a spammer. \$\endgroup\$
    – Vaillancourt
    Aug 15 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .