To install the required 32 bits libraries :
# apt-get install libsdl-mixer1.2:i386 libsmpeg0:i386
To install the game, mount your CD & run the installer with linux32 from the util-linux package :
# mount /dev/cdrom /media/cdrom $ linux32 bash /media/cdrom/setup.sh
Apply the last released patch :
$ linux32 bash heroes3-1.3.1a-cdrom-x86.run
./heroes3.dynamic greets you with “Segmentation fault”
This is due to a change in libgcc that broke some binaries that where compiled with gcc 2.95 in an unusual way (like compiling C++ code with gcc instead of g++).
You can use a little shim that add back functions required by a bunch of old games like this one.
LD_PRELOAD="/path/to/lokishim.so" ./heroes3.dynamic
The missing function can be found in a very old libstdc++, and you can use libstdc++-3-libc6.2-2-2.10.0.so from https://www.improbability.net/loki/
LD_PRELOAD="./libstdc++-3-libc6.2-2-2.10.0.so" ./heroes3.dynamic
If you are using sdl12-compat instead of a real SDL-1.2 (you should, any serious linux distribution should have made the transition now), the game will freeze as soon as you see the menu. But fear not, there is a workaround:
SDL12COMPAT_COMPATIBILITY_AUDIOCVT=1 LD_PRELOAD="/path/to/lokishim.so" ./heroes3.dynamic