Phaser Plugin: NavMesh Generation

[pixelburp]

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:

 

1. The Phaser.Tilemap (required)
2. The Phaser.TilemapLayer that's acting as your 'collision' layer (required)
3. Any collision indices that determine the impassable tiles (required)
4. Any debug options you want so you can see the calculations
5. How much you want to offset your Sprites from the calculated path
6. 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:

 

1. 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.
2. Recursively do this until we're confident we've found all possible impassable tile groups, and any groups within each other
3. 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.
4. Loop over all these triangles, and find each others' neighbours.
5. 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.

 

 

 

[AlanSmithee]

This is super cool! Been thinking about something in these lines too. Would really like to try it out! Regarding making it available on GitHub, I don't think you have to worry about it being WIP, just add a README.md stating the current status of the project. BTW, this is for phaser 2, I assume?

[pixelburp]

On 16/09/2017 at 1:09 AM, AlanSmithee said:

This is super cool! Been thinking about something in these lines too. Would really like to try it out! Regarding making it available on GitHub, I don't think you have to worry about it being WIP, just add a README.md stating the current status of the project. BTW, this is for phaser 2, I assume?

Yeah, I have a couple of ideas on how to solve the main bug that's highlighted, so I might wait until that's (hopefully!) solved before making the GH repo public.

And yes, this plugin is for Phaser 2. The whole plugin is kinda independent of the main Phaser pipeline, so assuming Point, Line and Polygon (not to mention Plugin loading) remain the same it should migrate to Phaser 3 without too much fuss.

[rich]

I would strongly suggest just releasing this, bugs and all. You'll get little meaningful feedback from a few YouTube videos I'm afraid! But source someone can play with, that's a different matter.

[pixelburp]

Yeah you're probably right @rich Ok, so if people want to actually use the plugin, I've published a rough, pre-alpha version that's available as a NPM package (it can be loaded normally as a script tag too though, and comes with source-maps): it can be found here:

https://www.npmjs.com/package/phaser-navmesh-generation

As for the SRC, I've made the repo public, so if people want to play / hack / criticise / comment on the SRC, it can be found here:

https://github.com/amaccann/phaser-navmesh-generation

Both contain rough documentation on how to use the plugin; there are really just two functions to use it (for now), with a couple of config. options to do the rest. Hopefully it's clear enough and works OK for people. Happy to answer any questions, queries etc.

I freely admit that my geometry is a little rusty, and as this is a pre-pre-alpha, I don't think this is anywhere near as performant as it could be; there are a few places I'm sure better options are available, but Stackoverlow got me out of a jam quite often!

 

[pixelburp]

Bumping the thread as I've fixed a big issue that was preventing use as an imported node package; that probably didn't help get much useful feedback if people couldn't actually use the plugin :-(

The newest version is 0.1.0 and also fixes a bug with pathfinding around parallel clusters of impassable terrain.

ES6 / Node

import it as you would any other project:

import NavMeshPlugin from 'phaser-navmesh-generation';

Legacy

If you're doing it the old fashioned way, simply add <script> tag after your main Phaser tag:

<script src="my/path/to/phaser.js"></script>
<script src="my/path/to/navmesh-plugin.js"></script>

Then in your game's JS code:

  preload() {
    var plugin = this.game.plugins.add(NavMeshPlugin);
  }

 

[mikewesthad]

@pixelburp - exciting! Great to see more navmesh stuff happening in Phaser! Looks like a great way to make navmeshes more accessible for people to test out.

In case it's helpful, I have an old branch off of phaser-navmesh where I used libtess to automate the process of decomposing a tilemap into polygons. The results with triangulation were a bit rough, though maybe using libtess in quad mode might return better results. I ended up abandoning that because manually generating the navmesh allowed me to get closer to an optimal decomposition in my projects (better performance & avoiding skinny polygons). Feel free to ping me if you want me to share that code.

[pixelburp]

18 hours ago, mikewesthad said:

@pixelburp - exciting! Great to see more navmesh stuff happening in Phaser! Looks like a great way to make navmeshes more accessible for people to test out.

In case it's helpful, I have an old branch off of phaser-navmesh where I used libtess to automate the process of decomposing a tilemap into polygons. The results with triangulation were a bit rough, though maybe using libtess in quad mode might return better results. I ended up abandoning that because manually generating the navmesh allowed me to get closer to an optimal decomposition in my projects (better performance & avoiding skinny polygons). Feel free to ping me if you want me to share that code.

Interesting; I must have a look at that, thanks @mikewesthad :-) Throughout my work, one of the big stumbling blocks was actually digging out some good documents & explanations over key pillars of NavMesh generation. A lot of the discussion was dominated by Unity / Unreal engine's GUI components, which didn't really help detail exactly what went into NavMeshes. 

As for updates from me; ATM there's a couple of things I'm working on that I think will be big improvements:

1. A developer might want non-map based obstacles or blockages on the map (Sprites such as buildings, trees etc.), which the plugin doesn't support. I'm refactoring the plugin to allow for parts of the Grid to be toggled as "blocked", which will override any tileLayer index underneath.
2. Trying to improve performance during triangulation. First step here is to STOP iterating across 2D arrays (which is how Phaser 2 stores its tileLayer data); a flattened 1D Array structure is much faster to iterate across, and already I'm finding the NavMesh is generating a lot faster. (Don't have any timings just yet)
3. Investigating if WebWorkers can be used to make things even faster. This feels like a frustrating dead-end though. Proper multithreading would be so nice, but there's too much overhead simply loading threads; my brief experiments showed it could take 1-2 seconds simply creating a new instance, and there doesn't seem any real benefit in the speed of messages to & from the Worker.
4. The A*star pathing is still not perfect, and sometimes the less optimal path is taken, even if it's obvious visually you can get to your destination via a (technically) longer path. Not sure how best to fix this though; it's a bit of a blocker.

[pixelburp]

The plugin has been updated to 0.2.1. I've added what IMO makes the navMesh a little more practical for use in games - the ability to dynamically override areas as impassable; useful for setting Sprites such as trees or buildings as blocked parts of the mesh. The main changes for this version include:

• Included support for 'sprites' to mark blocked areas of navMesh that isn't an explicit collision tile. This can be accessed through addSprite() method of plugin (use removeSprite to remove the sprite by uuid)
• Tilelayer data is now flattened from 2D Phaser format into 1D array; this makes it faster to iterate across the whole grid.
• Added updatedAt timestamp to generated navMesh
• Added createdAt timestamp for generated paths

The full changelog is here:

https://github.com/amaccann/phaser-navmesh-generation/blob/master/CHANGELOG.md