• Advertisement
Sign in to follow this  

(Voxel) Terrain collision with Newton!

Recommended Posts

What I am trying to do is create a bit more advanced physics for my (currently blocky) voxel engine. By now means am I an expert on computer graphics or physics... I just love to tinker around and learn a thing or two. (This was kinda the disclaimer)

Now my old physics implementation was really rudimentary, but it worked (kinda):

void World::doPhysics(std::shared_ptr<Entity> entity)

    {
        if (!entity->grounded) {
 
            glm::vec3 distanceToGravityPoint =
                entity->getPosition() -
                ((entity->getPosition() - gravityPoint) * 0.005d); // TODO multiply by time
 
            glm::vec3 oldPos = entity->getPosition();
 
            entity->setPosition(distanceToGravityPoint);
 
            glm::vec3 potentiallyNewPosition = entity->getPosition();
            glm::vec3 checkPos = glm::vec3(floorf(potentiallyNewPosition.x), floorf(potentiallyNewPosition.y), floorf(potentiallyNewPosition.z));
 
            if (getBlock(checkPos.x, checkPos.y, checkPos.z))
            {
                glm::vec3 floorPos = checkPos + glm::vec3(0,1,0); // If we are in the ground, we need to add offset to y
                glm::vec3 newPos = glm::vec3(oldPos.x, floorPos.y, oldPos.z);
                glm::vec3 sameLevel = floorPos;
                if(getBlock(sameLevel.x, sameLevel.y, sameLevel.z))
                {
                    newPos = glm::vec3(checkPos.x, newPos.y, checkPos.z);
                }
 
                entity->setPosition(newPos);
                entity->grounded = true;
            }
        }
    }
 
What this did was simply move the entity towards the "gravityPoint" and if there was a hit in between, it would determine the last valid position (not really, was hackish and towards walls it was really choppy and unreliable, but against the floor it was okay)
 
Now for the real physics I wanted this to be a little more sophisticated:
 
1) More real world like -> Switching to Newton's Law of universal gravity
2) Possibility for multiple sources of gravity that would allow for interesting gameplay (unfinished, code only features one)
 
    void World::newPhysics(std::shared_ptr<Entity> entity)
    {
        if (!entity->grounded)
        {
            glm::vec3 oldPos = entity->getPosition();
            glm::vec3 nearestGravityPoint = this->gravityPoint; // TODO obviously
 
            // TODO assuming every gravity point has mass of 50 here!
            float gravityPointMass = 50;
            float gravitationalConstant = 1;
 
            glm::vec3 diff = oldPos - nearestGravityPoint;
            glm::vec3 direction = glm::normalize(diff);
            double distance = glm::length2(diff);
 
            glm::vec3 force =
                    gravitationalConstant *
                    ((entity->getMass() * gravityPointMass) / distance)
                    * direction;
 
            entity->setPosition(entity->getPosition() - force);
 
            glm::vec3 potentiallyNewPosition = entity->getPosition();
            glm::vec3 checkPos = glm::vec3(floorf(potentiallyNewPosition.x), floorf(potentiallyNewPosition.y), floorf(potentiallyNewPosition.z));
 
            std::cout << "OLD POS: " << glm::to_string(oldPos) << std::endl;
            std::cout << "FORCE: " << glm::to_string(force) << std::endl;
            std::cout << "potentially new position: " << glm::to_string(potentiallyNewPosition) << std::endl;
            std::cout << "checkPos: " << glm::to_string(checkPos) << std::endl;
 
            glm::vec3 diff2 = oldPos - potentiallyNewPosition;
 
            if (getBlock(checkPos.x, checkPos.y, checkPos.z))
            {
                glm::vec3 floorPos = checkPos + glm::vec3(0, 1, 0); // If we are in the ground, we need to add offset to y
                glm::vec3 newPos = glm::vec3(oldPos.x, floorPos.y, oldPos.z);
                glm::vec3 sameLevel = floorPos;
                if (getBlock(sameLevel.x, sameLevel.y, sameLevel.z))
                {
                    newPos = glm::vec3(checkPos.x, newPos.y, checkPos.z);
                }
 
                entity->setPosition(newPos);
                entity->grounded = true;
                std::cout << "GROUNDED" << std::endl;
            }
        }
    }
 

Now this does not work. The entity is warping through the ground, then again being teleported way up into space and falling again, slowly. Sometimes it is even grounded, but often too late, when it is already beneath the ground.

 

I think I do understand why this happens (Please do correct me if I am wrong/not entirely correct/forget something):

To have a common base, here is some log:

OLD POS: vec3(0.150880, 5.958805, -0.063934)
FORCE: vec3(0.071230, 2.813126, -0.030183)
potentially new position: vec3(0.079650, 3.145679, -0.033751)
checkPos: vec3(0.000000, 3.000000, -1.000000)
GROUNDED
Seconds since last frame: 0.006
OLD POS: vec3(0.123258, 4.000000, -0.052229)
FORCE: vec3(0.192267, 6.239515, -0.081471)
potentially new position: vec3(-0.069009, -2.239515, 0.029242)
checkPos: vec3(-1.000000, -3.000000, 0.000000)
GROUNDED
 
...... a few dozen more lines, as the entity got shot up back high into the air
 
OLD POS: vec3(-0.468390, 9.671287, 0.198475)
FORCE: vec3(-0.051565, 1.064711, 0.021850)
potentially new position: vec3(-0.416825, 8.606576, 0.176625)
checkPos: vec3(-1.000000, 8.000000, 0.000000)
OLD POS: vec3(-0.416825, 8.606576, 0.176625)
FORCE: vec3(-0.065112, 1.344433, 0.027591)
potentially new position: vec3(-0.351713, 7.262143, 0.149034)
checkPos: vec3(-1.000000, 7.000000, 0.000000)
OLD POS: vec3(-0.351713, 7.262143, 0.149034)
FORCE: vec3(-0.091452, 1.888298, 0.038752)
potentially new position: vec3(-0.260261, 5.373845, 0.110282)
checkPos: vec3(-1.000000, 5.000000, 0.000000)
OLD POS: vec3(-0.260261, 5.373845, 0.110282)
FORCE: vec3(-0.167014, 3.448498, 0.070770)
potentially new position: vec3(-0.093247, 1.925347, 0.039512)
checkPos: vec3(-1.000000, 1.000000, 0.000000)
GROUNDED

 

Sometimes the "potentiallyNewPos" is already beneath the ground (when the force was strong in this one [iteration] *pun intended*)

 

then it checks a block beneath the earth and just moves the entity up one block, as the algorithm assumes that there is the ground.

 

To circumvent this I assume that I could do a rather nasty nested loop and check all the blocks between the old position and the potentially new one and set the position once we have a hit (and break the loop).

 

But I think that is rather nasty, especially if the force is big it could be that I check a lot of blocks and there could be cases where there is only air between the two points, then the whole check is ridiculous.

 

Maybe it's just too late here, but I am out of nice fixes here and would appreciate any help I can get!

Share this post


Link to post
Share on other sites
Advertisement

Some sleep definitely helped:

 if(!entity->grounded) { // TODO not sure if this really makes sense. What about horizontal pull? Or pull upwards?
        std::vector<glm::vec3> velocities;

        glm::vec3 oldPos = entity->getPosition();
        // TODO for each gravity point (in some area) 
        float gravityPointMass = 50;
        float gravitationalConstant = 1;

        glm::vec3 gravityPointPos = this->gravityPoint;
        glm::vec3 diff = oldPos - gravityPointPos;
        glm::vec3 direction = glm::normalize(diff);
        double distance = glm::length2(diff);

        glm::vec3 force =
                gravitationalConstant *
                ((entity->getMass() * gravityPointMass) / distance)
                * direction;

        glm::vec3 acceleration = force / entity->getMass();
        glm::vec3 velocity = acceleration * timer.getDeltaTime() * 0.01f;
        std::cout << "DIRECTION OF FORCE: " << glm::to_string(direction) << std::endl;
        std::cout << "CALCULATED FORCE: " << glm::to_string(force) << std::endl;
        std::cout << "CALCULATED ACCELERATION: " << glm::to_string(acceleration) << std::endl;
        std::cout << "CALCULATED VELOCITY: " << glm::to_string(velocity) << std::endl;
        velocity = direction * velocity;
        std::cout << "CALCULATED VELOCITY (directional): " << glm::to_string(velocity) << std::endl;
        velocities.push_back(velocity);

        for (auto v : velocities)
            entity->velocity += v;

        std::cout << "ENTITY VELOCITY AFTER APPLYING ALL FORCES: " << glm::to_string(entity->velocity) << std::endl;

        // 1) Cast ray in direction of force
        glm::vec3 currPos = entity->getPosition();
        glm::vec3 prevPos = currPos;

        int currentX, currentY, currentZ;

        glm::vec3 firstHit;

        for (int p = 0; p < 50; p++) {
            prevPos = currPos;
            currPos += direction * 0.1f; // TODO stride

            currentX = floorf(currPos.x);
            currentY = floorf(currPos.y);
            currentZ = floorf(currPos.z);

            // 2) Check for first hit
            if (chunky->getBlock(currentX, currentY, currentZ)) {
                firstHit.x = currentX;
                firstHit.y = currentY;
                firstHit.z = currentZ;
                break;
            }
        }

        // 3) Check if new pos would be behind, if so, set to natural barrier, else move on
        glm::vec3 potentiallyNewPos = entity->getPosition() + entity->velocity;
        // Actually check whether firstHit lies in between current pos and potentially new pos
        bool inBetween = false;
        if (abs(direction.x) >= abs(direction.y)) {
            if (direction.x > 0)
                inBetween = oldPos.x <= firstHit.x && firstHit.x <= potentiallyNewPos.x;
            else
                inBetween = oldPos.x >= firstHit.x && firstHit.x >= potentiallyNewPos.x;
        } else {
            if (direction.y > 0)
                inBetween = oldPos.y <= firstHit.y && firstHit.y <= potentiallyNewPos.y;
            else
                inBetween = oldPos.y >= firstHit.y && firstHit.y >= potentiallyNewPos.y;
        }

        glm::vec3 newPos;

        if (inBetween) {
            std::cout << " IN BETWEEN " << std::endl;
            newPos.x = firstHit.x;
            newPos.y = firstHit.y;
            newPos.z = firstHit.z;
            entity->grounded = true;
            entity->velocity = glm::vec3(0,0,0); // TODO check whether that makes sense
        } else {
            newPos.x = potentiallyNewPos.x;
            newPos.y = potentiallyNewPos.y;
            newPos.z = potentiallyNewPos.z;
        }

        entity->setPosition(newPos);
    }

Pretty straightforward, I think.

Problems:

glm::vec3 potentiallyNewPos = entity->getPosition() + entity->velocity;

actually leads to flying upwards instead of downwards. I am not sure why that is the case.

When I change it to be a substraction instead, it pulls down, but:

 

1) Problem with the ray casting approach is, that right now the entity still falls through the ground, until it stops (Not sure why, exactly. Thought it may be the ray casting parameters (stride and how often it iterates), but it breaks out, so I am a bit lost here.

2) I am not sure yet how to handle forces/physics once I am grounded. The entity still could be pulled towards another point in theory - horizontal one, as up would not make sense, as the one down was obviously stronger if it hit the floor in the first place)

3) Also not sure when to set the velocity to 0 again. I am pretty sure it makes sense, once you hit the ground/something in between the force pulling you and yourself, to stop the velocity, as that is exactly what happens in real life, no?

4) Actually setting the position to first hit makes no sense of course. Would need to be firstHit - 1 in the direction it was pulled to. Not sure right now how to write that elegantly.

edit 4) something like this probably:

	if (chunky->getBlock(currentX, currentY, currentZ)) {
		firstHit.x = prevPos.x;
		firstHit.y = prevPos.y;
		firstHit.z = prevPos.z;
		break;
	}

Anyway, I'll keep on digging and still appreciate any help I can get!

Edited by Salam

Share this post


Link to post
Share on other sites
I did not read through this, but if you use Newton physics engine it supports some kind of user collision:
http://newtondynamics.com/wiki/index.php5?title=NewtonCreateUserMeshCollision

I guess this doc is outdated and things have changed, but usually you need to implement callbacks to intersect a ray with your blocks or to provide triangle data itersecting a queried bounding box.
The physics engine then would care for resolving collisions.
(Newton forum should be a good place to ask for details)

Share this post


Link to post
Share on other sites

Thanks collision detection itself works like a charm with Bresenham algorithm. Just the movement itself is now a problem as the entity warps through the floor immediately, only to be reset the next instant... basically it can't move horizontally right now.

Probably setting the position wrong.

Well, I can move horizontally now, but sadly I fall through the ground then, slowly, but for each move unto the next layer beneath (where there is ground again).

     if(!entity->grounded) { // TODO not sure if this really makes sense. What about horizontal pull? Or pull upwards?
            std::vector<glm::vec3> velocities;

            glm::vec3 oldPos = entity->getPosition();
            // TODO for each gravity point (in some area)
            float gravityPointMass = 50;
            float gravitationalConstant = 1;

            glm::vec3 gravityPointPos = this->gravityPoint;
            glm::vec3 diff = gravityPointPos - oldPos;
            glm::vec3 direction = glm::normalize(diff);
            double distance = glm::length2(diff);

            glm::vec3 force =
                    gravitationalConstant *
                    ((entity->getMass() * gravityPointMass) / distance)
                    * direction;

            glm::vec3 acceleration = force / entity->getMass();
            glm::vec3 velocity = acceleration * timer.getDeltaTime() * 0.01f;
            std::cout << "DIRECTION OF FORCE: " << glm::to_string(direction) << std::endl;
            std::cout << "CALCULATED FORCE: " << glm::to_string(force) << std::endl;
            std::cout << "CALCULATED ACCELERATION: " << glm::to_string(acceleration) << std::endl;
            std::cout << "CALCULATED VELOCITY: " << glm::to_string(velocity) << std::endl;
            velocity = direction * velocity;
            std::cout << "CALCULATED VELOCITY (directional): " << glm::to_string(velocity) << std::endl;
            velocities.push_back(velocity);

            for (auto v : velocities)
                entity->velocity += v;

            std::cout << "ENTITY VELOCITY AFTER APPLYING ALL FORCES: " << glm::to_string(entity->velocity) << std::endl;

            // Bresenham
            glm::vec3 potentiallyNewPos = entity->getPosition() - entity->velocity;
            glm::vec3 hitInBetween = getBlockBetween(oldPos, potentiallyNewPos);

            if(hitInBetween.x != -666) {
                // We had a hit
                entity->setPosition(hitInBetween);
                entity->grounded = true;
                entity->velocity = glm::vec3(0,0,0); // TODO check whether that makes sense
            } else {
                entity->setPosition(potentiallyNewPos);
            }
        }
    glm::vec3 World::getBlockBetween(const glm::vec3 startPoint, const glm::vec3 endPoint)
    {
        int point[3];

        point[0] = startPoint.x;
        point[1] = startPoint.y;
        point[2] = startPoint.z;

        glm::vec3 diff = endPoint - startPoint;

        int dx = diff.x;
        int dy = diff.y;
        int dz = diff.z;

        int xIncrease = (dx < 0) ? -1 : 1;
        int l = abs(dx);
        int y_inc = (dy < 0) ? -1 : 1;
        int m = abs(dy);
        int z_inc = (dz < 0) ? -1 : 1;
        int n = abs(dz);
        int dx2 = l << 1;
        int dy2 = m << 1;
        int dz2 = n << 1;

        int err_1, err_2;

        if ((l >= m) && (l >= n)) { // x dominant
            std::cout << "x is dominant" << std::endl;

            err_1 = dy2 - l;
            err_2 = dz2 - l;
            for (int i = 0; i < l; i++) {
                // Check world if voxel is blocked
                if(this->chunky->getBlock(point[0], point[1], point[2])) {
                    glm::vec3 firstHit(point[0] - xIncrease, point[1], point[2]);
                    std::cout << "HIT! at " <<  glm::to_string(firstHit) << std::endl;
                    return firstHit;
                }

                if (err_1 > 0) {
                    point[1] += y_inc;
                    err_1 -= dx2;
                }
                if (err_2 > 0) {
                    point[2] += z_inc;
                    err_2 -= dx2;
                }
                err_1 += dy2;
                err_2 += dz2;

                // Prepare next iteration
                point[0] += xIncrease;
            }
        } else if ((m >= l) && (m >= n)) { // y dominant
            std::cout << "y is dominant" << std::endl;

            err_1 = dx2 - m;
            err_2 = dz2 - m;
            for (int i = 0; i < m; i++) {
                // Check world if voxel is blocked
                if(this->chunky->getBlock(point[0], point[1], point[2])) {
                    glm::vec3 firstHit(point[0], point[1] - y_inc, point[2]);
                    std::cout << "HIT! at " <<  glm::to_string(firstHit) << std::endl;
                    return firstHit;
                }

                if (err_1 > 0) {
                    point[0] += xIncrease;
                    err_1 -= dy2;
                }
                if (err_2 > 0) {
                    point[2] += z_inc;
                    err_2 -= dy2;
                }
                err_1 += dx2;
                err_2 += dz2;


                // Prepare next iteration
                point[1] += y_inc;
            }
        } else { // z dominant
            std::cout << "z is dominant" << std::endl;

            err_1 = dy2 - n;
            err_2 = dx2 - n;
            for (int i = 0; i < n; i++) {
                // Check world if voxel is blocked
                if(this->chunky->getBlock(point[0], point[1], point[2])) {
                    glm::vec3 firstHit(point[0], point[1], point[2] - z_inc);
                    std::cout << "HIT! at " <<  glm::to_string(firstHit) << std::endl;
                    return firstHit;
                }

                if (err_1 > 0) {
                    point[1] += y_inc;
                    err_1 -= dz2;
                }
                if (err_2 > 0) {
                    point[0] += xIncrease;
                    err_2 -= dz2;
                }
                err_1 += dy2;
                err_2 += dx2;

                // Prepare next iteration
                point[2] += z_inc;
            }
        }

        // TODO remove ugly hack!
        return glm::vec3(-666,0,0);
    }
Edited by Salam

Share this post


Link to post
Share on other sites

Any ideas what's wrong here? As soon as I move after initially hitting the surface I warp through the ground.

 

To me it looks like I start my bresenham off by one, but adding + 1 to y doesn't help here (just a quick debug)

 

HIT! at vec3(0.000000, 4.000000, 0.000000)
FORCE MOVED!
DIRECTION OF FORCE: vec3(0.000000, 1.000000, 0.000000)
CALCULATED FORCE: vec3(0.000000, 6.250000, 0.000000)
CALCULATED ACCELERATION: vec3(0.000000, 3.125000, 0.000000)
CALCULATED VELOCITY: vec3(0.000000, 0.156250, 0.000000)
CALCULATED VELOCITY (directional): vec3(0.000000, 0.156250, 0.000000)
ENTITY VELOCITY AFTER APPLYING ALL FORCES: vec3(1.275518, 0.156250, 1.540430)
x is dominant
FORCE MOVED!
DIRECTION OF FORCE: vec3(-0.294378, 0.887102, -0.355517)
CALCULATED FORCE: vec3(-1.567983, 4.725090, -1.893637)
CALCULATED ACCELERATION: vec3(-0.783992, 2.362545, -0.946819)
CALCULATED VELOCITY: vec3(-0.031360, 0.094502, -0.037873)
CALCULATED VELOCITY (directional): vec3(0.009232, 0.083833, 0.013464)
ENTITY VELOCITY AFTER APPLYING ALL FORCES: vec3(2.560267, 0.240083, 3.094324)
z is dominant
HIT! at vec3(-1.000000, 3.000000, 0.000000)
FORCE MOVED!
DIRECTION OF FORCE: vec3(-0.316228, 0.948683, 0.000000)
CALCULATED FORCE: vec3(-3.162278, 9.486833, 0.000000)
CALCULATED ACCELERATION: vec3(-1.581139, 4.743416, 0.000000)
CALCULATED VELOCITY: vec3(-0.031623, 0.094868, 0.000000)
CALCULATED VELOCITY (directional): vec3(0.010000, 0.090000, 0.000000)
ENTITY VELOCITY AFTER APPLYING ALL FORCES: vec3(0.647759, 0.090000, 0.770215)
x is dominant
FORCE MOVED!
DIRECTION OF FORCE: vec3(-0.480161, 0.847981, -0.224442)
CALCULATED FORCE: vec3(-4.077300, 7.200654, -1.905860)
CALCULATED ACCELERATION: vec3(-2.038650, 3.600327, -0.952930)
CALCULATED VELOCITY: vec3(-0.081546, 0.144013, -0.038117)
CALCULATED VELOCITY (directional): vec3(0.039155, 0.122120, 0.008555)
ENTITY VELOCITY AFTER APPLYING ALL FORCES: vec3(1.643552, 0.212120, 1.934092)
x is dominant
HIT! at vec3(0.000000, 2.000000, 0.000000)
FORCE MOVED!
DIRECTION OF FORCE: vec3(0.000000, 1.000000, 0.000000)
CALCULATED FORCE: vec3(0.000000, 25.000000, 0.000000)
CALCULATED ACCELERATION: vec3(0.000000, 12.500000, 0.000000)
CALCULATED VELOCITY: vec3(0.000000, 0.500000, 0.000000)
CALCULATED VELOCITY (directional): vec3(0.000000, 0.500000, 0.000000)
ENTITY VELOCITY AFTER APPLYING ALL FORCES: vec3(1.275518, 0.500000, 1.540430)
x is dominant
HIT! at vec3(1.000000, 2.000000, 0.000000)
FORCE MOVED!

Share this post


Link to post
Share on other sites

The problem occurs if dx, dy and dz all are 0, so basically when the difference between the old position and the new one is smaller than one full integer on each axis.

Then the warping occurs.

But I can't simply check for that, as that is also happening in free fall... so no solution so far.

Edited by Salam

Share this post


Link to post
Share on other sites

After sitting back I think there are major flaws in my design, among these:

 

Multiple problems with forces:

1) GRAVITATIONAL CONSTANT is probably way too big (check formula for gravitational constant)
-> initial thought (make it 1) was okay, probably: https://physics.stackexchange.com/questions/14349/why-can-you-remove-the-gravitational-constant-from-a-computer-game-simulation
-> https://www.gamedev.net/topic/390658-gravitational-constant/
2) Somehow with multiple forces suddenly the object gets repelled from the gravity point (maybe sign issue with force * -1 it should work? But why does the gravity towards the bottom work then?)
3) Gravity point not being moved, this may be an issue, but should it? I mean the mass of the gravity point is way bigger and I may move the world, when I jump, but I have heavy bones :)
4) Distance is not in meters for us. Distance was simply taken 1:1 from world coordinates. This may lead to weird issues!

 

Not yet sure how to solve all these. Especially the meters thing. I mean, sure, it's basically just a division but to get a useful value is hard.

 

Boy, it's hard to create a physics engine, yet it is very funny and informative at the same time.

Edited by Salam

Share this post


Link to post
Share on other sites

I cleaned the stuff up a bit... the main problem still is the collision detection with the ints in the bresenham... I am thinking wrong here, I guess:

 

     glm::vec3 oldPos = entity->getPosition();
        float m = entity->getMass();
        glm::vec3 vi = entity->velocity; // Initial velocity

        // Calculate forces affecting entity and add them up
        glm::vec3 F;
        for(auto gravityPoint : this->gravityPoints)
        {
            glm::vec3 diff = gravityPoint.position - oldPos;
            glm::vec3 direction = glm::normalize(diff);
            double squaredDistance = glm::length2(diff);

            glm::vec3 force =
                    -G * ((m * gravityPoint.mass) / squaredDistance)
                    * direction;

            F += force;
        }

        // F = ma -> a = F/m
        glm::vec3 a = F / m;

        glm::vec3 v = vi + a * timeStep;

        glm::vec3 d = (vi + v) / 2 * timeStep;

        std::cout << "Distance: " << glm::to_string(d) << std::endl;

        glm::vec3 newPos = oldPos - d;

        GroundHit hitInBetween = getBlockBetween(oldPos, newPos);
        if (hitInBetween.wasHit)
        {
            // We had a hit
            entity->setPosition(hitInBetween.positionRightBeforeHit);
        }
        else
        {
            entity->setPosition(newPos);
        }
 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Advertisement