opengl – Box2D simulation doesn’t work

I previously used Box2D and it always worked fine until recently I decided to test how it would work in my custom 2D game engine, I just wanted to test the physics updates without any GUI interaction, as you can see in the below code I just try to print the plain position values of the dynamic body and it just doesn’t move. All it does is print the initialisation position I set in the initialiser, afaik all I’m trying to do it print the values in a simple loop that runs more than 60 times per frame, the box2d code doesn’t interact with the rendering in anyway. IDK what’s wrong with box 2d to run fine in a simple loop. I’m really confused why the simulation isn’t happening. Let me know if you need more info about anything.

Freefall.h

 #include <fireworks/fireworks.h>
 #include <box2d/box2d.h>

using namespace fireworks;

class FreeFall : public Fireworks
{
private:
    Window*         m_Window;
    Layer*          defaultLayer;

    b2Vec2          m_Gravity;
    const double    m_PhysicsTimeStep = 1.0f / 60.0f;
    unsigned int    m_VelocityIterations;
    unsigned int    m_PositionIterations;
public:
    b2World* world;

    b2BodyDef       groundBodyDef;
    b2Body*         groundBody;
    b2PolygonShape  groundShape;
    b2FixtureDef    groundFixtureDef;

    b2BodyDef       dynBoxBodyDef;
    b2Body*         dynBoxBody;
    b2PolygonShape  dynBoxShape;
    b2FixtureDef    dynBoxFixtureDef;

    Sprite*         ground;
    Sprite*         dynBox;
public:
    FreeFall()
        : m_Gravity(b2Vec2(0.0f, -29.81f)), m_VelocityIterations(6), m_PositionIterations(2)
    {
        world = new b2World(m_Gravity);
        // Static ground body
        groundBodyDef.position.Set(0.0f, -10.0f);
        groundBody = world->CreateBody(&groundBodyDef);
        groundShape.SetAsBox(20.0f, 4.0f);
        groundFixtureDef.shape = &groundShape;
        groundFixtureDef.density = 1.0f;
        groundFixtureDef.friction = 0.3f;
        groundBody->CreateFixture(&groundFixtureDef);

        // Dynamic simulation box
        dynBoxBodyDef.type = b2_dynamicBody;
        dynBoxBodyDef.position.Set(-1.0f, 4.0f);
        dynBoxBody = world->CreateBody(&dynBoxBodyDef);
        dynBoxShape.SetAsBox(2.0f, 2.0f);
        dynBoxFixtureDef.shape = &dynBoxShape;
        groundFixtureDef.density = 1.5f;
        dynBoxFixtureDef.friction = 0.25f;
        dynBoxBody->CreateFixture(&dynBoxFixtureDef);
    }

    ~FreeFall()
    {
        delete defaultLayer;
        delete world;
    }

    // Runs once per initialisation
    void init() override
    {
        m_Window = createWindow("Freefall physics sim", 800, 600);
        glClearColor(0.8, 0.8f, 0.2f, 1.0f);

       

    }
    // Runs once per second
    void tick() override { }

    // Runs 60 times per second
    void update() override { }

    // Runs as fast as possible
    void render() override
    {
        //Physics Update
        world->Step(m_PhysicsTimeStep, m_VelocityIterations, m_PositionIterations);
        b2Vec2 dynPos = dynBoxBody->GetPosition();
        std::cout << "dynnamic Box2d Box position X : " << dynPos.x << " and Y is : " << dynPos.y << std::endl;
    }
};

MainGame.cpp

#include "physics-sims/Freefall.h"

int main()
{
    FreeFall game;
    game.start();
    return 0;
}

This is the output I get :
dynnamic Box2d Box position X : -1 and Y is : 4 for as long as the loop runs, this is soo infuriating, IDK what’s breaking what.

performance – Project Euler #645 — speed up Monte-Carlo simulation in Python

I am trying to solve Q645. While the logic used for my code seems to be appropriate, the code itself is way too slow for the large number required in this question. May I ask for suggestion(s) to improve my code’s performance?

The question is as in the link: https://projecteuler.net/problem=645

My Python code is as follow:

def Exp(D):
    day_list = (0)*D
    num_emperor = 0
    while all((d == 1 for d in day_list)) == False:
        #the birthday of the emperors are independent and uniformly distributed throughout the D days of the year
        bday = np.random.randint(0,D)
        day_list(bday) = 1
        num_emperor+=1
        #indices of d in day_list where d == 0
        zero_ind = (i for i,v in enumerate(day_list) if v == 0)
        for ind in zero_ind:
            try:
                if day_list(ind-1) and day_list(ind+1) == 1:
                    day_list(ind) = 1
            except IndexError:
                if ind == 0:
                    if day_list(-1) and day_list(1) == 1:
                        day_list(0) = 1
                elif ind == len(day_list)-1:
                    if day_list(len(day_list)-2) and day_list(0) == 1:
                        day_list(len(day_list)-1) = 1
    return num_emperor

def my_mean(values):
    n = 0
    summ = 0.0
    for value in values:
        summ += value
        n += 1
    return summ/n

def monte_carlo(iters, D):
    iter = 0
    n_emperor = 0
    while iter < iters:
        n_emperor = Exp(D)
        yield n_emperor
        iter += 1

avg_n_emperor = my_mean(monte_carlo(iters,D))
print(avg_n_emperor)

And my logic is as follow:

For the day_list inside the Exp(D) function, where D is the number of days in a year, zeros mean no holiday, and ones mean holiday. Initially the day_list is all zeros since there is no holiday to begin with.

The rules of defining a random day (d) as a holiday is as follow:

  1. At the beginning of the reign of the current Emperor, his birthday is declared a holiday from that year onwards.

  2. If both the day before and after a day d are holidays, then d also becomes a holiday.

I then subsequently implement the rules stated for the question, to gradually add holidays (ones) into the day_list. After num_emperor number of emperors, all the days (d) in day_list will become 1, i.e. all days will become holiday. This is the point to quit the while_loop in Exp(D) function and count the number of emperors required. To get the average number of emperors required for all the days to become holidays (avg_n_emperor), I then apply the monte-carlo method.

For my current code, the time takes is as follow:

avg_n_emperor = my_mean(monte_carlo(iters=100000,D=5)) #6-7 seconds

avg_n_emperor = my_mean(monte_carlo(iters=1000000,D=5)) #about 62 seconds

in which the time takes increase approx. linearly with the iters.

However,

avg_n_emperor = my_mean(monte_carlo(iters=1000,D=365)) #about 68 seconds

already takes about 68 seconds, and the question is asking for D=10000. Not to mention that the iters required for the answer to be accurate within 4 digits after the decimal points (as required by the question) would be much larger than 1000000 too…

Any suggestion(s) to speed up my code would be appreciated! 🙂

performance – N-body simulation in javascript

I’ve worked on an n-body simulation using javascript in the past few years and recently I decided to update it to use a barnes-hut tree to speed up performance. It currently handles about 2,000 bodies at roughly 30fps, which I believe is quite underwhelming despite being double the performance it had before the tree structure was implemented.

The following code is contained in the PhysicsWorld implementation. I’d like some insight on ways I could improve the performance of this class, and ideas on how I can take responsibility out of it, as I believe it’s doing too much currently but I’m not yet entirely sure how to move code to other classes.

Note that most of the time spent here is wasted on PhysicsWorld.traverseTree() so it’s a good idea to focus effort there.

Thanks in advance.

class PhysicsWorld {
    constructor (debugRenderer) {
        this.G = 0.01
        this.iterations = 1
        this.bodies = ()
        this.intersections = ()
        this.garbage = ()
        this.barnesHutTree = null
        this.theta = 0.5
        this.computationsPerIteration = 0
        this.debugRenderer = debugRenderer
        this.adaptiveDomainBoundary = new AABB(new Point(0, 0), new Size(innerWidth, innerHeight))
        this.enforceSquareNodes = false
        this.useAdaptiveDomainBoundary = true
    }
    createBarnesHutTree () {
        const position = new Point(0, 0),
            size = new Size(window.innerWidth, window.innerHeight),
            boundary = new AABB(position, size)
        this.barnesHutTree = new BarnesHutTree(this.adaptiveDomainBoundary, this.debugRenderer)

        for (let body of this.bodies) {
            this.barnesHutTree.insert(body)
        }
    }
    applyVelocityToPosition () {
        let index = 0

        let position = new Point(Infinity, Infinity),
            size = new Size(-Infinity, -Infinity)

        for (const body of this.bodies) {

            body.userData.bodiesArrayIndex = index

            body.pastPosition.x = body.position.x
            body.pastPosition.y = body.position.y
            body.position.x += body.velocity.dx / this.iterations
            body.position.y += body.velocity.dy / this.iterations

            // Store maximum and minimum body positions to use as adaptive domain boundary:
            position.x = Math.min(body.position.x, position.x)
            position.y = Math.min(body.position.y, position.y)
            size.width = Math.max(body.position.x, size.width)
            size.height = Math.max(body.position.y, size.height)

            ++index
        }

        // Use stored body positions for adaptive domain boundary:
        const margin = 1 // fixes floating point errors from preventing body from being added to tree
        position.x -= margin
        position.y -= margin
        size.width = size.width - position.x + margin / 2
        size.height = size.height - position.y + margin / 2
        if (this.enforceSquareNodes) {
            size.width = Math.max(size.width, size.height)
            size.height = Math.max(size.width, size.height)
        }
        if (this.useAdaptiveDomainBoundary)
            this.adaptiveDomainBoundary = new AABB(position, size)
    }
    traverseTree () {
        this.computationsPerIteration = 0
        for (const body of this.bodies) {
            this.barnesHutTree.forEachNode(node => {
                const distanceX = node.centerOfMass.x - body.position.x,
                    distanceY = node.centerOfMass.y - body.position.y,
                    distanceSquare = distanceX * distanceX + distanceY * distanceY,
                    averageNodeSideLength = Math.max(node.boundary.size.width, node.boundary.size.height),
                    averageNodeSideLengthSquare = averageNodeSideLength * averageNodeSideLength,
                    thetaSquare = this.theta * this.theta,
                    isNodeFarEnoughToApproximateAsSingleBody = averageNodeSideLengthSquare / distanceSquare < thetaSquare

                ++this.computationsPerIteration

                if (isNodeFarEnoughToApproximateAsSingleBody || node.isEndNode) {

                    if (node.isEndNode && node.isPopulated) {
                        if (node.body === body) return false

                        const radiiSum = node.body.shape.radius + body.shape.radius,
                            radiiSumSquare = radiiSum * radiiSum

                        if (radiiSumSquare > distanceSquare) {
                            if (body.collidable && node.body.collidable) 
                                this.markAsIntersection(body, node.body)

                            return false
                        }
                    }

                    const distance = Math.sqrt(distanceSquare),
                        force = this.G * ((body.mass * node.mass) / distanceSquare),
                        forceByIteration = force / this.iterations

                    body.velocity.dx += (forceByIteration / body.mass) * distanceX / distance
                    body.velocity.dy += (forceByIteration / body.mass) * distanceY / distance

                    return false
                } else return true
            })
        }
    }
    markAsIntersection (bodyA, bodyB) {
        const isAlreadyIntersectingWithAnotherBody = {
                bodyA: bodyA.contact !== null,
                bodyB: bodyB.contact !== null
            },
            numberOfBodiesWithPreviousIntersections = 
                isAlreadyIntersectingWithAnotherBody.bodyA + 
                isAlreadyIntersectingWithAnotherBody.bodyB

        switch (numberOfBodiesWithPreviousIntersections) {
            case 0:
                const intersection = (bodyA, bodyB),
                    index = this.intersections.length

                bodyA.contact = index
                bodyB.contact = index

                this.intersections.push(intersection)
                break
            case 1:
                if (isAlreadyIntersectingWithAnotherBody.bodyA) {
                    bodyB.contact = bodyA.contact
                    this.intersections(bodyA.contact).push(bodyB)
                } else {
                    bodyA.contact = bodyB.contact
                    this.intersections(bodyB.contact).push(bodyA)
                }
                break
            case 2:
                if (bodyA.contact !== bodyB.contact) { // no need to do anything if they're already in the same intersection
                    const oldIndex = bodyB.contact
                    for (const bodyC of this.intersections(bodyB.contact)) {
                        this.intersections(bodyA.contact).push(bodyC)
                        bodyC.contact = bodyA.contact
                    }
                    this.intersections(oldIndex).length = 0 // can't remove array element otherwise all indexes after it would get messed up
                }
                break
        }
    }
    mergeIntersectingBodies () {
        for (const intersection of this.intersections) {
            if (intersection.length > 0) {
                let bodyA = intersection(0)
                for (let i = 1; i < intersection.length; ++i) {
                    let bodyB = intersection(i)

                    if (bodyB.mass > bodyA.mass) {
                        const buffer = bodyA
                        bodyA = bodyB
                        bodyB = buffer
                    }

                    bodyA.position.x = (bodyA.position.x * bodyA.mass + bodyB.position.x * bodyB.mass) / (bodyA.mass + bodyB.mass)
                    bodyA.position.y = (bodyA.position.y * bodyA.mass + bodyB.position.y * bodyB.mass) / (bodyA.mass + bodyB.mass)

                    bodyA.velocity.dx = (bodyA.velocity.dx * bodyA.mass + bodyB.velocity.dx * bodyB.mass) / (bodyA.mass + bodyB.mass)
                    bodyA.velocity.dy = (bodyA.velocity.dy * bodyA.mass + bodyB.velocity.dy * bodyB.mass) / (bodyA.mass + bodyB.mass)

                    bodyA.shape.volume += bodyB.shape.volume / bodyA.density

                    this.garbage.push(bodyB.userData.bodiesArrayIndex)

                    bodyB.contact = null
                }
                bodyA.contact = null
            }
        }
        this.intersections.length = 0
    }
    collectGarbage () {
        let numberOfDeletedItems = 0

        const sortAlgorithmDescendingOrder = (a, b) => b - a
        this.garbage.sort(sortAlgorithmDescendingOrder) // prevents from having to shift the index of subsequent items

        for (const index of this.garbage) {
            const body = this.bodies(index)

            this.bodies.splice(index, 1)
            body.destroy()

            ++numberOfDeletedItems
        }
        this.garbage.length = 0
    }
    step () {
        for (let i = 0; i < this.iterations; ++i) {
            
            this.applyVelocityToPosition()

            this.createBarnesHutTree()
            this.traverseTree()

            this.mergeIntersectingBodies()
            this.collectGarbage()
        }
    }
}

If you want to take a look on the entire project please check out its github repository.

python 3.x – How can I shorten the runtime of my simulation?

Before you read the code below, note the following explanation:
I have three classes: Driver, Vehicle, and Itinerary.

They have attributes Driver.behavior, Vehicle.pRange, Vehicle.pBattery, Itinerary.destinations, and Itinerary.startTime.

The function findCand takes all these class attributes as input and returns as an output a dataframe with three columns.

So here is the code that I use to run my simulation:

n = 1000 
m = 1000 

agentA = ()
iterationA = ()
itineraryA = (None)*n
behaviorA = (None)*n
rangeA = (None)*n
batteryA = (None)*n
startTimeA = (None)*n
df = pd.DataFrame(columns = ('Loc', 'Amount', 'Time'))

for j in range(m):
    for i in range(n):
        x = Itinerary()
        y = Vehicle()
        z = Driver()
        itineraryA(i) = x.destinations
        behaviorA(i) = z.behavior
        rangeA(i) = y.pRange
        batteryA(i) = y.pBattery
        startTimeA(i) = x.startTime
        dfi = findCand(itineraryA(i), behaviorA(i), rangeA(i), batteryA(i), startTimeA(i))
        df = df.append(dfi)
        agentA = agentA + (i)*len(dfi)
        iterationA = iterationA + (j)*len(dfi)

df('Ag') = agentA
df('It') = iterationA

I run it n times, m iterations. For each dataframe I get from findCand, I append it to the dataframe df.

The code works, but it’s taking a crazy amount of time to run.

If n=10 and m=10, it takes about a second.

If n=100 and m=100, it takes around 97 seconds.

I put n=1000 and m=1000 and it was running for more than 3 hours before I stopped it.

I need to do this for a way higher value of both n and m. I realize that it takes a lot of time to append a dataframe so often but I’ve tried a few other methods

  • I used a dictionary and appended larger dataframes fewer times.
  • I used lists instead of dataframes and then made one large dataframe in the end.

But these methods took just as long or even longer than the one above. So my question is, can anyone suggest areas that I can improve that might shorten the runtime?

open source – Travelling Salesman Problem simulation

I apologise if I’m wrong to ask this here but I couldn’t think of a better forum.

I am learning about the travelling sales man algorithm and wish to implement a demonstration.

My initial thought was to develop it in a webpage but as I am natively a PHP developer, I feel it might not be the best solution to use javascript/jQuery to animate characters from point to point through a graph.

I wonder if there is an open-source 2D game engine I can use and write PHP/javascript logic for my algorithm implementation?

rendering – Is it a useful strategy for Mobile VR titles to render faster than their simulation loop?

For example – If a title had a very heavy simulation loop (say 20ms), is it desirable to render at a greater rate, say 90hz?

This would always a present head pose correct to the view, without being stalled on simulation.

Or does this result in discomfort for the player, and instead render and sim should stay in lockstep?

optimization – Optimizing falling sand simulation

So, for the past couple week I’ve been working on a falling sand simulation inspired by games such as The Powder Toy, Noita and Sandspiel. I’ve been making it in Love2D and I’m please with what I got so far. The simulation can handle 59k particles at 60FPS however pretty much anything over that amount will cause the FPS to plummit so I’ve been thinking of other ways to optimize it.

The way my simulation works is that I have a large table that contains numbers. These numbers refer to an index inside a table which contains particle data. The particle data is structured as:

Name, Color(table containing 4 values, r,g,b,a), Update logic function, Color variation modifier (0 = no color variation between particles)

I’ve got the options for optimization narrowed down to a pretty small list:

  • Spatialhashing/Quadtree – splitting the screen into a grid and only updating cells with particles in it
  • GPU simulation – Moving simulation logic to the GPU
  • Multithreading – Moving simulation logic to separate CPU threads

The downsides of all of these are as follow:

  • Spatialhashing/Quadtree – There’s no unique identifiers for the particles themselves as they’re only stored in the table as the index for their data so it’s hard to have a reference that can be added/removed when needed

  • GPU simulation – I’m not good with shader code and there’s not any good ways to do GPU code in Love2D that’s purely computational.

  • Multithreading – Similar to GPU simulation, I’m not knowledgable when it comes to multithreading nor do I have any idea of how to parallelize my simulation code.

Some information about how to multithread a falling sand physics simulation comes from the devs of Noita, where they split the world into chunks and updated each on a different thread in a checkerboard pattern (to make ensure that pixels weren’t being updated by multiple threads at the same time). They also had ‘dirty rects’ which showed which particles needed updating which is similar to spatialhashing.

However, the talk the noita dev did just showed what they did, rather than how they did it. Since I lack alot of knowledge in these fields, I don’t really have much to go on for implementing them.

My code is open source and viewable on github. You’ll need the latest version of Love2D to run it:

https://github.com/BradBath/Sand (either drag the Sand-master folder on the love2D executable or open the folder in VSCode and use the Love2D plugin to run it via LALT+L)

If anyone has any ideas I could implement some of these optimizations, or has any other ideas for optimization, I’d love to hear them. Thanks!

Here’s a gif of my simulation at it’s current point

unity – Car simulation, motor torque and brake torque combine problem

I am creating a custom wheel collider in Unity. Every thing is fine now (suspension, collision, friction) except one problem that i cant get my head over for last 3 weeks. So now i have a car (one wheel only), it stand on top of a hill, then i apply a brake torque enough to make it stand still, after that i apply a motor torque that less than max brake torque, my question is how the car behave?. In my opinion, that if sum of motor torque (roll down hill direction) and gravity torque(friction force * radius) greater than the max brake torque will cause the car to roll down hill, and it remain stand still if motor torque (roll up hill direction). I really need help!

simulation – Pros and cons of position as properties of a spatial object?

Building games and simulation frameworks, it seems I regularly hounded by this conundrum:

Let’s say you have a 2D grid, and you have an crate in that grid. I can put the coordinates on the crate, or somewhere else.

# Option A:
grid = Grid()
crate = Crate()
grid.add(x,y,crate)

# Option B:
grid = Grid()
crate = Crate(x,y)
grid.add(crate)

I prefer option A because why should the crate know where it is? Its position only makes sense in the context of its holding space (the grid). However, it seems that everywhere I encounter spatial positioning, Option B is used. I have noticed that this somehow does make the code simpler, and indeed more intuitive. However it irks my sense of conceptual integrity.

There is another option which seems to me to be an additional level of complexity, so I tend to avoid it:

# Option C
grid = Grid()
index = GridIndex(grid)
crate = Crate()
index.add(x,y,crate)

Some inconclusive thoughts:

Thought 1:
When trying to find items quickly, given a coordinate, we want option A, or C. With those we have some hope of indexing. Well with C, we have indexing explicitly of course.

Thought 2:
Option B suffers from this problem:

# Problem
grid = Grid()
crate = Crate(cx,cy)
room = Room(rx,ry)
grid.add(crate)
grid.add(room)
# oh actually crate is in the room
room.add(crate)

Now, the crate has coordinates intended for a grid, but it is actually in a room.

For me the above issues are fundamental conceptual issues that I cannot resolve. Have I missed why Option B is everywhere, and Option A is nowhere? What are the other pros and cons of A vs B vs C?

Aside
For me, it is useful to consider other similar(?) structures. The values of a dict/hash-table, do not typically know their own key. So, in this case, they use my conceptually preferred option, Option A.