Time Proportional control
It sounds like you are looking at the absolute value of the error; instead, you should calculate the error as a positive or negative value.  If you only have one-directional control (e.g., no active cooling), you should just do nothing when the actual temperature is above the set point.

Specifically for your two examples:


When AT=19, error = +1, output = heater on 50% 
When AT=21, error = -1, output = heater off


Edit:


When AT=20, error = 0, output = heater off


Pseudo-code is something like:

const Kp = 1/2.
error = SP - AT
control_output = Kp * error 
set_heater_power(clip(control_output, 0.0, 1.0))