Any plans on adding tools for dynamic meshes?

[malahaas]

I'm making a game where obstacles can be placed during run time. Right now I've added a very simple grid generator that saves tile removals and regenerates the NavMesh from a new array, but it definitely starts to slog pretty quickly as tile count increases. I know I could make improvements by making a smarter tile generator, but just wondering if there are resources that already exist for this kind of thing (or if you have plans around this concept) so I'm not reinventing the wheel.

[malahaas]

Another issue I've worked around is being able to set the destination point within an unwalkable tile. Basically I want to wander around obstacles until the last one which I can "enter". For now I've just calculated an entrance point on the edge of the unwalkable tile and used navmesh to get there then move the rest of the way 'manually.' Anyway, these are my 2 use cases that I need to work around and was just wondering if you've though about these types of things. The library was super helpful and I very easily got pathfinding up and running in my Phaser 3 game from none. Thanks!

[mikewesthad]

Glad it helped with getting things up and running. Some initial thoughts:

• Dynamic updates, good question. I haven't experimented with that, but it might be possible to refactor how navmesh calculates the neighbors and portals between polygons in the mesh so that it can do smarter updates. I'll have to think on that.
• Getting close to an unwalkable location - so you have obstacles that have some kind of door on them that the agent can interact with to enter? Or did I misunderstand? Maybe the navmesh could have method to get the nearest path where, if you give it an unwalkable end point, it tries to find a path using the nearest walkable point (nearest via "as the crow flies" distance)?

[malahaas]

Good thoughts.

• I was considering seeing if I could shortcut the underlying objects for the dynamic updates, but initial thoughts were total hacks. I agree a refactor might be needed. The next issue would be figuring out a better way to cut holes because for now I just have a uniform grid and use the object's shape to calculate which grid squares in the original array to exclude. It's super fast calculations , but that means a whole lot more polys than is truly necessary so building NavMesh takes time. I'll be thinking on that too.

• For the second point, that's roughly what I'm doing. I made the door a spot on the border because it was quick and easy and after I thought about it often makes more sense. Some 'buildings' might want an open plan around the edges so the closest point was what I was thinking if/when I get to that type of structure.

Both these issues come from the fact that the game's a city builder, so you place a building and characters have to be able to get to it and interact with it, but also it should remove the grid area it was placed on so pathfinding routes around it. This is all super early development for me, so I have lots of other things to be working in the meantime ;-D

[mikewesthad]

Hmm, I'll have to think on these this weekend. Thanks for sharing your thoughts. Sounds like an intriguing game.

• Just making sure I've got my head around the use case. You've got your world broken down into a uniform square grid. You place obstacles dynamically by excluding any overlapping squares from the NavMesh. So the optimization you mention is collapsing the leftover walkable squares into the smallest number of convex polygons? I experimented a little with automatically decomposing a level into convex polygons, but I ended up finding that it decomposed the levels into too many polygons and the performance suffered. That said, I suppose it might be worth including that as a feature and just warning folks about that possibility.
• The door thing you mention sounds like it might be related to what Unity implements with "links" (ref). So if I understand this, you've got a door asset that is within the "blocked" zone of the obstacle (sits on one of the obstacle polygon's edges). If you tell an agent to move to the center of the door, they can't make it directly there. But if you told the agent to move to a location near the door and just outside the obstacle, it would be fine? Would it work if you could pass in a startPoint, endPoint and a fudgeRadius when looking for a path (where it looks for a path from startPoint to the closest location near endPoint within the fudgeRadius)? If you've got a build of your game (or screenshots), that you don't mind sharing. It might help my brain grasp all the details.

By the way, pull requests are totally welcome, so if you feel motivated to dig in any changes, feel free.

[malahaas]

Ugh, for some reason Github has stopped sending me email notifications so I just saw this.

• Yes, you've got my setup correct. Yea, if there's an optional feature to collapse polygons that'd be pretty cool (with the caveat that of course it will slow down building the mesh.
• I think you get this part just fine. I'm tearing up and rebuilding my game constantly as it's largely an outlet for me to play with ideas and tools outside of work-related tasks. I'll let you know when I get something at least a bit stable.

I'll keep that in mind. Right now my focus is on using a reactive loop for my game logic (a slightly modified version of SAM architecture). Right now I'm having fun trying to use the benefits of SAM in an arena I don't think it was intended for. The main benefits would be the almost 'built-in' ability to save replays.

[mikewesthad]

Heh - no worries. Sounds good. I just started a push to get the library converted to typescript so that I can start looking into improvements more seriously (and in a more maintainable way). I'll keep this thread updated as I go.

Ah, intriguing. I hadn't heard of SAM, though I see some similarities to Redux-like approaches. Thanks for sharing. Will have to do a closer read of it some time.

[mikewesthad]

Slowly plugging away at these issues. A few updates here:

• Added a way to generate meshes from Tilemaps via buildMeshFromTilemap (or 2D grids via buildPolysFromGridMap). I still need to run some larger scale tests on it, but so far, it seems to be doing well (and beating some of my hand generated mesh).
• Still working on the best way to incorporate the nearest path idea. In the meantime, I added a method to the NavMesh class - findClosestMeshPoint - which can tell you the distance from a location to the navmesh and give you the closest point in the mesh to your given location.

[malahaas]

Awesome, thanks for the update. I just did YAMR (YET ANOTHER MAJOR REFACTOR ;-P) but I think I'm about ready to start working on art and a tutuorial level.

[mikewesthad]

Heh, I've definitely been there 👍🏽