[SOLVED] Complete a list of vertices to form a polygonal shape with pathfinding

[Bigfoot71]

Hi there,

I would need some clarification on a question, I have a shape I have triangulated then got each center of these triangles, now I would need to define a path between two of these points in order to complete a list of vertices outside the polygon and unite with the new shape but I'm lost, I tried a lot of different techniques that worked in most cases but ended up having flaws that didn't work for me satisfied...

So here is what I would like to do, I have this shape, triangulate with all the centers obtained:


And I would like to be able to find the shortest path between two of these points while staying inside the shape (it shouldn't cut into the void if the shape is concave), a bit like this:


I've been told that with an A* library I should be able to do this, so I've tried all (or maybe all) of the community created libraries, but can't find how to do it, if anyone Does anyone have any ideas to give me or who could guide me on what to do, that would be great because I'm a little lost...

[milon]

I implemented an A* algorithm in a mostly-discontinued project here. You can see the source code etc by unzipping the .love file. Note that my implementation assumes a 2D integer-based grid, rather than floating-point nodes. You may need to alter the code to work for your case. If you use it, great! No attribution is required.

To avoid a region of space, set the "cost" for that area (any non-triangle region) to math.huge (infinity). This guarantees the algorithm will follow a "cheaper" path instead.

[pgimeno]

A* works on graphs, not on points. You need to define both the points (vertices) and the lines (edges) that connect them for the algorithm to find the path (a subset of edges) between two vertices.

I believe there are pathfinding libraries that accept an arbitrary graph instead of a grid.

I think that using the triangle centres is not a good strategy. See https://www.david-gouveia.com/pathfindi ... ygonal-map for an alternative.

[Bigfoot71]

I implemented an A* algorithm in a mostly-discontinued project here

I tried but the problem is that I'm on a 4000x4000 map for the game I'm working on, so setting each node with a cost can be very slow and tedious, otherwise I should see how to reduce the size virtually and still have a valid path, quite complicated so, I'm starting to think that the A* method is not the right one in my case, maybe I'll change the title of my question...

But nice job by the way!

I think that using the triangle centres is not a good strategy. See https://www.david-gouveia.com/pathfindi ... ygonal-map for an alternative.

As for the centers of the triangles, I need to work like this, the path obtained will be used to fill a shape drawn by the player then to unite it to the first one. I had made myself a function that returned me the shortest path but sometimes it only took the vertices of the border of the polygon and it caused problems to unite the two shapes afterwards.

I will go and study the link you sent me, thank you for your help.

Edit:

Precision for milon, when I say it was slow, I tried it with the AStar library which supports floating point and it was the initialization of the nodes which was very long, the rest I was able to optimize to work only on the area where the polygon is (although that was slow too). If ever an A* algorithm can do the trick and I can't do it any other way, I'll see to completely readapt the work you've done and I will see if it works better.

[darkfrei]

Pathfun polygon pathfinding solver
viewtopic.php?t=91750

[milon]

As for the centers of the triangles, I need to work like this, the path obtained will be used to fill a shape drawn by the player then to unite it to the first one. I had made myself a function that returned me the shortest path but sometimes it only took the vertices of the border of the polygon and it caused problems to unite the two shapes afterwards.

So what's the big picture here? Do you need pathfinding to allow AI entities to move around? Or is it just to define a shape to draw? It's starting to sound more like a case for Bezier curves.

[Bigfoot71]

Pathfun polygon pathfinding solver
viewtopic.php?t=91750

I managed to get what I wanted! Without going through the centers of the triangles (only at the start and at the finish), the problem is that I come across this error of which I cannot yet determine the cause (knowing that I give him the list of triangles, converted in "table of table" for the positions):

Code: Select all

lib/pathfun/navigation.lua:323: attempt to index local 'p' (a nil value)
stack traceback:
        [string "boot.lua"]:777: in function '__index'
        lib/pathfun/navigation.lua:323: in function '_shortest_path'
        lib/pathfun/navigation.lua:394: in function 'shortest_path'

So what's the big picture here? Do you need pathfinding to allow AI entities to move around? Or is it just to define a shape to draw? It's starting to sound more like a case for Bezier curves.

The image was simply a test script which seemed to me more demonstrative to explain my problem. The goal is to complete a shape drawn by the player's path by going back inside the polygon in order to unite them.

Like this (with the player's path in blue and the completion in yellow):



Here it is a fairly simple shape, but completing the shape will be useful to me if the shape is concave and the player makes a simple straight line between two ends of the shape, otherwise it may cause me either triangulation problems , or form union problems.

I will be interested in what you send me, thank you.

Edit: I just tried Bezier curves but that's not what I need unfortunately, but I discovered a new feature of Love2d, thanks

[Bigfoot71]

Problem finally solved thanks to pahtfun library !

The error I was getting (see above) most likely came from my function that generated the polygons, there must have been a problem during the triangulation that made it invalid for pathfun. I rewrote this function in the meantime and I haven't had any problems since, thank you all for your help