"I have an idea. Checking self collision for solutions while pathfinding is not possible for performance reasons, but would it be possible to check the final proposed solution for self collisions? Like, just turn the ghosts red where they would fail to place? That would keep the game from misleading the player about the path being valid, but you'd only need to check collision on one solution instead of every possible one."