Improved HitBlox Algorithm

This is based on this pull request.

This is a "beam" example when I was testing it out .

I was having a discussion on this pull request with Grum on IRC and it is hard to describe an algorithm one line at a time, so I thought I would post it here.

Anyway, the idea is to find what block a player is targeting.

This is the proof (I hope) that it will work.

A Location is considered to be in the block that is given by the getBlockX/Y/Z() methods. This means that each Location is uniquely defined to be in a particular block. It also means that a Location is never on an edge and not in either of the blocks.

The recursive function implements

for any 2 points Start and End,
-- add all the blocks between Start and End to the list,
-- except
---- the one that contains Start
---- any blocks after the first solid block along the line

return false if a solid block is detected between the points

The psudeo code is:

Code:

lineOfSight(start, end, list) {

 - convert Start into block coordinates (B-start)
 - convert End into block coordinates (B-end)

 // If both in same block, there is no block between start and end
 if(B-start == B-end)
  return true;

 // if they are different by 1 block, then add the end block
 if(B-start touches B-end) {
  add B-end to list;
  if(B-end is a solid block) 
   return false;
  else
   return true;
 }

// recursively call function

 midpoint = midpoint of start and end

 if(!lineOfSight(start, midpoint))
  return false;
 

 return lineOfSight(midpoint, end);

}

Note:

lineOfSight(start, midpoint) and then lineOfSight(midpoint, end)

gives the same result as
lineOfSight(start, end)

lineOfSight(start, midpoint) places all blocks from start (exclusive) to midpoint
lineOfSight(midpoint, end) places all blocks from midpoint (exclusive) to end

This means that midpoint is only added once.

As long as if the line is broken up into tiny pieces, it will pass through all the blocks, then this algorithm will also return all the blocks along the line.

A line that went from 0,0,0 to 2,2,0 would be a problem. It technically goes (0,0,0) -> (1,1,0) -> (2,2,0). No matter how you break it up, it will never pass through (0,1,0) or (1,0,0), it always goes from (0,0,0) to (1,1,0).

Adding a little bit of dither would fix that. This could be added with a depth check. If it goes through more that 16 levels of recursion, then it would activate dither.

However, rounding errors would almost certainly make dither present automatically.

One way to ensure that would be to travel 0.49999 alone the line instead of half way to get the midpoint.

Any comments, have a missed any errors (obvious or otherwise)?

 

The idea is solid and useful, but I have some points/concerns:

• I'm a bit concerned about recursion in this case. It basically means a stack frame for every block encountered, and someone might try to take this to infinity. (Stack Overflow!) Take a look at Bresenham's line algorithm; it should apply to 3-dimensions as well.
• It makes sense for this kind of tracing API to return blocks neatly in order from start to end. (I'm guessing that's not something you needed when you set out on this. Bresenham's algorithm should also help with this.)
• You can also score bonus points by making the tracing generic, as opposed to tying it to Player. It looks like your private helpers are capable of tracing from anywhere to anywhere. Make them public! World seems like a good place.
  You should probably expose both a method that traces from a start position and direction, and one that traces between two positions. Your Player methods can simply wrap these.
• If you really want your implementation to appeal to this man, make your methods return an Iterator. That way, you can leave such concerns as maximum distance and transparent blocks to the caller, if he/she so desires. It'd also eliminate the overhead of a List.

 

The algorithm does find the blocks in order. Also, it doesn't process blocks after the first hit.

That is an interesting point about making it an iterator. I didn't think of that.

What I like about the algorithm is that you don't need to have loads of special cases. Even if the path was being handled block by block, it would still be useful for figuring out which blocks are intercepted.

 

But each recursion is convertable to a iteration. But at the moment it's too late for me to think about the conversion.

Fabian

 

It needs more thought, I want a simple algorithm that doesn't have loads of special cases .

 

This screams Bresenham.

 

Just to add another thing to consider.
Currently when I'm using TargetBlock, if there's a button or lever block in the line of sight they are treated as completely solid blocks. That is, they will hide the block behind them even if you can see it and the selection frame is set on it. It would be nice if it would use the same algorithm the minecraft client is using to highlight the block you're pointing at (except the 5 blocks distance limit of course).

 

The problem is that it causes diagonal jumps.

Anyway, I have updated again (well created a new pull request). It now has an iterator and moves one step at a time.
--- merged: Feb 13, 2011 9:53 PM ---
I have update again, it doesn't use the midpoint trick at all now (in the last pull it used it once the two points were within a 2x2x2 cube).

The new method just calculate the distance to each of the 3 planes.

There is a direction vector which points in the direction that the player is looking.

This vector can be multiplied by a double to give any position on the line.

It is easy to calculate the required value to hit a particular plane. For example, for x, you can use

d = ((x of plane) - start.getX())/(direction.getX())

There are 6 faces on the cube but only 3 are valid since they need to be "forward". I check the 3 planes, and then take the face that gives the lowest d value.

I can then use

nextBlock = currentBlock.getBlock(nearest);

nearest is a BlockFace, so this guarantees that the blocks are obtained in order.
--- merged: Feb 13, 2011 9:54 PM ---

You can use a HashSet to indicate which blocks to ignore. If you use null, then it will default to air.
--- merged: Feb 13, 2011 9:55 PM ---
However, maybe I could add some default HashSets as static variables.

 

Well, you can't ignore levers, buttons, sign blocks, etc. altogether, sometimes you do want to point at them. I guess this could be too complicated to accomplish on the server side.

 

@Grum
The new integer stepping algorithm works as follows

Setup (using double arithmetic)

- Find a vector pointing in the direction of the player
- Find the player's eye position
- Find the longest component of the direction vector
- Set the direction of that component as the main direction
- Set the other 2 as second and third (doesn't matter which is which)
- Rescale the direction vector so that main component has a magnitude of 1

The stepping process will move forward by 1 block in the main direction each pass. This means that the the algorithm processes one plane at a time. The plane is perpendicular to the direction of the main component.

This plane may contain 1, 2 or 3 blocks in the trace.
1 block -> neither the 2nd or 3rd error crosses the threshold
2 block -> one or other of the 2nd or 3rd error crosses the threshold
3 blocks -> both cross the threshold

- Trace the ray backwards so that it hits the nearest plane behind
- This is the new start position

- Convert the positions and direction vectors for the second and third component to integers.
- All positions/directions ints are positive in the direction of travel
- This uses a grid with a resolution of 2^24 per block

- Sanity check the double to int rounding so that the resultant ray goes through the start block
-- This may require moving the start position by 1 grid slot (highly unlikely)

- subtract one block (2^24) from each of the errors
-- This means that an error above zero counts as crossing the threshold
-- It also makes the maths for the case where both errors trigger simpler

- scan the first plane
-- This will contain the start block
-- Set the start block as the next block

Scan Process - integer arithmetic only

The scan process is
- if the queue is not empty, do nothing/return

- Otherwise, calculate the next plane

-- increment the second and third error value by the step size

-- If the errors go above zero, that means that the ray must step in that direction

-- If no error goes above zero
--- Add one block to the queue
---- Step in the main direction

-- If one error goes above zero
--- Add two blocks to the queue
--- Step in the main direction and then step in the whichever direction went above zero
--- Subtract grid size (2^24) from the error that went above zero

-- If both errors goes above zero
--- Add three blocks to the queue
--- Step in the main direction
--- check( errorSecond*stepFirst < thirdStep*SecondError )
---- Step in the second direction and then the third direction
---- Otherwise, step in the third direction and then the second direction
--- Subtract grid size (2^24) from the both errors

Note: the "check" actually uses long arithmetic, since int*int could overflow. If ints are required, the grid size could be reduced to 2^15 per block.