2
\$\begingroup\$

Below is my attempt at bitmap in bitmap searching using 1bpp bitmaps. Any suggestions on how I can reduce complexity and improve speed? Any comment is appreciated.

using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using System.Linq;
using System.Collections.Generic;
using System.Windows.Forms;

namespace AutoBot
{
    public partial class ActiveScreenMatch
    {
        public static bool ScreenMatch(Rectangle rect = default, string path = "")
        {
            if (rect == default && string.IsNullOrEmpty(path))
            {
                return false;
            }
            Bitmap bw;
            if (rect == default)
            {
                bw = new Bitmap(path);
                bw = bw.Clone(new Rectangle(new Point(0, 0), new Size(bw.Width, bw.Height)), PixelFormat.Format1bppIndexed);
            }
            else
            {
                bw = GetBlackWhiteAt(rect.Location, rect.Size);
            }
            /// Initialize Search image array.
            bool[][] ba1;

            using (bw)
            {
                ba1 = GetBooleanArray(bw).ToArray();
            }
            int SkippedBlackLines = 0;
            foreach (bool[] bl1 in ba1)
            {
                if (bl1.Any(x => x))
                {
                    break;
                }
                else
                {
                    SkippedBlackLines++;
                }
            }
            bool[][] ba2;
            using (Bitmap SearchWindow = GetBlackWhiteAt(new Point(0, 0), new Size(Screen.PrimaryScreen.Bounds.Width, Screen.PrimaryScreen.Bounds.Height)))
            {
                ba2 = GetBooleanArray(SearchWindow).ToArray();
            }
            var Base = ba1.Skip(SkippedBlackLines);
            for (int i = ba2.GetUpperBound(0); i > 0; i--)
            {
                if (SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) != -1)
                {
                    if (Base.Count() == 1)
                    {
                        MoveTo(
                                SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) + (ba1[0].Length / 2),
                                i + (ba1.GetUpperBound(0) / 2));
                        return true;
                    }
                    else
                    {
                        Base = Base.Take(Base.Count() - 1);
                    }
                }
            }
                return false;
        }

        private static IEnumerable<bool[]> GetBooleanArray(Bitmap bitmap)
        {
            BitmapData data = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);

            for (int y = 0; y <= bitmap.Height - 1; y++)
            {
                var ba2 = new bool[bitmap.Width];
                for (int x = 0; x <= bitmap.Width - 1; x++)
                {
                    if (GetIndexedPixel(x, y, data) > 0)
                    {
                        ba2[x] = true;
                    }
                }
                yield return ba2;
            }
            bitmap.UnlockBits(data);
        }

        private static int GetIndexedPixel(int x, int y, BitmapData data)
        {
            var index = (y * data.Stride) + (x >> 3);
            var mask = (byte)(0x80 >> (x & 0x7));
            byte ret = Marshal.ReadByte(data.Scan0, index);
            ret &= mask;
            return ret;
        }

        private static int SubListIndex(IEnumerable<bool> list, int start, IEnumerable<bool> sublist)
        {
            for (int listIndex = start; listIndex < list.Count() - sublist.Count() + 1; listIndex++)
            {
                int count = 0;
                while (count < sublist.Count() && sublist.ElementAt(count).Equals(list.ElementAt(listIndex + count)))
                    count++;
                if (count == sublist.Count())
                    return listIndex;
            }
            return -1;
        }

        private static Bitmap GetBlackWhiteAt(Point On, Size PickArea)
        {
            // Create a new bitmap.
            using (Bitmap bmp = PrintWindow())
                return bmp.Clone(new Rectangle(On, PickArea), PixelFormat.Format1bppIndexed);
        }

        private static void PrintScreen()
        {
            keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_EXTENDEDKEY, 0);
            keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_KEYUP, 0);
        }

        private static Bitmap PrintWindow()
        {
            PrintScreen();
            Application.DoEvents();
            if (Clipboard.ContainsImage())
            {
                using (Image img = Clipboard.GetImage())
                {
                    if (img != null)
                    {
                        return new Bitmap(img);
                    }
                }
            }
            return PrintWindow();
        }
    }

    public static class VKey
    {
        public readonly static byte VK_BACK = 0x08;
        public readonly static byte VK_TAB = 0x09;
        public readonly static byte VK_RETURN = 0x0D;
        public readonly static byte VK_SHIFT = 0x10;
        public readonly static byte VK_CONTROL = 0x11;
        public readonly static byte VK_MENU = 0x12;
        public readonly static byte VK_PAUSE = 0x13;
        public readonly static byte VK_CAPITAL = 0x14;
        public readonly static byte VK_ESCAPE = 0x1B;
        public readonly static byte VK_SPACE = 0x20;
        public readonly static byte VK_END = 0x23;
        public readonly static byte VK_HOME = 0x24;
        public readonly static byte VK_LEFT = 0x25;
        public readonly static byte VK_UP = 0x26;
        public readonly static byte VK_RIGHT = 0x27;
        public readonly static byte VK_DOWN = 0x28;
        public readonly static byte VK_PRINT = 0x2A;
        public readonly static byte VK_SNAPSHOT = 0x2C;
        public readonly static byte VK_INSERT = 0x2D;
        public readonly static byte VK_DELETE = 0x2E;
        public readonly static byte VK_LWIN = 0x5B;
        public readonly static byte VK_RWIN = 0x5C;
        public readonly static byte VK_NUMPAD0 = 0x60;
        public readonly static byte VK_NUMPAD1 = 0x61;
        public readonly static byte VK_NUMPAD2 = 0x62;
        public readonly static byte VK_NUMPAD3 = 0x63;
        public readonly static byte VK_NUMPAD4 = 0x64;
        public readonly static byte VK_NUMPAD5 = 0x65;
        public readonly static byte VK_NUMPAD6 = 0x66;
        public readonly static byte VK_NUMPAD7 = 0x67;
        public readonly static byte VK_NUMPAD8 = 0x68;
        public readonly static byte VK_NUMPAD9 = 0x69;
        public readonly static byte VK_MULTIPLY = 0x6A;
        public readonly static byte VK_ADD = 0x6B;
        public readonly static byte VK_SEPARATOR = 0x6C;
        public readonly static byte VK_SUBTRACT = 0x6D;
        public readonly static byte VK_DECIMAL = 0x6E;
        public readonly static byte VK_DIVIDE = 0x6F;
        public readonly static byte VK_F1 = 0x70;
        public readonly static byte VK_F2 = 0x71;
        public readonly static byte VK_F3 = 0x72;
        public readonly static byte VK_F4 = 0x73;
        public readonly static byte VK_F5 = 0x74;
        public readonly static byte VK_F6 = 0x75;
        public readonly static byte VK_F7 = 0x76;
        public readonly static byte VK_F8 = 0x77;
        public readonly static byte VK_F9 = 0x78;
        public readonly static byte VK_F10 = 0x79;
        public readonly static byte VK_F11 = 0x7A;
        public readonly static byte VK_F12 = 0x7B;
        public readonly static byte VK_NUMLOCK = 0x90;
        public readonly static byte VK_SCROLL = 0x91;
        public readonly static byte VK_LSHIFT = 0xA0;
        public readonly static byte VK_RSHIFT = 0xA1;
        public readonly static byte VK_LCONTROL = 0xA2;
        public readonly static byte VK_RCONTROL = 0xA3;
        public readonly static byte VK_LMENU = 0xA4;
        public readonly static byte VK_RMENU = 0xA5;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Partitioning to me is bad in this case, as it gives way to a match on the boundary of the split leading to a 'non-completable' search pattern. This is unacceptable to me, so rather than fail with one. How do I Concurrently run the Left half, Right half, the top half, and bottom half and whole and cancel them all when one is successful? \$\endgroup\$
    – BanMe
    Feb 3, 2020 at 1:45
  • \$\begingroup\$ Instead of doing the detection in parallel, I redid that portion to simply check the whole screen. \$\endgroup\$
    – BanMe
    Feb 3, 2020 at 18:45

2 Answers 2

1
\$\begingroup\$

Ok so let's focus on this part the actual search routine.

        for (int i = ba2.GetUpperBound(0); i > 0; i--)
        {
            if (SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) != -1)
            {
                if (Base.Count() == 1)
                {
                    MoveTo(
                            SubListIndex(ba2[i].AsEnumerable(), 0, Base.LastOrDefault()) + (ba1[0].Length / 2),
                            i + (ba1.GetUpperBound(0) / 2));
                    return true;
                }
                else
                {
                    Base = Base.Take(Base.Count() - 1);
                }
            }
        }
        return false;

This routine resizes the search Image on each successful pass instead of iterating it

The amount of checking when finding a potential match can be reduced to 3 checks.

        var m = SearchImage.Length - 1;
        for (int i = SearchArea.GetUpperBound(0); i > 0; i--)
        {
            if (SubListIndex(SearchArea[i].AsEnumerable(), 0, SearchImage[m]) != -1)
            {
                int x;
                if (SubListIndex(SearchArea[i - m].AsEnumerable(), 0, SearchImage[0]) != -1)
                {
                    if (SubListIndex(SearchArea[i - (m / 2)].AsEnumerable(), 0, SearchImage[m / 2]) != -1)
                    {
                        x = SubListIndex(SearchArea[i - m].AsEnumerable(), 0, SearchImage[0]);
                    }
                    else
                    {
                        continue;
                    }
                }
                else
                {
                    continue;
                }

                if (x != -1)
                {
                    return new Point(x + (SearchImage.Length / 2), (SearchImage.Length / 2) + i);
                }
            }
        }
        return default;

Linq version, reduces Search Area, by directly checking Target sequence in Search Area Instead of using SubListIndex.

        var m = SearchImage.Length - 1;
        return (from line in Enumerable.Range(0, SourceArea.GetUpperBound(0))
                                        let Index = SubListIndex(SourceArea[line].AsEnumerable(), 0, TargetArea[m])
                                        where Index != -1
                                        let Test = SourceArea[line - m].AsEnumerable().Skip(Index).SequenceEqual(TargetArea[0])
                                        let Test2 = SourceArea[line - (m / 2)].AsEnumerable().Skip(Index).SequenceEqual(TargetArea[m / 2])
                                        where Test && Test2
                                        select new Point(Index + (TargetArea[0].Length / 2), line + (TargetArea.Length / 2))).FirstOrDefault();
\$\endgroup\$
0
\$\begingroup\$

That last linq routine was half baked. Moving to a more Drier Approach for bitmap handling.

First here is the new Search Routine

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Windows.Forms;

namespace AutoBot
{
    public partial class ActiveScreenMatch
    {
        public static Point ScreenMatch(BitData Target = default)
        {
            if (Target == default)
            {
                return default;
            }
            var TargetArea = Target.GetBitData();

            int SkippedBlackLines = 0;
            foreach (bool[] bl1 in TargetArea)
            {
                if (bl1.Any(x => x))
                {
                    break;
                }
                else
                {
                    SkippedBlackLines++;
                }
            }
            TargetArea = TargetArea.Skip(SkippedBlackLines).ToArray();

            Bitmap SourceImage = GetBlackWhiteAt(new Point(0, 0), new Size(Screen.PrimaryScreen.Bounds.Width, Screen.PrimaryScreen.Bounds.Height));

            BitData SourceData = new BitData(dataMap: SourceImage);

            var SourceArea = SourceData.GetBitData();

            SourceImage.Dispose();

            var m = TargetArea.Count() -1;

            return (from line in Enumerable.Range(0, SourceArea.Count() - 1)
                    let Index = SubListIndex(SourceArea.ElementAt(line), 0, TargetArea.ElementAt(0))
                    where Index != -1 && Index != 0 && line > m
                    let SourceLast = SourceArea.ElementAt(line + m).Skip(Index).Take(TargetArea.ElementAt(0).Length).ToArray()
                    let TargetLast = TargetArea.ElementAt(m).ToArray()
                    let SourceMid = SourceArea.ElementAt(line + (m/2)).Skip(Index).Take(TargetArea.ElementAt(0).Length).ToArray()
                    let TargetMid = TargetArea.ElementAt(m/2).ToArray()
                    where TargetLast.SequenceEqual(SourceLast) && TargetMid.SequenceEqual(SourceMid)
                    select new Point(Index + (TargetArea.ElementAt(0).Length / 2), line + (TargetArea.ElementAt(0).Length / 2))).FirstOrDefault();
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int SubListIndex(IEnumerable<bool> list, int start, IEnumerable<bool> sublist)
        {
            for (int listIndex = start; listIndex < list.Count() - sublist.Count() + 1; listIndex++)
            {
                int count = 0;
                while (count < sublist.Count() && sublist.ElementAt(count).Equals(list.ElementAt(listIndex + count)))
                    count++;
                if (count == sublist.Count())
                    return listIndex;
            }
            return -1;
        }

        public static Bitmap GetBlackWhiteAt(Point On, Size PickArea)
        {
            // Create a new bitmap.
            using (Bitmap bmp = PrintWindow())
                return bmp.Clone(new Rectangle(On, PickArea), PixelFormat.Format1bppIndexed);
        }

        private static void PrintScreen()
        {
            keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_EXTENDEDKEY, 0);
            keybd_event(VKey.VK_SNAPSHOT, 0, KEYEVENTF_KEYUP, 0);
        }

        private static Bitmap PrintWindow()
        {
            PrintScreen();
            Application.DoEvents();
            if (Clipboard.ContainsImage())
            {
                using (Image img = Clipboard.GetImage())
                {
                    if (img != null)
                    {
                        img.Save("Output.PNG", ImageFormat.Png);
                        return new Bitmap(img);
                    }
                }
            }
            return PrintWindow();
        }
    }

    public static class VKey
    {
        public readonly static byte VK_BACK = 0x08;
        public readonly static byte VK_TAB = 0x09;
        public readonly static byte VK_RETURN = 0x0D;
        public readonly static byte VK_SHIFT = 0x10;
        public readonly static byte VK_CONTROL = 0x11;
        public readonly static byte VK_MENU = 0x12;
        public readonly static byte VK_PAUSE = 0x13;
        public readonly static byte VK_CAPITAL = 0x14;
        public readonly static byte VK_ESCAPE = 0x1B;
        public readonly static byte VK_SPACE = 0x20;
        public readonly static byte VK_END = 0x23;
        public readonly static byte VK_HOME = 0x24;
        public readonly static byte VK_LEFT = 0x25;
        public readonly static byte VK_UP = 0x26;
        public readonly static byte VK_RIGHT = 0x27;
        public readonly static byte VK_DOWN = 0x28;
        public readonly static byte VK_PRINT = 0x2A;
        public readonly static byte VK_SNAPSHOT = 0x2C;
        public readonly static byte VK_INSERT = 0x2D;
        public readonly static byte VK_DELETE = 0x2E;
        public readonly static byte VK_LWIN = 0x5B;
        public readonly static byte VK_RWIN = 0x5C;
        public readonly static byte VK_NUMPAD0 = 0x60;
        public readonly static byte VK_NUMPAD1 = 0x61;
        public readonly static byte VK_NUMPAD2 = 0x62;
        public readonly static byte VK_NUMPAD3 = 0x63;
        public readonly static byte VK_NUMPAD4 = 0x64;
        public readonly static byte VK_NUMPAD5 = 0x65;
        public readonly static byte VK_NUMPAD6 = 0x66;
        public readonly static byte VK_NUMPAD7 = 0x67;
        public readonly static byte VK_NUMPAD8 = 0x68;
        public readonly static byte VK_NUMPAD9 = 0x69;
        public readonly static byte VK_MULTIPLY = 0x6A;
        public readonly static byte VK_ADD = 0x6B;
        public readonly static byte VK_SEPARATOR = 0x6C;
        public readonly static byte VK_SUBTRACT = 0x6D;
        public readonly static byte VK_DECIMAL = 0x6E;
        public readonly static byte VK_DIVIDE = 0x6F;
        public readonly static byte VK_F1 = 0x70;
        public readonly static byte VK_F2 = 0x71;
        public readonly static byte VK_F3 = 0x72;
        public readonly static byte VK_F4 = 0x73;
        public readonly static byte VK_F5 = 0x74;
        public readonly static byte VK_F6 = 0x75;
        public readonly static byte VK_F7 = 0x76;
        public readonly static byte VK_F8 = 0x77;
        public readonly static byte VK_F9 = 0x78;
        public readonly static byte VK_F10 = 0x79;
        public readonly static byte VK_F11 = 0x7A;
        public readonly static byte VK_F12 = 0x7B;
        public readonly static byte VK_NUMLOCK = 0x90;
        public readonly static byte VK_SCROLL = 0x91;
        public readonly static byte VK_LSHIFT = 0xA0;
        public readonly static byte VK_RSHIFT = 0xA1;
        public readonly static byte VK_LCONTROL = 0xA2;
        public readonly static byte VK_RCONTROL = 0xA3;
        public readonly static byte VK_LMENU = 0xA4;
        public readonly static byte VK_RMENU = 0xA5;
    }
}

And the BitData Class

using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

namespace AutoBot
{
    public class BitData
    {
        private Rectangle DataRect { get; }
        private string DataPath { get; }
        private Stream DataStream { get; }
        private Image DataImage { get; }
        private Bitmap DataMap { get; }

        public IEnumerable<bool[]> GetBitData()
        {
            if (DataMap == default && DataRect == default && string.IsNullOrEmpty(DataPath) && DataStream == default && DataImage == default)
            {
                return default;
            }

            Bitmap TargetImage;
            if (DataMap != default)
            {
                TargetImage = DataMap;
            }
            else if (DataRect != default)
            {
                TargetImage = ActiveScreenMatch.GetBlackWhiteAt(DataRect.Location, DataRect.Size);
            }
            else if (!string.IsNullOrEmpty(DataPath))
            {
                if (File.Exists(DataPath))
                {
                    using (var Image = new Bitmap(DataPath))
                        TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
                }
                else
                {
                    return default;
                }
            }
            else if (DataStream != default)
            {
                using (var Image = new Bitmap(DataStream))
                    TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
            }
            else
            {
                using (var Image = new Bitmap(DataImage))
                    TargetImage = Image.Clone(new Rectangle(new Point(0, 0), new Size(Image.Width, Image.Height)), PixelFormat.Format1bppIndexed);
            }

            var Array = GetBooleanArray(TargetImage);

            TargetImage.Dispose();

            return Array;
        }

        public BitData(Rectangle dataRect = default, string dataPath = default, Stream dataStream = default, Image dataImage = default, Bitmap dataMap = default)
        {
            DataRect = dataRect;
            DataPath = dataPath;
            DataStream = dataStream;
            DataImage = dataImage;
            DataMap = dataMap;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static IEnumerable<bool[]> GetBooleanArray(Bitmap bitmap)
        {
            BitmapData data = bitmap.LockBits(new Rectangle(0, 0, bitmap.Width, bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format1bppIndexed);
            bool[][] ba2 = new bool[bitmap.Height][];
            for (int y = 0; y <= bitmap.Height - 1; y++)
            {
                ba2[y] = new bool[bitmap.Width];
                for (int x = 0; x <= bitmap.Width - 1; x++)
                {
                    if (GetIndexedPixel(x, y, data) > 0)
                    {
                        ba2[y][x] = true;
                    }
                }
            }

            bitmap.UnlockBits(data);
            return ba2;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int GetIndexedPixel(int x, int y, BitmapData data)
        {
            var index = (y * data.Stride) + (x >> 3);
            var mask = (byte)(0x80 >> (x & 0x7));
            byte ret = Marshal.ReadByte(data.Scan0, index);
            ret &= mask;
            return ret;
        }
    }
}

I think this version is much improved and would greatly appreciate another's eye.

\$\endgroup\$
1
  • \$\begingroup\$ I can optimize it even further, With BitVector32 for size, and doing a competition style search where one thread searches top-down, and another thread searches down up to ensure speed, use WaitHanlde WaitAny(). I would like to turn the source search area into a plane, and my target into a 4x4 matrix and subtract from the plane, but I think it would be hard to ensure it was put together in the same way that results in the same matrix being created in the plane. I am not sure if I can do that, so more research is needed from me. \$\endgroup\$
    – BanMe
    Feb 7, 2020 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.