What senses can we postulate that these creatures have?
You said they're deaf so I guess that rules out echolocation.
But do they have some organ that can send some other sort of signal that bounces off the target object and returns, and which their brains can then time the trip to determine the distance? If not sound, maybe radio waves. Or less exotic, a burst of air. Or whatever.
If the creatures exist in an environment with air, they could judge distance by how "foggy" the image is, i.e. the more air an image has to pass through, the more distorted it will become. Humans do this in a very vague way: you know an object is far away because it's dim and hazy. This gets complicated because air density and composition varies, but perhaps these creatures have another sense that determines the composition of the air, how much humidity, etc, and then adjusts the computation in their brains.
They could have a very fine sense of scale. They know that an object is a certain size. When it's close up it looks big, when it's far away it looks small. Some objects, of course, have very variable sizes, but one could imagine a creature that can detect scale from detail. Again, humans do this to some extent, and it's always good for an optical illusion or a joke to have an object that looks like an object that you think you know the size, but really it's a very different size.
For any such alternative sense, you could say, "But the calculations that would have to be done in their brains for that to work would be very complicated." Well, sure. But the calculations that have to be done in our brains for us to determine distance by parallax are pretty complicated. What bats do to determine distance by echolocation is pretty complicated. Etc. The complexity and sophistication of living things is amazing. That's one of the classic arguments for intelligent design.