Click here to Skip to main content
15,885,278 members
Articles / Programming Languages / C# 4.0

A Complex - Yet Quite Intelligible - Pathfinding in C#

Rate me:
Please Sign up or sign in to vote.
4.96/5 (41 votes)
30 Aug 2013CPOL21 min read 59.5K   2.5K   88  
A semi-analytic 2D path-finding for large dynamic scenarios.
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace YinYang.CodeProject.Projects.SimplePathfinding.Helpers
{
    public class EllipseRasterizer
    {
        private const Double Step = 0.001;
        private const Double HalfPi = Math.PI / 2.0;

        protected static IEnumerable<Point> CreateYield(Int32 x, Int32 y)
        {
            yield return new Point(x, y);
        }

        public static IEnumerable<Point> Enumerate(Int32 centerX, Int32 centerY, Int32 radiusX, Int32 radiusY, Boolean filled = false)
        {
            IEnumerable<Point> points = Enumerate(radiusX, radiusY, filled);
            return points.Select(point => new Point(point.X + centerX - radiusX, point.Y + centerY - radiusY));
        }

        public static IEnumerable<Point> Enumerate(Int32 radiusX, Int32 radiusY, Boolean filled = false)
        {
            // preliminary check - zero point
            if (radiusX == 0 || radiusY == 0) return Enumerable.Empty<Point>();

            // preliminary check - horizontal line
            if (radiusY == 1 || radiusY == -1) return LineRasterizer.EnumerateHorizontalLine(radiusX);

            // preliminary check - vertical line
            if (radiusX == 1 || radiusX == -1) return LineRasterizer.EnumerateVerticalLine(radiusY);

            // potencial problem - negative radius X
            if (radiusX < 0) radiusX = -radiusX;

            // potencial problem - negative radius Y
            if (radiusY < 0) radiusY = -radiusY;

            // enumerates ellipse
            return EnumerateEllipse(radiusX, radiusY, filled);
        }

        /// <summary>
        /// If you wonder why I didn't use some faster algorithm (bresenham, mid-point..) it's because it wouldn't match
        /// the outline of drawn ellipse via Graphics.DrawEllipse. So the obstacle looks elsewhere then the drawn ellipse.
        /// </summary>
        private static IEnumerable<Point> EnumerateEllipse(Int32 radiusX, Int32 radiusY, Boolean filled = false)
        {
            Double anomaly = HalfPi;
            Point lastPoint = Point.Empty;

            List<Point> result = new List<Point>
            {
                new Point(-radiusX, radiusY), 
                new Point(radiusX, radiusY)
            };

            if (filled) result.Add(Point.Empty);

            while (anomaly >= 0.0)
            {
                Int32 shiftX = Convert.ToInt32(radiusX*Math.Cos(anomaly));
                Int32 shiftY = Convert.ToInt32(radiusY*Math.Sin(anomaly));

                Int32 x = radiusX + shiftX;
                Int32 y = radiusY + shiftY;

                if (x != lastPoint.X || y != lastPoint.Y)
                {
                    Point topLeft = new Point(radiusX - shiftX, radiusY - shiftY);
                    Point topRight = new Point(radiusX + shiftX, radiusY - shiftY);
                    Point bottomLeft = new Point(radiusX - shiftX, radiusY + shiftY);
                    Point bottomRight = new Point(radiusX + shiftX, radiusY + shiftY);

                    result.Add(topLeft);
                    if (filled) result.AddRange(LineRasterizer.EnumerateHorizontalLine(radiusX - shiftX + 1, radiusX + shiftX - 1, radiusY - shiftY));
                    result.Add(topRight);

                    result.Add(bottomLeft);
                    if (filled) result.AddRange(LineRasterizer.EnumerateHorizontalLine(radiusX - shiftX + 1, radiusX + shiftX - 1, radiusY + shiftY));
                    result.Add(bottomRight);

                    lastPoint = bottomRight;
                }

                anomaly -= Step;
            }

            return result;
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Czech Republic Czech Republic
Contacts: EMAIL - smartk8@gmail.com

Comments and Discussions