collision detection – Need help improving my Flow Field and Unit Avoidance code so that the units can properly surround a unit instead of getting stuck

My setup is like this. Every update my movement system moves all of the units on the field. They use some Boid logic to avoid eachother, and a flow field that directs them towards each other. This is the result. https://imgur.com/a/CaUpfT7

My general setup is to calculate 2 flow fields, one for each player. From every field on the map (32×32 fields) I calculate the vector that points towards the closest enemy. Now this is a fine approach but I’d like to somehow take into consideration obstacles somehow (without another round of for loops)? Or should I handle that in my movement system avoidance? I was maybe thinking of doing A* once a unit is close enough to the enemy but all of these systems together seem rather hacky and overkill.

There are no obstacles currently, maybe a spell will generate it in the future. For now there are only units on the battleground without terrain or obstacles (besides units fighting eachother)

Here is some code. Firstly how I create the flowfields (kinda costly, will look into a way to optimize it further, don’t really need every single tile, can probably merge 2 or 3 together)

func (g *Grid) Update() {
    g.entityPositions(0) = g.entityPositions(0)(:0)
    g.entityPositions(1) = g.entityPositions(1)(:0)
    entities := g.world.GetEntityManager().GetEntities()
    posComps := g.world.GetObjectPool().Components("PositionComponent")

    for _, ent := range entities {
        g.entityPositions(ent.PlayerTag) = append(g.entityPositions(ent.PlayerTag), posComps(ent.Index).(components.PositionComponent).Position)
    }

    for x := 0; x <= g.MaxWidth/FlowTileSize; x++ {
        for y := 0; y <= g.MaxHeight/FlowTileSize; y++ {

            curPosVector := engine.Vector{X: float32(x * 32), Y: float32(y * 32)}
            // find closest tile to this one for both players
            minDist := float32(100000.0)
            minIndx := -1
            for indx, pos := range g.entityPositions(0) {
                d := engine.GetDistanceIncludingDiagonal(pos, curPosVector)
                if d < minDist {
                    minIndx = indx
                    minDist = d
                }
            }

            //  fmt.Printf("CurPos : %v, enemyPos : %v,  direction %v n", curPosVector, g.entityPositions(0)(minIndx), g.entityPositions(0)(minIndx).Subtract(curPosVector).Normalize())
            g.flowTiles(1)(x)(y).Direction = g.entityPositions(0)(minIndx).Subtract(curPosVector).Normalize()

            minDist1 := float32(100000.0)
            minIndx1 := -1
            for indx, pos := range g.entityPositions(1) {
                d := engine.GetDistanceIncludingDiagonal(pos, curPosVector)
                if d < minDist1 {
                    minIndx1 = indx
                    minDist1 = d
                }
            }

            g.flowTiles(0)(x)(y).Direction = g.entityPositions(1)(minIndx1).Subtract(curPosVector).Normalize()
        }
    }
}

And my movement code. A lot of code but just basic allignnment cohesion/ separation. With added 2 look ahead vectors to steer away from the collision.

        desiredDirection := world.Grid.GetDesiredDirectionAt(positionComp.Position, tag)
        direction := movementComp.Direction
        maxSpeed = movementComp.MovementSpeed

        //Avoidance
        nearbyEntities := helper.GetNearbyEntities(100, world, index)

        avoidance := engine.Zero()
        avoidance = avoidance.Add(alignment(world, nearbyEntities, direction).MultiplyScalar(alignmentCoef))
        avoidance = avoidance.Add(cohesion(world, nearbyEntities, direction, positionComp.Position).MultiplyScalar(cohesionCoef))
        avoidance = avoidance.Add(separation(world, nearbyEntities, direction, positionComp.Position).MultiplyScalar(separationCoef))


        //Checking ahead of us whether or not we'll encounter something
        lookAheadVectorLong := direction.Add(desiredDirection).MultiplyScalar(maxSpeed * 2.5)
        lookAheadVectorShort := direction.Add(desiredDirection).MultiplyScalar(maxSpeed)
        maxAvoidanceForce := float32(1.0)

        checkPosShort := positionComp.Position.Add(lookAheadVectorShort)
        checkPosLong := positionComp.Position.Add(lookAheadVectorLong)

        collidedIndexShort := world.Grid.IsPositionFree(index, checkPosShort, positionComp.BoundingBox)
        collidedIndexLong := world.Grid.IsPositionFree(index, checkPosLong, positionComp.BoundingBox)

        if collidedIndexShort != -1 {
            direction = engine.Zero()
            avoidance = checkPosShort.Subtract(world.ObjectPool.Components("PositionComponent")(collidedIndexShort).(components.PositionComponent).Position).Normalize()
            avoidance = avoidance.MultiplyScalar(maxAvoidanceForce * 1.5)
        } else if collidedIndexLong != -1 {
            direction = direction.MultiplyScalar(breakingForce)
            avoidance = checkPosShort.Subtract(world.ObjectPool.Components("PositionComponent")(collidedIndexLong).(components.PositionComponent).Position).Normalize()
            avoidance = avoidance.MultiplyScalar(maxAvoidanceForce * 1.2)
        }

        direction = desiredDirection
        direction = direction.Add(avoidance).Normalize()

        positionComp.Position = positionComp.Position.Add(direction.MultiplyScalar(maxSpeed))

        positionComp.Position.X = engine.Constraint(positionComp.Position.X, 0, 799)
        positionComp.Position.Y = engine.Constraint(positionComp.Position.Y, 0, 511)

        movementComp.Direction = direction.Normalize()

        world.ObjectPool.Components("PositionComponent")(index) = positionComp
        world.ObjectPool.Components("MovementComponent")(index) = movementComp

        fmt.Printf("I %d am at %vn", index, positionComp.Position)
    }

}

func limit(p engine.Vector, lim float32) engine.Vector {
    if p.X > lim {
        p.X = lim
    } else if p.X < -lim {
        p.X = -lim
    }
    if p.Y > lim {
        p.Y = lim
    } else if p.Y < -lim {
        p.Y = -lim
    }
    return p
}
func alignment(world *game.World, siblings ()int, velocity engine.Vector) engine.Vector {
    avg := engine.Vector{X: 0, Y: 0}
    total := float32(0.0)

    for _, siblingIndex := range siblings {
        avg = avg.Add(world.ObjectPool.Components("MovementComponent")(siblingIndex).(components.MovementComponent).Direction)
        total++
    }
    if total > 0 {
        avg = avg.DivideScalar(total)
        avg = avg.Normalize().MultiplyScalar(maxSpeed)
        avg = avg.Subtract(velocity)
        avg = limit(avg, maxForce)
        return avg
    }
    return engine.Vector{X: 0.0, Y: 0.0}

}

func cohesion(world *game.World, siblings ()int, velocity engine.Vector, position engine.Vector) engine.Vector {
    avg := engine.Vector{X: 0, Y: 0}
    total := float32(0)

    for _, siblingindex := range siblings {

        avg = avg.Add(world.ObjectPool.Components("PositionComponent")(siblingIndex).(components.PositionComponent).Position)
        total++

    }
    if total > 0 {
        avg = avg.MultiplyScalar(1.0 / total * cohesionCoef)
        avg = avg.Subtract(position)
        avg = avg.Normalize().MultiplyScalar(maxSpeed)
        avg = avg.Subtract(velocity)
        avg = limit(avg, maxForce)
        return avg
    }
    return engine.Vector{X: 0.0, Y: 0.0}
}

func separation(world *game.World, siblings ()int, velocity engine.Vector, position engine.Vector) engine.Vector {
    avg := engine.Vector{X: 0, Y: 0}
    total := float32(0)

    for _, siblingIndex := range siblings {
        siblingPos := world.ObjectPool.Components("PositionComponent")(siblingIndex).(components.PositionComponent).Position
        d := position.Distance(siblingPos)
        if d < desiredSeperation {
            diff := position.Subtract(siblingPos)
            diff = diff.Normalize()
            diff = diff.DivideScalar(d)
            avg = avg.Add(diff)
            total++
        }
    }
    if total > 0 {
        avg.DivideScalar(total)
    }

    if total > 0 {
        avg = avg.MultiplyScalar(1.0 / total * separationCoef)
        avg = avg.Normalize().MultiplyScalar(maxSpeed)
        avg = avg.Subtract(velocity)
        avg = limit(avg, maxForce)
    }
    return avg
}

What I am trying to achieve is:

Units not mashing into each other and just positioning themselves in a free spot around their target.

What are my problems :

  1. Make the flow field direct them away from collision rather than just towards closest unit.
  2. Make it work with the current system without adding too many nested loops and awful checks.
  3. I am doing the avoidance correctly? I have a desired direction that I get from the flow field (that directs me towards closest enemy), then I add avoidance to it to avoid any other units in the area.

My units move really well up untill the point of collision/ going to a spot next to a target. I am not sure how to implemenent that behaviour yet.

(This is my forth iteration of the movement system. I went from pure boid, to grid based, to A*, to this. So I tried a lot of variations and this going surrounding behaviour has been bugging me every time.)

Custom engine (server) written in Golang and then dispatched to Godot for the visuals. Performance is not my concern, but this is a server, so I am more mindful of that, I could probably brute force it but I’d rather hear some better take on it.

Any suggestion/article/ video is greatly appreciated !!

Edit: Thinking about it, flow field is currently useless. I can basically just have a vector pointing to the closest enemy for each unit… Would be less costly as well. But the problem of them clumping and not knowing how to surround still stands.

Unity – Pushing a companion aside on collision

I’ve recently implemented companions in my game (without a NavMesh Agent) and it all works nicely except for one thing.

If I’m colliding (Rigidbodies) with my companion, the player will stop.

I’ve tried to implement stuff like this:

    private void OnCollisionEnter(Collision collision)
    {
        // how much the character should be knocked back
        var magnitude = 1000;
        // calculate force vector
        var force = transform.position - collision.transform.position;
        // normalize force vector to get direction only and trim magnitude
        force.Normalize();
        myRB.AddForce(force * magnitude);
    }

And it does push my companion away, but not the way I want to. It’s pushing the character in the way I’m moving, so that partner still blocks my path. I want it to push my helpmate away/aside, so that it doesn’t block the path of my player.

This is what I’m trying to archieve.

The properties for both Rigidbodies are the following:

Mass: 1
Drag: 5
Angular Drag: 0.05
Use Gravity: True
Is Kinematic: False
Interpolate: None
Collision Detection: Discrete

I’d prefer to not change anything about the player’s rigidbody, since I already adjusted these properties for a good movement.

If anyone has any idea on how to implement this, please let me know.

Thanks in advance!

collision detection – player disappears when collides with enemy

I was making a game and then when I tested it out, if I keep on colliding with the enemy, the player’s image just disappears but the rect is still there.

main.py:

import pygame as pg
import sys
from random import choice, random
from os import path
from settings import *
from sprites import *
from tilemap import *

# HUD functions
def draw_player_health(surf, x, y, pct):
    if pct < 0:
        pct = 0
    BAR_LENGTH = 100
    BAR_HEIGHT = 20
    fill = pct * BAR_LENGTH
    outline_rect = pg.Rect(x, y, BAR_LENGTH, BAR_HEIGHT)
    fill_rect = pg.Rect(x, y, fill, BAR_HEIGHT)
    if pct > 0.6:
        col = GREEN
    elif pct > 0.3:
        col = YELLOW
    else:
        col = RED
    pg.draw.rect(surf, col, fill_rect)
    pg.draw.rect(surf, WHITE, outline_rect, 2)

class Game:
    def __init__(self):
        pg.mixer.pre_init(44100, -16, 4, 2048)
        pg.init()
        self.screen = pg.display.set_mode((WIDTH, HEIGHT))
        pg.display.set_caption(TITLE)
        self.clock = pg.time.Clock()
        self.load_data()

    def draw_text(self, text, font_name, size, color, x, y, align="topleft"):
        font = pg.font.Font(font_name, size)
        text_surface = font.render(text, True, color)
        text_rect = text_surface.get_rect(**{align: (x, y)})
        self.screen.blit(text_surface, text_rect)

    def load_data(self):
        game_folder = path.dirname(__file__)
        self.img_folder = path.join(game_folder, 'img')
        self.font_folder = path.join(game_folder, 'fonts')
        self.weapon_folder = path.join(game_folder, 'weapons')
        self.snd_folder = path.join(game_folder, 'snd')
        self.music_folder = path.join(game_folder, 'music')
        self.item_folder = path.join(game_folder, 'items')
        self.potion_folder = path.join(self.item_folder, 'potions')
        self.map_folder = path.join(game_folder, 'maps')
        self.monster_folder = path.join(game_folder, 'enemies')
        self.title_font = path.join(self.font_folder, 'AlegreyaSC-Italic.ttf')
        self.hud_font = path.join(self.font_folder, 'AlegreyaSC-Italic.ttf')
        self.dim_screen = pg.Surface(self.screen.get_size()).convert_alpha()
        self.dim_screen.fill((0, 0, 0, 180))
        self.player_img = pg.image.load(path.join(self.img_folder, PLAYER_IMG)).convert_alpha()
        self.bullet_images = {}
        self.bullet_images('lg') = pg.image.load(path.join(self.weapon_folder, BULLET_IMG)).convert_alpha()
        self.bullet_images('sm') = pg.transform.scale(self.bullet_images('lg'), (10, 10))
        self.mob_img = pg.image.load(path.join(self.monster_folder, MOB_IMG)).convert_alpha()
        self.splat = pg.image.load(path.join(self.img_folder, SPLAT)).convert_alpha()
        self.splat = pg.transform.scale(self.splat, (64, 64))
        self.item_images = {}
        for item in ITEM_IMAGES:
            # Todo: give each item a type, and make it like path.join(f'{item(type)}_folder, ITEM_IMAGES(item)')
            self.item_images(item) = pg.image.load(path.join(self.potion_folder, ITEM_IMAGES(item))).convert_alpha()        # Sound loading
        pg.mixer.music.load(path.join(self.music_folder, BG_MUSIC))
        self.effects_sounds = {}
        for type in EFFECTS_SOUNDS:
            self.effects_sounds(type) = pg.mixer.Sound(path.join(self.snd_folder, EFFECTS_SOUNDS(type)))
        self.weapon_sounds = {}
        for weapon in WEAPON_SOUNDS:
            self.weapon_sounds(weapon) = ()
            for snd in WEAPON_SOUNDS(weapon):
                s = pg.mixer.Sound(path.join(self.snd_folder, snd))
                s.set_volume(0.3)
                self.weapon_sounds(weapon).append(s)
        self.zombie_moan_sounds = ()
        for snd in ZOMBIE_MOAN_SOUNDS:
            s = pg.mixer.Sound(path.join(self.snd_folder, snd))
            s.set_volume(0.2)
            self.zombie_moan_sounds.append(s)
        self.player_hit_sounds = ()
        for snd in PLAYER_HIT_SOUNDS:
            self.player_hit_sounds.append(pg.mixer.Sound(path.join(self.snd_folder, snd)))
        self.zombie_hit_sounds = ()
        for snd in ZOMBIE_HIT_SOUNDS:
            self.zombie_hit_sounds.append(pg.mixer.Sound(path.join(self.snd_folder, snd)))

    def new(self, map_name):
        # initialize all variables and do all the setup for a new game
        self.all_sprites = pg.sprite.LayeredUpdates()
        self.walls = pg.sprite.Group()
        self.mobs = pg.sprite.Group()
        self.bullets = pg.sprite.Group()
        self.items = pg.sprite.Group()
        self.portals = pg.sprite.Group()
        self.map = TiledMap(path.join(self.map_folder, map_name))
        self.map_img = self.map.make_map()
        self.map.rect = self.map_img.get_rect()
        for tile_object in self.map.tmxdata.objects:
            obj_center = vec(tile_object.x + tile_object.width / 2,
                             tile_object.y + tile_object.height / 2)
            if tile_object.name == 'player':
                self.player = Player(self, obj_center.x, obj_center.y)
            if tile_object.name == 'zombie':
                Mob(self, obj_center.x, obj_center.y)
            if tile_object.name == "https://gamedev.stackexchange.com/#":
                Obstacle(self, tile_object.x, tile_object.y,
                         tile_object.width, tile_object.height)
            if tile_object.name in ('health', 'shotgun'):
                Item(self, obj_center, tile_object.name)
            # delete this if cant work!!!
            if tile_object.name == 'portal':
                Portal(self, tile_object.x, tile_object.y,
                       tile_object.width, tile_object.height, tile_object.type)


        self.camera = Camera(self.map.width, self.map.height)
        self.draw_debug = False
        self.paused = False
        self.night = False
        self.effects_sounds('level_start').play()

    def run(self):
        # game loop - set self.playing = False to end the game
        self.playing = True
        pg.mixer.music.play(loops=-1)
        while self.playing:
            self.dt = self.clock.tick(FPS) / 1000.0  # fix for Python 2.x
            self.events()
            if not self.paused:
                self.update()
            self.draw()

    def quit(self):
        pg.quit()
        sys.exit()

    def update(self):
        # update portion of the game loop
        self.all_sprites.update()
        self.camera.update(self.player)
        # player hits items
        hits = pg.sprite.spritecollide(self.player, self.items, False)
        for hit in hits:
            if hit.type == 'health' and self.player.health < PLAYER_HEALTH:
                hit.kill()
                self.effects_sounds('health_up').play()
                self.player.add_health(HEALTH_PACK_AMOUNT)
            if hit.type == 'shotgun':
                hit.kill()
                self.effects_sounds('gun_pickup').play()
                self.player.weapon = 'shotgun'
        # mobs hit player
        hits = pg.sprite.spritecollide(self.player, self.mobs, False, collide_hit_rect)
        for hit in hits:
            if random() < 0.7:
                choice(self.player_hit_sounds).play()
            self.player.health -= MOB_DAMAGE
            hit.vel = vec(0, 0)
            if self.player.health <= 0:
                self.playing = False
        if hits:
            self.player.hit()
            self.player.pos += vec(MOB_KNOCKBACK, 0).rotate(-hits(0).rot)
        # bullets hit mobs
        hits = pg.sprite.groupcollide(self.mobs, self.bullets, False, True)
        for mob in hits:
            # hit.health -= WEAPONS(self.player.weapon)('damage') * len(hits(hit))
            for bullet in hits(mob):
                mob.health -= bullet.damage
            mob.vel = vec(0, 0)

    def draw_grid(self):
        for x in range(0, WIDTH, TILESIZE):
            pg.draw.line(self.screen, LIGHTGREY, (x, 0), (x, HEIGHT))
        for y in range(0, HEIGHT, TILESIZE):
            pg.draw.line(self.screen, LIGHTGREY, (0, y), (WIDTH, y))


    def draw(self):
        pg.display.set_caption("{:.2f}".format(self.clock.get_fps()))
        # self.screen.fill(BGCOLOR)
        self.screen.blit(self.map_img, self.camera.apply(self.map))
        # self.draw_grid()
        for sprite in self.all_sprites:
            if isinstance(sprite, Mob):
                sprite.draw_health()
            self.screen.blit(sprite.image, self.camera.apply(sprite))
            if self.draw_debug:
                pg.draw.rect(self.screen, CYAN, self.camera.apply_rect(sprite.hit_rect), 1)
        if self.draw_debug:
            for wall in self.walls:
                pg.draw.rect(self.screen, CYAN, self.camera.apply_rect(wall.rect), 1)

        # pg.draw.rect(self.screen, WHITE, self.player.hit_rect, 2)
        # HUD functions
        draw_player_health(self.screen, 10, 10, self.player.health / PLAYER_HEALTH)
        self.draw_text('Zombies: {}'.format(len(self.mobs)), self.hud_font, 30, WHITE,
                       WIDTH - 10, 10, align="topright")
        if self.paused:
            self.screen.blit(self.dim_screen, (0, 0))
            self.draw_text("Paused", self.title_font, 105, RED, WIDTH / 2, HEIGHT / 2, align="center")
        pg.display.flip()

    def events(self):
        # catch all events here
        for event in pg.event.get():
            if event.type == pg.QUIT:
                self.quit()
            if event.type == pg.KEYDOWN:
                if event.key == pg.K_ESCAPE:
                    self.quit()
                if event.key == pg.K_h:
                    self.draw_debug = not self.draw_debug
                if event.key == pg.K_p:
                    self.paused = not self.paused
                if event.key == pg.K_n:
                    self.night = not self.night

    def show_start_screen(self):
        pass

    def show_go_screen(self):
        self.screen.fill(BLACK)
        self.draw_text("GAME OVER", self.title_font, 100, RED,
                       WIDTH / 2, HEIGHT / 2, align="center")
        self.draw_text("Press a key to start", self.title_font, 75, WHITE,
                       WIDTH / 2, HEIGHT * 3 / 4, align="center")
        pg.display.flip()
        self.wait_for_key()

    def wait_for_key(self):
        pg.event.wait()
        waiting = True
        while waiting:
            self.clock.tick(FPS)
            for event in pg.event.get():
                if event.type == pg.QUIT:
                    waiting = False
                    self.quit()
                if event.type == pg.KEYUP:
                    waiting = False

thegame.py

from main import *

#the game!
g = Game()
while True:

sprites.py

import pygame as pg
from random import uniform, choice, randint, random
from settings import *
from tilemap import collide_hit_rect
import pytweening as tween
from itertools import chain
vec = pg.math.Vector2

def collide_with_walls(sprite, group, dir):
    if dir == 'x':
        hits = pg.sprite.spritecollide(sprite, group, False, collide_hit_rect)
        if hits:
            if hits(0).rect.centerx > sprite.hit_rect.centerx:
                sprite.pos.x = hits(0).rect.left - sprite.hit_rect.width / 2
            if hits(0).rect.centerx < sprite.hit_rect.centerx:
                sprite.pos.x = hits(0).rect.right + sprite.hit_rect.width / 2
            sprite.vel.x = 0
            sprite.hit_rect.centerx = sprite.pos.x
    if dir == 'y':
        hits = pg.sprite.spritecollide(sprite, group, False, collide_hit_rect)
        if hits:
            if hits(0).rect.centery > sprite.hit_rect.centery:
                sprite.pos.y = hits(0).rect.top - sprite.hit_rect.height / 2
            if hits(0).rect.centery < sprite.hit_rect.centery:
                sprite.pos.y = hits(0).rect.bottom + sprite.hit_rect.height / 2
            sprite.vel.y = 0
            sprite.hit_rect.centery = sprite.pos.y

def collide_with_portal(game, destination, sprite, group, direction):
    # todo: copy paste above and make it into the portal thing and look at tutorials
    if direction == 'y':
        hits = pg.sprite.spritecollide(sprite, group, False, collide_hit_rect)
        if hits:
            if hits(0).rect.centery > sprite.hit_rect.centery:
                sprite.pos.y = hits(0).rect.top - sprite.hit_rect.height / 2
            if hits(0).rect.centery < sprite.hit_rect.centery:
                sprite.pos.y = hits(0).rect.bottom + sprite.hit_rect.height / 2
            sprite.vel.y = 0
            sprite.hit_rect.centery = sprite.pos.y
            go_to_place(game, destination)
    # todo: same for x!
    if direction == 'x':
        hits = pg.sprite.spritecollide(sprite, group, False, collide_hit_rect)
        if hits:
            if hits(0).rect.centerx > sprite.hit_rect.centerx:
                sprite.pos.x = hits(0).rect.left - sprite.hit_rect.width / 2
            if hits(0).rect.centerx < sprite.hit_rect.centerx:
                sprite.pos.x = hits(0).rect.right + sprite.hit_rect.width / 2
            sprite.vel.x = 0
            sprite.hit_rect.centerx = sprite.pos.x
            go_to_place(game, destination)

def go_to_place(game, destination):
    # portal thingy
    game.new(destination)

class Player(pg.sprite.Sprite):
    def __init__(self, game, x, y):
        self._layer = PLAYER_LAYER
        self.groups = game.all_sprites
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.image = game.player_img
        self.rect = self.image.get_rect()
        self.rect.center = (x, y)
        self.hit_rect = PLAYER_HIT_RECT
        self.hit_rect.center = self.rect.center
        self.vel = vec(0, 0)
        self.pos = vec(x, y)
        self.rot = 0
        self.last_shot = 0
        self.health = PLAYER_HEALTH
        self.weapon = 'pistol'
        self.damaged = False

    def get_keys(self):
        # self.rot_speed = 0
        # self.vel = vec(0, 0)
        # keys = pg.key.get_pressed()
        # if keys(pg.K_LEFT) or keys(pg.K_a):
        #     self.rot_speed = PLAYER_ROT_SPEED
        # if keys(pg.K_RIGHT) or keys(pg.K_d):
        #     self.rot_speed = -PLAYER_ROT_SPEED
        # if keys(pg.K_UP) or keys(pg.K_w):
        #     self.vel = vec(PLAYER_SPEED, 0).rotate(-self.rot)
        # if keys(pg.K_DOWN) or keys(pg.K_s):
        #     self.vel = vec(-PLAYER_SPEED / 2, 0).rotate(-self.rot)
        # if keys(pg.K_SPACE):
        #     self.shoot()
        self.vel = vec(0, 0)
        keys = pg.key.get_pressed()
        if keys(pg.K_LEFT) or keys(pg.K_a):
            self.vel = vec(-PLAYER_SPEED, 0)
        if keys(pg.K_RIGHT) or keys(pg.K_d):
            self.vel = vec(PLAYER_SPEED, 0)
        if keys(pg.K_UP) or keys(pg.K_w):
            self.vel = vec(0, -PLAYER_SPEED)
        if keys(pg.K_DOWN) or keys(pg.K_s):
            self.vel = vec(0, PLAYER_SPEED)
        if keys(pg.K_SPACE):
            self.shoot()

    def shoot(self):
        now = pg.time.get_ticks()
        if now - self.last_shot > WEAPONS(self.weapon)('rate'):
            self.last_shot = now
            dir = vec(1, 0).rotate(-self.rot)
            pos = self.pos + BARREL_OFFSET.rotate(-self.rot)
            self.vel = vec(-WEAPONS(self.weapon)('kickback'), 0).rotate(-self.rot)
            for i in range(WEAPONS(self.weapon)('bullet_count')):
                spread = uniform(-WEAPONS(self.weapon)('spread'), WEAPONS(self.weapon)('spread'))
                Bullet(self.game, pos, dir.rotate(spread), WEAPONS(self.weapon)('damage'))
                snd = choice(self.game.weapon_sounds(self.weapon))
                if snd.get_num_channels() > 2:
                    snd.stop()
                snd.play()

    def hit(self):
        self.damaged = True
        self.damage_alpha = chain(DAMAGE_ALPHA * 4)

    def update(self):
        self.get_keys()
        self.image = self.game.player_img
        if self.damaged:
            try:
                self.image.fill((255, 255, 255, next(self.damage_alpha)), special_flags=pg.BLEND_RGBA_MULT)
            except:
                self.damaged = False
        self.rect = self.image.get_rect()
        self.rect.center = self.pos
        self.pos += self.vel * self.game.dt
        self.hit_rect.centerx = self.pos.x
        collide_with_walls(self, self.game.walls, 'x')
        collide_with_portal(self.game, 'eg.dungeon.tmx', self, self.game.portals, 'x')
        self.hit_rect.centery = self.pos.y
        collide_with_walls(self, self.game.walls, 'y')
        collide_with_portal(self.game, 'eg.dungeon.tmx', self, self.game.portals, 'y')
        self.rect.center = self.hit_rect.center

    def add_health(self, amount):
        self.health += amount
        if self.health > PLAYER_HEALTH:
            self.health = PLAYER_HEALTH

class Mob(pg.sprite.Sprite):
    def __init__(self, game, x, y):
        self._layer = MOB_LAYER
        self.groups = game.all_sprites, game.mobs
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.image = game.mob_img.copy()
        self.rect = self.image.get_rect()
        self.rect.center = (x, y)
        self.hit_rect = MOB_HIT_RECT.copy()
        self.hit_rect.center = self.rect.center
        self.pos = vec(x, y)
        self.vel = vec(0, 0)
        self.acc = vec(0, 0)
        self.rect.center = self.pos
        self.rot = 0
        self.health = MOB_HEALTH
        self.speed = choice(MOB_SPEEDS)
        self.target = game.player

    def avoid_mobs(self):
        for mob in self.game.mobs:
            if mob != self:
                dist = self.pos - mob.pos
                if 0 < dist.length() < AVOID_RADIUS:
                    self.acc += dist.normalize()

    def update(self):
        target_dist = self.target.pos - self.pos
        if target_dist.length_squared() < DETECT_RADIUS**2:
            if random() < 0.002:
                choice(self.game.zombie_moan_sounds).play()
            self.rot = target_dist.angle_to(vec(1, 0))
            self.image = pg.transform.rotate(self.game.mob_img, self.rot)
            self.rect.center = self.pos
            self.acc = vec(1, 0).rotate(-self.rot)
            self.avoid_mobs()
            self.acc.scale_to_length(self.speed)
            self.acc += self.vel * -1
            self.vel += self.acc * self.game.dt
            self.pos += self.vel * self.game.dt + 0.5 * self.acc * self.game.dt ** 2
            self.hit_rect.centerx = self.pos.x
            collide_with_walls(self, self.game.walls, 'x')
            self.hit_rect.centery = self.pos.y
            collide_with_walls(self, self.game.walls, 'y')
            self.rect.center = self.hit_rect.center
        if self.health <= 0:
            choice(self.game.zombie_hit_sounds).play()
            self.kill()
            self.game.map_img.blit(self.game.splat, self.pos - vec(32, 32))

    def draw_health(self):
        if self.health > 60:
            col = GREEN
        elif self.health > 30:
            col = YELLOW
        else:
            col = RED
        width = int(self.rect.width * self.health / MOB_HEALTH)
        self.health_bar = pg.Rect(0, 0, width, 7)
        if self.health < MOB_HEALTH:
            pg.draw.rect(self.image, col, self.health_bar)

class Bullet(pg.sprite.Sprite):
    def __init__(self, game, pos, dir, damage):
        self._layer = BULLET_LAYER
        self.groups = game.all_sprites, game.bullets
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.image = game.bullet_images(WEAPONS(game.player.weapon)('bullet_size'))
        self.rect = self.image.get_rect()
        self.hit_rect = self.rect
        self.pos = vec(pos)
        self.rect.center = pos
        #spread = uniform(-GUN_SPREAD, GUN_SPREAD)
        self.vel = dir * WEAPONS(game.player.weapon)('bullet_speed') * uniform(0.9, 1.1)
        self.spawn_time = pg.time.get_ticks()
        self.damage = damage

    def update(self):
        self.pos += self.vel * self.game.dt
        self.rect.center = self.pos
        if pg.sprite.spritecollideany(self, self.game.walls):
            self.kill()
        if pg.time.get_ticks() - self.spawn_time > WEAPONS(self.game.player.weapon)('bullet_lifetime'):
            self.kill()

class Obstacle(pg.sprite.Sprite):
    def __init__(self, game, x, y, w, h):
        self.groups = game.walls
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.rect = pg.Rect(x, y, w, h)
        self.hit_rect = self.rect
        self.x = x
        self.y = y
        self.rect.x = x
        self.rect.y = y


class Item(pg.sprite.Sprite):
    def __init__(self, game, pos, type):
        self._layer = ITEMS_LAYER
        self.groups = game.all_sprites, game.items
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.image = game.item_images(type)
        self.rect = self.image.get_rect()
        self.type = type
        self.pos = pos
        self.rect.center = pos
        self.tween = tween.easeInOutSine
        self.step = 0
        self.dir = 1

    def update(self):
        # bobbing motion
        offset = BOB_RANGE * (self.tween(self.step / BOB_RANGE) - 0.5)
        self.rect.centery = self.pos.y + offset * self.dir
        self.step += BOB_SPEED
        if self.step > BOB_RANGE:
            self.step = 0
            self.dir *= -1

class Portal(pg.sprite.Sprite):
    def __init__(self, game, x, y, w, h, where):
        self.destination = where
        self._layer = ITEMS_LAYER
        self.groups = game.portals
        pg.sprite.Sprite.__init__(self, self.groups)
        self.game = game
        self.rect = pg.Rect(x, y, w, h)
        self.hit_rect = self.rect
        self.x = x
        self.y = y
        self.rect.x = x
        self.rect.y = y
        g.new('overworld.tmx')
        g.run()

tilemap.py

import pygame as pg
import pytmx
from settings import *

def collide_hit_rect(one, two):
    return one.hit_rect.colliderect(two.rect)

class Map:
    def __init__(self, filename):
        self.data = ()
        with open(filename, 'rt') as f:
            for line in f:
                self.data.append(line.strip())

        self.tilewidth = len(self.data(0))
        self.tileheight = len(self.data)
        self.width = self.tilewidth * TILESIZE
        self.height = self.tileheight * TILESIZE

class TiledMap:
    def __init__(self, filename):
        tm = pytmx.load_pygame(filename, pixelalpha=True)
        self.width = tm.width * tm.tilewidth
        self.height = tm.height * tm.tileheight
        self.tmxdata = tm

    def render(self, surface):
        ti = self.tmxdata.get_tile_image_by_gid
        for layer in self.tmxdata.visible_layers:
            if isinstance(layer, pytmx.TiledTileLayer):
                for x, y, gid, in layer:
                    tile = ti(gid)
                    if tile:
                        surface.blit(tile, (x * self.tmxdata.tilewidth,
                                            y * self.tmxdata.tileheight))

    def make_map(self):
        temp_surface = pg.Surface((self.width, self.height))
        self.render(temp_surface)
        return temp_surface

class Camera:
    def __init__(self, width, height):
        self.camera = pg.Rect(0, 0, width, height)
        self.width = width
        self.height = height

    def apply(self, entity):
        return entity.rect.move(self.camera.topleft)

    def apply_rect(self, rect):
        return rect.move(self.camera.topleft)

    def update(self, target):
        x = -target.rect.centerx + int(WIDTH / 2)
        y = -target.rect.centery + int(HEIGHT / 2)

        # limit scrolling to map size
        x = min(0, x)  # left
        y = min(0, y)  # top
        x = max(-(self.width - WIDTH), x)  # right
        y = max(-(self.height - HEIGHT), y)  # bottom
        self.camera = pg.Rect(x, y, self.width, self.height)

settings.py

import pygame as pg
vec = pg.math.Vector2

# define some colors (R, G, B)
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
DARKGREY = (40, 40, 40)
LIGHTGREY = (100, 100, 100)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
YELLOW = (255, 255, 0)
BROWN = (106, 55, 5)
CYAN = (0, 255, 255)

# game settings
WIDTH = 1024   # 16 * 64 or 32 * 32 or 64 * 16
HEIGHT = 768  # 16 * 48 or 32 * 24 or 64 * 12
FPS = 60
TITLE = "some rpg"
BGCOLOR = BROWN

TILESIZE = 64
GRIDWIDTH = WIDTH / TILESIZE
GRIDHEIGHT = HEIGHT / TILESIZE

# Player settings
PLAYER_HEALTH = 100
PLAYER_SPEED = 280
PLAYER_ROT_SPEED = 200
PLAYER_IMG = 'dir_down_fmale.png'
PLAYER_HIT_RECT = pg.Rect(0, 0, 35, 35)
BARREL_OFFSET = vec(30, 10)

# Weapon settings
BULLET_IMG = 'stone spear2.png'
WEAPONS = {}
WEAPONS('pistol') = {'bullet_speed': 500,
                     'bullet_lifetime': 1000,
                     'rate': 250,
                     'kickback': 200,
                     'spread': 5,
                     'damage': 10,
                     'bullet_size': 'lg',
                     'bullet_count': 1}
WEAPONS('shotgun') = {'bullet_speed': 400,
                      'bullet_lifetime': 500,
                      'rate': 900,
                      'kickback': 300,
                      'spread': 20,
                      'damage': 5,
                      'bullet_size': 'sm',
                      'bullet_count': 12}

# Mob settings
MOB_IMG = 'Enemy 06-1.png'
MOB_SPEEDS = (150, 100, 75, 125)
MOB_HIT_RECT = pg.Rect(0, 0, 30, 30)
MOB_HEALTH = 100
MOB_DAMAGE = 10
MOB_KNOCKBACK = 20
AVOID_RADIUS = 50
DETECT_RADIUS = 400

# Effects
MUZZLE_FLASHES = ('whitePuff15.png', 'whitePuff16.png', 'whitePuff17.png',
                  'whitePuff18.png')
SPLAT = 'splat.png'
FLASH_DURATION = 50
DAMAGE_ALPHA = (i for i in range(0, 255, 55))
LIGHT_RADIUS = (500, 500)
LIGHT_MASK = "light_350_soft.png"

# Layers
WALL_LAYER = 1
PLAYER_LAYER = 2
BULLET_LAYER = 3
MOB_LAYER = 2
EFFECTS_LAYER = 4
ITEMS_LAYER = 1
PORTAL_LAYER = 1

# Items
ITEM_IMAGES = {'health': 'Icon3.png',
               'shotgun': 'Icon5.png'}
HEALTH_PACK_AMOUNT = 20
BOB_RANGE = 10
BOB_SPEED = 0.3

# Sounds
BG_MUSIC = 'espionage.ogg'
PLAYER_HIT_SOUNDS = ('pain/8.wav', 'pain/9.wav', 'pain/10.wav', 'pain/11.wav')
ZOMBIE_MOAN_SOUNDS = ('brains2.wav', 'brains3.wav', 'zombie-roar-1.wav', 'zombie-roar-2.wav',
                      'zombie-roar-3.wav', 'zombie-roar-5.wav', 'zombie-roar-6.wav', 'zombie-roar-7.wav')
ZOMBIE_HIT_SOUNDS = ('splat-15.wav')
WEAPON_SOUNDS = {'pistol': ('pistol.wav'),
                 'shotgun': ('shotgun.wav')}
EFFECTS_SOUNDS = {'level_start': 'level_start.wav',
                  'health_up': 'health_pack.wav',
                  'gun_pickup': 'gun_pickup.wav'}

collision detection – How can I find the closest point between an oriented bounding box and a capsule?

My capsule is defined by a center position with a radius and length. I have capsule/capsule, sphere/sphere, sphere/capsule, sphere/obb, obb/obb, and sphere/triangle collision working, but I cannot figure out how to do capsule/obb.

I know how to find the closest point on an obb to another point, the closest point on a line to another point, and the closest point between two lines.

How do I resolve a collision in SAT-3D when the projection axis is zero?

I am doing SAT in 3D, right now just between cuboids/3D rects (idk the terminology). I have intersection working fully, and static collision works as long as the projection axis is not zero. But if it is zero, I am unsure how to get the minimum translation vector and overlap.

Right now my collision response is this, if it helps.

        float3 dir = polyPosB - polyPosA;
        if ( math.dot( minOverlapAxis , dir ) <= 0 )
            minOverlapAxis *= -1;

        minOverlapAxis = math.normalize( minOverlapAxis );

        float3 displacement1 = -( minOverlapAxis * minOverlap ) / 2;
        float3 displacement2 = ( minOverlapAxis * minOverlap ) / 2;

        polyPosA = polyPosA + displacement1;
        polyPosB = polyPosB + displacement2;

dnd 5e – Is a target pushed into a wall by a spell effect subject to collision damage?

No, there is no such collision damage which results from being forcibly moved by a spell effect

This is one of those cases where a couple of D&D rules analysis clichés apply, though they still deserve explication: spells do what they say they do, and D&D is not a physics simulator. These are important because they offer the most direct way to consider such an effect from such a spell. In the absence of a specific rule stating that this is or is not possible we have to look at rules that do exist for guidance, at least as a first-order investigation. Let’s take those in turn:

Spells do what they say they do

This one is pretty straightforward. Spells that contain text about forced movement, like Thunderwave, don’t say anything about situational or environmental damage. There aren’t many that I can think of offhand (Thunderwave, Eldritch Blast with the Repelling Blast invocation, and Telekinesis all push or can push, and Thorn Whip and Eldritch Blast with the Grasp of Hadar invocation can pull), and none of them contain such text.

We can also look at the rules’ description of how damage from spells is defined:

A spell tells you which dice to roll for damage and whether to add any modifiers. (PHB, Chapter 9: Combat, Damage and Healing, Damage Rolls)

If a spell doesn’t tell you to to roll a damage die, you don’t roll it. If the spell’s effects trigger some other defined mechanic (like being moved off of a cliff, after which the moved creature or object falls ten or more feet), then you would adjudicate that other mechanic as the rules define it. Both of those are absent in the case of being moved into a wall.

This isn’t great evidence that a secondary effect, like impact against a surface, cannot occur. But the key point to draw here is that we have no resources (from the spell descriptions themselves) to guide our thinking on how to implement those effects in a generic sense. What damage die would be the right one to pick? Does the material the wall is made of make a difference? What about the size of the creature? The spells don’t touch these details at all, and parsimony suggests that reading such effects into the spells is not the right approach.

D&D is not a physics simulator

This item completely addresses the sole argument presented in the question that collision damage should exist:

To me it seems logical that it would: it is like falling, sudden force applied to a creature due to encountering resistance from an object.

In the real world, this is 100% correct. But the real world doesn’t contain Eldritch Blasts or Thunderwaves, so real-world considerations may not be the best way to understand in-game circumstances.

Even if you don’t like that approach, the game rules do not deal with most of the relevant details either:

  • The impulse applied is mysteriously variable (a Gargantuan creature
    gets pushed 10 feet, as does a Tiny creature– those forces then
    cannot be equal, even though the spell cast may be identical in each
    case)
  • The amount of time over which the effect is applied is unclear (does
    it take six seconds to cast the spell, with the movement occurring over
    a zero-time duration, suggesting infinite acceleration? If the spell takes fewer than 6 seconds, how many remain for the creature or object to be moved that 10-foot distance?)
  • The characteristics of the wall being struck (there aren’t clearly
    distinct representations of mud brick walls vs. stone walls vs. metal
    walls in terms of their ability to absorb kinetic energy)
  • Which portion of a square (on a grid) is the affected creature or
    object in when the forced movement starts? Five feet is as precise as
    positioning gets, but you’re not going to get a very precise
    calculation from “give or take five feet”

Whether or not you want to model these kinds of interactions in the game, the official rules do not provide enough detail to apply them. The game is instead a set of simplified mechanics which simulate some specific things and not others, while also simulating some decidedly unreal things.


By analogy

As pointed out in the question, forced movement from one of these spells seems similar to mechanics for falling. That’s as close as we can get because there are no published rules for being bashed against a solid surface. The PHB describes damage from falling as

At the end of a fall, a creature takes 1d6 bludgeoning damage for every 10 feet it fell, to a maximum of 20d6. The creature lands prone, unless it avoids taking damage from the fall. (PHB, Chapter 8: Adventuring, The Environment, Falling)

The damage doesn’t occur because it’s realistic– it occurs because the rules state it. It is pretty clear that falls of less than 10 feet do no damage (which is itself not realistic; I’ve sprained my ankle from falling way less than that!). Falling from 15 feet is exactly as dangerous as falling from 10 feet, or 19 feet, or 11 feet. Realism is not a factor.

In that light, the lack of a rule describing being slammed into walls by forced movement is conclusive. There is no rule, so there is no damage.

We have a few other indications in the rules of hitting walls (or sort-of-walls hitting you) not having the most realistic effects:

The Rolling Sphere trap description in the DMG states

Activation of the sphere (a 10-foot-diameter rolling sphere of solid stone) requires all creatures present to roll initiative. The sphere rolls initiative with a +8 bonus. On its turn, it moves 60 feet in a straight line. The sphere can move through creatures’ spaces, and creatures can move through its space, treating it as difficult terrain. Whenever the sphere enters a creature’s space or a creature enters its space while it’s rolling, that creature must succeed on a DC 15 Dexterity saving throw or take 55 (10d10) bludgeoning damage and be knocked prone.

The sphere stops when it hits a wall or similar barrier. It can’t go around corners, but smart dungeon builders incorporate gentle, curving turns into nearby passages that allow the sphere to keep moving. (DMG, Chapter 5: Adventure Environments, Traps, Rolling Sphere)

It doesn’t matter what the wall or barrier is made of, nor what the sphere is made of, nor that the sphere is moving at ten feet per second. The sphere stops completely on contact with the wall or barrier.

There is an interesting, similar case in the Sphere of Crushing Doom:

The trap’s active element is a sphere of steel that almost fills the 10-foot width of the hallway and rolls to the bottom of the slope on its turn. Each creature in the sphere’s path must make a DC 20 Strength saving throw. On a failed save, a creature takes 22 (4d10) bludgeoning damage and is knocked prone. On a successful save, a creature takes half as much damage and isn’t knocked prone. Objects that block the sphere, such as a conjured wall, take maximum damage from the impact. (Xanathar’s Guide to Everything, Chapter 2: Traps Revisited, Example Complex Traps, Sphere of Crushing Doom)

When the sphere is made of solid steel, as opposed to solid stone, a wall that it hits takes damage but the sphere does not. This is at least an example of a lateral impact with a wall causing bludgeoning damage, and is the closest support for collision damage I can find. Whether or not a given creature is more durable than a giant, solid ball of steel is another question (and one which is probably not too solidly answered by the rules as written).


It’s probably a reasonable house rule to apply 1d6 bludgeoning damage on collision

1d6 damage isn’t so much that it risks breaking the game, and isn’t wildly out of line with damage that attack cantrips deal (especially when characters reach a high enough level to get extra damage dice), and is pretty conditional in when it can be applied. It also never gets better, as the maximum forced movement from these spells is ten feet. There may be unintended consequences of a ruling in this direction with other game mechanics, but that’s out of scope here.

Importantly, it isn’t so good that players will be driven to force enemies to within ten feet of walls to set this collision up or use a spell slot on Thunderwave rather than something else that might be situationally valuable. But it is cool and dramatic enough that players might be excited to get the extra damage when the opportunity arises organically.

physics – What is the science behind 3d collision relative to the ground?

To my understanding you have the model of the character and the model of the map.

It seems extremely redundant and process intensive to have to calculate that the ground exerts a force on the player model.

So to my understanding if y coord was less than a certain value then the physics would behave differently.

but what if the map becomes an incline instead of linear? the model would just walk through the ramp into nothingness….

EDIT: i remember a commercial game where you could “sink” if your speed was high enough. So it seems to me like the ground is somehow coded to exert a force on the player without putting too much work on th cpu

collision detection – player teleporting into other levels

So I basically want to load another map once the player collides with a object, specifically a “Portal” in my game. Which is really making the player move onto other levels. I don’t want to jumble up my code with a bunch of function like “go_to_level_9” or something so I’m planning to use a list or dictionary or something. So how to those game devs out do that? Code’s here: https://pastebin.com/rpddq1MP. The part with the portal stuff, walls and a few others:

    for tile_object in self.map.tmxdata.objects:
        obj_center = vec(tile_object.x + tile_object.width / 2,
                         tile_object.y + tile_object.height / 2)
        if tile_object.name == 'player':
            self.player = Player(self, obj_center.x, obj_center.y)
        if tile_object.name == 'zombie':
            Mob(self, obj_center.x, obj_center.y)
        if tile_object.name == "https://gamedev.stackexchange.com/#":
            Obstacle(self, tile_object.x, tile_object.y,
                     tile_object.width, tile_object.height)
        if tile_object.name in ('health', 'shotgun'):
            Item(self, obj_center, tile_object.name)
        if tile_object.name == 'portal':
            self.map = TiledMap(path.join(self.map_folder, tile_object.type))

how do you do it? I’m currently using Tiled and pygame so I’m also using pytmx.

java – Another not working 2D collision system

As many before me, I’m trying to make a 2D platformer. The current problem is the collision system. I tried to be smart and use sweeping and line segments to implement this, which ended up somewhat working, but not quite.

Here’s what I’m trying to do:

  1. The player is made of four vertices
  2. The map is made of axis-aligned line segments creating polygons
  3. Calculate the next frame’s position of all four points
  4. Create four line segments from the before/after positions, one for each vert
  5. Intersect these segments with the map
  6. Move the player to the collision point on the axis perpendicular to the wall only

Here’s what happens:

  1. Some walls work just fine
  2. Some walls have collision from the “wrong” side
  3. Some walls have no collision
  4. Some walls stop having collisions when sliding on them
  5. Some walls can’t be moved away from

Here’s the relevant excerpts of my code. Subject to be refactored, I wanted to get this working first.

// Player
public class Player extends Sprite {

    private PlayScreen scr;

    public Vector2 vel;
    public Vector2 lastMove;

    public Vector2() verts = new Vector2(2);
    

    public Player(PlayScreen s, float x, float y) {
        this.scr = s;
        this.setPosition(x, y);
        this.setSize(8, 16);
        vel = new Vector2(0, 0);
        lastMove = new Vector2(0, 0);
        
        Rectangle r = this.getBoundingRectangle();
        float x1 = r.x;
        float x2 = r.x + r.width;
        float y1 = r.y; 
        float y2 = r.y + r.height;
        
        verts(0) = new Vector2(x1,y1);
        verts(1) = new Vector2(x2,y2);
    }

    public void update(float delta) {
        float xpos = this.getX();
        float ypos = this.getY();

        float dx = vel.x * delta;
        float dy = vel.y * delta;

        this.setPosition(xpos + dx, ypos + dy);
        this.lastMove.set(dx, dy);
    }

    public Vector2 getTR() {
        return new Vector2(this.getVertices()(Batch.X3),this.getVertices()(Batch.Y3));
    }

    public Vector2 getBR() {
        return new Vector2(this.getVertices()(Batch.X4),this.getVertices()(Batch.Y4));
    }
    
    public Vector2 getTL() {
        return new Vector2(this.getVertices()(Batch.X2),this.getVertices()(Batch.Y2));
    }
    
    public Vector2 getBL() {
        return new Vector2(this.getVertices()(Batch.X1),this.getVertices()(Batch.Y1));
    }
    
}
// PlayScreen
public class PlayScreen implements Screen {

    private OrthogonalTiledMapRenderer renderer;
    private Player player;
    private Collision collision;

    public PlayScreen(MovementGame mg) {
        
        // omitted cam/viewport setup
        // omitted map loading
        this.renderer = new OrthogonalTiledMapRenderer(map, 1);
        cam.position.set(viewport.getWorldWidth() / 2, viewport.getWorldHeight() / 2, 0);

        player = new Player(this, -50, -50);
        collision = new Collision();

        for (PolygonMapObject obj : this.map.getLayers().get(2).getObjects().getByType(PolygonMapObject.class)) {
            collision.addObj(obj);
        }
    }

    @Override
    public void render(float delta) {
        Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT);

        player.vel.x = 0;
        player.vel.y = 0;

        // omitted input handling. sets player.vel to +-100 x/y on arrow key press

        player.update(delta);

        // omitted debug player drawing
        // omitted debug player drawing for next position

        collision.doCollision(player, cam);
        cam.position.lerp(new Vector3(player.getX(), player.getY(), 0),1f);

        cam.update();
        renderer.setView(cam);

        // omitted debug map drawing
    }
}

public class Collision {

    public ArrayList<Vector2()> lines;

    public Collision() {
        lines = new ArrayList<>();
    }

    // convert polygon verts to lines and add to list
    public void addObj(PolygonMapObject obj) {
        float() a = obj.getPolygon().getTransformedVertices();
        ArrayList<Vector2> verts = new ArrayList<>();
        for (int i = 0; i < obj.getPolygon().getVertices().length; i += 2) {
            verts.add(new Vector2(a(i + 0), a(i + 1)));
        }

        for (int i = 0; i < verts.size() - 1; i++) {
            lines.add(new Vector2() { verts.get(i), verts.get(i + 1) });
        }
        lines.add(new Vector2() { verts.get(0), verts.get(verts.size() - 1) });
    }

    // detect and resolve collision. camera is for debug drawing
    public void doCollision(Player p, Camera cam) {
        Vector2 col;
        float dx = 0;
        float dy = 0;
        // try to intersect with every line
        for (Vector2() line : lines) {
            dx = dy = 0;
            // create the movement line for each vert of the player 
            // try to intersect it with the currect line
            // there HAS to be a better way...
            if ((col = getLineIntersection(p.getBL(), p.getBL().sub(p.lastMove), line(0), line(1))) != null) {
                dx = p.getBL().x - col.x;
                dy = p.getBL().y - col.y;
            }
            if ((col = getLineIntersection(p.getTL(), p.getTL().sub(p.lastMove), line(0), line(1))) != null) {
                dx = p.getTL().x - col.x;
                dy = p.getTL().y - col.y;
            }
            if ((col = getLineIntersection(p.getBR(), p.getBR().sub(p.lastMove), line(0), line(1))) != null) {
                dx = p.getBR().x - col.x;
                dy = p.getBR().y - col.y;
            }
            if ((col = getLineIntersection(p.getTR(), p.getTR().sub(p.lastMove), line(0), line(1))) != null) {
                dx = p.getTR().x - col.x;
                dy = p.getTR().y - col.y;
            }
            // something collided. resolve
            if (col != null) {
                
                if (line(0).y == line(1).y) {
                // line is horizontal. push player up/down only
                    p.vel.x = 0;
                    dx = 0;
                } else {
                // line is vertical. push player left/right only
                    p.vel.y=0;
                    dy = 0;
                }

                // omitted debug drawing
                // finally, update the player pos
                p.setPosition(p.getX() - dx, p.getY() - dy);
            }
        }
    }

    private Vector2 getLineIntersection(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3) {
        Vector2 res = new Vector2();
        if (Intersector.intersectSegments(p0, p1, p2, p3, res)) {
            return res;
        } else {
            return null;
        }
    }
}

Any ideas or tips on how this could be turned into something working? Or should I give up on this and do grid AABB-collision instead?

Finally, here’s a rare screenshot of the code doing what it should. Blue is the player’s position before the movement, red the intended position, yellow the resolved position and white the distance the player moved too far.
screenshot

Same colors, but issue #5. The collision gets resolved onto the wall instead of away.
screenshot2

Thank you in advance for your help! Please excuse the form of this question, this is making me lose my mind…

unity – In collision detection/resolution, what is a “collide and slide” algorithm?

Can anyone help me to better understand the concepts behind this algorithm?

I’ve seen this phrase come up several times during my research into creating a 3D character controller, but am having issues finding much information about it. One example is from a user manual that accompanies a character controller asset on the Unity asset store.

I’m used to handling collisions in 2D that involve primitive colliders, so most of the time I simply move my entity, check for overlaps, and then calculate the shortest distance out of the primitive (if one is using Unity, he or she can also use the ColliderDistance2D API for this). It seems like “collide and slide” might be a bit more involved, especially in 3D where contact with a mesh may be the norm instead of contact with primitives. From the manual I linked earlier it seems that an entity’s movement vector is altered based on the normal of the surface with which that entity collides, but where does the actual collision (overlap) occur, and how do we resolve it?