C# A* improved pathfinder (fast, lightweight)

[Mextur]

so.. whats better?
it's faster to calculate the route, and also very lightweighted.
i'm using the newest features of the .NET framework to make this happening.
it's also optimized for multi-core servers.

what's inside?
a pathfinder, and an rotation calculator.

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Pathfinding
{
    public static class Pathfinder
    {
        public static short[,] mapping = new short[8, 2] { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { -1, -1 }, { 1, -1 }, { -1, 1 }, { 1, 1 } };

        // be aware that this function will terminate the thread! use a new thread for this calculation
        public static ConcurrentQueue calculate(Coord start, Coord end, HeightMapData[,] tiles)
        {
            try
            {
                ConcurrentQueue output = new ConcurrentQueue();
                Coord currentTile = start;

                while (true)
                {
                    var surr = currentTile.getSurrounding(tiles, end);

                    Coord preferedTile = Coord.Empty;
                    int prefered = -1;

                    Parallel.ForEach(surr, coord =>
                    {
                        int g = coord.distance(currentTile);
                        int h = coord.distance(end);
                        int f = g + h;

                        if (prefered == -1 || f < prefered)
                        {
                            prefered = f;
                            preferedTile = coord;
                        }
                    });

                    currentTile = preferedTile;
                    // we got a new tile.
                    output.Enqueue(preferedTile);

                    if (preferedTile == end)
                    {
                        break;
                    }
                }

                return output;
            }
            catch (Exception ex)
            {
                throw ex;
            }

            return null;
        }

        public static int getRotation(Coord a, Coord b)
        {
            try
            {
                float xDiff = b.x - a.x;
                float yDiff = b.y - a.y;
                double angle = Math.Atan2(yDiff, xDiff) * 180 / Math.PI;

                switch ((int)angle)
                {
                    default:
                    case -135:
                        return 7;
                    case -180:
                        return 8;
                    case -90:
                        return 0;
                    case -45:
                        return 1;
                    case 0:
                        return 2;
                    case 45:
                        return 3;
                    case 90:
                        return 4;
                    case 135:
                        return 5;
                    case 180:
                        return 6;
                }
            }
            catch (Exception ex)
            {
                throw ex;
            }

            return 0;
        }
    }
}

Later i will give you the other classes.

[MentaL]

[LeChris]

Any emulator?

[AKllX]

You must use dijkstra's algorithm like sulake does. Calculete the whole route before start moving.

[Mextur]

You must use dijkstra's algorithm like sulake does. Calculete the whole route before start moving.

This function is used to calculate a whole route. (Before walking)

[Mextur]

It's not finished yet. It has some deadloops and other bugs. But this one does the job quite good, and its fast. (I've tested it)

[Mextur]

*i read on the internet that A* is much faster to reach the goal, and uses less ram. Also i read that the A* is more common for calculating 2D grids.

Just what i found

[maritnmine]

You must use dijkstra's algorithm like sulake does. Calculete the whole route before start moving.

Do you even know what dijkstra's algorithm is? Also, let me just get started:
- Data member 'mapping' shall be private
- Remove empty try-catch with an catch that just throws the exceptions. Then there is simply no point in having the try-catch block around it.
- while (true) with a break is bad. The code can easily be rewritten using a do-while instead.
- var is bad, this is C#, not Javascript.
- Don't do parallel foreach on such a small operation. It is a lot more work to distribute the work to new threads and make the context switch instead of doing a normal for loop. You haven't optimized it, you just made it far slower for no reason. Only use a parallel foreach if the payload in each loop is very large. I'm pretty sure the other CPUs have enough work to do so you should restrict yourself to a normal for loop instead.
- The switch with the angle can be rewritten to a math function
- Your code is not light-weight. The parallel foreach loop would cause your code to eat up cpu from other threads. In a gameserver, it is not a good idea to distribute work on a simple task like this on several cores. You have to wait for all the operations to finish anyways.

Edit: Also, your code has a race condition as prefered and preferedTile is a shared resource :)

[Mextur]

Do you even know what dijkstra's algorithm is? Also, let me just get started:
- Data member 'mapping' shall be private
- Remove empty try-catch with an catch that just throws the exceptions. Then there is simply no point in having the try-catch block around it.
- while (true) with a break is bad. The code can easily be rewritten using a do-while instead.
- var is bad, this is C#, not Javascript.
- Don't do parallel foreach on such a small operation. It is a lot more work to distribute the work to new threads and make the context switch instead of doing a normal for loop. You haven't optimized it, you just made it far slower for no reason. Only use a parallel foreach if the payload in each loop is very large. I'm pretty sure the other CPUs have enough work to do so you should restrict yourself to a normal for loop instead.
- The switch with the angle can be rewritten to a math function
- Your code is not light-weight. The parallel foreach loop would cause your code to eat up cpu from other threads. In a gameserver, it is not a good idea to distribute work on a simple task like this on several cores. You have to wait for all the operations to finish anyways.

Edit: Also, your code has a race condition as prefered and preferedTile is a shared resource :)

Thanks for feedback! I will improve my code as soon as possible.

I wrote this code at night, I was on holiday. And I had not much time.

Btw. That try catch thing, I use an exceptionhandler there, but removed it for this release.

And also the while loop is bad. I know, im working on it.

You were right about the paralell, I wasn't thinking about the other things running in a server. My bad.

And yes the rotation can be rewritten in math, but i'm working on it.

And about the 'var', I thought the compiler just knows what type it should be and replaces it in the final release.

[Mextur]

And yea the prefered objects are not placed well. They will be re-created every cycle. My bad

[Mextur]

I will study more about A* and improve the code tomorrow. For the best experience!

I'm missing some parts of A*

[maritnmine]

And about the 'var', I thought the compiler just knows what type it should be and replaces it in the final release.

Yes, it does that. It is about documentation and readable code. As Microsoft was dumb enough to add var to the C# language (C++ got auto), they made the language a bit more weak-type. It is a terrible practice to use var every single place in your code. Instead of doing int a = getA(); you do var a = getA(); You cannot on the last code say what the return type of getA() is or the type of a is. It could be critical to the performance or what types you are working with, whether it is IFoo or Foo that you are working with. I only use var when I use Linq as I don't want those IQueryableOrSomething<SomeStuff>, which was the intentional purpose of using var. Some people use var everywhere which is bad, as it makes the code far less self-documenting (which is one of the points of strong-type languages) while it also makes the language more weak-type which also has its down-sides when it comes to code robustness. Some people just says "get used to it". Well, it is a bad habit.

[Mextur]

I've corrected the whole code. It's almost working 100%. Just some diagonal issues.

[Emily]

Do you even know what dijkstra's algorithm is? Also, let me just get started:
- Data member 'mapping' shall be private
- Remove empty try-catch with an catch that just throws the exceptions. Then there is simply no point in having the try-catch block around it.
- while (true) with a break is bad. The code can easily be rewritten using a do-while instead.
- var is bad, this is C#, not Javascript.
- Don't do parallel foreach on such a small operation. It is a lot more work to distribute the work to new threads and make the context switch instead of doing a normal for loop. You haven't optimized it, you just made it far slower for no reason. Only use a parallel foreach if the payload in each loop is very large. I'm pretty sure the other CPUs have enough work to do so you should restrict yourself to a normal for loop instead.
- The switch with the angle can be rewritten to a math function
- Your code is not light-weight. The parallel foreach loop would cause your code to eat up cpu from other threads. In a gameserver, it is not a good idea to distribute work on a simple task like this on several cores. You have to wait for all the operations to finish anyways.

Edit: Also, your code has a race condition as prefered and preferedTile is a shared resource :)

There's nothing wrong with using var. It's for lazy people and as a programmer you should be lazy :)

[Mextur]

using NexusAPI;
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace API_ROOMS.Classes.Pathfinding
{
    public static class Pathfinder
    {
        private static short[,] mapping = new short[8, 2] { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { -1, -1 }, { 1, -1 }, { -1, 1 }, { 1, 1 } };

        // be aware that this function will terminate the thread!
        public static ConcurrentQueue<Coord> calculate(Coord start, Coord end, HeightMapData[,] data)
        {
            try
            {
                ConcurrentDictionary<Coord, PathfinderNode> openNodes = new ConcurrentDictionary<Coord, PathfinderNode>();
                ConcurrentDictionary<Coord, PathfinderNode> closedNodes = new ConcurrentDictionary<Coord, PathfinderNode>();

                PathfinderNode processingNode = new PathfinderNode() { location = start };
                closedNodes.TryAdd(processingNode.location, processingNode);

                do
                {
                    ConcurrentBag<Coord> nodeChilds = processingNode.location.getChilds(Pathfinder.mapping);

                    foreach (Coord child in nodeChilds)
                    {
                        if (child.x < 0 || child.y < 0 || child.x >= data.GetLength(0) || child.y >= data.GetLength(1))
                        {
                            continue;
                        }

                        if (closedNodes.ContainsKey(child))
                        {
                            continue;
                        }

                        HeightMapData childData = data[child.x, child.y];
                        
                        if (childData.state == TileState.BLOCKED)
                        {
                            continue;
                        }

                        PathfinderNode node = null;

                        if (!openNodes.TryGetValue(child, out node))
                        {
                            node = new PathfinderNode();
                            node.location = child;
                            node.parent = processingNode;
                            node.H = manhattanHeuristic(child, end);
                            node.G = pythagoras(child, start);
                            bool added = openNodes.TryAdd(node.location, node);
                        }
                        else
                        {
                            int gCheck = processingNode.G + pythagoras(processingNode.location, node.location);

                            if (gCheck < node.G)
                            {
                                node.G = gCheck;
                                node.parent = processingNode;
                            }
                        }
                    }

                    PathfinderNode removeNode;
                    bool remove = openNodes.TryRemove(processingNode.location, out removeNode);

                    if (remove)
                    {
                        bool moved = closedNodes.TryAdd(removeNode.location, removeNode);
                    }

                    PathfinderNode nextNode = openNodes.Values.OrderBy(obj => obj.G).OrderBy(obj => obj.F).FirstOrDefault();

                    if (nextNode != null)
                    {
                        processingNode = nextNode;
                    }
                    else
                    {
                        return null;
                    }
                }
                while (processingNode != null && processingNode.location != end);

                ConcurrentBag<Coord> output = new ConcurrentBag<Coord>() { processingNode.location };
                PathfinderNode tracingNode = processingNode;

                do
                {
                    PathfinderNode parentNode = tracingNode.parent;

                    if (parentNode.location == start)
                    {
                        break;
                    }

                    output.Add(parentNode.location);
                    tracingNode = parentNode;
                }
                while (tracingNode != null && tracingNode.location != start);

                return new ConcurrentQueue<Coord>(output);
            }
            catch (Exception ex)
            {
                ApplicationPool.handleException(ex);
            }

            return null;
        }

        public static int getRotation(Coord a, Coord b)
        {
            try
            {
                float xDiff = b.x - a.x;
                float yDiff = b.y - a.y;
                double angle = Math.Atan2(yDiff, xDiff) * 180 / Math.PI;
                double absolute = Math.Abs(angle);

                switch ((int)angle)
                {
                    default:
                    case -135:
                        return 7;
                    case -180:
                        return 8;
                    case -90:
                        return 0;
                    case -45:
                        return 1;
                    case 0:
                        return 2;
                    case 45:
                        return 3;
                    case 90:
                        return 4;
                    case 135:
                        return 5;
                    case 180:
                        return 6;
                }
            }
            catch (Exception ex)
            {
                ApplicationPool.handleException(ex);
            }

            return 0;
        }

        private static int pythagoras(Coord a, Coord b)
        {
            double quad1 = Math.Pow(Math.Abs(a.x - b.x), 2.0),
                   quad2 = Math.Pow(Math.Abs(a.y - b.y), 2.0);

            double pythagoras = Math.Sqrt(quad1 + quad2) * 10;

            //pythagoras = Math.Floor(pythagoras / 10) * 10;

            return Convert.ToInt32(pythagoras);
        }

        private static int manhattanHeuristic(Coord a, Coord b)
        {
            int ab1 = a.x - b.x,
                ab2 = a.y - b.y;

            int heuristic = Math.Abs(ab1) + Math.Abs(ab2);
            return heuristic;
        }
    }

    public class PathfinderNode
    {
        public Coord location;
        public PathfinderNode parent;
        public int G;
        public int H;
        public int F
        {
            get
            {
                return G + H;
            }
        }
    }

    public struct Coord
    {
        public int x, y;

        public Coord(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public static Coord Empty
        {
            get
            {
                return new Coord(-1, -1);
            }
        }

        public static bool operator ==(Coord a, Coord b)
        {
            return a.x == b.x && a.y == b.y;
        }

        public static bool operator !=(Coord a, Coord b)
        {
            return a.x != b.x || a.y != b.y;
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            try
            {
                if (obj is Coord)
                {
                    Coord coord = (Coord)obj;
                    return coord.x == this.x && coord.y == this.y;
                }

                return obj == (object)this;
            }
            catch (Exception ex)
            {
                ApplicationPool.handleException(ex);
            }

            return false;
        }

        public ConcurrentBag<Coord> getChilds(short[,] mapping)
        {
            try
            {
                ConcurrentBag<Coord> output = new ConcurrentBag<Coord>();

                for (short i = 0; i < mapping.GetLength(0); i++)
                {
                    int x = (this.x + mapping[i, 0]);
                    int y = (this.y + mapping[i, 1]);
                    Coord coord = new Coord(x, y);

                    output.Add(coord);
                    // check height ..
                }

                return output;
            }
            catch (Exception ex)
            {
                ApplicationPool.handleException(ex);
            }

            return null;
        }
    }
}

The new pathfinder code. (needs cleanup)

[maritnmine]

There's nothing wrong with using var. It's for lazy people and as a programmer you should be lazy :)

I see everything wrong with using var for simple data types. It makes your code far harder to read (as you cannot see the type the object is or what the function you call returns), it basically throws away half of the readabillity, documentation and maintainbillity of your code. C# is supposed to be a strong-type language, but when some dickhead over at Microsoft (I'm sorry Microsoft, but sometimes you really make some dumb ass decisions) came up with the idea of var. As a result of this, half the example codes over at MSDN looks Javascriptified and is way harder to read if they took their time to write int instead of var. It really annoys me when people says programmers are lazy. We are not. We are supposed to write code which other humans shall be able to effectively read, extend, modify and maintain. At the same time we shall write comments in our code and at least a dozen reports on how we decided to design and implement this and that. If you don't take your time to write self-documented code that is both easy to read and understand, you make a hell not only for yourself when you are going to maintain your code, but also for those "dumb-ass next generation kids" who are going to figure out what your code does in ten years.
I'm clearly not a fan of weak-type languages and I only think they should be used for scripting purposes and not programming larger systems (like those hipsters who wants to run JavaScript server-side). I have been working on a school project in PHP and JS for about a month now and much of the documentation goes to describe what type this variable is. And when you in addition to your code specify what type this variable is, or what this function returns - I don't really see why the language is weak-type. I have been sitting for hours going through the layers in my web-app to find a bug, which turned out was that I managed to mix up a function parameter with a local value. So, yeah....

TL;DR: Good programmers aren't lazy and weak-type languages sucks.

Also, Mextur, don't use "continue;", it creates more exit-points for your foreach which makes it harder to read. break, return and continue are all considered as bad practice when used in foreach where they can easily be avoided by using normal if-statements or adding conditions to a while statement.

[Emily]

I see everything wrong with using var for simple data types. It makes your code far harder to read (as you cannot see the type the object is or what the function you call returns), it basically throws away half of the readabillity, documentation and maintainbillity of your code. C# is supposed to be a strong-type language, but when some dickhead over at Microsoft (I'm sorry Microsoft, but sometimes you really make some dumb ass decisions) came up with the idea of var. As a result of this, half the example codes over at MSDN looks Javascriptified and is way harder to read if they took their time to write int instead of var. It really annoys me when people says programmers are lazy. We are not. We are supposed to write code which other humans shall be able to effectively read, extend, modify and maintain. At the same time we shall write comments in our code and at least a dozen reports on how we decided to design and implement this and that. If you don't take your time to write self-documented code that is both easy to read and understand, you make a hell not only for yourself when you are going to maintain your code, but also for those "dumb-ass next generation kids" who are going to figure out what your code does in ten years.
I'm clearly not a fan of weak-type languages and I only think they should be used for scripting purposes and not programming larger systems (like those hipsters who wants to run JavaScript server-side). I have been working on a school project in PHP and JS for about a month now and much of the documentation goes to describe what type this variable is. And when you in addition to your code specify what type this variable is, or what this function returns - I don't really see why the language is weak-type. I have been sitting for hours going through the layers in my web-app to find a bug, which turned out was that I managed to mix up a function parameter with a local value. So, yeah....

TL;DR: Good programmers aren't lazy and weak-type languages sucks.

Also, Mextur, don't use "continue;", it creates more exit-points for your foreach which makes it harder to read. break, return and continue are all considered as bad practice when used in foreach where they can easily be avoided by using normal if-statements or adding conditions to a while statement.

Wrong. Hover over var and you see the type ;)

[Joopie]

Wrong. Hover over var and you see the type ;)

Yhee, waiting a second to get that hover option and then read the var type.. Everytime you need to do that, you can better write the type down instead of using var. In a long time run, it's more efficient.

Every searched in a weak-typed code what type a variable is (without running and printing what type it is)? It's annoying and time consuming. I'm talking about people who join the development...

[maritnmine]

Wrong. Hover over var and you see the type ;)

You do know how much faster it is to read the actual type instead of hovering and waiting for the box to appear?

[The General]

Its actually a derpy solution to use var. Not really you want to use if you want to keep your code clean.

[Mextur]

Stop about the var. Focus on my last code.

[maritnmine]

Stop about the var. Focus on my last code.

No, this is all about the var. Don't use var. Var is bad, mkay.

[Mextur]

No, this is all about the var. Don't use var. Var is bad, mkay.

Yea i know. Its bad everywhere but why not use it sometimes when it is there.

[AWA]

Here's my rotation function, cleaner and about the same speed as the commonly used one:

internal static int Calculate(int X1, int Y1, int X2, int Y2, bool moonwalk = false)
{
    int dX = X2 - X1;
    int dY = Y2 - Y1;

    if (moonwalk)
    {
        dX *= -1;
        dY *= -1;
    }
    double d = Math.Atan2(dY, dX)*180/Math.PI;
    return ((int) d + 90)/45;
}