Add map reduce feature for software drawing.

Now invisible tiles will be removed if this mode enabled.

8 files changed, 174 insertions, 17 deletions

diff --git a/src/defaults.cpp b/src/defaults.cpp
index 2f505502e..0fcf1c5d7 100644
--- a/src/defaults.cpp
+++ b/src/defaults.cpp
@@ -206,6 +206,7 @@ DefaultsData* getConfigDefaults()
     AddDEF(configData, "showDidYouKnow", true);
     AddDEF(configData, "useLocalTime", false);
     AddDEF(configData, "enableAdvert", true);
+    AddDEF(configData, "enableMapReduce", true);
     return configData;
 }
 
diff --git a/src/gui/setup_video.cpp b/src/gui/setup_video.cpp
index 38250bedc..8afb0ae69 100644
--- a/src/gui/setup_video.cpp
+++ b/src/gui/setup_video.cpp
@@ -283,6 +283,7 @@ Setup_Video::Setup_Video():
     mFps(config.getIntValue("fpslimit")),
     mAltFps(config.getIntValue("altfpslimit")),
     mAlphaCache(config.getBoolValue("alphaCache")),
+    mEnableMapReduce(config.getBoolValue("enableMapReduce")),
     mShowBackground(config.getBoolValue("showBackground")),
     mSpeechMode(static_cast<Being::Speech>(
         config.getIntValue("speech"))),
@@ -301,6 +302,7 @@ Setup_Video::Setup_Video():
     mPickupParticleCheckBox(new CheckBox(_("as particle"),
                             mPickupParticleEnabled)),
     mAlphaCacheCheckBox(new CheckBox(_("Enable opacity cache"), mAlphaCache)),
+    mEnableMapReduceCheckBox(new CheckBox(_("Enable map reduce"), mEnableMapReduce)),
     mShowBackgroundCheckBox(new CheckBox(_("Show background"),
                             mShowBackground)),
     mSpeechSlider(new Slider(0, 3)),
@@ -343,6 +345,7 @@ Setup_Video::Setup_Video():
     mAlphaSlider->setValue(mOpacity);
     mAlphaSlider->setWidth(90);
     mAlphaCacheCheckBox->setEnabled(mOpenGLDropDown->getSelected() == 0);
+    mEnableMapReduceCheckBox->setEnabled(mOpenGLDropDown->getSelected() == 0);
 
     mFpsLabel->setCaption(mFps > 0 ? toString(mFps) : _("None"));
     mFpsLabel->setWidth(60);
@@ -375,6 +378,7 @@ Setup_Video::Setup_Video():
     mParticleDetailSlider->setActionEventId("particledetailslider");
     mParticleDetailField->setActionEventId("particledetailfield");
     mAlphaCacheCheckBox->setActionEventId("alphaCache");
+    mEnableMapReduceCheckBox->setActionEventId("enableMapReduce");
     mOpenGLDropDown->setActionEventId("opengl");
 
     mModeList->addActionListener(this);
@@ -394,6 +398,7 @@ Setup_Video::Setup_Video():
     mOpenGLDropDown->addActionListener(this);
 
     mAlphaCacheCheckBox->addKeyListener(this);
+    mEnableMapReduceCheckBox->addKeyListener(this);
 
     mSpeechLabel->setCaption(speechModeToString(mSpeechMode));
     mSpeechSlider->setValue(mSpeechMode);
@@ -413,6 +418,7 @@ Setup_Video::Setup_Video():
 
     place(0, 6, mHwAccelCheckBox, 6);
     place(0, 7, mAlphaCacheCheckBox, 6);
+    place(0, 8, mEnableMapReduceCheckBox, 6);
 
     place(1, 0, mFsCheckBox, 2);
 
@@ -426,27 +432,27 @@ Setup_Video::Setup_Video():
     place(1, 5, mPickupChatCheckBox, 1);
     place(2, 5, mPickupParticleCheckBox, 2);
 
-    place(0, 8, mAlphaSlider);
-    place(1, 8, alphaLabel, 3);
+    place(0, 9, mAlphaSlider);
+    place(1, 9, alphaLabel, 3);
 
-    place(0, 9, mFpsSlider);
-    place(1, 9, mFpsCheckBox).setPadding(3);
-    place(2, 9, mFpsLabel).setPadding(1);
+    place(0, 10, mFpsSlider);
+    place(1, 10, mFpsCheckBox).setPadding(3);
+    place(2, 10, mFpsLabel).setPadding(1);
 
-    place(0, 10, mAltFpsSlider);
-    place(1, 10, mAltFpsLabel).setPadding(3);
+    place(0, 11, mAltFpsSlider);
+    place(1, 11, mAltFpsLabel).setPadding(3);
 
-    place(0, 11, mSpeechSlider);
-    place(1, 11, speechLabel);
-    place(2, 11, mSpeechLabel, 3).setPadding(2);
+    place(0, 12, mSpeechSlider);
+    place(1, 12, speechLabel);
+    place(2, 12, mSpeechLabel, 3).setPadding(2);
 
-    place(0, 12, mOverlayDetailSlider);
-    place(1, 12, overlayDetailLabel);
-    place(2, 12, mOverlayDetailField, 3).setPadding(2);
+    place(0, 13, mOverlayDetailSlider);
+    place(1, 13, overlayDetailLabel);
+    place(2, 13, mOverlayDetailField, 3).setPadding(2);
 
-    place(0, 13, mParticleDetailSlider);
-    place(1, 13, particleDetailLabel);
-    place(2, 13, mParticleDetailField, 3).setPadding(2);
+    place(0, 14, mParticleDetailSlider);
+    place(1, 14, particleDetailLabel);
+    place(2, 14, mParticleDetailField, 3).setPadding(2);
 
     int width = 600;
 
@@ -544,6 +550,7 @@ void Setup_Video::apply()
     config.setValue("altfpslimit", mAltFps);
 
     config.setValue("alphaCache", mAlphaCacheCheckBox->isSelected());
+    config.setValue("enableMapReduce", mEnableMapReduceCheckBox->isSelected());
     config.setValue("showBackground", mShowBackgroundCheckBox->isSelected());
 
     // We sync old and new values at apply time
@@ -551,6 +558,7 @@ void Setup_Video::apply()
     mCustomCursorEnabled = config.getBoolValue("customcursor");
     mParticleEffectsEnabled = config.getBoolValue("particleeffects");
     mAlphaCache = config.getBoolValue("alphaCache");
+    mEnableMapReduce = config.getBoolValue("enableMapReduce");
     mShowBackground = config.getBoolValue("showBackground");
 
     mSpeechMode = static_cast<Being::Speech>(
@@ -577,6 +585,7 @@ void Setup_Video::cancel()
     mAltFpsSlider->setEnabled(mAltFps > 0);
     mSpeechSlider->setValue(mSpeechMode);
     mAlphaCacheCheckBox->setSelected(mAlphaCache);
+    mEnableMapReduceCheckBox->setSelected(mEnableMapReduce);
     mShowBackgroundCheckBox->setSelected(mShowBackground);
     mAlphaSlider->setValue(mOpacity);
     mOverlayDetailSlider->setValue(mOverlayDetail);
@@ -598,6 +607,7 @@ void Setup_Video::cancel()
     config.setValue("particleeffects", mParticleEffectsEnabled);
     config.setValue("speech", static_cast<int>(mSpeechMode));
     config.setValue("alphaCache", mAlphaCache);
+    config.setValue("enableMapReduce", mEnableMapReduce);
     config.setValue("showBackground", mShowBackground);
     config.setValue("guialpha", mOpacity);
     Image::setEnableAlpha(mOpacity != 1.0f);
@@ -742,6 +752,7 @@ void Setup_Video::action(const gcn::ActionEvent &event)
     {
         bool isSoftware = (mOpenGLDropDown->getSelected() == 0);
         mAlphaCacheCheckBox->setEnabled(isSoftware);
+        mEnableMapReduceCheckBox->setEnabled(isSoftware);
     }
 }
 
diff --git a/src/gui/setup_video.h b/src/gui/setup_video.h
index 3f2ab09c8..4448b05c8 100644
--- a/src/gui/setup_video.h
+++ b/src/gui/setup_video.h
@@ -64,6 +64,7 @@ class Setup_Video : public SetupTab, public gcn::KeyListener
         int mFps;
         int mAltFps;
         bool mAlphaCache;
+        bool mEnableMapReduce;
         bool mShowBackground;
         Being::Speech mSpeechMode;
 
@@ -90,6 +91,7 @@ class Setup_Video : public SetupTab, public gcn::KeyListener
         gcn::CheckBox *mPickupParticleCheckBox;
 
         gcn::CheckBox *mAlphaCacheCheckBox;
+        gcn::CheckBox *mEnableMapReduceCheckBox;
         gcn::CheckBox *mShowBackgroundCheckBox;
         gcn::Slider *mSpeechSlider;
         gcn::Label *mSpeechLabel;
diff --git a/src/map.cpp b/src/map.cpp
index 88eecf4e8..0d98628fd 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -1652,6 +1652,119 @@ void Map::clearIndexedTilesets()
     mIndexedTilesetsSize = 0;
 }
 
+void Map::reduce()
+{
+    if (!mFringeLayer || mOpenGL > 0 ||
+        !config.getBoolValue("enableMapReduce"))
+    {
+        return;
+    }
+
+    int cnt = 0;
+    for (int x = 0; x < mWidth; x ++)
+    {
+        for (int y = 0; y < mHeight; y ++)
+        {
+            Layers::const_iterator layeri = mLayers.begin();
+            bool correct(true);
+            bool dontHaveAlpha(false);
+
+            for (; layeri != mLayers.end(); ++ layeri)
+            {
+                MapLayer *layer = *layeri;
+                if (x >= layer->mWidth || y >= layer->mHeight)
+                    continue;
+
+                Image *img = layer->mTiles[x + y * layer->mWidth];
+                if (img)
+                {
+                    img->setAlphaVisible(true);
+                    if (img->mBounds.w > 32 || img->mBounds.h > 32)
+                    {
+                        correct = false;
+                        break;
+                    }
+                    else if (!img->isHasAlphaChannel())
+                    {
+                        dontHaveAlpha = true;
+                        img->setAlphaVisible(false);
+                    }
+                    else if (img->hasAlphaChannel())
+                    {
+                        Uint8 *arr = img->SDLgetAlphaChannel();
+                        if (!arr)
+                            continue;
+                        bool bad(false);
+                        bool stop(false);
+                        int width;
+                        SubImage *subImg = dynamic_cast<SubImage*>(img);
+                        if (subImg)
+                            width = subImg->mInternalBounds.w;
+                        else
+                            width = img->mBounds.w;
+
+                        for (int f = img->mBounds.x;
+                             f < img->mBounds.x + img->mBounds.w; f ++)
+                        {
+                            for (int d = img->mBounds.y;
+                                 d < img->mBounds.y + img->mBounds.h; d ++)
+                            {
+                                Uint8 chan = arr[f + d * width];
+                                if (chan != 255)
+                                {
+                                    bad = true;
+                                    stop = true;
+                                    break;
+                                }
+                            }
+                            if (stop)
+                                break;
+                        }
+                        if (!bad)
+                        {
+                            dontHaveAlpha = true;
+                            img->setAlphaVisible(false);
+                        }
+                        else
+                        {
+                            img->setAlphaVisible(true);
+                        }
+                    }
+                }
+            }
+            if (!correct || !dontHaveAlpha)
+                continue;
+
+            Layers::const_reverse_iterator ri = mLayers.rbegin();
+            while (ri != mLayers.rend())
+            {
+                MapLayer *layer = *ri;
+                if (x >= layer->mWidth || y >= layer->mHeight)
+                    continue;
+
+                Image *img = layer->mTiles[x + y * layer->mWidth];
+                if (img && !img->isAlphaVisible())
+                {   // removing all down tiles
+                    ++ ri;
+                    while (ri != mLayers.rend())
+                    {
+                        img = (*ri)->mTiles[x + y * (*ri)->mWidth];
+                        if (img)
+                        {
+                            (*ri)->mTiles[x + y * (*ri)->mWidth] = 0;
+                            cnt ++;
+                        }
+                        ++ ri;
+                    }
+                    break;
+                }
+                ++ ri;
+            }
+        }
+    }
+    logger->log("tiles reduced: %d", cnt);
+}
+
 SpecialLayer::SpecialLayer(int width, int height, bool drawSprites):
     mWidth(width), mHeight(height)
 {
diff --git a/src/map.h b/src/map.h
index c8ce7918c..e33a9a35c 100644
--- a/src/map.h
+++ b/src/map.h
@@ -119,6 +119,8 @@ class TileAnimation
 class MapLayer: public ConfigListener
 {
     public:
+        friend class Map;
+
         /**
          * Constructor, taking layer origin, size and whether this layer is the
          * fringe layer. The fringe layer is the layer that draws the actors.
@@ -468,6 +470,8 @@ class Map : public Properties, public ConfigListener
         void setVersion(int n)
         { mVersion = n; }
 
+        void reduce();
+
     protected:
         friend class Actor;
         friend class Minimap;
diff --git a/src/resources/image.cpp b/src/resources/image.cpp
index 2d3676304..fdcf210c3 100644
--- a/src/resources/image.cpp
+++ b/src/resources/image.cpp
@@ -53,7 +53,8 @@ Image::Image(SDL_Surface *image, bool hasAlphaChannel, Uint8 *alphaChannel):
     mAlpha(1.0f),
     mHasAlphaChannel(hasAlphaChannel),
     mSDLSurface(image),
-    mAlphaChannel(alphaChannel)
+    mAlphaChannel(alphaChannel),
+    mIsAlphaVisible(hasAlphaChannel)
 {
 #ifdef USE_OPENGL
     mGLImage = 0;
@@ -88,6 +89,7 @@ Image::Image(GLuint glimage, int width, int height,
     mSDLSurface(0),
     mAlphaChannel(0),
     mUseAlphaCache(false),
+    mIsAlphaVisible(true),
     mGLImage(glimage),
     mTexWidth(texWidth),
     mTexHeight(texHeight)
@@ -792,11 +794,13 @@ SubImage::SubImage(Image *parent, SDL_Surface *image,
         mParent->incRef();
         mParent->SDLTerminateAlphaCache();
         mHasAlphaChannel = mParent->hasAlphaChannel();
+        mIsAlphaVisible = mHasAlphaChannel;
         mAlphaChannel = mParent->SDLgetAlphaChannel();
     }
     else
     {
         mHasAlphaChannel = false;
+        mIsAlphaVisible = false;
         mAlphaChannel = 0;
     }
 
@@ -805,6 +809,10 @@ SubImage::SubImage(Image *parent, SDL_Surface *image,
     mBounds.y = static_cast<short>(y);
     mBounds.w = static_cast<Uint16>(width);
     mBounds.h = static_cast<Uint16>(height);
+    mInternalBounds.x = mParent->mBounds.x;
+    mInternalBounds.y = mParent->mBounds.y;
+    mInternalBounds.w = mParent->mBounds.w;
+    mInternalBounds.h = mParent->mBounds.h;
     mUseAlphaCache = false;
 }
 
@@ -823,6 +831,11 @@ SubImage::SubImage(Image *parent, GLuint image,
     mBounds.y = static_cast<short>(y);
     mBounds.w = static_cast<Uint16>(width);
     mBounds.h = static_cast<Uint16>(height);
+    mInternalBounds.x = mParent->mBounds.x;
+    mInternalBounds.y = mParent->mBounds.y;
+    mInternalBounds.w = mParent->mBounds.w;
+    mInternalBounds.h = mParent->mBounds.h;
+    mIsAlphaVisible = mHasAlphaChannel;
 }
 #endif
 
diff --git a/src/resources/image.h b/src/resources/image.h
index 72b85cc1e..ee341af75 100644
--- a/src/resources/image.h
+++ b/src/resources/image.h
@@ -208,6 +208,15 @@ class Image : public Resource
         int getTextureHeight() const
         { return mTexHeight; }
 
+        bool isHasAlphaChannel()
+        { return mHasAlphaChannel; }
+
+        bool isAlphaVisible()
+        { return mIsAlphaVisible; }
+
+        void setAlphaVisible(bool b)
+        { mIsAlphaVisible = b; }
+
         static int getTextureType()
         { return mTextureType; }
 
@@ -247,6 +256,7 @@ class Image : public Resource
         std::map<float, SDL_Surface*> mAlphaCache;
 
         bool mUseAlphaCache;
+        bool mIsAlphaVisible;
 
         static bool mEnableAlphaCache;
         static bool mEnableAlpha;
@@ -305,6 +315,8 @@ class SubImage : public Image
          */
         Image *getSubImage(int x, int y, int width, int height);
 
+        SDL_Rect mInternalBounds;
+
     private:
         Image *mParent;
 };
diff --git a/src/resources/mapreader.cpp b/src/resources/mapreader.cpp
index 098af0909..35267533f 100644
--- a/src/resources/mapreader.cpp
+++ b/src/resources/mapreader.cpp
@@ -376,6 +376,7 @@ Map *MapReader::readMap(xmlNodePtr node, const std::string &path)
     map->initializeAmbientLayers();
     map->clearIndexedTilesets();
     map->setActorsFix(0, atoi(map->getProperty("actorsfix").c_str()));
+    map->reduce();
     return map;
 }