Jump to content
  • Advertisement
Galdred

How to determine whether a region of a tiled hexmap is convex?

This topic is 375 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a set of tiles in an hexagonal coordinate system, and I want to see whether it forms an "almost convex" region. By almost convex, I mean that a square with zigzaging hex edges would still count as convex.

The idea is to split non convex regions into convex ones, and merge small regions into larger convex ones.

What I don't want is merging a corridor with a room or 2 rooms separated by a wall together.

XJ1YVKx.png

I was thinking about sweeping a line along 2 axis and see whether it goes through any missing tile (in case of diagonal, the check would fail only if both tiles are missing).

Would that work?

Edit: it wouldn't, as a L or cross shaped area would pass.

 

 

How can I do it?

Edited by Galdred

Share this post


Link to post
Share on other sites
Advertisement

 

I found a way to do it:

 

First of all, tiles that were surrounded by 4 tiles of another region were converted to this region to avoid weird borders, until there was no such tile left.

The polygon theorem says that all the angles of a polygon should be clockwise or counter clockwise.

In a hexmap, that would translate more or less to: no hexagon that is not in the area should be adjacent to 3 or more hexagons of the area.

convex3.png.20b5abf8fd1bd6fbc0c21a8479b490fe.png

If we didn't care about the quasi convex corner cases, just checking that no neighbors  is close to 3 region hex would be enough, but we also have to make sure our algorithm does not throw away cases we want to keep.

 

One way to do that would be to check that the region does not cross the zigzaging line passing through one of these neighbors:(cf image convex3b.png) 

 

convex3b.png

 

In my game, I chose to accept a more lenient check that still result in reasonably

shaped areas. (because it works better with the shape of my walls).

convex3_gamerule.png.19533ebb25199e3c194f86db343aaa44.png

 

 

Edited by Galdred

Share this post


Link to post
Share on other sites

Indee,d that is what I planned to do first. One nice property is that it would work well with the zigzaging vertical lines indeed,, but then, I would still have to floodfill to check whether all tiles inside the convex hull are inside the area (by floodfilling?) to see whether it is convex,, no?

And it seems slower than just checking the border tiles and check their neighbors (especially since I already had to track them).

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!