+1 vote

So gist of my problem is I have "Entities" (Kinematic Body 2Ds) that occupy a grid of "Tiles" (Area 2Ds) - think a custom TileMap. I move these entities via the physicsprocess(), but I move them in discrete steps (from one tile to the next, think a chess board) so I don't apply any velocity to them (which from what I understand is a no-no). I have an issue where every so often when two entities try to move in the exact same frame they can occupy the same tile. I've tried numerous ways to resolve this. I've double checked that the tile is collision masked for entities and vise versa.

in the physicsprocess() of the entity if it is in a moving state it will get a path to follow then attempt to move one tile during that frame. in attempt to make sure two entities don't occupy the same tile i've made locks for the tile.

class_name Tile
extends Area2D

var _lock := Mutex.new()
...
func lockTileForEntity(e):
    if !isEmpty():
        return false
    if _lock.try_lock() == OK:
        _lock.lock()
        _lockedForEntity = e
        return true
    else:
        return false

func isLockedForEntity(e):
    return _lockedForEntity == e

func unlockTile():
    _lock.unlock()
    _lockedForEntity = null

func isEmpty():
    return get_overlapping_bodies().empty()

This is (modified code but essentially what executes, entities interface with a board which interfaces with a tile) what the entity attempts to execute during physicsprocess() if it is in the moving state:

extends KinematicBody2D
...
if targetTile.lockTileForEntity(self):
    if targetTile.isLockedForEntity(self):
        self.position = targetTile.position
        _MoveTimer.start()
        _canMove = false
        targetTile.unlockTile()

I left the movetimer in there to show that entities are locked out of movement for a period of time after moving so they don't try to move every frame.

From what I gather if there is a situation where two entities want to move to the same unoccupied tile: isEmpty() will be true - and that's where i get confused because:

  1. the Mutex should ensure thread safe, single access locking for the tile
  2. i even double check to make sure it's locked for the correct entity before attempting to move.

I've tried the brute force solution of:

 yield(get_tree().create_timer(rand_range(0.05, 0.1), "timeout")

at the start of lockTileForEntity(e), until i realized that yielding drops the thread out of the function back up the call stack. This definitely cut down on the occurrences of two entities occupying the same tile, but didn't eliminate it all together.

I'm new to game development and godot so i'm definitely open to proper solutions for this issue.
Thank you for your help!

Godot version 3.3 (was happening in 3.2 as well)
in Engine by (2,190 points)

I managed to solve this issue. Here are my discoveries for anyone in the future with the same issue:

  • If funcA() calls funcB() and funcB() has a yield() statement in it funcB() returns a GDScriptFunctionState object back to funcA(). So in my case I thought targetTile.lockTileForEntity(self) was only ever receiving a boolean back, but it turns out the yield was causing it to return a GDScriptFunctionState object. Since that object was not null, it was continuing on through the if conditional.
  • Mutexes ARE thread safe. There is only a single thread running in my game so it gets the lock, recognizes that it is locked for itself (thread) and continues on through the conditional. My use case was a complete misuse of the Mutex object.

How I solved it, after realizing Mutexes aren't going to work for my use case of locking, I implemented a FIFO "lock queue" where objects request to lock the tile, then ultimately the tile decides who it is locked for. In order to avoid a deadlock scenario where a tile remains locked despite not having an entity present in it, I created a timer that handled the unlocking of the tile. It's kind of hacky but I figure the physics frame will catch up and allow isEmpty() to work correctly after the timer (0.15 seconds) times out. Code:

_lockQueue = []
func _process(_delta: float) -> void:
    if _lockQueue.empty():
        pass
    elif _lockedForEntity:
        pass
    else:
        _lockedForEntity = _lockQueue.pop_front()
        _lockTimer.start()

func lockTileForEntity(e):
    if e in _lockQueue:
        return true
    elif !isEmpty():
        return false
    else:
        _lockQueue.push_back(e)
        return true

func unlockTile():
    yield(get_tree(), "physics_frame")
    _lockedForEntity = null

func _on_LockTimer_timeout() -> void:
    unlockTile()

This isn't an ideal solution because now I have 64 more nodes chewing up resources each frame but I figure if performance takes a hit in the future I can setprocess(false) if _lockQueue.empty() and setprocess(true) when adding another entity to the lockQueue and isprocessing() is false.

Please log in or register to answer this question.

Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.