Navmesh and pathfinding

(Hussein Tammam) #1

Hey, this is more of a collection of thoughts than a question really.

I just finished an A* pathfinder that works on grids when I got this idea. Why aren’t navmeshes arent used commonly in 2d games. I’ve searched a lot and there are very few implementations mostly related to unity2d. Is there any AS3 or Flashpunk navmesh generator out there?

Now I know I dont NEED a navmesh for my game, but honestly I WANT to make this. It just seems like a really fun project with the side benefit of possible gameplay and performance improvments, although its more for the learning experience. This could evolve into an interesting library for Flashpunk too.

TLDR: Are there any navmesh generators for AS3 or flashpunk? If not, do you know any tutorials or tips on how to make one.

(Martí Angelats i Ribera) #2

Usually path finding uses grids or graphs to search it. I’ll center my response in the second type (it seems the one you are interested in).

There are a lot of types, but the more usual is a shortest path finder (finds the shortest posible path) because everything you need is already made. The main problem with them is that they are slow. I’ve also seen some projects that try to emule the animal/human behaviour.

(Jean) #3

I don’t think that a single thread engine(like FP is) would deal good with navigation mesh. Hardware acceleration is another point so that leading with polygons instead of grids would be easier.

Going with A* or even a basic “Flood Fill” pathfinding is more than enough, since navigation mesh isn’t that trivial and easy to implement.

(Jacob Albano) #4

Navigation meshes don’t necessarily have anything to do with the type of mesh you use to render 3d models. They can be as simple as a set of convex polygons with connections: if your destination point lies in the same zone as your current location, move straight towards it; if not, use A* to navigate from one zone to another until it does.

(Jean) #5

I said that because detecting if you are inside a convex polygon all the time is time consuming and isn’t that trivial to implement.

Maybe a funnel algorithm should be more than enough? (and a lot more easier to implement, and you don’t need meshs, just a few waypoints)

(Hussein Tammam) #6

@jacobalbano Well I guess I guess navigation mesh is sort of a confusing term especially, for 2d games. What I meant is a bunch of polygons forming a graph which can be traversed using A* like you said. That part I get. Its the actual implementation details that escape me. Where are the actual nodes? the center of the polygon? the edges?:frowning:.

@DarkHyudrA I guess I am starting off with a bit too much complexity. I’ve decided to go back to using a grid for my game. BUT now I wanna make this just for fun. So I thought that maybe I should start with the simplest way to do this, triangles, which I think have a relatively simple point-in-triangle test? Ummm I don’t think I’ve head of funnel algorithms. What are they used for?

(azrafe7) #7

Maybe the daedalus lib is what you’re looking for. An intro here: http://totologic.blogspot.it/2013/12/introducing-daedalus-lib_19.html

And if you go through that blog you’ll find some interesting info about half-edge data structures, triangulation, etc…

(Zachary Lewis) #8

Here’s something to think about.

Navigation meshes are used all the time in games. You even used them when you created your A* pathfinding algorithm!

A navigation mesh is just a graph of points that hold reference to other points in the graph. A grid is a graph of items with relationships to other items in the graph. A grid can be used as a very strict implementation of a navigation mesh!

Each cell on the grid can be considered a navigation point, and it is linked with four (eight, if you allow diagonal grid traversal) other points — its adjacent cells. The A* search algorithm doesn’t care if it’s operating on a grid or a mesh: All it does is find the cheapest path to a target node.

(rostok) #9

Well, I did it. Using arbitrary 2d mesh and simple A* implementation. My approach was as follows: world has number of solid impassible objects (called solids). To simplify collision detection with solids I assumed that each of them is a regular polygon. Based on this I have build navmesh. There are number of ways to do it. First quite simple - triangulate solids centers, and then again from such mesh use triangle centers as waypoints and triangulate again. Alternatively you could scale up each solid and use its vertices as waypoints. Remember to include option for adding arbitrary waypoints, it helped me a lot. IMHO this is way better than grid as you don’t have to cover empty areas. Pathfinding is pretty straitforwad, do A* and then optimize path because following A* result path doesn’t include cutting corners.

As for performance I used QuadTrees for both waypoints and solids in order to speed up calculations. I also created simple cache engine not to create those structures with level initialization. I stored waypoints, edges and look-up table. This final structure is symmetrical NxN matrix (with N being number of nodes) that has already all nodes in it. Once built it can yield results instantly.

Unfortunately my code is quite shitty and undocumented but for triangulation I would recommend net.nicoptere.delaunay package http://en.nicoptere.net/. Stable and predictible.

(Hussein Tammam) #10

Thanks for all the insightful ideas and resources guys! I’ll be sure to read into everything. @azrafe7 Looking at the video of the lib, it looks exactly like what I was looking for :stuck_out_tongue: @rostok wow thanks for the detailed process. there’s a lotta steps to this haha. If you don’t mind I would love to look at your shitty, undocumented code :smile: