PathFinder status

[LogicParrot]

Analysis - Bounding boxes

EDIT: Okay, this has some missing bits. Words have failed me, I will post some pseudo-code instead later on.

Bounding boxes are tricky, here is my proposed solution. peer review will be appreciated.

For simplicity, let us assume we have a 2d world.

Intro: The simplest version of A* divides the world into blocks, each X,Y is either solid or empty, let us define a function get_solid(int x,int y), which simply returns true if the position is occupied by a block.

The problem: Minecraft: might have more exotic structures, such as half-blocks.

One solution is to use a more complex algorithm. My proposed solution is hopefully better.

1. Stick to regular A*, change nothing except the get_solid(int x,int y) function.
2. Instead of a simple get_solid(int x,int y), our new function which will be called get_traversable(int x,int y), checks if the player can possibly stand right in the center of the block (x+0.5,y+0.5), (it checks the bounding box of the character as if it were standing on (x+0.5,y+0.5) and scans for collisions with surrounding bounding boxes.)
If there are no collisions, false is returned and A* continues as if there is no block.
If there are collisions, we swap (x+0.5,y+0.5) with (x+m,y+n) where m is the average point between the position of the rightmost and leftmost bounding boxes of the surrounding objects, and n is the average point between the uppermost and bottommost bounding boxes of the surrounding objects. We check for collisions again, if none found, false is returned and A* continues as if there is no block.
If a collision is found, true is returned and A* continues as if there is a solid block.