Is it possible to implement A* path finding with a set of objects containing 4 or more vertices each?

Question

I have a set of objects (rectangles having 4 vertices of (X,Y) each) draw on a map using OpenGL ES. I would want to implement way finding between each of them.

For example I have rectangles A,B,C,D,E

Structure:

A[Vertex(X,Y),Vertex(X,Y),Vertex(X,Y),Vertex(X,Y)] - Rectangle A
..
..
E[Vertex(X,Y),Vertex(X,Y),Vertex(X,Y),Vertex(X,Y)] - Rectangle E

And I have no other information other than this. Is it possible to draw a path from B to E using A* path finding alogrithm.

Is there anything else required for its implemented? I've looked up A star search implementation but most of them word on grid based maps, where they calculate costs with the nearby nodes and use them for finding the map? Is there a way I could I calculate those with the data I have?

Answer 1

I can think of two ways off the top of my head to transform your data into something A* can work with, keeping in mind that A* can work on graphs, not just grids.

1. The simplest would just be to "gridify" your data. Come up with a high enough resolution grid covering the area you want to perform pathfinding in, and then mark cells as occupied, or not, based on whether or not they fall within your rectangles. "high enough resolution" might require more memory than you care to expend.
2. Apply a polygon triangulation algorithm to a polygon representing the open, traversable area of your your map, and then turn the triangles into vertices of a graph. The graph vertices would have edges between them whenever their corresponding triangles touched one another. Determining the weights to assign to the graph edges to ensure optimal pathfinding might be tricky. Smaller triangles should help.

In this case, you'll need to perform triangulation on a polygon with a number of holes in it, which complicates things. Fortunately, the subject has already come up here on stackoverflow, in "Polygon Triangulation with Holes". They point to a library called "Triangle", which has a picture of exactly what you need done, right on the front page. Their demo page has some more pictures, including these helpful ones:

Suppose you do a very rough triangulation:

Paths going around corners might remain rather far from them, depending on how you convert the path on a graph to a path in your coordinate space. But if you do a much finer triangulation:

Then the paths will be able to stay closer to corners, walls, etc.

This technique ought to work for nearly any sort "map" with a polygonal outline, and polygonal areas that can't be traversed.