koobas.hobune.stream
How to keep and grow a polygonal area in 2D
Working on a 2D game and I have a player 'base'. Think of a strategy game where you have your buildings in an area. Now I want my NPCs to be able to choose a random location within the confines of this base and walk around it - think of an idle task where they move around.
Here's the problem - I can't just use a rect for this base since the player can construct buildings and essentially extend the 'shape' of the base in any way. I need something more accurate that I can also extend.
A polygon (list of points) seem like a good solution, but I have a bunch of questions on how to do this:
I just built a new building, how do I grow my polygon?
I thought about finding the 2 closest points to this new structure and adding a point behind it - thus adding a triangle shape to my polygon. Problem is this can quickly get outta hand and has some crappy edge cases (start with a rect and draw it on a piece of paper using circles as buildings. You'll reach a point where it looks horrible with concave shapes).
With any solution for the above problem I will need to find a way to 'trim' the polygon and make sure it's not concave and doesn't grow too big in terms of points (the actual size doesn't matter).
In this 'base' there will be unique locations (perimeter is important for defenders, farming structures important for farming NPCs). How should I approach this problem? Should I make the base definition be constructed of smaller bases so that I 'create' bases on the fly in regards to my specific needs? For example I now need my blacksmith area and farming area combined, so I create an area constructed of both. How do I go about doing that?
This gets super complicated and I'm in too deep and wondering if I'm missing a much simpler solution.
Any ideas? How would you approach this?
Sounds like a job for Nav$$anonymous$$eshes to me. Have you looked into them at all?
For a single convexed polygon to envelop the base:
I would add the points to the current polygon I have and than create a convex polygon from the new points and save the new Polygon.
https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/amp/
I would wait on reducing the polygon until i see the results of a lot of test cases
This looks like a great solution. Each building added will require a recalculation but we're not talking about anything massive and we're not adding a million buildings.
I'm still not sure how to denote specific areas inside but I might just use lists of buildings for every type of area and work something out when it comes to it's 'area'.
Thank you!
You could check distamce from one polygon to another and if it's lower then Delta attach otherwise, create new polygon.
You will need to adjust the algorithm to accumulate multiple polygons and select who (or even how many) to join with the new building
Some thoughts: I'd look to maintain separate rectangle lists. 1 list for each set of important regions, such as a farms, and then another list for the base footprint.
For the base footprint, you'd merge/trim rectangles whenever you add a new structure/zone. You'd need to make design decisions about the rules that govern your establishment. For example, can buildings/zones overlap existing ones? Do new buildings/zones need to be adjacent to existing ones?
The new rectangle can be fully overlapped by 1 or more existing rectangles. If this is the case, nothing needs to be added fo the footprint rectangles list.
The new rectangle can be partially overlapped by 1 or more existing rectangles. For this case, you would split the new rectangle and only add the portion that is not overlapping.
The new rectangle could align with an existing rectangle (if it shares an edge with an existing rectangle) where you would merge it into the other rectangle.
The new rectangle could not overlap or share an edge with any existing rectangles, and you can determine if you want to discard it as an invalid base placement (making an exception if it's your first rectangle) or allow for non-adjacent rectangles in your base footprint (probably tricky for perimeter patrols that way though)
'+1 Jarvis
This has a mathematical solution to it, and it is called... Drum roll... Ray Casting! Take the point you wish to test against your polygon. Draw a ray from it in any direction, although for simplicity sake make it horizontal. Check the times it intersects your polygon - this is an easy test done with line segments intersection, like 9th grade. If you are using a horizontal line then you can compare the points' Y values. If it intersects your polygon even times it is outside of it. If odd times then it is inside. If it is outside you can add it to your polygon's list of points in the right location, effectively making it larger.
