After a lot of preparation, finally removed full redraw at every tile addition and removal. There is still some room for optimization, but at 800x600 play area the game is now using less than 1% of a 2GHz cpu, with minimal redrawings.

Unfortunately, this change is for KDE4 only and can not be backported to 3.5.x series.