(kein Titel)

AABB Collision Detection with Intersection Points (Incl. Rotation)

    public struct Line
    {
        public Vector2 a;
        public Vector2 b;

        public Line(float x1, float y1,
            float x2, float y2)
        {
            a = new Vector2(x1, y1);
            b = new Vector2(x2, y2);
        }

        public void Rotate(float rad, Vector2 center)
        {
            Rotate(rad, ref a, center);
            Rotate(rad, ref b, center);
        }

        private void Rotate(float rad, ref Vector2 point, Vector2 center)
        {
            point = Vector2.Transform(point - center, Matrix.CreateRotationZ(rad)) + center;
        }

        public bool Intersect(Line line, out Vector2? intersectionPoint)
        {
            intersectionPoint = null;

            float a1 = b.Y - a.Y;
            float b1 = a.X - b.X;
            float c1 = a1 * a.X + b1 * a.Y;

            float a2 = line.b.Y - line.a.Y;
            float b2 = line.a.X - line.b.X;
            float c2 = a2 * line.a.X + b2 * line.a.Y;

            //If the lines are parallel, no collision possible.
            float det = a1 * b2 - a2 * b1;
            if (det == 0) return false;

            float x = (b2 * c1 - b1 * c2) / det;
            float y = (a1 * c2 - a2 * c1) / det;

            if (OnLine(this, x, y) && OnLine(line, x, y))
            {
                intersectionPoint = new Vector2(x, y);
                return true;
            }

            return false;
        }

        public static bool OnLine(Line line, float x, float y)
        {
            return Math.Min(line.a.X, line.b.X) <= x &&
                x <= Math.Max(line.a.X, line.b.X) &&
                Math.Min(line.a.Y, line.b.Y) <= y &&
                y <= Math.Max(line.a.Y, line.b.Y);
        }
    }

public struct Line

{

public Vector2 a;

public Vector2 b;

public Line(float x1, float y1,

float x2, float y2)

{

a = new Vector2(x1, y1);

b = new Vector2(x2, y2);

}

public void Rotate(float rad, Vector2 center)

{

Rotate(rad, ref a, center);

Rotate(rad, ref b, center);

}

private void Rotate(float rad, ref Vector2 point, Vector2 center)

{

point = Vector2.Transform(point - center, Matrix.CreateRotationZ(rad)) + center;

}

public bool Intersect(Line line, out Vector2? intersectionPoint)

{

intersectionPoint = null;

float a1 = b.Y - a.Y;

float b1 = a.X - b.X;

float c1 = a1 * a.X + b1 * a.Y;

float a2 = line.b.Y - line.a.Y;

float b2 = line.a.X - line.b.X;

float c2 = a2 * line.a.X + b2 * line.a.Y;

//If the lines are parallel, no collision possible.

float det = a1 * b2 - a2 * b1;

if (det == 0) return false;

float x = (b2 * c1 - b1 * c2) / det;

float y = (a1 * c2 - a2 * c1) / det;

if (OnLine(this, x, y) && OnLine(line, x, y))

{

intersectionPoint = new Vector2(x, y);

return true;

}

return false;

}

public static bool OnLine(Line line, float x, float y)

{

return Math.Min(line.a.X, line.b.X) <= x &&

x <= Math.Max(line.a.X, line.b.X) &&

Math.Min(line.a.Y, line.b.Y) <= y &&

y <= Math.Max(line.a.Y, line.b.Y);

}

    public struct SRectangle
    {
        public Line left;
        public Line top;
        public Line right;
        public Line bottom;

        public void Rotate(float rad, Vector2 center)
        {
            left.Rotate(rad, center);
            top.Rotate(rad, center);
            right.Rotate(rad, center);
            bottom.Rotate(rad, center);
        }

        public static SRectangle FromRectangle(Rectangle rectangle, Vector2 origin, float rotation)
        {
            Line left = new Line(rectangle.X, rectangle.Y, rectangle.X, rectangle.Y + rectangle.Height);
            Line top = new Line(rectangle.X, rectangle.Y, rectangle.X + rectangle.Width, rectangle.Y);
            Line right = new Line(rectangle.X + rectangle.Width, rectangle.Y, rectangle.X + rectangle.Width, rectangle.Y + rectangle.Height);
            Line bottom = new Line(rectangle.X, rectangle.Y + rectangle.Height, rectangle.X + rectangle.Width, rectangle.Y + rectangle.Height);

            left.a.X -= origin.X;
            left.a.Y -= origin.Y;
            left.b.X -= origin.X;
            left.b.Y -= origin.Y;
            top.a.X -= origin.X;
            top.a.Y -= origin.Y;
            top.b.X -= origin.X;
            top.b.Y -= origin.Y;
            right.a.X -= origin.X;
            right.a.Y -= origin.Y;
            right.b.X -= origin.X;
            right.b.Y -= origin.Y;
            bottom.a.X -= origin.X;
            bottom.a.Y -= origin.Y;
            bottom.b.X -= origin.X;
            bottom.b.Y -= origin.Y;

            origin.X += rectangle.X - rectangle.Width / 2;
            origin.Y += rectangle.Y - rectangle.Height / 2;

            left.Rotate(rotation, origin);
            right.Rotate(rotation, origin);
            top.Rotate(rotation, origin);
            bottom.Rotate(rotation, origin);

            return new SRectangle()
            {
                left = left,
                right = right,
                top = top,
                bottom = bottom
            };
        }
    }

public struct SRectangle

{

public Line left;

public Line top;

public Line right;

public Line bottom;

public void Rotate(float rad, Vector2 center)

{

left.Rotate(rad, center);

top.Rotate(rad, center);

right.Rotate(rad, center);

bottom.Rotate(rad, center);

}

public static SRectangle FromRectangle(Rectangle rectangle, Vector2 origin, float rotation)

{

Line left = new Line(rectangle.X, rectangle.Y, rectangle.X, rectangle.Y + rectangle.Height);

Line top = new Line(rectangle.X, rectangle.Y, rectangle.X + rectangle.Width, rectangle.Y);

Line right = new Line(rectangle.X + rectangle.Width, rectangle.Y, rectangle.X + rectangle.Width, rectangle.Y + rectangle.Height);

Line bottom = new Line(rectangle.X, rectangle.Y + rectangle.Height, rectangle.X + rectangle.Width, rectangle.Y + rectangle.Height);

left.a.X -= origin.X;

left.a.Y -= origin.Y;

left.b.X -= origin.X;

left.b.Y -= origin.Y;

top.a.X -= origin.X;

top.a.Y -= origin.Y;

top.b.X -= origin.X;

top.b.Y -= origin.Y;

right.a.X -= origin.X;

right.a.Y -= origin.Y;

right.b.X -= origin.X;

right.b.Y -= origin.Y;

bottom.a.X -= origin.X;

bottom.a.Y -= origin.Y;

bottom.b.X -= origin.X;

bottom.b.Y -= origin.Y;

origin.X += rectangle.X - rectangle.Width / 2;

origin.Y += rectangle.Y - rectangle.Height / 2;

left.Rotate(rotation, origin);

right.Rotate(rotation, origin);

top.Rotate(rotation, origin);

bottom.Rotate(rotation, origin);

return new SRectangle()

{

left = left,

right = right,

top = top,

bottom = bottom

};

}

        public static bool AABB_AABB(SmartRectangle x, SmartRectangle y, out Vector2[] collisionPoints)
        {
            List<Vector2> cp = new List<Vector2>();

            /* Left against y */
            if (x.left.Intersect(y.left, out Vector2? llcp)) cp.Add(llcp.Value);
            if (x.left.Intersect(y.top, out Vector2? ltcp)) cp.Add(ltcp.Value);
            if (x.left.Intersect(y.right, out Vector2? lrcp)) cp.Add(lrcp.Value);
            if (x.left.Intersect(y.bottom, out Vector2? lbcp)) cp.Add(lbcp.Value);
            /* Top against y */
            if (x.top.Intersect(y.left, out Vector2? tlcp)) cp.Add(tlcp.Value);
            if (x.top.Intersect(y.top, out Vector2? ttcp)) cp.Add(ttcp.Value);
            if (x.top.Intersect(y.right, out Vector2? trcp)) cp.Add(trcp.Value);
            if (x.top.Intersect(y.bottom, out Vector2? tbcp)) cp.Add(tbcp.Value);
            /* Right against y */
            if (x.right.Intersect(y.left, out Vector2? rlcp)) cp.Add(rlcp.Value);
            if (x.right.Intersect(y.top, out Vector2? rtcp)) cp.Add(rtcp.Value);
            if (x.right.Intersect(y.right, out Vector2? rrcp)) cp.Add(rrcp.Value);
            if (x.right.Intersect(y.bottom, out Vector2? rbcp)) cp.Add(rbcp.Value);
            /* Bottom against y */
            if (x.bottom.Intersect(y.left, out Vector2? blcp)) cp.Add(blcp.Value);
            if (x.bottom.Intersect(y.top, out Vector2? btcp)) cp.Add(btcp.Value);
            if (x.bottom.Intersect(y.right, out Vector2? brcp)) cp.Add(brcp.Value);
            if (x.bottom.Intersect(y.bottom, out Vector2? bbcp)) cp.Add(bbcp.Value);

            collisionPoints = cp.ToArray();
            return cp.Count > 0;
        }

public static bool AABB_AABB(SmartRectangle x, SmartRectangle y, out Vector2[] collisionPoints)

{

List<Vector2> cp = new List<Vector2>();

/* Left against y */

if (x.left.Intersect(y.left, out Vector2? llcp)) cp.Add(llcp.Value);

if (x.left.Intersect(y.top, out Vector2? ltcp)) cp.Add(ltcp.Value);

if (x.left.Intersect(y.right, out Vector2? lrcp)) cp.Add(lrcp.Value);

if (x.left.Intersect(y.bottom, out Vector2? lbcp)) cp.Add(lbcp.Value);

/* Top against y */

if (x.top.Intersect(y.left, out Vector2? tlcp)) cp.Add(tlcp.Value);

if (x.top.Intersect(y.top, out Vector2? ttcp)) cp.Add(ttcp.Value);

if (x.top.Intersect(y.right, out Vector2? trcp)) cp.Add(trcp.Value);

if (x.top.Intersect(y.bottom, out Vector2? tbcp)) cp.Add(tbcp.Value);

/* Right against y */

if (x.right.Intersect(y.left, out Vector2? rlcp)) cp.Add(rlcp.Value);

if (x.right.Intersect(y.top, out Vector2? rtcp)) cp.Add(rtcp.Value);

if (x.right.Intersect(y.right, out Vector2? rrcp)) cp.Add(rrcp.Value);

if (x.right.Intersect(y.bottom, out Vector2? rbcp)) cp.Add(rbcp.Value);

/* Bottom against y */

if (x.bottom.Intersect(y.left, out Vector2? blcp)) cp.Add(blcp.Value);

if (x.bottom.Intersect(y.top, out Vector2? btcp)) cp.Add(btcp.Value);

if (x.bottom.Intersect(y.right, out Vector2? brcp)) cp.Add(brcp.Value);

if (x.bottom.Intersect(y.bottom, out Vector2? bbcp)) cp.Add(bbcp.Value);

collisionPoints = cp.ToArray();

return cp.Count > 0;

}

Supported Frameworks

Full Functional Range Support .NET Framework >= 4.5 No Bluetooth Support .NET Core >= 2.0 Mono >= 5.4 Xamarin.iOS >= 10.14 Xamarin.MAC >= 3.8 Xamarin.Android >= 8.0 UWP >= 10.0.16299 .NET Standard 2.0

Switching to Linux – Roadmap

Since Window 8.0 has been released I thought about switching to Linux due many different reasons, whichever I won’t cover in this article. However, the idea to try Linux was always present and the desire to do so, grew from day to day. Long story short, due Driver problems Nearly none-existing games Lacking productivity tools Missing… Lesen Sie den ganzen Artikel

WPF ObservableCollection – Add millions of data within milliseconds

- Thomas Christof
- 26. März 2017
- März 26th, 2017
- Hinterlasse einen Kommentar
- Blog
- ObservableCollection Performance Snippet WPF

Adding huge amount of Data to an ObservableCollection can cause GUI freezes. Even if operating on another thread, the process of adding items is pretty slow. But why?

WPF Scrollable + Zoomable + Dragable Control

Unluckily there is no standard control to zoom, drag and scroll your content. My implementation is based on following tutorial. With this implementation you are able to zoom, drag and scroll arbitrary controls. Showcase ScrollDragZoomControl.xaml

<UserControl x:Class="MinimalMonitoringClient.Controls.ScrollDragZoomControl"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             Background="Transparent">

    <UserControl.Template>
        <ControlTemplate TargetType="UserControl">
            <ScrollViewer x:Name="scrollViewer"
                  Loaded="scrollViewer_Loaded"
                  HorizontalScrollBarVisibility="Visible"
                  VerticalScrollBarVisibility="Visible">

                <Grid Name="grid" RenderTransformOrigin="0.5,0.5">
                    <Grid.LayoutTransform>
                        <TransformGroup>
                            <ScaleTransform x:Name="scaleTransform" />
                        </TransformGroup>
                    </Grid.LayoutTransform>
                    <Viewbox>
                        <!-- Present the actual stuff the user wants to display -->
                        <ContentPresenter />
                    </Viewbox>
                </Grid>
            </ScrollViewer>
        </ControlTemplate>
    </UserControl.Template>
</UserControl>

<UserControl x:Class="MinimalMonitoringClient.Controls.ScrollDragZoomControl"

xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

Background="Transparent">

<UserControl.Template>

<ScrollViewer x:Name="scrollViewer"

Loaded="scrollViewer_Loaded"

HorizontalScrollBarVisibility="Visible"

VerticalScrollBarVisibility="Visible">

<Grid.LayoutTransform>

</TransformGroup>

</Grid.LayoutTransform>

</Viewbox>

</Grid>

</ScrollViewer>

</ControlTemplate>

</UserControl.Template>

</UserControl>

ScrollDragZoomControl.xaml.cs

using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.Windows.Media;

namespace NAMESPACE
{
    /// <summary>
    /// Interaktionslogik für ScrollDragZoomControl.xaml
    /// </summary>
    public partial class ScrollDragZoomControl : UserControl
    {
        private int zoomLevel = 1;

        private ScaleTransform scaleTransform;
        private ScrollViewer scrollViewer;
        private Grid grid;

        Point? lastCenterPositionOnTarget;
        Point? lastMousePositionOnTarget;
        Point? lastDragPoint;

        public ScrollDragZoomControl()
        {
            InitializeComponent();
        }

        private void scrollViewer_Loaded(object sender, RoutedEventArgs e)
        {
            scaleTransform = (ScaleTransform)Template.FindName("scaleTransform", this);
            scrollViewer = (ScrollViewer)Template.FindName("scrollViewer", this);
            grid = (Grid)Template.FindName("grid", this);

            scrollViewer.ScrollChanged += OnScrollViewerScrollChanged;
            scrollViewer.MouseLeftButtonUp += OnMouseLeftButtonUp;
            scrollViewer.PreviewMouseLeftButtonUp += OnMouseLeftButtonUp;
            scrollViewer.PreviewMouseWheel += OnPreviewMouseWheel;
            scrollViewer.PreviewMouseLeftButtonDown += OnMouseLeftButtonDown;
            scrollViewer.MouseMove += OnMouseMove;
        }

        void OnMouseMove(object sender, MouseEventArgs e)
        {
            if (lastDragPoint.HasValue)
            {
                Point posNow = e.GetPosition(scrollViewer);

                double dX = posNow.X - lastDragPoint.Value.X;
                double dY = posNow.Y - lastDragPoint.Value.Y;

                lastDragPoint = posNow;

                scrollViewer.ScrollToHorizontalOffset(scrollViewer.HorizontalOffset - dX);
                scrollViewer.ScrollToVerticalOffset(scrollViewer.VerticalOffset - dY);
            }
        }

        void OnMouseLeftButtonDown(object sender, MouseButtonEventArgs e)
        {
            var mousePos = e.GetPosition(scrollViewer);
            if (mousePos.X <= scrollViewer.ViewportWidth && mousePos.Y <
                scrollViewer.ViewportHeight) //make sure we still can use the scrollbars
            {
                scrollViewer.Cursor = Cursors.SizeAll;
                lastDragPoint = mousePos;
                Mouse.Capture(scrollViewer);
            }
        }

        void OnPreviewMouseWheel(object sender, MouseWheelEventArgs e)
        {
            lastMousePositionOnTarget = Mouse.GetPosition(grid);

            if (e.Delta > 0)
                zoomLevel++;
            else if (e.Delta < 0)
                zoomLevel--;

            zoomLevel = zoomLevel < 1 ? 1 : zoomLevel;

            scaleTransform.ScaleX = zoomLevel;
            scaleTransform.ScaleY = zoomLevel;

            var centerOfViewport = new Point(scrollViewer.ViewportWidth / 2, scrollViewer.ViewportHeight / 2);
            lastCenterPositionOnTarget = scrollViewer.TranslatePoint(centerOfViewport, grid);

            e.Handled = true;
        }

        void OnMouseLeftButtonUp(object sender, MouseButtonEventArgs e)
        {
            scrollViewer.Cursor = Cursors.Arrow;
            scrollViewer.ReleaseMouseCapture();
            lastDragPoint = null;
        }

        void OnScrollViewerScrollChanged(object sender, ScrollChangedEventArgs e)
        {
            if (e.ExtentHeightChange != 0 || e.ExtentWidthChange != 0)
            {
                Point? targetBefore = null;
                Point? targetNow = null;

                if (!lastMousePositionOnTarget.HasValue)
                {
                    if (lastCenterPositionOnTarget.HasValue)
                    {
                        var centerOfViewport = new Point(scrollViewer.ViewportWidth / 2,
                                                         scrollViewer.ViewportHeight / 2);
                        Point centerOfTargetNow =
                              scrollViewer.TranslatePoint(centerOfViewport, grid);

                        targetBefore = lastCenterPositionOnTarget;
                        targetNow = centerOfTargetNow;
                    }
                }
                else
                {
                    targetBefore = lastMousePositionOnTarget;
                    targetNow = Mouse.GetPosition(grid);

                    lastMousePositionOnTarget = null;
                }

                if (targetBefore.HasValue)
                {
                    double dXInTargetPixels = targetNow.Value.X - targetBefore.Value.X;
                    double dYInTargetPixels = targetNow.Value.Y - targetBefore.Value.Y;

                    double multiplicatorX = e.ExtentWidth / grid.Width;
                    double multiplicatorY = e.ExtentHeight / grid.Height;

                    double newOffsetX = scrollViewer.HorizontalOffset -
                                        dXInTargetPixels * multiplicatorX;
                    double newOffsetY = scrollViewer.VerticalOffset -
                                        dYInTargetPixels * multiplicatorY;

                    if (double.IsNaN(newOffsetX) || double.IsNaN(newOffsetY))
                    {
                        return;
                    }

                    scrollViewer.ScrollToHorizontalOffset(newOffsetX);
                    scrollViewer.ScrollToVerticalOffset(newOffsetY);
                }
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

using System.Windows;

using System.Windows.Controls;

using System.Windows.Input;

using System.Windows.Media;

namespace NAMESPACE

{

/// <summary>

/// Interaktionslogik für ScrollDragZoomControl.xaml

/// </summary>

public partial class ScrollDragZoomControl : UserControl

{

private int zoomLevel = 1;

private ScaleTransform scaleTransform;

private ScrollViewer scrollViewer;

private Grid grid;

Point? lastCenterPositionOnTarget;

Point? lastMousePositionOnTarget;

Point? lastDragPoint;

public ScrollDragZoomControl()

{

InitializeComponent();

}

private void scrollViewer_Loaded(object sender, RoutedEventArgs e)

{

scaleTransform = (ScaleTransform)Template.FindName("scaleTransform", this);

scrollViewer = (ScrollViewer)Template.FindName("scrollViewer", this);

grid = (Grid)Template.FindName("grid", this);

scrollViewer.ScrollChanged += OnScrollViewerScrollChanged;

scrollViewer.MouseLeftButtonUp += OnMouseLeftButtonUp;

scrollViewer.PreviewMouseLeftButtonUp += OnMouseLeftButtonUp;

scrollViewer.PreviewMouseWheel += OnPreviewMouseWheel;

scrollViewer.PreviewMouseLeftButtonDown += OnMouseLeftButtonDown;

scrollViewer.MouseMove += OnMouseMove;

}

void OnMouseMove(object sender, MouseEventArgs e)

{

if (lastDragPoint.HasValue)

{

Point posNow = e.GetPosition(scrollViewer);

double dX = posNow.X - lastDragPoint.Value.X;

double dY = posNow.Y - lastDragPoint.Value.Y;

lastDragPoint = posNow;

scrollViewer.ScrollToHorizontalOffset(scrollViewer.HorizontalOffset - dX);

scrollViewer.ScrollToVerticalOffset(scrollViewer.VerticalOffset - dY);

}

void OnMouseLeftButtonDown(object sender, MouseButtonEventArgs e)

{

var mousePos = e.GetPosition(scrollViewer);

if (mousePos.X <= scrollViewer.ViewportWidth && mousePos.Y <

scrollViewer.ViewportHeight) //make sure we still can use the scrollbars

{

scrollViewer.Cursor = Cursors.SizeAll;

lastDragPoint = mousePos;

Mouse.Capture(scrollViewer);

}

void OnPreviewMouseWheel(object sender, MouseWheelEventArgs e)

{

lastMousePositionOnTarget = Mouse.GetPosition(grid);

if (e.Delta > 0)

zoomLevel++;

else if (e.Delta < 0)

zoomLevel--;

zoomLevel = zoomLevel < 1 ? 1 : zoomLevel;

scaleTransform.ScaleX = zoomLevel;

scaleTransform.ScaleY = zoomLevel;

var centerOfViewport = new Point(scrollViewer.ViewportWidth / 2, scrollViewer.ViewportHeight / 2);

lastCenterPositionOnTarget = scrollViewer.TranslatePoint(centerOfViewport, grid);

e.Handled = true;

}

void OnMouseLeftButtonUp(object sender, MouseButtonEventArgs e)

{

scrollViewer.Cursor = Cursors.Arrow;

scrollViewer.ReleaseMouseCapture();

lastDragPoint = null;

}

void OnScrollViewerScrollChanged(object sender, ScrollChangedEventArgs e)

{

if (e.ExtentHeightChange != 0 || e.ExtentWidthChange != 0)

{

Point? targetBefore = null;

Point? targetNow = null;

if (!lastMousePositionOnTarget.HasValue)

{

if (lastCenterPositionOnTarget.HasValue)

{

var centerOfViewport = new Point(scrollViewer.ViewportWidth / 2,

scrollViewer.ViewportHeight / 2);

Point centerOfTargetNow =

scrollViewer.TranslatePoint(centerOfViewport, grid);

targetBefore = lastCenterPositionOnTarget;

targetNow = centerOfTargetNow;

}

else

{

targetBefore = lastMousePositionOnTarget;

targetNow = Mouse.GetPosition(grid);

lastMousePositionOnTarget = null;

}

if (targetBefore.HasValue)

{

double dXInTargetPixels = targetNow.Value.X - targetBefore.Value.X;

double dYInTargetPixels = targetNow.Value.Y - targetBefore.Value.Y;

double multiplicatorX = e.ExtentWidth / grid.Width;

double multiplicatorY = e.ExtentHeight / grid.Height;

double newOffsetX = scrollViewer.HorizontalOffset -

dXInTargetPixels * multiplicatorX;

double newOffsetY = scrollViewer.VerticalOffset -

dYInTargetPixels * multiplicatorY;

if (double.IsNaN(newOffsetX) || double.IsNaN(newOffsetY))

{

return;

}

scrollViewer.ScrollToHorizontalOffset(newOffsetX);

scrollViewer.ScrollToVerticalOffset(newOffsetY);

}

Usage Add the “ScrollDragZoomControl” to your project and use it as follows:

    <controls:ScrollDragZoomControl>
        <!-- Your Content to present -->
    </controls:ScrollDragZoomControl>

<controls:ScrollDragZoomControl>

</controls:ScrollDragZoomControl>

ABP – Alpha-Beta Pruning

	private BiPredicate<Integer, Node> searchLimitingPredicate;
	private int depth;

	public AlphaBetaSearch(BiPredicate<Integer, Node> searchLimitingPredicate) {
		this.searchLimitingPredicate = searchLimitingPredicate;
	}

	public Pair<Node, Double> search(Node start, Function<Node, Double> evalFunction) {
		Node winner = start;
		double value = Double.NEGATIVE_INFINITY;
		double alpha = Double.NEGATIVE_INFINITY;
		double beta = Double.POSITIVE_INFINITY;
		
		for (Node n : start.adjacent()) {
			double temp = min(n, evalFunction, alpha, beta);
			if (temp > value) {
				value = temp;
				winner = n;
			}
			depth = 0;
		}
		return new Pair<Node, Double>(winner, value);
	}

	private double min(Node node, Function<Node, Double> evalFunction, double alpha, double beta) {
		if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {
			return evalFunction.apply(node);
		}
		
		depth++;
		double value = Double.POSITIVE_INFINITY;
		for (Node n : node.adjacent()) {
			value = Math.min(value, max(n, evalFunction, alpha, beta));
			if (value <= alpha) break;
			beta = Math.min(beta, value);
		}
		depth--;
		return value;
	}

	private double max(Node node, Function<Node, Double> evalFunction, double alpha, double beta) {
		if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {
			return evalFunction.apply(node);
		}
		
		depth++;
		double value = Double.NEGATIVE_INFINITY;
		for (Node n : node.adjacent()) {
			value = Math.max(value, min(n, evalFunction, alpha, beta));
			if (value >= beta) break;
			alpha = Math.max(alpha, value);
		}
		depth--;
		return value;
	}

private BiPredicate<Integer, Node> searchLimitingPredicate;

private int depth;

public AlphaBetaSearch(BiPredicate<Integer, Node> searchLimitingPredicate) {

this.searchLimitingPredicate = searchLimitingPredicate;

}

public Pair<Node, Double> search(Node start, Function<Node, Double> evalFunction) {

Node winner = start;

double value = Double.NEGATIVE_INFINITY;

double alpha = Double.NEGATIVE_INFINITY;

double beta = Double.POSITIVE_INFINITY;

for (Node n : start.adjacent()) {

double temp = min(n, evalFunction, alpha, beta);

if (temp > value) {

value = temp;

winner = n;

}

depth = 0;

}

return new Pair<Node, Double>(winner, value);

}

private double min(Node node, Function<Node, Double> evalFunction, double alpha, double beta) {

if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {

return evalFunction.apply(node);

}

depth++;

double value = Double.POSITIVE_INFINITY;

for (Node n : node.adjacent()) {

value = Math.min(value, max(n, evalFunction, alpha, beta));

if (value <= alpha) break;

beta = Math.min(beta, value);

}

depth--;

return value;

}

private double max(Node node, Function<Node, Double> evalFunction, double alpha, double beta) {

if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {

return evalFunction.apply(node);

}

depth++;

double value = Double.NEGATIVE_INFINITY;

for (Node n : node.adjacent()) {

value = Math.max(value, min(n, evalFunction, alpha, beta));

if (value >= beta) break;

alpha = Math.max(alpha, value);

}

depth--;

return value;

}

DLS – Depth-Limited Search

	private StackWithFastContains<Node> path;
	private int limit;

	public DLDFS(int limit) {
		this.limit = limit;
	}

	public Node search(Node start, Predicate<Node> endPredicate) {
        //Initial the stackWithFastContains
        path = new StackWithFastContains<>();
        return searchForNode(start, endPredicate, limit);
    }

    private Node searchForNode(Node currentNode, Predicate<Node> toSearchFor, int depth){
        path.push(currentNode);

        if (depth >= 0) {
            //As long as we are depth > or equal zero, we are allowed to check for its predicate
            //Return if the node equals the goal.
            if (toSearchFor.test(currentNode))
                return currentNode;

            for (Node currentChildNode : currentNode.adjacent()) {
                if (path.contains(currentChildNode))
                    continue; //If the current child is already in the stack path, continue.

                //Recursively search for the result node.
                Node result = searchForNode(currentChildNode, toSearchFor, depth - 1);
                if (result != null)
                    return result;
            }
        }

        //Limit reached, remove it from the stack.
        path.pop();

        //We found nothing, return nothing.
        return null;
    }

private StackWithFastContains<Node> path;

private int limit;

public DLDFS(int limit) {

this.limit = limit;

}

public Node search(Node start, Predicate<Node> endPredicate) {

//Initial the stackWithFastContains

path = new StackWithFastContains<>();

return searchForNode(start, endPredicate, limit);

}

private Node searchForNode(Node currentNode, Predicate<Node> toSearchFor, int depth){

path.push(currentNode);

if (depth >= 0) {

//As long as we are depth > or equal zero, we are allowed to check for its predicate

//Return if the node equals the goal.

if (toSearchFor.test(currentNode))

return currentNode;

for (Node currentChildNode : currentNode.adjacent()) {

if (path.contains(currentChildNode))

continue; //If the current child is already in the stack path, continue.

//Recursively search for the result node.

Node result = searchForNode(currentChildNode, toSearchFor, depth - 1);

if (result != null)

return result;

}

//Limit reached, remove it from the stack.

path.pop();

//We found nothing, return nothing.

return null;

}

GBFS – Greedy Best-First Search

	private Function<Node, Double> heuristic;

	public GBFS(Function<Node, Double> heuristic) {
		this.heuristic = heuristic;
	}

	public Node search(Node start, Predicate<Node> endPredicate) {
		//Check if the start node is the endPredicate
		if (endPredicate.test(start))
			return start;

		//The queue containing all the nodes we have to search for
		StablePriorityQueue<Double, Node> nodeQueue = new StablePriorityQueue<>();
		//Add the start node as the head. The priority does not matter since we remove it anyway.
		nodeQueue.add(new Pair<>(heuristic.apply(start), start));
		//Adjacent, definition from the handbook.pdf contain all neighbors.
		//That means, that we would search in a node which we already searched for at another position.
		//Because of the insertion and lookup time O(1) in both situations, we chose the HashSt.
		HashSet<Node> checkedNodes = new HashSet<>();
		//Insert the start node into the hashset, since we are using it
		checkedNodes.add(start);

		//Repeat till we have no element in the queue left.
		while (nodeQueue.size() > 0) {
			Pair<Double, Node> currentNode = nodeQueue.remove();
			if (endPredicate.test(currentNode.s))
				return currentNode.s;
				//Nothing found. Add all it's children
			else currentNode.s.adjacent().stream() //Get the stream
					.filter(node -> !checkedNodes.contains(node)) //Filter only the nodes we did not visit yet.
					.forEach(node -> {
						nodeQueue.add(new Pair<>(heuristic.apply(node), node)); //Add the node to the priority queue to search for the result.
						checkedNodes.add(node); //Add the node to the hashset, so that we do not search for that again.
					});
		}

		//We cant reach that state, but just in case return null.
		return null;
	}

private Function<Node, Double> heuristic;

public GBFS(Function<Node, Double> heuristic) {

this.heuristic = heuristic;

}

public Node search(Node start, Predicate<Node> endPredicate) {

//Check if the start node is the endPredicate

if (endPredicate.test(start))

return start;

//The queue containing all the nodes we have to search for

StablePriorityQueue<Double, Node> nodeQueue = new StablePriorityQueue<>();

//Add the start node as the head. The priority does not matter since we remove it anyway.

nodeQueue.add(new Pair<>(heuristic.apply(start), start));

//Adjacent, definition from the handbook.pdf contain all neighbors.

//That means, that we would search in a node which we already searched for at another position.

//Because of the insertion and lookup time O(1) in both situations, we chose the HashSt.

HashSet<Node> checkedNodes = new HashSet<>();

//Insert the start node into the hashset, since we are using it

checkedNodes.add(start);

//Repeat till we have no element in the queue left.

while (nodeQueue.size() > 0) {

Pair<Double, Node> currentNode = nodeQueue.remove();

if (endPredicate.test(currentNode.s))

return currentNode.s;

//Nothing found. Add all it's children

else currentNode.s.adjacent().stream() //Get the stream

.filter(node -> !checkedNodes.contains(node)) //Filter only the nodes we did not visit yet.

.forEach(node -> {

nodeQueue.add(new Pair<>(heuristic.apply(node), node)); //Add the node to the priority queue to search for the result.

checkedNodes.add(node); //Add the node to the hashset, so that we do not search for that again.

});

}

//We cant reach that state, but just in case return null.

return null;

}

MM – MinMax Search

	private BiPredicate<Integer, Node> searchLimitingPredicate;
	private int depth;

	/**
	 * To limit the extent of the search, this implementation should honor a
	 * limiting predicate. The predicate returns 'true' as long as we are below
	 * the limit, and 'false', if we exceed the limit.
	 * 
	 * @param searchLimitingPredicate
	 */
	public MinMaxSearch(BiPredicate<Integer, Node> slp) {
		this.searchLimitingPredicate = slp;
		depth = 0;
	}

	public Pair<Node, Double> search(Node start, Function<Node, Double> evalFunction) {
		Node winner = start;
		double value = Double.NEGATIVE_INFINITY;
		
		for (Node n : start.adjacent()) {
			double temp = min(n, evalFunction);
			if (temp > value) {
				value = temp;
				winner = n;
			}
			depth = 0;
		}
		return new Pair<Node, Double>(winner, value);
	}

	private double min(Node node, Function<Node, Double> evalFunction) {
		if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {
			return evalFunction.apply(node);
		}
		
		depth++;
		double value = Double.POSITIVE_INFINITY;
		for (Node n : node.adjacent()) {
			value = Math.min(value, max(n, evalFunction));
		}
		depth--;
		return value;
	}

	private double max(Node node, Function<Node, Double> evalFunction) {
		if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {
			return evalFunction.apply(node);
		}
		
		depth++;
		double value = Double.NEGATIVE_INFINITY;
		for (Node n : node.adjacent()) {
			value = Math.max(value, min(n, evalFunction));
		}
		depth--;
		return value;
	}

private BiPredicate<Integer, Node> searchLimitingPredicate;

private int depth;

/**

* To limit the extent of the search, this implementation should honor a

* limiting predicate. The predicate returns 'true' as long as we are below

* the limit, and 'false', if we exceed the limit.

* @param searchLimitingPredicate

public MinMaxSearch(BiPredicate<Integer, Node> slp) {

this.searchLimitingPredicate = slp;

depth = 0;

}

public Pair<Node, Double> search(Node start, Function<Node, Double> evalFunction) {

Node winner = start;

double value = Double.NEGATIVE_INFINITY;

for (Node n : start.adjacent()) {

double temp = min(n, evalFunction);

if (temp > value) {

value = temp;

winner = n;

}

depth = 0;

}

return new Pair<Node, Double>(winner, value);

}

private double min(Node node, Function<Node, Double> evalFunction) {

if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {

return evalFunction.apply(node);

}

depth++;

double value = Double.POSITIVE_INFINITY;

for (Node n : node.adjacent()) {

value = Math.min(value, max(n, evalFunction));

}

depth--;

return value;

}

private double max(Node node, Function<Node, Double> evalFunction) {

if (node.isLeaf() || !searchLimitingPredicate.test(depth+1, node)) {

return evalFunction.apply(node);

}

depth++;

double value = Double.NEGATIVE_INFINITY;

for (Node n : node.adjacent()) {

value = Math.max(value, min(n, evalFunction));

}

depth--;

return value;

}

A* – AStar

	private Function<Node, Double> heuristic;
	private Function<Node, Double> cost;

	public ASTAR(Function<Node, Double> heuristic, Function<Node, Double> cost) {
		this.heuristic = heuristic;
		this.cost = cost;
	}

	//A class to store heuristic and costs and also the possibility to compare each other.
	private class CostPair implements Comparable<CostPair> {
		private double heuristic;
		private double cost;

		private CostPair(double heuristic, double cost) {
			this.heuristic = heuristic;
			this.cost = cost;
		}

		@Override
		public int compareTo(CostPair other) {
			return Double.compare(heuristic + cost, other.heuristic + other.cost);
		}
	}

	public Node search(Node start, Predicate<Node> endPredicate) {
		// Check if the start node is the endPredicate
		if (endPredicate.test(start))
			return start;
		
		// The queue containing all the nodes we have to search for
		StablePriorityQueue<CostPair, Node> nodeQueue = new StablePriorityQueue<>();
		// Add the start node as the head. The priority does not matter since we
		// remove it anyway.
		nodeQueue.add(new Pair<>(new CostPair(heuristic.apply(start), cost.apply(start)), start));
		// Adjacent, definition from the handbook.pdf contain all neighbors.
		// That means, that we would search in a node which we already searched for at another position.
		// Because of the insertion and lookup time O(1) in both situations, we chose the HashSt.
		HashSet<Node> checkedNodes = new HashSet<>();

		// Repeat till we have no element in the queue left.
		while (nodeQueue.size() > 0) {
			Pair<CostPair, Node> currentNode = nodeQueue.poll();
			if (endPredicate.test(currentNode.s))
				return currentNode.s;
			// Nothing found. Add all it's children
			currentNode.s.adjacent().stream().filter(node -> !checkedNodes.contains(node))
					.forEach(node -> {
						CostPair pair = new CostPair(heuristic.apply(node), currentNode.f.cost + cost.apply(node));
						nodeQueue.add(new Pair<>(pair, node));
						checkedNodes.add(currentNode.s); //Add the node to the hashset, so that we do not search for that again.
					});
		}

		// We cant reach that state, but just in case return null.
		return null;
	}

private Function<Node, Double> heuristic;

private Function<Node, Double> cost;

public ASTAR(Function<Node, Double> heuristic, Function<Node, Double> cost) {

this.heuristic = heuristic;

this.cost = cost;

}

//A class to store heuristic and costs and also the possibility to compare each other.

private class CostPair implements Comparable<CostPair> {

private double heuristic;

private double cost;

private CostPair(double heuristic, double cost) {

this.heuristic = heuristic;

this.cost = cost;

}

@Override

public int compareTo(CostPair other) {

return Double.compare(heuristic + cost, other.heuristic + other.cost);

}

public Node search(Node start, Predicate<Node> endPredicate) {

// Check if the start node is the endPredicate

if (endPredicate.test(start))

return start;

// The queue containing all the nodes we have to search for

StablePriorityQueue<CostPair, Node> nodeQueue = new StablePriorityQueue<>();

// Add the start node as the head. The priority does not matter since we

// remove it anyway.

nodeQueue.add(new Pair<>(new CostPair(heuristic.apply(start), cost.apply(start)), start));

// Adjacent, definition from the handbook.pdf contain all neighbors.

// That means, that we would search in a node which we already searched for at another position.

// Because of the insertion and lookup time O(1) in both situations, we chose the HashSt.

HashSet<Node> checkedNodes = new HashSet<>();

// Repeat till we have no element in the queue left.

while (nodeQueue.size() > 0) {

Pair<CostPair, Node> currentNode = nodeQueue.poll();

if (endPredicate.test(currentNode.s))

return currentNode.s;

// Nothing found. Add all it's children

currentNode.s.adjacent().stream().filter(node -> !checkedNodes.contains(node))

.forEach(node -> {

CostPair pair = new CostPair(heuristic.apply(node), currentNode.f.cost + cost.apply(node));

nodeQueue.add(new Pair<>(pair, node));

checkedNodes.add(currentNode.s); //Add the node to the hashset, so that we do not search for that again.

});

}

// We cant reach that state, but just in case return null.

return null;

}