Range was brought below 144 again? Square farms will now work again, 4x intended limits

[GavJenks]

Reason given was "Changed all ranges to 70 to keep spigot from filtering the getentities call."

Not sure what that means, maybe it needs something other than just a config change then, but at range 70, people can have 4 farms in corners and a single player can load 4x as many entities as you want them to be able to.

For example, you just reduced pigmen to 5, if I feel like getting more gold again anyway, I could just build 12 or so portals in 4 corners of a render distance and get 20 pigmen at once in one farm.

[ProgrammerDan]

Spigot was noisily tossing out ranged getEntity calls where the range was > 80 blocks. With testing, it was discovered that 70 blocks represented a "safe" getEntity call, where safe was Spigot stopped rejecting the request.

[GavJenks]

Okay, so then some other method is needed to stop people from using square farm layouts.

[ttk2]

Just lower the limits. Or provide some fix for mustercull native.

On Tue, May 19, 2015, 11:20 AM GavJenks notifications@github.com wrote:

Okay, so then some other method is needed to stop people from using square farm layouts.

— Reply to this email directly or view it on GitHub https://github.com/Civcraft/MusterCull/issues/29#issuecomment-103575534.

[GavJenks]

You can't "just lower the limits" -- that severely punishes everybody who built a normal, responsible farm, and forces everybody to go make stupid minmax square farms just to get by...

The most straightforward fix would be to rewrite a less dumb custom rangechecker method.

This would just be bukkit's world.getLivingEntities() which returns a global list. Then iterate through the list, checking each one with two nested if() statements, one for X range, one for Z range within the actual range we want, 160 or so blocks. If any entity falls outside of X, don't waste the cycles checking Z.

That would be the same thing bukkit is already doing, although without a silly range cap (the algorithm's speed shouldn't even be related at all to range... I have no idea why they'd do that). Actually, it would be very slightly faster than bukkit, since we don't need to check Y.

I've never used getEntitiesByClass() but that might be faster (I kind of doubt it though, checking the classes is probably slower or equal than checking the ranges)

[ttk2]

why are they even limiting based on range then?

On Tue, May 19, 2015 at 5:19 PM GavJenks notifications@github.com wrote:

You can't "just lower the limits" -- that severely punishes everybody who built a normal, responsible farm, and forces everybody to go make stupid minmax square farms just to get by...

The most straightforward fix would be to rewrite a less dumb custom rangechecker method.

This would just be bukkit's world.getLivingEntities() which returns a global list. Then iterate through the list, checking each one with two nested if() statements, one for X range, one for Z range within the actual range we want, 160 or so blocks. If any entity falls outside of X, don't waste the cycles checking Z.

That would be the same thing bukkit is already doing, although without a stupid, patronizing range cap (the algorithm's speed shouldn't even be related at all to range...). Actually, it would be very slightly faster than bukkit, since we don't need to check Y.

I've never used getEntitiesByClass() but that might be faster (I kind of doubt it though, checking the classes is probably slower or equal than checking the ranges)

— Reply to this email directly or view it on GitHub https://github.com/Civcraft/MusterCull/issues/29#issuecomment-103682932.

[rourke750]

@ttk2 According to ThinkofDeath it has huge issues and was resource intensive. Anyways if anyone wants to tackle this issue be my guest because there is so much more important stuff then this

[GavJenks]

Maybe they aren't after all using the obvious O(1) algorithm, but something else? I don't know.

Agreed it's not super high priority right now.

[ProgrammerDan]

Here's one person's solution:

http://www.hastebin.com/viduqofuqu.avrasm

[ProgrammerDan]

using the obvious O(1) algorithm

Care to explain? Dealing with 3D lookups, there are no obvious O(1) algorithms that I am aware of for area searching. Full list traversal would be O(n); some clever space partition algorithms, O(ln(n)) --- but none are constant time.

[GavJenks]

If the independent variable is number of server entities, it is O(n) (or higher?). But we're talking about different ranges of search as the variable of interest here.

In terms of the independent variable being range, I'm saying it's O(1) in that sense, because checking for the number of relevant entities in a range of 100 blocks should be no faster or slower than checkin in a range of 50 blocks or a range of 2 blocks, or a range of 10,000 blocks. Because subtracting a large number from each entity's coordinates should be no slower than subtracting a large number.

So talking about f(range) not f(entities). Sorry if that's not exactly proper terminology, but hopefully my meaning is clear regardless now.

On Wed, May 20, 2015 at 5:31 PM, Daniel Boston notifications@github.com wrote:

using the obvious O(1) algorithm

Care to explain? Dealing with 3D lookups, there are no obvious O(1) algorithms that I am aware of for area searching. Full list traversal would be O(n); some clever space partition algorithms, O(ln(n)) --- but none are constant time.

— Reply to this email directly or view it on GitHub https://github.com/Civcraft/MusterCull/issues/29#issuecomment-104062515.

[ProgrammerDan]

Consider the datastructures involved; if they are already "geolocated", then I'd hazard that your core conceit has merit -- namely, it is possible to perform constant time searching (in big-O notation) against geographically organized data, if you really know what you're doing.

I have doubts that the folks building spigot or minecraft fit that category, and that leaves us with the most likely candidates: Hashmaps and lists, without much geographically located-ness among them. Searching likely involves iteration over active entities, as you imply by saying "subtracting a large number from each ...". The from each is a killer, means we have to touch each active entity.

That said, unless spigot's developers are dunces, I agree with your principle thrust -- if they aren't using pre-optimized datastructures with entities geolocated, then it shouldn't make much difference whether you are looking at range(50) vs. range(500) -- it's still going to be a ton of iteration. So ... I agree? It's not clear to me yet why this change was enforced, although I'm planning to look into it.

[GavJenks]

O(1) in terms of range as the variable. O(n) in terms of number of entities on the server.

For the problem of range checking itself in any one instance, number of entities is fixed though. So i am talking in terms of the fact that any range should be equally quick to look up since the bukkit methods generally begin with a worldwide collection of entities. And so subtracting a large number from each coordinate is not slower than subtracting a small number from each coordinate. On May 20, 2015 5:32 PM, "Daniel Boston" notifications@github.com wrote:

using the obvious O(1) algorithm

Care to explain? Dealing with 3D lookups, there are no obvious O(1) algorithms that I am aware of for area searching. Full list traversal would be O(n); some clever space partition algorithms, O(ln(n)) --- but none are constant time.

— Reply to this email directly or view it on GitHub https://github.com/Civcraft/MusterCull/issues/29#issuecomment-104062515.

[ProgrammerDan]

Yeah, my longwind problem made it seem like I didn't grok you, but I do.

No worries.

My point was same as yours; just your terminology is incorrect. It's not an O(1) function to search a list by iteration, because the order of the most expensive operation is the iteration. Checking if an object is inside a range or not, yeah, that's an O(1) operation for each element in the iteration ... but the algorithm as a whole is O(n). So just use O(n). Your point stands, though, it doesn't make any difference to the ranging function as it'll still need to search "N" entities .... unless they are using geolocated datastructures, then my longwind points apply.

[GavJenks]

Yes that is what I'm saying -- I don't think bukkit offers any way to get entities that does not begin explicitly or internally with a global list of non-geographihcally-organized entities.

Which makes it seem very odd that it should throw an error based on range. But since it does for whatever reason, we could just re-code our own iteration that is no worse than theirs (given the starting point of a non-geo-global entity list), but doesn't have the bizarre restriction placed on it.

On Thu, May 21, 2015 at 4:45 PM, Daniel Boston notifications@github.com wrote:

Consider the datastructures involved; if they are already "geolocated", then I'd hazard that your core conceit has merit -- namely, it is possible to perform constant time searching (in big-O notation) against geographically organized data, if you really know what you're doing.

I have doubts that the folks building spigot or minecraft fit that category, and that leaves us with the most likely candidates: Hashmaps and lists, without much geographically located-ness among them. Searching likely involves iteration over active entities, as you imply by saying "subtracting a large number from each ...". The from each is a killer, means we have to touch each active entity.

That said, unless spigot's developers are dunces, I agree with your principle thrust -- if they aren't using pre-optimized datastructures with entities geolocated, then it shouldn't make much difference whether you are looking at range(50) vs. range(500) -- it's still going to be a ton of iteration. So ... I agree? It's not clear to me yet why this change was enforced, although I'm planning to look into it.

— Reply to this email directly or view it on GitHub https://github.com/Civcraft/MusterCull/issues/29#issuecomment-104430481.

[idoash4]

https://github.com/Civcraft/MusterCull/pull/34