• 15
• 15
• 11
• 9
• 10
• ### Similar Content

• By GytisDev
Hello,
me and few friends are developing simple city building game with unity for a school project, think something like Banished but much simpler. I was tasked to create the path-finding for the game so I mostly followed this tutorial series up to episode 5. Then we created simple working system for cutting trees. The problem is that the path-finding is working like 90% of the time, then it get stuck randomly then there's clearly a way to the objective (tree). I tried looking for some pattern when it happens but can't find anything. So basically I need any tips for how I should approach this problem.
Use this image to visualize the problem.
• By aymen
please any know how can i' calculate the centroid from any number vertices
• By owenjr
Hi there!
I am trying to implement a basic AI for a Turrets game in SFML and C++ and I have some problems.
This AI follows some waypoints stablished in a Bezier Courve.
In first place, this path was followed only by one enemy. For this purpose, the enemy has to calculate his distance between his actual position
to the next waypoint he has to pick.
If the distance is less than a specific value we stablish, then, we get to the next point. This will repeat until the final destination is reached. (in the submitting code, forget about the var m_go)

Okay, our problem gets when we spawn several enemies and all have to follow the same path, because it produces a bad visual effect (everyone gets upside another).
In order to solve this visual problem, we have decided to use a repulsion vector. The calculus gets like this:

As you can see, we calculate the repulsion vector with the inverse of the distance between the enemy and his nearest neighbor.
Then, we get it applying this to the "theorical" direction, by adding it, and we get a resultant, which is the direction that
our enemy has to follow to not "collide" with it's neighbors. But, our issue comes here:

The enemys get sepparated in the middle of the curve and, as we spawn more enemys, the speed of all of them increases dramatically (including the enemies that don't calculate the repuslion vector).
1 - Is it usual that this sepparation occours in the middle of the trajectory?
2 - Is it there a way to control this direction without the speed getting affected?
3 - Is it there any alternative to this theory?

I submit the code below (There is a variable in Spanish [resultante] which it means resultant in English):

if (!m_pathCompleted) { if (m_currentWP == 14 && m_cambio == true) { m_currentWP = 0; m_path = m_pathA; m_cambio = false; } if (m_neighbors.size() > 1) { for (int i = 0; i < m_neighbors.size(); i++) { if (m_enemyId != m_neighbors[i]->GetId()) { float l_nvx = m_neighbors[i]->GetSprite().getPosition().x - m_enemySprite.getPosition().x; float l_nvy = m_neighbors[i]->GetSprite().getPosition().y - m_enemySprite.getPosition().y; float distance = std::sqrt(l_nvx * l_nvx + l_nvy * l_nvy); if (distance < MINIMUM_NEIGHBOR_DISTANCE) { l_nvx *= -1; l_nvy *= -1; float l_vx = m_path[m_currentWP].x - m_enemySprite.getPosition().x; float l_vy = m_path[m_currentWP].y - m_enemySprite.getPosition().y; float l_resultanteX = l_nvx + l_vx; float l_resultanteY = l_nvy + l_vy; float l_waypointDistance = std::sqrt(l_resultanteX * l_resultanteX + l_resultanteY * l_resultanteY); if (l_waypointDistance < MINIMUM_WAYPOINT_DISTANCE) { if (m_currentWP == m_path.size() - 1) { std::cout << "\n"; std::cout << "[GAME OVER]" << std::endl; m_go = false; m_pathCompleted = true; } else { m_currentWP++; } } if (l_waypointDistance > MINIMUM_WAYPOINT_DISTANCE) { l_resultanteX = l_resultanteX / l_waypointDistance; l_resultanteY = l_resultanteY / l_waypointDistance; m_enemySprite.move(ENEMY_SPEED * l_resultanteX * dt, ENEMY_SPEED * l_resultanteY * dt); } } else { float vx = m_path[m_currentWP].x - m_enemySprite.getPosition().x; float vy = m_path[m_currentWP].y - m_enemySprite.getPosition().y; float len = std::sqrt(vx * vx + vy * vy); if (len < MINIMUM_WAYPOINT_DISTANCE) { if (m_currentWP == m_path.size() - 1) { std::cout << "\n"; std::cout << "[GAME OVER]" << std::endl; m_go = false; m_pathCompleted = true; } else { m_currentWP++; } } if (len > MINIMUM_WAYPOINT_DISTANCE) { vx = vx / len; vy = vy / len; m_enemySprite.move(ENEMY_SPEED * vx * dt, ENEMY_SPEED * vy * dt); } } } } } else { float vx = m_path[m_currentWP].x - m_enemySprite.getPosition().x; float vy = m_path[m_currentWP].y - m_enemySprite.getPosition().y; float len = std::sqrt(vx * vx + vy * vy); if (len < MINIMUM_WAYPOINT_DISTANCE) { if (m_currentWP == m_path.size() - 1) { std::cout << "\n"; std::cout << "[GAME OVER]" << std::endl; m_go = false; m_pathCompleted = true; } else { m_currentWP++; } } if (len > MINIMUM_WAYPOINT_DISTANCE) { vx = vx / len; vy = vy / len; m_enemySprite.move(ENEMY_SPEED * vx * dt, ENEMY_SPEED * vy * dt); } } }
¡¡Thank you very much in advance!!
• By SinnedB
Hello,
I am not sure if I phrased the title properly. What I am trying to achieve is the following:
Winning chances:
Red card: 10%
Blue card: 20%
Green card: 15%
Nothing card: 10%
Now a player has the chances above to win those cards but how would that look like in code?

• I'm stuck trying to make a simple ray sphere intersection test. I'm using this tutorial as my guide and taking code from there. As of now, I'm pretty sure I have the ray sorted out correctly. The way I'm testing my ray is by using the direction of the ray as the position of a cube, just to make sure it's in front of me.
cube.transform.position.x = Camera.main.ray.origin.x + Camera.main.ray.direction.x * 4; cube.transform.position.y = Camera.main.ray.origin.y + Camera.main.ray.direction.y * 4; cube.transform.position.z = Camera.main.ray.origin.z + Camera.main.ray.direction.z * 4;
So if I rotate the camera, the cube follows. So it's looking good.

The problem occurs with the actual intersection algorithm. Here are the steps I'm taking, I'll be very brief:
1) I subtract the sphere center with the ray origin:
L.x = entity.rigidbody.collider.center.x - ray.origin.x; L.y = entity.rigidbody.collider.center.y - ray.origin.y; L.z = entity.rigidbody.collider.center.z - ray.origin.z; L.normalize(); 2) I get the dot product of L and the ray direction:
const b = Mathf.dot(L, ray.direction); 3) And also the dot product  of L with itself (I'm not sure if I'm doing this step right):
const c = Mathf.dot(L, L); 4) So now I can check if B is less than 0, which means it's behind the object. That's working very nicely.
L.x = entity.rigidbody.collider.center.x - ray.origin.x; L.y = entity.rigidbody.collider.center.y - ray.origin.y; L.z = entity.rigidbody.collider.center.z - ray.origin.z; const b = Mathf.dot(L, ray.direction); const c = Mathf.dot(L, L); if (b < 0) return false;
Problem starts here
5) I now do this:
let d2 = (c * c) - (b * b); 6) ...and check if d2 > (entity.radius * entity.radius) and if it's greater: stop there by returning false. But it always passes, unless I don't normalize L and d2 ends up being a larger number and then it return false:
const radius2 = entity.rigidbody.collider.radius * entity.rigidbody.collider.radius; if (d2 > radius2) return false; but again, since I'm normalizing, it NEVER stops in that step. Which worries me.
7) I then do this:
let t1c = Math.sqrt(radius2 - d2); ...but it always returns a number in the range of 0.98, 0.97, if I'm standing still. But if I strafe left and right, the number lowers. If I rotate the camera, it makes no difference. Only if I strafe.
So I'm clearly doing something wrong and stopped there. Hopefully I made sense

# Velocity Verlet WORSE than Sympletic Euler for simple spring. What gives?

## Recommended Posts

Hello

I've taken it upon myself to finally start learning how game engines work by making a toy engine myself. I've never done any game programming or anything like that but as an avid gamer and someone with a physics degree I've always wondered how these things are done.

Today I implemented a basic spring force using Hooks Law. I was surprised however when over a short time span, maybe 30s, my default integrator of Velocity Verlet caused the spring's motion to escalate wildly. I tried stepping down to Symplectic Euler and the motion became normal. At first I was thinking there might be a bug in my code, but I can't see one so now I'm wondering if the good people of this forum might help shed some light on this. It does not make any sense to me that Symplectic Euler would be a better integrator than Velocity Verlet. Both are time reversible and symplectic, but Velocity Verlet is second order accurate.

I've been writing up what I learn on a little blog, feel free to check it out to see my current understanding of these methods

Code

Symplectic Euler

void SymplecticEuler::Solve(
const NetForceAccumulator& net_force_accumulator,
const std::vector<std::shared_ptr<PhysicsEntity>> &entity_ptrs,
const std::shared_ptr<PhysicsEntity> entity_ptr)
{
Vector3Gf xi = entity_ptr->GetPosition();
Vector3Gf vi = entity_ptr->GetVelocity();
GLfloat mass = entity_ptr->GetMass();

Vector3Gf F;
F.setZero();
net_force_accumulator.ComputeNetForce(entity_ptrs,entity_ptr,F);

Vector3Gf vf = vi + m_dt*(1/mass)*F;
Vector3Gf xf = xi + m_dt*vf;

entity_ptr->SetNextPosition(xf);
entity_ptr->SetNextVelocity(vf);
};

Velocity Verlet

void Verlet::Solve(
const NetForceAccumulator& net_force_accumulator,
const std::vector<std::shared_ptr<PhysicsEntity>> &entity_ptrs,
const std::shared_ptr<PhysicsEntity> entity_ptr)
{
Vector3Gf xi = entity_ptr->GetPosition();
Vector3Gf vi = entity_ptr->GetVelocity();
GLfloat mass = entity_ptr->GetMass();

Vector3Gf Fi,Ff,ai,xf,af,vf;

Fi.setZero();
net_force_accumulator.ComputeNetForce(entity_ptrs,entity_ptr,Fi);

ai = (1/mass)*Fi;
xf = xi + m_dt*vi + 0.5f*m_dt*m_dt*ai;

entity_ptr->SetPosition(xf); // Load xf into position slot for computing F(x(t+h))

Ff.setZero();
net_force_accumulator.ComputeNetForce(entity_ptrs,entity_ptr,Ff); // Compute F(x(t+h))

af = (1/mass)*Ff;
vf = vi + 0.5f*m_dt*(ai + af);

entity_ptr->SetPosition(xi); // Load xi back into position slot as to not affect force calulations for other entities

entity_ptr->SetNextPosition(xf);
entity_ptr->SetNextVelocity(vf);
};

Spring force

void SpringForceGenerator::AccumulateForce(
const GLfloat k,
const GLfloat l0,
const std::shared_ptr<PhysicsEntity> entity1_ptr,
const std::shared_ptr<PhysicsEntity> entity2_ptr,
Vector3Gf &F) const
{
Vector3Gf x1 = entity1_ptr->GetPosition();
Vector3Gf x2 = entity2_ptr->GetPosition();

Vector3Gf n = x2 - x1;
GLfloat l = n.norm();
n = n/l;

F += k*(l - l0)*n;
}

Thanks!

##### Share on other sites

I believe that the reason for the enhanced stability of Sympletic/Semi-implicit Euler is that it tends to have a damping effect (loses energy) and undershoots the integral, rather than overshoots. Vertlet might be more accurate but since it doesn't have that damping effect it is less stable. This is why most game physics engines (e.g. Bullet) use Semi-implicit Euler, even though it's not that accurate (it's also faster).

When I once implemented physics for a cannon projectile, Semi-implicit Euler would always undershoot the analytical trajectory, regular Euler would overshoot, and RK4 would be very close to the analytical path. With springs/constraints, RK4 was actually less stable than Semi-implicit Euler. Accuracy != stability.

Edited by Aressera

##### Share on other sites

Thanks for your reply Aressera. I'm aware of the difference between accuracy and stability (I wrote some articles about it as a slightly high level on the blog I linked). I would have expected the region of stability for Velocity Verlet to be nicer than Symplectic Euler, although to be fair I've never seen it pictured. Since both methods are symplectic they should both nearly conserve energy (see sections 1.1.3 and 1.2.2 here) so I would not have expected the damping of Symplectic Euler to have such a pronounced effect. However I guess the degree to which they (nearly) preserve energy need not be the same. I am new to all of this so I'll have to take your word for it. It's good to know I'm not insane after all!

Thanks!