I’m making this post as gaps between colony cells has always been quite a big issue.There are still gaps between the cells even after my stretching algorithm implementation. Players often wish were no gaps whatsoever. It turns out to be quite complicated issue for a few reasons. I have been thinking a lot about the possibilities to achieve full gap fill but there were some problems I couldn’t overcome. I don’t know if I will be able to do it, but hopefully it might help someone who will try to tackle this issue in the future.
Current issues
-
The generated membrane is convex, even though the cell plans often are not. This can lead to overlaps in the membranes of the organism and in some rare cases enables creation of “matryoshka” colonies
-
The generated membrane is bigger then the cell hexes build plan (it has a padding). Because of that MULTICELLULAR_CELL_DISTANCE_MULTIPLIER = 1.55f has been added, so that positions of the spawned cells are multiplier by 1.55f relative to the cell layout calculated by the positioning algorithm. This makes it so that gaps between cells can be different depending on how thick they are. Big cells will have much bigger gaps between them then small ones. Also thin cells (3 hexes thin) will overlap in certain configurations because the multiplier is too small for them.
We have to keep those issues in mind. Whatever stretching algorithm we come up with, getting rid of the issues above will probably be necessary.
Possible fixes
Fill the gaps to make cells convex
After the player edits their cell, fill in the hole with “dummy” hexes. This will prevent “matryoshka” colonies.
Get rid of MULTICELLULAR_CELL_DISTANCE_MULTIPLIER by adding padding
This is the only idea I had. I don’t quite like it, but makes the spawned cells positioning more predicatable and regular regardless of the thickness of the cells. I hoped the 1 hex padding around the cell would be enough, but of course it isn’t. There needs to be 2 hexes padding ;/
1 hex padding
2 hexes padding
How stretching currently works
We process each pair of cells that neighobur each other:
- A point is created between the cells on the line between their centers,
- For both cells 2 tangent lines are drawn going through that created middle point,
- The cells’ membrane points are cast onto that line if they do not overlap with other cells
Different algorithm
The other algorithm I came up with is harder to implement, but leaves minimal gaps (if any) but also has colony edge issue which I couldn’t fix…
Requirements
Cells need to be QUARANTEED to not overlap, otherwise they will create very ugly artefacts
Steps
- Create voronoi-like borders between the cells. For each 2 cells get 2 closest points on their membranes. Create a temporary segment between them and then create a line that is perpendicular to that segment and goes through the middle of it.
- When its done for all cells (in certain neighbourhood for performance) voronoi-like border will be created and the membranes can be stretched. It works great inside the colonies but it is HARD to tell when not to stretch on the borders of the colonies.
Conclusion
So, this is my proposal and some issues I came across, but there might be a better algorithm that will work faster and be less fragile. If someone has any proposal, please share it here, as it really might help