Bentobox: Do not make assumptions about island locations

[leonardochaia]

Description

Describe the bug

Hi guys.

When I introduced NewIslandLocationStrategy on https://github.com/BentoBoxWorld/BentoBox/pull/984 I didn't consider that other places of the code expected the islands to be created in a grid pattern.

This seems to be due to IslandsManager.getIslandAt not returning an island at the provided location when there's actually one.
After following the code, it looks like the culprit is IslandGrid class. It's kind-of a data-structure used to store the islands in memory by the IslandCache. As the class name suggest, this assumes a grid-like island location strategy.

Steps to reproduce the behavior

Currently, if you provide a custom NewIslandLocationStrategy which does not follow a grid pattern (i.e circle) many features will not work correctly, including protection and anything that has to do with determining if "its inside the island space".

Screenshots and videos

I'd expect /is info to return the island on the left at that location, since it's inside island space.

Expected behavior

I expect IslandsManager.getIslandAt to return the correct information despite of the NewIslandLocationStrategy being used.

Environment

Server

• OS: Docker container itzg/docker-minecraft-server
• Java version: Java 1.8 (OpenJDK 64-Bit Server VM 25.212-b04) Host: Linux 4.15.0-65-generic (amd64)

Plugins

Only bentobox

BentoBox setup

Custom built bentobox based off 1.8. Everything default except location strategy.

[tastybento]

Yes, we absolutely use a grid. Islands are assumed to operate in 2D space with X and Z coordinates, to have a square area and be on a grid.

The 2D data structure in memory is used because it's fast. It can locate whether a location is on an island quickly, which has to be done every move event for every in-world player. If you can come up with an equally fast or faster method of island determination, then I'm ready for your PR!

Currently, if you provide a custom NewIslandLocationStrategy which does not follow a grid pattern (i.e circle) many features will not work correctly, including protection and anything that has to do with determining if "its inside the island space".

Yes. You would have to do a circle algorithm that snaps to the grid. There is a static Util method getClosestIsland(Location location) that you can use for that.

[leonardochaia]

Yes, we absolutely use a grid. Islands are assumed to operate in 2D space with X and Z coordinates, to have a square area and be on a grid.

This changed when https://github.com/BentoBoxWorld/BentoBox/pull/984 was merged. Addon creators can now change the grid behavior, which does make this behavior a bug, IMHO.

The 2D data structure in memory is used because it's fast. It can locate whether a location is on an island quickly, which has to be done every move event for every in-world player. If you can come up with an equally fast or faster method of island determination, then I'm ready for your PR!

That's what I saw: since it's quite performance critical I'm hesitant to change it. Ideally, BentoBox should not make any assumptions on where islands are gonna be generated. I understand that the current data structure is perfect for grids, is there any balanced algorithm that can work for other patterns too?

Yes. You would have to do a circle algorithm that snaps to the grid. There is a static Util method getClosestIsland(Location location) that you can use for that.

I'm not sure I follow here. My NewIslandLocationStrategy should provide locations "based on a circle algorithm that snaps to the grid"? Or a new implementation of IslandGrid that does so?

Either way I'm not really quite sure how to do "a circle algorithm that snaps to the grid", but could be a workaround. Will look into it.

I wouldn't close this since, IMHO this is currently an issue. The framework allows to customize island location generation but then assumes that the islands will be generated in a grid.

[tastybento]

Yes, we absolutely use a grid. Islands are assumed to operate in 2D space with X and Z coordinates, to have a square area and be on a grid.

This changed when #984 was merged. Addon creators can now change the grid behavior, which does make this behavior a bug, IMHO.

984 allows you to pick a new island location. However, it must (for now) still be on the grid. If it isn't then methods like fixIslandCenter in IslandsManager will try to fix that on loading. Essentially, you can place your next island anywhere in the world, but it must be on a gridline. Further, the island's min and max coordinates must not overlap any other island in the vicinity. If it does, then it'll be flagged and quarantined at load time.

The 2D data structure in memory is used because it's fast. It can locate whether a location is on an island quickly, which has to be done every move event for every in-world player. If you can come up with an equally fast or faster method of island determination, then I'm ready for your PR!

That's what I saw: since it's quite performance critical I'm hesitant to change it. Ideally, BentoBox should not make any assumptions on where islands are gonna be generated. I understand that the current data structure is perfect for grids, is there any balanced algorithm that can work for other patterns too?

Technically, the treemap system doesn't enforce a grid. It was originally designed to support variable-sized islands and locations and can do that. It is other code that assumes a grid, like in IslandsManager. There are some good reasons for this that are more practical than anything and involve being robust to real-life admin challenges, like importing legacy data sets (like ASkyBlock) that may have duplicate/overlapping database entries, mismanagement of the configs (changing the island distance for example) or just plain bugs that muck up the placement of islands.
It may be possible to go through the code carefully and refactor these approaches, but the GridManager part should not need to change.

Yes. You would have to do a circle algorithm that snaps to the grid. There is a static Util method getClosestIsland(Location location) that you can use for that.

I'm not sure I follow here. My NewIslandLocationStrategy should provide locations "based on a circle algorithm that snaps to the grid"? Or a new implementation of IslandGrid that does so?

Either way I'm not really quite sure how to do "a circle algorithm that snaps to the grid", but could be a workaround. Will look into it.

In your NewIslandLocationStrategy have it pick a new island based on a concentric circle or spiral algorithm then pass that location to the ClosestIsland utility function and then check if the result is already occupied. If not then you have your next island, if not, move further around the circle. The upshot is that you will have a layout something like this:

[leonardochaia]

Thank you @tastybento for your deep explanation.
TBH, I was not aware that a grid-like implementation was needed, I should have looked deeper in the code.

I understand now that this would be quite a change, and it's not really needed considering your last paragraph. Will try that over the weekend.

Again, thank you guys. Still got lot's to learn. 😁

[tastybento]

Let me know if there's any other issues.