Handle new kinds of bounding boxes

[rom1504]

For example a carpet is not really a block but we shouldn't fall through it.
See also :

• fences
• doors
• bars

Currently we'll consider a carpet has an empy bounding box but that's not perfect.

[deathcap]

also slabs, stairs, snow (etc.)? simplest non-cubic bounding box is of blocks of varying heights:

http://minecraft.gamepedia.com/Solid_block#Heights

Height	Block types
2	Door, Iron Door
1 1/2	Fence, Cobblestone Wall
15/16	Cactus
7/8	Soul Sand, Chest, Ender Chest, Trapped Chest, Brewing Stand (stand part)
13/16	End Portal Frame (without Eye of Ender)
3/4	Enchantment Table, Cocoa Bean (plant), Head (on wall)
5/8	Inside of Hopper
9/16	Bed
1/2	Bottom slab, Head (on ground), bottom part of Stair, Cake
3/8	Daylight Sensor, Flower Pot
5/16	Inside of Cauldron
3/16	Bottom Trapdoor
1/8	Brewing Stand (base), Redstone Repeater, Redstone Comparator, Snow
1/16	Carpet
1/64	Lily Pad

[demipixel]

How do we want to handle all these? Different bounding boxes can be an issue, but things like doors or fences which can change depending on blocks or state, or even brewing stands which have multiple "bound boxes" will have an issue. One idea was to make bounding box an area of boxes, ex:

[ { x: 0, y: 0, z: 0, width: 1, length: 1, height: 0.5 } ]

Not ideal but better than nothing. Might cause it to get a bit slow.

As for actually supporting them, we have SOME support right now. We test for all blocks in the area (surrounding the character) but the current method returns a bool. Instead we're going to need to return the bounding box(es). From there we can calculate the height each player would be on any given block (full block VS on top of brewing stand). Then limit the player's Y to the highest one (similar for X and Z).

When I was writing my own node-minecraft-protocol bot, I found that all I would need to do is set the player's position inside of a block that was 0.5 height or lower (like a slab). As soon as the bot thought it was inside a slab, the "highest block" it was stepping on was no longer air, but the slab so it automatically stepped up.

[thejoshwolfe]

this has been a known problem forever. the most daunting challenge with detailed bounding boxes is the path finding code. the path finder has a hardcoded set of jumps it believes it can make, and half slabs et al add an inordinate amount of complexity. we could change the jumping logic to do dynamic calculations, which would be very difficult to program, very expensive to compute, and perfectly correct. simple bounding boxes survived so long because they are very easy to deal with.

I don't think we should charge ahead with this issue without a plan to keep the path finding up to date. I understand that the path finding is actually a different repository, but I think it's important enough to consider here.

[thejoshwolfe]

a plan to keep the path finding up to date.

I can't find it anymore, but I used to have a navigator bot that would just fly everywhere like superman. That would be the simplest code to write, although many would consider it "cheating". The vanilla server used to do very little checking on the client's physics, so flying mods and flying bots were pretty easy to get away with. last I checked (2 years ago), the "allow-flight" setting in server.properties just sets a timer for being in the air, so it could be somewhat easy to fool.

If we implement correct bounding boxes, I propose that the navigator code do a hybrid of flying and fair physics, where it finds standable ground within a paraboloid of somewhat reasonable jumps, and then just kinda flies over to it. I believe this is the best compromise between correctness (which is also fairness) and implementation and CPU difficulty.

See also PrismarineJS/mineflayer-navigate#15

[roblabla]

I would love to see an actual benchmark showing how much CPU complexity correct bounding boxes actually inflicts. I don't think it'd be that bad. The code might be more complex, but that's another issue.

Besides, pathfinding isn't part of mineflayer AFAIK, it's part of a mineflayer plugin. Bounding boxes in mineflayer are only used for the physics engine, which I believe should be as correct and accurate as possible. Reason is simple : mineflayer bots should work on any server software, including spigot servers with NCP, which implements harsh rules for things like flying.

Plugins can still implement things in a hackish way by hijacking bot.position directly, but I seriously think it should be done outside of mineflayer core.

[rom1504]

So I think we need to :

• define how to store these bounding boxes
• handle them in physics.js (and elsewhere ?)
• see how that might affect mineflayer-navigate and how to address this

[thejoshwolfe]

on good hardware 4 years ago, we had to limit the algorithm to 10 seconds to make sure a bot would eventually give up on an impossible path before exploring the entire loaded world. Normally, straight obvious paths were nearly instant up to 100m, but I was able to craft mazes that were possible to solve, but the bot couldn't figure it out in the 10s time limit. The basic idea to fooling the bot is to build a large flat structure above the ground (like a wheat farm) with a staircase about 50m away from where you stand, then ask a bot directly below you to "come here". The algorithm will get overwhelmed exploring the possibility of navigating a larger and larger radius around him over the terrain, and won't find the staircase in time to try exploring it.

This isn't a benchmark, like you asked for, but cpu time was a limiting factor in how useful the path finding was, and, as discussed in PrismarineJS/mineflayer-navigate#2 , caused other problems, because it can lock up the main javascript thread for 10s at a time. At worst, this might theoretically kick the bot for not sending physics updates fast enough or something, although I don't remember that actually being a problem.

See also PrismarineJS/mineflayer-navigate#20 for another idea to improve CPU performance.

In general, I'm fine with implementing correct bounding boxes; this feature has been missing for years. I'm just giving a heads up that we will need to make some kind of compromises in the path finding when we do it. Either compromising correctness (by ignoring the correct bounding boxes), compromising algorithmic simplicity and performance (by exhaustively trying everything with fair jumping), or compromising fairness (by fudging the jumping physics and flying for short distances). I am a fan of the third option.

[roblabla]

Hmm, fair enough. I still think we should implement correct bounding boxes, but then maybe we could find a way to disable them in physics, reverting to the simple "solid vs air" logic, if the bot wants to.

[vogonistic]

One of the problems with speed on the path finding was that it was calculated block by block when asked for. If the path finder pre-calculates the possible areas to stand on chunk load and change, it could be sped up a lot.

On Mar 23, 2015, at 17:34, Robin Lambertz [email protected] wrote:

Hmm, fair enough. I still think we should implement correct bounding boxes, but then maybe we could find a way to disable them in physics, reverting to the simple "solid vs air" logic, if the bot wants to.

—
Reply to this email directly or view it on GitHub.

[Gjum]

OT @thejoshwolfe:

a navigator bot that would just fly everywhere like superman

Just wanted to mention that my bot does "superman" navigation by 3-step-teleporting (code).
It basically teleports 300 blocks up, then to 300 blocks over the target, then to the target; that's three position updates, so it won't be detected as flying.
The vanilla server collision checks allow you to move through blocks vertically, so this method always works as long as the position you navigate to is valid. Very cheaty but also very useful for testing.

[rom1504]

Good way to check if that works properly : checks whether the bot (jumper.js for example) can walk on soulsand on a server with no cheap plus (see #319)

After some testing : it seems you need to come out of the ground before you move out of soulsand if you want the server to accept. So : between a blockA and a blockB you need to be at max(boundingBoxA,boundingBoxB).

Actually likely the highest of the blocks you are on.

[czaarek99]

I was considering how to implement this and I'm not exactly sure what the best way would be.

I looked into the minecraft source code and it seems like there are three different ways that block bounding boxes are handled.

Bounding boxes based on state

Lets take the cake as an example. The boundingbox for a cake changes based on its state i.e how many slices of the cake are left:

protected static final AxisAlignedBB[] CAKE_AABB = new AxisAlignedBB[] {new AxisAlignedBB(0.0625D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.1875D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.3125D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.4375D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.5625D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.6875D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D), new AxisAlignedBB(0.8125D, 0.0D, 0.0625D, 0.9375D, 0.5D, 0.9375D)};
...
public AxisAlignedBB getBoundingBox(IBlockState state, IBlockAccess source, BlockPos pos)
{
    return CAKE_AABB[((Integer)state.getValue(BITES)).intValue()];
}

But state can be more than just how much there is left of a cake. For a fence the state is decided by which direction it's connected in.

Combined bounding boxes

Then there is a second type of bounding box which is a combined bounding box. A good example for this is the brewing stand. It consists of the rod and the base.

protected static final AxisAlignedBB BASE_AABB = new AxisAlignedBB(0.0D, 0.0D, 0.0D, 1.0D, 0.125D, 1.0D);
protected static final AxisAlignedBB STICK_AABB = new AxisAlignedBB(0.4375D, 0.0D, 0.4375D, 0.5625D, 0.875D, 0.5625D);
...
public void addCollisionBoxToList(IBlockState state, World worldIn, BlockPos pos, AxisAlignedBB entityBox, List<AxisAlignedBB> collidingBoxes, @Nullable Entity entityIn, boolean p_185477_7_)
{
    addCollisionBoxToList(pos, entityBox, collidingBoxes, STICK_AABB);
    addCollisionBoxToList(pos, entityBox, collidingBoxes, BASE_AABB);
}

public AxisAlignedBB getBoundingBox(IBlockState state, IBlockAccess source, BlockPos pos)
{
    return BASE_AABB;
}

Complex bounding boxes

But then comes the interesting part. Blocks like stairs which are a combination of both types. Stairs rely on state to decided which way they should face. They are also composed of multiple bounding boxes. So called quarters and eights. The quarter is if I understand the code correctly the bottom base of the Stair while the eight is the actual step in the stair block

Read BlockStairs.java

---

Now I understand that to make a simple bot that navigates around we really only need the height of a block. But if we're introducing handling of the height why not just go all the way to bounding boxes? Eventually someone would find a use for it and we would be back to implementing bounding boxes all over again. By implementing complex bounding boxes we could solve the height and navigation issue and probably more future issues.

As of right now if a block is solid or not is decided by minecraft-data. So it probably makes sense to drop this data in there.

For bounding boxes based on state this would be fairly simple to implement. You could just do something like this in minecraft-data:

{
    "id": 126,
    "displayName": "Wooden Slab",
    "name": "wooden_slab",
    "boundingBox": [
        {
		"x1": 0,
		"y1": 0,
		"z1": 0,
		"x2": 1,
		"y2": 0.5,
		"z2": 1
	},
	{
		"x1": 0,
		"y1": 0.5,
		"z1": 0,
		"x2": 1,
		"y2": 1,
		"z2": 1
	},
    ],
    "boundingBoxType": "state"
},

Where the first item is state 0 and the second item is state 1 and so on.

And for a combined bounding box you could just have a list of all the bounding boxes:

{
    "id": 117,
    "displayName": "Brewing Stand",
    "name": "brewing_stand",
    "boundingBox": [
        {
		"x1": 0,
		"y1": 0,
		"z1": 0,
		"x2": 1,
		"y2": 0.125,
		"z2": 1
	},
	{
		"x1": 0.4375,
		"y1": 0,
		"z1": 0.4375,
		"x2": 0.5625,
		"y2": 0.875,
		"z2": 0.5625
	},
    ],
    "boundingBoxType": "combined"
},

Alright! Easy enough right? The issue is when you come to complex bounding boxes like stairs. How do we handle those? If you peek into BlockStairs.java you can see that it is handled by the private static List<AxisAlignedBB> getCollisionBoxList(IBlockState bstate) function. This function takes the state into account and then combines the gives back a List of bounding boxes that the stair consits of. We could make a list of all the possible state combinations and the bounding boxes but that would make a huge list since there is a lot of combinations.

I'm not completely sure how to handle this yet and I'm open to ideas.

---

Then after we've decided on how we're going to store the data we also need to write the code that would interpret this data and chuck it into physics.js

[czaarek99]

After further consideration we could just store all the boundingboxes that make up the complex boundingbox and then just delegate the combination of them to the implementation?

{
    "id": 128,
    "displayName": "Sandstone Stairs",
    "name": "sandstone_stairs",
    "boundingBox": {
        "AAB_SLAB_TOP": {
		"x1": 0,
		"y1": 0.5,
		"z1": 0,
		"x2": 1,
		"y2": 1,
		"z2": 1
	},
	"AAB_QTR_TOP_WEST" :{
		"x1": 0,
		"y1": 0.5,
		"z1": 0,
		"x2": 0.5,
		"y2": 1,
		"z2": 1
	},
    },
    "boundingBoxType": "complex"
},

Then you would have to implement a method that combines these properly. We would also probably want to change the combined and state boundingBoxTypes to also use an object instead of an array:

{
    "id": 117,
    "displayName": "Brewing Stand",
    "name": "brewing_stand",
    "boundingBox": {
        "0": {
		"x1": 0,
		"y1": 0,
		"z1": 0,
		"x2": 1,
		"y2": 0.125,
		"z2": 1
	},
	"1": {
		"x1": 0.4375,
		"y1": 0,
		"z1": 0.4375,
		"x2": 0.5625,
		"y2": 0.875,
		"z2": 0.5625
	},
    },
    "boundingBoxType": "combined"
},

[czaarek99]

@rom1504 If you think that this is the right way to implement it please tell me. I'll get right onto coding it, just don't want to start and have to redo everything because it won't get merged 😄

[rom1504]

Sounds good to me. There's just one point missing : what is the source of bounding box information ? Is there some way to extract it automatically ? For any version of minecraft ? But anyway, we currently have no implementation of bounding box so anything you do, even if it works in just a part of the cases, is pretty good. So yes feel free to implement it. Just makes sure it works (maybe try with the jumper example and/or mineflayer navigate) I don't have much time to work directly on mineflayer myself these days, but I would definitely review any PRs you would do.

…

On Sat, Apr 14, 2018, 19:42 Cezary Borowski ***@***.***> wrote: @rom1504 <https://github.com/rom1504> If you think that this is the right way to implement it please tell me. I'll get right onto coding it, just don't want to start and have to redo everything because it won't get merged 😄 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#228 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACPN_ouR5CQ1OBQYyRFVjAISuK0rbi5jks5tojUXgaJpZM4DyuJ4> .

[czaarek99]

@rom1504 Yeah... Seems like the data extraction part might be an issue. As it currently seems to me the only way to do that is to decompile minecraft and extract them from the class files. The issue is that the bounding box data doesn't really conform to any pattern at all. The bounding boxes are usually a static final field in the class and then the getBoundingBox function decies on what to return. Seems like most of it would have to be extracted by hand.

[rom1504]

Ok well I think you can start by writing a few by hand and trying to make it work, we can think on how to write/extract all the other ones later.

…

On Mon, Apr 16, 2018, 17:17 Cezary Borowski ***@***.***> wrote: @rom1504 <https://github.com/rom1504> Yeah... Seems like the data extraction part might be an issue. As it currently seems to me the only way to do that is to decompile minecraft and extract them from the class files. The issue is that the bounding box data doesn't really conform to any pattern at all. The bounding boxes are *usually* a static final field in the class and then the getBoundingBox function decies on what to return. Seems like most of it would have to be extracted by hand. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#228 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACPN_sCcKC21pBw-mmo9-y5_D8cB28jeks5tpLX8gaJpZM4DyuJ4> .

[czaarek99]

@rom1504 I'd be fine doing all bounding boxes manually for just one version... But the issue is that I'd have to repeat the change accross like 16 versions in the minecraft-data repo which is something that I'm not interested in.

[rom1504]

Ah actually I have an idea. What about creating a bounding_boxes.json file where you just reference the block by its id (or name). That would make it much easier for us to propagate then to other versions afterwards. It's already very good if you do it for one version. To be honest I believe the hardest part is not the data, the most difficult part is changing mineflayer physic engine to handle more stuff. Anyway, don't worry if you don't support everything and anything. Start small. Really even supporting a few more cases would already be appreciated, a lot of people have asked for having that in mineflayer.

…

On Mon, Apr 16, 2018, 17:49 Cezary Borowski ***@***.***> wrote: @rom1504 <https://github.com/rom1504> I'd be fine doing all bounding boxes manually for just one version... But the issue is that I'd have to repeat the change accross like 16 versions in the minecraft-data repo which is something that I'm not interested in. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#228 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACPN_lqn2_92KNh88XRcvBLM1F-fK8Hiks5tpL2CgaJpZM4DyuJ4> .

[czaarek99]

@rom1504 Yeah that seems like a good idea. Considering the most common blocks that make the bots moving abilities unusable are ones that have stayed the same for a long time like slabs, stairs and soul sand. These blocks are frequently used on servers in spawns and so on so it's important to be able to manouver them. Those probably have the same bounding box in all the versions mineflayer supports.

The question in this case is, would you like me to start the PR against the minecraft-data repo or should it be against mineflayer? I think the data should land in this repo to begin with since it will be very incomplete. The question is also important because it decides if I'll base the bounding boxes against 1.7 (the lowest supported version in minecraft-data) or if I'll base them against 1.8 (the lowest supported version for mineflayer). Although I'm not 100% sure if there is any difference in the most common blocks even as far back as 1.7 tbh.

[rom1504]

Probably go for the latest version, so 1.12. You can do 2 PRs, it's ok if the data in minecraft-data is incomplete to begin with. And you can start testing without merging anything anyway ;)

…

On Tue, Apr 17, 2018 at 8:45 PM Cezary Borowski ***@***.***> wrote: @rom1504 <https://github.com/rom1504> Yeah that seems like a good idea. Considering the most common blocks that make the bots moving abilities unusable are ones that have stayed the same for a long time like slabs, stairs and soul sand. These blocks are frequently used on servers in spawns and so on so it's important to be able to manouver them. Those probably have the same bounding box in all the versions mineflayer supports. The question in this case is, would you like me to start the PR against the minecraft-data repo or should it be against mineflayer? I think the data should land in this repo to begin with since it will be very incomplete. The question is also important because it decides if I'll base the bounding boxes against 1.7 (the lowest supported version in minecraft-data) or if I'll base them against 1.8 (the lowest supported version for mineflayer). Although I'm not 100% sure if there is any difference in the most common blocks even as far back as 1.7 tbh. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#228 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACPN_oQtVU2brRWIgtx-PvxjcTWUTKRGks5tpjg_gaJpZM4DyuJ4> .

[derjp]

@rom1504 Yeah that seems like a good idea. Considering the most common blocks that make the bots moving abilities unusable are ones that have stayed the same for a long time like slabs, stairs and soul sand. These blocks are frequently used on servers in spawns and so on so it's important to be able to manouver them. Those probably have the same bounding box in all the versions mineflayer supports.

The question in this case is, would you like me to start the PR against the minecraft-data repo or should it be against mineflayer? I think the data should land in this repo to begin with since it will be very incomplete. The question is also important because it decides if I'll base the bounding boxes against 1.7 (the lowest supported version in minecraft-data) or if I'll base them against 1.8 (the lowest supported version for mineflayer). Although I'm not 100% sure if there is any difference in the most common blocks even as far back as 1.7 tbh.

Any updates on this?

I would really be interested in a basic implementation of bounding boxes, even without pathfinding support. For the beginning, in my opinion it would be enough if you could manouver the bot using locations given by the coder. For most use cases this would be enough.

[rom1504]

@lluiscab has an extractor to get the bounding box data into Minecraft Data.
However nobody started working on actually implementing them in mineflayer afaik.
I don't really have the interest to doing this myself, but if anyone want to try I'd support it and answer to any questions (come to discord or gitter)

[lluiscab]

My plan is to first update mineflayer to 1.13, then add the bounding box data to mcdata in some way (probably just a boundingBoxes.json file) and then implement a new physics engine (or just rework the current one) to support bounding boxes.
It's going to take a while tbh and now that I'm back at school I don't really have that much time (Was planning to do all of this this summer but the mcdata update took too much)

[Peda1996]

Is there already some work in progress?
I am interesting in trying various stuff, to make bounding boxes working..

Firstly, I just want to focus on carpet, half steps, stairs,..

I just have to edit the physics.js for this or?

[rom1504]

No there isn't, you can start something

…

On Sat, Sep 14, 2019, 00:45 Peter Wassermair ***@***.***> wrote: Is there already some work in progress? I am interesting in trying various stuff, to make bounding boxes working.. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#228?email_source=notifications&email_token=AAR437VYKFFDZ3PXCVVAFW3QJQJXXA5CNFSM4A6K4J4KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD6WLUCQ#issuecomment-531413514>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAR437Q4C2BUWNVPMSHRZVLQJQJXXANCNFSM4A6K4J4A> .

[Peda1996]

It's actually harder than anticipated before...
My problem is that i don't know where I have to put the lowered height of blocks..

[2peter3]

@Peda1996 same here ;) i can detect incompatible blocks like carpets with something like:

var block = bot.blockAt(pos.offset(0, 0.06250, 1)); if (block.type === 171) {..

But the question is, how i can move the bot over the carpet?

any advice would be nice ;)