There is an open source reimplementation of the settlers II engine, called RttR and it works flawlessly (better than the original for me).

There's also an open source clone of Settlers II called Widelands.