2
\$\begingroup\$

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) Tilemap Example

Visualization of the wanted polygons

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I usually refer to marching squares. However Flood fill and memorize the border pieces seems to be a valid alternative. \$\endgroup\$ – Trilarion Oct 14 '14 at 12:34
  • \$\begingroup\$ Marching squares is a bit different thing, although similar. \$\endgroup\$ – Kromster says support Monica Oct 14 '14 at 12:39

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.