feature-request: Swept collision detection

[whitespacecode]

I'm creating an player movable by mouse ondrag so when you hold and drag behind a wall the player shouldn't cross the wall. Yet it spawns on the other side when there is no collision anymore with the wall.

Something like this https://github.com/mreinstein/collision-2d?tab=readme-ov-file#aabb-aabb-sweep-1

i quickly re-created the example with this fork (hold mouse and drag far enough from the right wall): https://tzqx4z.csb.app/

[Prozi]

@whitespacecode

I don't understand your question

Whatever that (https://github.com/mreinstein/collision-2d?tab=readme-ov-file#aabb-aabb-sweep-1) is I am sure you can do this with detect-collisions

If you want to stop the movement on collision refer to the docs: https://github.com/Prozi/detect-collisions?tab=readme-ov-file#step-5-collision-detection-and-resolution

please write the question again in more detail

[whitespacecode]

@Prozi No problem.

So you can move the player by dragging it with your mouse. Whenever you drag the player i update the coordinates (x,y) where player should be. In combination with the collisionSystem we can detect a collision between the wall and the player. Only problem is that when you move the mouse further away the collision 'ends' and the player just gets the new coordinates

Visual example of the problem: https://github.com/Prozi/detect-collisions/assets/37139936/0fd561f5-c2f9-4fe0-8cbe-6166ec3c0d44

Code i use:

function onDragMove() {
  let mousePosition = this.dragData.getLocalPosition(this.parent);

  this.x = mousePosition.x
  this.y = mousePosition.y

    collisionSystem.checkAll((response: Response) => {
        if (response.a.isPlayer && response.b.isWall) {
            // Player can't move through walls
            const { overlapV } = response;

            response.a.setPosition(
                response.a.x - overlapV.x,
                response.a.y - overlapV.y
            );
            this.x = mousePosition.x - overlapV.x
            this.y = mousePosition.y - overlapV.y
        } 
    });
 }

More information about the problem: https://gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/

[Prozi]

@whitespacecode

Now I get your point.

Thing is, all the shapes are really "hollow" if you get me.

I will think of implementing the https://gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/ in the next week

Have a good day

[Prozi]

@whitespacecode

it occured to me how to solve this

you need raycast from 2 farthest of 4 points of aabb box into direction

and if there is no hit on raycast you allow move if there was hit you disallow

I might do this in upcoming days/weeks

best regsrds, Prozi

[Prozi]

see

see https://prozi.github.io/detect-collisions/demo/ (the dotted line is raycast, try to move and see it cross other things)

[whitespacecode]

@Prozi Yes i currently implemented my own 'swept' detection using the raycast feature. I'm creating raycasts on each corner of the moveable object.

I already changed the walls to lines so i don't get any hollow shapes

By all means this code isn't working properly and is for me a temporary fix until proper swept detection was in place. Edit: Is there a way i can contact you? I could share the code i made. Maybe you can do something with it ?

[Prozi]

@whitespacecode if possible fork this repository on github and add your changes on top then open a merge request thanks

we can discuss it there

[whitespacecode]

I didn't change any existing code, so i'm not sure what changes i should make. This is what i'm currently doing. It's not perfect in any way and i'm not even sure this is the best way to handle things.

function onDragMove() {
//...

const objectBody = collisionSystem.all().find((body): body is ObjectPoly => body instanceof ObjectPoly && body.id === this.id);
objectBody.setAngle(this.angle * (Math.PI/180));
objectBody.setPosition(this.x, this.y);
debugCollision.update()

//We first check if there is a collision (overlap) with the object and one of the walls
collisionSystem.checkOne(object, (response: Response) => {
  Collision.handleCollisionWithRaycast(response, closestWall, objectBody);
})

this.x = object.x;
this.y = object.y;
}

//Collision.ts

function handleCollisionWithRaycast(response: Response, closestWall: Wall, objectBody: ObjectPoly): void {
    if(checkCorrectCollidingBodies(response, closestWall.id)){
        //When there is an overlap we draw raycasts to move the object to the other side
        const firstRaycast = raycast(closestWall, objectBody);
        //With the inverted direction we then raycast again so we now to where we can move the object to
        raycast(closestWall, objectBody, firstRaycast.directionInverted);
    }
}

function checkCorrectCollidingBodies(response: Response, closestWallId: number): boolean {
    return (
        response.a.isObject &&
        response.b.isWall &&
        response.b.wall_id !== closestWallId
    );
}

function raycast(closestWall: Wall, objectBody: ObjectPoly, directionInverted = null) {
    const normalizedDirection = closestWall.getDirectionVector();

    const raycastSets = createRaycastSets();

    objectBody.points.forEach((point, i) => {
        const invertDirection = point.x < 0;

        if(directionInverted === invertDirection){
            return
        }

        if (!shouldPerformRaycast(point, directionInverted)){
            return
        }

        const { start, end } = calculateRaycastEndpoints(point, normalizedDirection, objectBody);

        // const currentSet = point.x < 0 ? raycastSets.left : raycastSets.right;
        const currentSet = invertDirection ? raycastSets.left : raycastSets.right;
        currentSet.raycasts.push({start: start, end: end})

        const hit = performRaycast(start, end, closestWall);

        updateClosestHit(currentSet, start, hit);

        //Save the hit to draw later
        raycastSets.raycastHits.push(hit);

        //Create and save raycastLine to visualize, remove later
        const debugLine = collisionSystem.createLine(start, end, { isTrigger: false });
        raycastSets.raycastLines.push(debugLine);
    });

    //Draw the hits
    drawDebugHits(raycastSets.raycastHits);

    debugCollision.update()

    //Remove the raycast lines from the tree
    removeRaycastLinesFromTree(raycastSets.raycastLines);

    return determineNextPosition(objectBody, raycastSets);
}

function createRaycastSets(): { 
    left: RaycastSet; 
    right: RaycastSet, 
    raycastLines: Line[],
    raycastHits: RaycastHit<Body>[]
} {
    const createRaycastSet = (): RaycastSet => ({
        raycasts: [],
        hasMissed: false,
        closestDistance: Infinity,
        closestHit: null,
        closestVector: { x: 0, y: 0 },
    });

    return {
        left: createRaycastSet(),
        right: createRaycastSet(),
        raycastLines: [],
        raycastHits: [],
    };
}

//checks whether a raycast should be performed based on the point and direction inversion. 
//It returns true if the direction should be inverted and false otherwise.
function shouldPerformRaycast(point: SATVector, directionInverted: boolean): boolean {
    const invertDirection = point.x < 0;
    return directionInverted !== invertDirection;
}

//calculates the object's next position based on raycast data and its current position. 
//It updates the object's position and returns the new coordinates along with a direction flag.
function determineNextPosition(
    objectPoly: ObjectPoly, 
    raycastSets: RaycastSets
    ) {
    const { left, right } = raycastSets;
    const { closestVector } = left.hasMissed || left.raycasts.length <= 0 ? right : left;
    const { x, y } = objectPoly;

    objectPoly.setPosition(x + closestVector.x, y + closestVector.y);

    return {
        x: objectPoly.x, 
        y: objectPoly.y, 
        directionInverted: !left.hasMissed && left.raycasts.length > 0 
    };
}

//Create a raycast on each corner point of the object
function calculateRaycastEndpoints(
    point: SATVector, 
    normalizedDirection: Coordinates, 
    objectPoly: ObjectPoly
    ): { start: Coordinates, end: Coordinates } {
    const invertDirection = point.x < 0;

    const corner = objectPoly.calcPoints[objectPoly.points.indexOf(point)];

    const start = { x: corner.x + objectPoly.x, y: corner.y + objectPoly.y };
    const end = {
        x: start.x + (invertDirection ? -1 : 1) * normalizedDirection.x * 800,
        y: start.y + (invertDirection ? -1 : 1) * normalizedDirection.y * 800,
    };

    return { start, end };
}

function performRaycast(start: Coordinates, end: Coordinates, closestWall: Wall): RaycastHit<Body> {
    return collisionSystem.raycast(start, end, (collision) => {
        //change isObject in the future to current object 
        //so collisions can happen with other object
        return !collision.isObject && collision.wall_id !== closestWall.id
    });
}

function updateClosestHit(currentSet: RaycastSet, start: Coordinates, hit: RaycastHit<Body>): void {
    if (hit) {
        const distance = Math.sqrt(Math.pow(hit.point.x - start.x, 2) + Math.pow(hit.point.y - start.y, 2));
        if (distance < currentSet.closestDistance) {
            currentSet.closestDistance = distance;
            currentSet.closestHit = hit;
            currentSet.closestVector = { x: hit.point.x - start.x, y: hit.point.y - start.y };
        }
    } else {
        currentSet.hasMissed = true;
    }
}

function removeRaycastLinesFromTree(raycastLines: Line[]): void {
    raycastLines.forEach((line) => {
        collisionSystem.remove(line);
    });
}

function drawDebugHits(hits: RaycastHit<Body>[]): void {
    debugCollision.drawCallback = () => {
        debugCollision.context.strokeStyle = "#FF0000";

        hits.forEach(hit => {
            if(!hit){ return }
            const { point, body } = hit;
            debugCollision.context.beginPath();
            debugCollision.context.arc(point.x, point.y, 5, 0, 2 * Math.PI);
            debugCollision.context.stroke();
            // console.log("Hit at point:", point);
            // console.log("Body:", body.wall_id);
        });
    };
}

[Prozi]

@whitespacecode

I thought about this

1. I THINK THERE MAY BE MISCOMUNICATION IN README

2. I THINK WE CAN DO THIS WITHOUT RAYCAST

3. I THINK YOU ARE TELEPORTING INSTEAD OF MOVING TOWARDS ANGLE WITH SPEED

Try this:

function onDragMove() {
  const objectBody = collisionSystem.all().find((body): body is ObjectPoly =>
    body instanceof ObjectPoly && body.id === this.id
  );
  const speed = 1; // this should be later changed to be based on time delta, see [stress test]
  const updateNow = false; // optimization

  const angleInRadians = deg2rad(this.angle);
  const moveX = Math.cos(angleInRadians) * speed;
  const moveY = Math.sin(angleInRadians) * speed;

  // last param = false will not update this instantly but in updateBody() - it will only set body.dirty = true
  objectBody.setAngle(angleInRadians, updateNow);
  objectBody.setPosition(objectBody.x + moveX, objectBody.y + moveY, updateNow);

  // no need to update whole system in this iteration, since nothing else moved, update just body now
  objectBody.updateBody();

  collisionSystem.checkOne(objectBody, ({ overlapV }: Response) => {
    objectBody.setPosition(objectBody.x - overlapV.x, objectBody.y - overlapV.y);
  })

  this.x = objectBody.x;
  this.y = objectBody.y;
}

THIS WAY:

you are not TELEPORTING it to mouse position,

you are moving it with speed = 1 towards angleInRadians so it SHOULD NOT MOVE THROUGH WALLS

IF THIS WORKS PLS HELP ME MAKE THIS MORE CLEAR IN README

WHAT U SUGGEST???

---

stress test delta time example: https://github.com/Prozi/detect-collisions/blob/master/src/demo/stress.js#L103C3-L108C4

[Prozi]

import { deg2rad } from 'detect-collisions' also

[Prozi]

since v9.9.0 you can use body.move() like this:

function onDragMove() {
  const objectBody = collisionSystem.all().find((body): body is ObjectPoly =>
    body instanceof ObjectPoly && body.id === this.id
  );
  const speed = 1; // this should be later changed to be based on time delta, see [stress test]
  const updateNow = false; // optimization

  const angleInRadians = deg2rad(this.angle);

  // last param = false will not update this instantly but in updateBody() - it will only set body.dirty = true
  objectBody.setAngle(angleInRadians, updateNow);
  objectBody.move(1, updateNow); // <================================================

  // no need to update whole system in this iteration, since nothing else moved, update just body now
  objectBody.updateBody();

  collisionSystem.checkOne(objectBody, ({ overlapV }: Response) => {
    objectBody.setPosition(objectBody.x - overlapV.x, objectBody.y - overlapV.y);
  })

  this.x = objectBody.x;
  this.y = objectBody.y;
}

[whitespacecode]

Hmmn, i tried to implement this but found it not working properly. 'move' updates the object in angle position but the user has free movement what to do with their mouse cursor..

So steps are:

• Click and hold down the cursor on the object
• Move the object around in any direction
• User can move it's mouse cursor outside the room (walls), while holding the object.

That's why you would need swept to get the movement trajectory from the object to the new mouse position

[Prozi]

I will try to do a stackblitz because I feel this can be done @whitespacecode

probably today later

[Prozi]

@whitespacecode isn't like this https://stackblitz.com/edit/detect-collisions-tehkkd?file=src%2FApp.js

exactly what you need/talk about ??

[Ewok167]

@whitespacecode isn't like this https://stackblitz.com/edit/detect-collisions-tehkkd?file=src%2FApp.js

exactly what you need/talk about ??

Nice, but it can pass through if too fast like 0.2 instead of the *0.067, not necessary to move the cursor fast.

I think it is just because you are multiplying the speed with the distance. Going faster if further is cool. Wonder how you can fix that without a speed cap. Without raycasting...? Perhaps store the last speed before hitting an object then use that when hitting. Not sure what would happen when hitting objects in other directions though.

[Prozi]

@whitespacecode isn't like this https://stackblitz.com/edit/detect-collisions-tehkkd?file=src%2FApp.js exactly what you need/talk about ??

Nice, but it can pass through if too fast like 0.2 instead of the *0.067, not necessary to move the cursor fast.

I think it is just because you are multiplying the speed with the distance. Going faster if further is cool. Wonder how you can fix that without a speed cap. Without raycasting...? Perhaps store the last speed before hitting an object then use that when hitting. Not sure what would happen when hitting objects in other directions though.

glad it works

I am going to close this now

if you do

const maximum = 5; // example value
const speed = Math.min(maximum, distance);

it will work

just reiterate a few times if you want to not have speed cap and just substract how much speed you already used from amount of what you should've

this feature (swept detection) I dont think is required for such a simple library

hope I helped

[Prozi]

updated https://stackblitz.com/edit/detect-collisions-tehkkd?file=src%2FApp.js to apply the maximum

[whitespacecode]

Thank you for the example! It's clear now i need to look differently how i need to build my collision. I'm still not sure about the speed.. Your object is following the mouse it doesn't really feel like you are dragging it. Best example i can give you is this planner Choose a layout -> click 'make it yours' -> click 'floor view' -> add any item and drag it around

[Prozi]

I feel you

@whitespacecode

if you want to move from { x1, y1 } to { x2, y2 } without moving through walls imitating perfect drag do this:

1. lets say the delta/distance is when you move a bit just 1 and when you move a lot 50
2. so you should do what I did in the react stackblitz example but do - the move by a bit and check collision and stuff - it 50 times
3. each time you do it (in each small step iteration) substract from copy of delta until it is 0

const speed = Math.min(maximumPixelsSoItWontGoThroughWalls, delta);
delta -= speed;

// do stuff for speed
// what I did in stackblits (move, and checkOnce, and push back if collision)

if (!collision && delta > 0) {
  // again goto top
}

you feel me?

[Prozi]

think like this

A: each step you move by a part of whole amount until you reach destination B: and after each small step you check for collisions C: if no collision and still some way to go substract from the destination left and repeat whole process since A.

that is the way

[Prozi]

its like when you start at paris and want to go to rome

you dont move instantly 1000 km

you go 1m then check collision, in real life then again 1m and again until your distance gets 0