Generating nav meshes from tile based map (2D)

by Xyt   Last Updated August 10, 2018 12:13 PM

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



Answers 1


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

genaray
genaray
August 10, 2018 11:53 AM

Related Questions


Navigation Mesh & 2D Tilemaps

Updated September 07, 2017 17:13 PM

Simplify navmesh path

Updated June 01, 2015 00:05 AM

Book that goes through Navigation Mesh process

Updated August 26, 2017 00:13 AM

A* navigational mesh path finding

Updated May 09, 2018 22:13 PM