Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am working on a box-based game engine like minecraft and I was wondering how to detect the "clicked face" when placing blocks.

I have created this engine in C++ ( DirectX / D3D ), C# ( XNA ) and Flash ( away3d & papervision3d ).

The engine code is pretty much the same on each, however as one is C# and the other C++ I'm just looking for the pseudo code, theory or advice on how to "snap" placed blocks on the face that has been clicked on.

How should I get its orientation and then place a block on that face in that position with the corresponding orientation.

UPDATE

For now, I've decided to go with a simple but effective method:

First I've remembered the basic 3D to 2D Projection Algorythm. enter image description here

If I now have a click-point on the screen, I can simply trace a line from the camera ( eye ) through the screen, up to a specific distance.

With this line "in mind" and a modified ( 3D ) version of Bresenham's ( 2D ) line algorithm, I was now able to see, if my imagined line is "pointing" onto a Block in my 3D grid.

thx for all of your suggestions.

UPDATE 2

enter image description here

I hope it explains my solution. ( red is the original algorythm, green is my modified version )

also: with "rounded" i mean that the original algorythm is just rounding the x-y-factor-value to get the nearest pixel. hope u guys know what i'm talking about.

share|improve this question
    
Take a look at the unproject methods in directX (xna) and OpenGL. This translates 2d screen coords (where you clickted the mouse) into 3d world coords depending on the matrices you use. This then can be used to raycast and find the right face. The only thing I don't know is how to efficiently determine the closest face and how to handle finding multiple faces that are on practicly the same place (like when you put 2 boxes close to eachother). This could result in some strange behaviour –  Thomas Jul 30 '13 at 8:56
    
One thing to be careful with if using the Bresenham algorthimn its self is it skips over some cells (see en.wikipedia.org/wiki/File:Bresenham.svg). The playtechs approach however should not. For example if you have rows of blocks diagonally (e.g. say many roofs in minecraft) you can see "through" them with Bresenhams. –  Will Newbery Aug 6 '13 at 9:50
    
Also does that solution provide any means to support a fractional start position within a block? I found that was something I had to manage to make things feel right. –  Will Newbery Aug 6 '13 at 10:04
    
yes u are right, bresenhams algorythm IS skipping some cells, therfore i've modifyed it like i said. see my update2 to understand how i did it. what do you mean with "fractional start position" ? –  Ace Aug 6 '13 at 23:46
    

4 Answers 4

If your ray tracing through a grid, you can simply iterate over the cells that the ray would pass through, in order. I found this to be extremely fast compared to dealing with a bunch of AABB's in a large world.

For each cell you can see if it is considered solid, if it is, given the previous cell coordinates you have the face as well. You can also have a maximum distance and calculate the entry and exit points for each cell.

You can combine this with some more complex collision testing for non-cube cells (e.g. you know the ray goes through this cell with a fence, so you can then do detailed testing to see if you hit the fence or passed through a gap.

There is a blog post here that gives some details and an implementation in 2D. I managed to create my own 3D version without any real problems.

http://playtechs.blogspot.co.uk/2007/03/raytracing-on-grid.html

EDIT:

Note that it can be important to consider where the ray starts from within a cell, e.g. consider the image below with a ray starting at the red point and heading towards the green one. The start and end cells are are the same, but I changed the position in the cell which then changed some of the cells in between picked. The blue dots are the intersection points, I calculated those with "start + time * heading", and stopped iterating once I passed time = 1 (in this case direction is not a unit vector. Of course if it was a unit vector then time = distance so you could iterate up to some distance that way).

enter image description here

share|improve this answer
    
thx for that answer. you've just exactly discribed my personal solution method that i've thought of about after hours of research. i think in a cube based game engine this method is definitly the most powerful one. i'll mark the "right" answer after i've test all given methods. –  Ace Aug 1 '13 at 14:24
    
could you provide us with a little bit of code for example of "finding the look-vector" and stepping through the "look-line" and get all the "block-positions" that the "looking line" is passing until it hits a solid block or the "max-distance" ? this is just for marking the right answer because Jason Coombes has a similar attempt with his solutuion. –  Ace Aug 1 '13 at 14:38
    
I just handled the middle of screen by taking (0,0,1) and rotating it by the cameras pitch and yaw. For mouse clicks anywhere on the screen this is wrong due to the field of view, you cant just translate the vector by the mouse pos. Most API's seem to have something like Viewport.Unproject(mousex, mousey, z, viewProjMatrix). If it wants a world matrix, I think Identity works fine. You can set z to 0 to get the near plane position, and z to 1 to get the far plane position, your direction/ray is just the vector from near to far. –  Will Newbery Aug 1 '13 at 15:26
    
thx for yout update. keep in mind that my player ( the camera ) is not calculated my blocks. so the starting position will always be exact. in my version of Bresenham's algorythm, there is only a "rounding" while the line is dividet into even peaces according to the number of blocks in the longest direction ( x, y or z ) of the view-line. –  Ace Aug 7 '13 at 20:36
    
So you are saying your camera always "snaps" to grid lines? While for the purposes of the algorithm the grid is like a grid of pixels, in practice my cells are 16x16, and in 3d it makes even less sense to think of them in terms of pixels since up close one cell is say 600x600 on the screen. –  Will Newbery Aug 8 '13 at 7:40

The idea is to cast a ray and see what face it hits. This is pretty much a ray to AABB intersection test, in which you find the initial point of contact.

A good resource (which I'm looking at as I write this) is in the book Real-Time Collision Detection by Christer Ericson. The idea is to use 3 slabs and test the ray against them. A slab would be a region between two planes (being opposite sides of the AABB). If the ray intersects all three slabs, it intersects the AABB and a point of contact and time t can be returned.

Using this point of contact determining which face most faces this point can be done easily, especially if the AABB is stored implicity. If the AABB is implictly defined, then the face can be outright computed, as you know the point of contact lies upon that face.

If your box has an orientation, the problem can be transformed into ray vs AABB by transforming the ray into the basis of the oriented box.

This calculation can be greatly sped up with the use of some sort of broad phase tree structure using bounding boxes. AABB trees or dynamic AABB trees are great for these sort of ray cast queries.

Since you're clicking with your mouse this is also commonly referred to as "picking".

I hope this helps! I haven't implemented raycasting myself yet, so I can't write out the psuedo-code for the implementation myself, but at least referred you to a great resource.

share|improve this answer
    
thank you for that answer. i think the method that Will Newbery have discribed is the simplest solution for this kind of project. –  Ace Aug 1 '13 at 14:26

This question seems similar to how I managed a selection block in TechCraft:

public void RenderSelectionBlock()
{
    //Get exact centre vector
    Vector3 position = player.currentSelection.Value.position.asVector3() + new Vector3(0.5f, 0.5f, 0.5f);

    Matrix matrix_a, matrix_b;
    Matrix identity = Matrix.Identity;                       // setup the matrix prior to translation and scaling  
    Matrix.CreateTranslation(ref position, out matrix_a);    // translate the position a half block in each direction
    Matrix.CreateScale((float)0.51f, out matrix_b);          // scales the selection box slightly larger than the targetted block

    identity = Matrix.Multiply(matrix_b, matrix_a);          // the final position of the block

    // set up the World, View and Projection
    _selectionBlockEffect.World = identity;
    _selectionBlockEffect.View = camera.View;
    _selectionBlockEffect.Projection = camera.Projection;
}

This gives us the WVP matrix for rendering the mesh at the chosen block. But, we still need to determine which block to place adjacent to that selection block.

This is done by using a vector3 to that position:

private float setPlayerSelectedBlock(bool waterSelectable)
    {

// 0.5f = min distance to check // 8f = max distance to check. Further, there wont be a selection block

        for (float x = 0.5f; x < 8f; x += 0.1f)
        {
            Vector3 targetPoint = camera.Position + (lookVector * x);

            Block block = player.world.BlockAt(targetPoint);

// Shouldnt be attempting to select or place adjacent to water or other fluids

            if (block.Type != BlockType.None && (waterSelectable || block.Type != BlockType.Water))
            {
                player.currentSelection = new PositionedBlock(new Vector3i(targetPoint), block);
                return x;
            }
            else
            {
                player.currentSelection = null;
                player.currentSelectedAdjacent = null;
            }
        }
        return 0;
    }

// Now we can get the ray to the adjacent block properly:

    private void setPlayerAdjacentSelectedBlock(float xStart)
    {
        for (float x = xStart; x > 0.7f; x -= 0.1f)
        {
            Vector3 targetPoint = camera.Position + (lookVector * x);
            Block block = player.world.BlockAt(targetPoint);

            if (player.world.BlockAt(targetPoint).Type == BlockType.None)
            {
                player.currentSelectedAdjacent = new PositionedBlock(new Vector3i(targetPoint), block);
                break;
            }
        }
    }
share|improve this answer
    
thank you for that solution. it is like the solution that Will Bewbery has given. how do you get the lookVector ? –  Ace Aug 1 '13 at 14:29
    
All of the code i pasted is available at techcraft.codeplex.com. Look in the player handler classes specifically. Trace through the code for the lookVector, its better than me trying to explain here. –  Jason Coombes Aug 2 '13 at 9:08
    
This looks to me like the code just starts at a position, then makes small (0.1) steps in the heading direction. After each step it sees what is at the current position. So it will likely visit the same block many times as it passes through, whereas my solution in effect jumps directly from cell to cell by calculating which grid line will be crossed next. –  Will Newbery Aug 4 '13 at 9:32

There is a straightforward precise algorithm for visiting the cubes that a ray passes through in a grid-based world like Minecraft; see this answer for full source code.

share|improve this answer
    
thx for the advice. i'll check it out. but as i've mentioned, i think i'll go with that simple and fast method seen in my update 1 & 2. –  Ace Aug 7 '13 at 0:22
    
@Ace I just looked at Will Newbery's code link and it is the same algorithm as I link to, although the sourcecode I link to is for 3D. The key thing is its exact. I myself messed around trying to add fuzz factor to Breshenhams and it basically doesn't work. Simply adopt the proper algorithm as linked and move on. –  Will Aug 7 '13 at 0:27
4  
Instead of a link-only answer, leave a comment or mark as duplicate. –  Sean Middleditch Aug 7 '13 at 0:27
    
my solution is working perfectly fine. also i don't think that this is a duplicate because my solution is not mentioned in similar questions. i think my code is working much faster, because it's only a few lines of code. i'll test the speed and accuracy of both and let you know. –  Ace Aug 7 '13 at 0:51
    
The algorithm that @WillNewbery and I link to is optimal. Speed != lines of code. –  Will Aug 7 '13 at 0:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.