2
\$\begingroup\$

I'm working on a 2D game (top down / zelda like view)

I'm struggling with navigation mesh generation, in complex scenarios my homemade algorithm is lost and too slow...

I would really love to see a detailed explanation of Hertel-Melhorn Algorithm (if you have any ressources). I'm open to suggestions for other good algorithms, as long as I can process round and square obstacles.

My map is randomly generated and obstacles can be added anytime.

  • I don't want to use a grid system, my entities are positionned freely.
  • My map is big so I can't store precalculated paths / I just need pathfinding to be efficient

I'm working with Javascript, I can't use c++ library like detour/recast


Edit

I am looking for serious documentation of fast triangulation algorithm

If I understand the process of navmesh generation :

  1. Input walkable area(s) as polygons
  2. triangulation of walkable area
  3. (Optionnal) merge triangles to big convex polygons
  4. Output a node graph
\$\endgroup\$
  • \$\begingroup\$ How exactly do you find grid systems to be a problem with freely positioned objects? \$\endgroup\$ – William Mariager Apr 15 '16 at 10:35
  • \$\begingroup\$ I can't flag the question because of the bounty, but a possible duplicate with gamedev.stackexchange.com/questions/31208/…. \$\endgroup\$ – Tyyppi_77 Apr 15 '16 at 10:36
  • \$\begingroup\$ @Tyyppi_77 my question is more about the HM algorithm, already saw this question but it did not help. WilliamMariager: obstacles and moving objects won't "snap" to a grid and I could have round objects (transformed to pseudo-round polygons). At the end, I want to generate a graph of convex polygons, but I need a fast-triangulation algorithm to achieve this \$\endgroup\$ – Apolo Apr 15 '16 at 10:53
  • 1
    \$\begingroup\$ Navigation and how things move visually are two different things. The result of navigation on a grid doesn't mean your object has to move in a gridlike manner. Just has to move from one node to the next. \$\endgroup\$ – William Mariager Apr 15 '16 at 11:00
  • \$\begingroup\$ but you can only deal with horizontal and vertical segments, right ? \$\endgroup\$ – Apolo Apr 15 '16 at 11:04
1
+50
\$\begingroup\$

I'm afraid this answer won't be satisfactory for you.

  1. You say you have obstacles, and if i understand right, these would be inside a surrounding, large polygon? The Hertel-Melhorn algorithm works on a single polygon only, not on a polygon holding polygons inside. Additionally, having multiple obstacles (polygons) for partitioning on the outside creates a "compare each polygon to each other" situation. And that sounds very exponential = expensive.

  2. You say you want to include round obstacles. Seen from outside, a circle is concave, implying that each of it's vertices is a partition point, and the same of course goes for each other round obstacle as well. It seems this pretty much nullifies the advantage of partitioning in the first place?

A bad path for the logic may be that you want to first create a large, full data set for the entire scenario, and apply navmesh thinking on that - have that as a basis for all objects' all navigation, and maybe for a loger period of time, while yet having moving (or at least appearing/disappearing) obstacles. As partitioning is a "global" thing, each minor change somewhere would cause an entire arena re-partitioning?

Perhaps it would still be more sensible to apply local-to-the-moving-object pathfinding grids (small, isolated ones) with high granularity, such that only take into consideration what is relevant for (very nearby to) the object in question, at it's very current position and only for the next few moments. And then have a larger scale similar, for general (main goal) movement directions?

Also to note: Moving objects do often not have to follow grid points (or node points) exactly. This depends on what they are. You can still make them dislike turning, react slowly, aim n points ahead, calculate curves/polynoms to follow in the grid, etc.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your try. I'm aware circle being a problem, that's why I turn them into polygons. I had a look at people.mpi-inf.mpg.de/~mehlhorn/ftp/FastTriangulation.pdf and I am looking for the outer tirangulation algorithm. My map is divided into chunks and each one is responsible of maintaining its navmesh. This way I have multiple levels of pathfinding and I can avoid generating a huge navmesh each time something is added. \$\endgroup\$ – Apolo Apr 16 '16 at 17:01
  • \$\begingroup\$ It's not as much the circle (which IS a polygon) being the problem, but that your polygon is not simple - you want to triangulate between multiple polygons. BUT: Would it be acceptable to merge any obstacle polygon with the surrounding "arena" polygon, each time one appears (and reverse as it disappears), so that you still end up with one simple polygon for that chunk? This would simply mean finding the closest vertex in the "full" poly. THEN the HM algorithm (which is rather simple to implement) would do the job you want. You'd possibly have to number each obstacle, for chain breaking issues. \$\endgroup\$ – Stormwind Apr 16 '16 at 19:20
  • \$\begingroup\$ I made a pen to show different use case : codepen.io/VincentCharpentier/full/bpMYVd I don't see how you would merge an obstacle with the area polygon if they have no vertice in common (first example). (Thanks for your help) \$\endgroup\$ – Apolo Apr 17 '16 at 10:00
  • \$\begingroup\$ Maybe I should go for a Delaunay triangulation instead ? It seems to accept holes in the poly \$\endgroup\$ – Apolo Apr 17 '16 at 10:01
  • \$\begingroup\$ You would connect the obstacle square/poly with the surrounding arena poly, by drawing two lines, one from an arena corner A to an obstacle corner B, and one from that same corner B back to the same arena corner A, hence merging the two polys into one. It would have two vertexes on top of each other, but that shouldn't be a problem, just keep track of the line segment's direction, to be able to skip the bad line of them when testing for opposite vertexes in the HM partition. Ofc cut the arena poly where this happens. Same with next obstacle, "bridge" to a nearby arena poly vertex. \$\endgroup\$ – Stormwind Apr 17 '16 at 11:57
0
\$\begingroup\$

I believe, if you are creating a voxel mesh up 2D, you should create a class that takes a 2D position (Vector2), and one byte (0-255). Every position, there is a value from 0 to 1, and there is a function in the script the AI that makes it surround a position, and a script that do it an interaction between the positions of enemies and items from the list, and when are with a distance, I know it, 10, it calls the function or void AI and passes the corresponding position.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.