Search the Community

Update 27 Sept: v0.1.0 Released: I've published the plugin and is available on NPM: https://www.npmjs.com/package/phaser-navmesh-generation The SRC can be viewed on the GitHub repo: https://github.com/amaccann/phaser-navmesh-generation Summary (apologies for the long post) I've been working on this for a few weeks now, and thought I'd share the Work in Progress so far: I'm still working on various edge cases, bugs and performance R&D, but it's in a state worth demoing IMO & thought I'd share the progress with the forum, see if there's any interest in that sort of thing. It's a relatively simple plugin to use, where you give it the ref. of a Phaser.Tilemaplayer, a couple of options & it generates a Navigation Mesh for use later by your Sprites & Game Objects. This plugin for now has a very simple set of options; all that's passed to it includes: The Phaser.Tilemap (required) The Phaser.TilemapLayer that's acting as your 'collision' layer (required) Any collision indices that determine the impassable tiles (required) Any debug options you want so you can see the calculations How much you want to offset your Sprites from the calculated path What I call a 'midpoint' threshold - more on that in a minute Demo Videos: (NB: the 'pause' between the drawing of new tiles & the NavMesh update was intentional, so it didn't get run until onMouseUp - it's not performance lag - the NavMeshs are generating / updating in about 15 - 20ms ) This demos basic movement; the test Sprite is a little hard to make out, sorry! I draw some extra impassable tiles to show the NavMesh re-calculating new triangles: https://youtu.be/7v4wIn7mrNY This shows how with narrow spaces, the NavMesh uses the 'midpoint' of the the polygon line segment, instead of trying to turn around corners https://youtu.be/AYUKLRmVzUQ Why do this? This all started with a larger project I'm working on: it's going to (hopefully!) involve large tilemaps, a large number of sprites and procedural generation. A messy combination. As a result, I've been looking into ways I could perform pathfinding around Tilemaps in Phaser, and the most popular choice seems to be the grid-based a*star plugins; while in the main it probably does the job for smaller tilemaps, I don't think they scale very well. One standard method of pathfinding used by other engines is something called Navigation (Nav) Meshes: basically, you calculate all the passable areas on your map and reduce it all to a small array of connected polygons, then figure out how to travel across those polygons. In my R&D, I did come across Mike Westhad's great Phaser NavMesh plugin that does this, but one limitation of it is that it expects the Developer to have manually drawn the NavMesh in the Tiled Editor. IMO, this didn't go far enough as it'd be great if a plugin could 'just' take any Phaser.TilemapLayer, inspect its passable areas and calculate a NavMesh on the fly. Assuming your game uses a larger, more complicated map, then in theory a NavMesh could be much more performance friendly than a giant A*Star grid. Because we're reducing all passable tiles into a smaller number of triangle space, there are fewer computations needed to get from point A to point B, as rather than (for instance) iterating across dozens, or even hundreds of grid tiles to find the shortest path, you're only iterating across a handful of polygons instead. Equally, if you do this at the load of your game level it should be a relatively small footprint of memory in your game. The Science Bit: How does this work? Well, the principle is actually quite 'simple' really. To give a rough breakdown of the process of calculation: Iterate across the tileLayer and merge all the impassable tiles into a series of unified polygons; this is done using what's known as 'Marching Squares Algorithm' - often used for finding the outlines of graphics objects. Recursively do this until we're confident we've found all possible impassable tile groups, and any groups within each other Extract all the corner points for these polygons, and perform 'Constrained Delaunay Triangulation' on these points. Basically, fill the area with connected triangles with these corner points. Loop over all these triangles, and find each others' neighbours. When we actually want to trace a path from A to B, find the triangle underneath the two points, then use A*Star to discover the shortest sequence of triangles to get to that destination. Use Funnel Algorithm to draw a path through those triangles, finding the corners around which to move. - This is where the 'midpoint threshold' comes into play, as some polygons might be too small to properly corner around: so instead we just take the midpoint of the funnel edge instead.