5
\$\begingroup\$

I have this problem, which isn't really a problem, but I feel like it's some sort of glitch in my code maybe.

My pathfinder, to find a path from A to B, does this:

my A* pathfinder

which is almost fine, it works great, but others I have seen do this:

http://theory.stanford.edu/~amitp/game-programming/a-star/manhattan.png

which, appears less "robot-like", looks cleaner, more real I think.. what am I doing wrong? I've tried several different heuristics:

tested with all of these and more (that got removed), and all produce the same/similar results:

(Manhattan, Euclidean, MaxDXDY, Diagonal) can't post more than 2 links, but I tried all of those + more

So I really think at this point it's to do with my algorithm code, could anybody see any problems?:

    public virtual Path Find(Point start, Point end, Func<Node, Node, float> heuristic, bool cutCorners = true, bool memorizePath = false)
    {
        if (CutCorners != cutCorners) { CutCorners = cutCorners; if (precalculatedNeighbours) PrecalculateNeighbours(); }
        if ((start == end) || !InBounds(start) || !InBounds(end)) return null;
        else
        {
            Node source = Nodes[start.X, start.Y], goal = Nodes[end.X, end.Y];
            if (memorizePath && memoryDictionary.ContainsKey(source) && memoryDictionary[source].ContainsKey(goal)) return memoryDictionary[source][goal].Clone();
            var open = new HashSet<Node>();
            var closed = new bool[Width, Height];
            while (!open.Contains(goal))
            {
                var current = open.LowestFScore(source);
                open.Remove(current);
                closed[current.X, current.Y] = true;
                foreach (Node neighbour in Neighbours(current))
                {
                    if (closed[neighbour.X, neighbour.Y]) continue;
                    float gScore = (current.GScore + neighbour.CostFrom(current));
                    if (!open.Contains(neighbour)) open.Add(neighbour);
                    else if (gScore >= neighbour.GScore) continue;

                    // 1st param - set parent, 2nd - gScore, 3rd - fScore
                    neighbour.Record(ref current, gScore, (gScore + heuristic(neighbour, goal)));
                }
                if (open.Count == 0) return null;
            }
            return ConstructPath(source, goal, memorizePath);
        }
    }
\$\endgroup\$
11
  • \$\begingroup\$ What is your cost function? Is it cheaper to move horizontally or vertically than diagonal? \$\endgroup\$
    – Steven
    Dec 8 '15 at 2:20
  • \$\begingroup\$ public float CostFrom(Node node) { if ((X == node.X) || (Y == node.Y)) return Cost; else return (Cost + 1); } // same cost for horizontal/vertical - + 1 for diagonal, tried different values for that, no difference \$\endgroup\$ Dec 8 '15 at 2:48
  • \$\begingroup\$ Your heuristic looks like it's wildly overestimating in that first picture. I know you tried several, but what one did you use for that? \$\endgroup\$ Dec 8 '15 at 2:50
  • \$\begingroup\$ Euclidean, though each produce the same path/similar \$\endgroup\$ Dec 8 '15 at 2:52
  • \$\begingroup\$ Manhattan would be 22, Euclidean should be less... How is F 250+ at the start? Is there a square root missing? \$\endgroup\$ Dec 8 '15 at 2:55
2
\$\begingroup\$

There is nothing wrong with your algorithm, it finds the shortest path. Want you want you can do with a extra step after your path is found. Usually its called something like 'SmoothPath'

  • first compress the path: you're only interested in the important points, the important ones are the ones where the direction changes: in this example the startPoint, the endPoint and the one point where you change direction (g:12, f112)

  • then you start with the startPoint and use a linedrawing algorithm (Bresenham) to see if you can skip a point, by trying to draw the line directly to the point after that. (in this case the endPoint) if that succeeds you can try the next point up until you cannot 'see' the point anymore. rinse and repeat (until the endPoint).

this way in your example you learn you can get rid of that middle point and are only left with two points as a path (the start and end)

  • then you use that same line drawing algorithm to draw a line between them and voila

here's a link with pictures: http://deepnight.net/bresenham-magic-raycasting-line-of-sight-pathfinding/

\$\endgroup\$
1
  • \$\begingroup\$ Thanks but I already did it, the result followed similarly to what you've said so I'll mark this as the answer. \$\endgroup\$ Jan 21 '16 at 23:38
0
\$\begingroup\$

This answer sort of tries to solve the question in a different way than you ask, but is useful in the context of games development, especially since your code appears to be working and finding a short path.

Is there any place you store X & Y coordinates in nodes ? because you could apply interpolation by using a catmull rom spline by taking all the points and lerping them to make a more natural route human like route.

http://gamesnorthwest.net/resources/modules/co2301/materials.html -- < if you check week 12 there is an example program in a engine called TL(its visual studio 2013 modification using DirectX9/10) , its C++ but you can use the lecture notes and formula in the program to apply it.

https://www.youtube.com/watch?v=CFKWkYb1KZg << video here shows what it looks like.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thanks for taking your time to answer, though I did figure this out, thanks again! \$\endgroup\$ Jan 21 '16 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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