# How to create polygons from tilemap areas?

I'm currently working on a project which needs simple AI's to walk around using pathfinding.

I'm trying to find a way to generate a polygon based on the connected tiles (explained below), an i'm wondering how to do this.

I know about the flood fill algorithm, but have never used it before.

This is what a map (could) look like (maps are created by the players)

Basically, i wan't the yellow outline as one polygon (vector2 array) and the red outline/area as another polygon (vector2 array)

• How do you plan that constructing 2 polygons (in this example) will help your AI pathfinding? Commented Oct 14, 2014 at 12:12
• Commented Oct 14, 2014 at 12:32

For the exact problem (how to create a polygon from tiles forming some area) you basically:

1. Flood fill the area to limit the number of tiles you check and avoid situations alike checkerboard pattern (where edge node can have 4 neighbour edge nodes)
2. Pick up a node on the edge of the area
3. Look for the nodes that are connected to it, that lay on the edge too (there should be always 2)
4. At first you will get 2 nodes, pick one to go one of the direction
5. Repeat step2 for new node, ignoring the one you already parsed
6. Repeat 2-4 until you have closed the loop - that is your polygon.
7. Optionally remove nodes from straight sides.

P.S. This algo has a name, but I cannot recall it, sorry.

• I usually refer to marching squares. However Flood fill and memorize the border pieces seems to be a valid alternative. Commented Oct 14, 2014 at 12:34
• Marching squares is a bit different thing, although similar. Commented Oct 14, 2014 at 12:39