GAM456 Week 3

Week 3 Activities
 
Practical Exercise A
Video at: https://youtu.be/_mFOsBUvMgo
 
Apologies for this week being late, it was hectic on my side, so im doing all my catch up now 😊
As can be seen in the video, I had some interesting problems with framerate that I am still going after. However, at 300 units moving simultaneously, and recalculating path every ~3 seconds, the framerate is fairly steady from 50-70 fps.
I have attempted various techniques for both node and path smoothing. I can confidently say that my attempts on node smoothing did not work, at all. My initial logic was that if a node was surrounded by other similar nodes, that its edges and connections could be transferred to the outside nodes, and the node itself deleted. However, considering that all my nodes are similar, I ended up with a set of nodes bordering my obstructions, and none to path. E.g.
https://twitter.com/DraconInt/status/1007961775365451776 
 
Thus, the player could not navigate to… anywhere, as there was no node present.
I did manage to scavenge some level of success from this approach, when I increased the nodes compared from the nearest neighbours, to the next level of neighbours inclusive (neighbours, as well as neighbours of neighbours). This created a sort of shell around the obstacles, removing nodes on the far edges of the maps. Useful for some situations, perhaps not others. E.g.
https://twitter.com/DraconInt/status/1007967144552718336
 
Now, for path smoothing;
More success! With just a single function, my paths are shrinking from ~17 nodes to ~3.
The function in question follows as such:
public List<Node> SmoothPath (List<Node> original)
        {
            List<Node> smoothPath = new List<Node>(original);
            print("Smooth begun: " + smoothPath.Count);
            Node checkPoint = smoothPath[0];
            Node currentPoint = smoothPath[1];
            while (currentPoint != null)
            {
                Ray ray = new Ray(checkPoint.position, (currentPoint.position - checkPoint.position).normalized);
                if (Physics.SphereCast(ray, 1, Vector3.Distance(checkPoint.position, currentPoint.position), obstructionMask))
                {
                    checkPoint = currentPoint;
                    if ((smoothPath.IndexOf(currentPoint) + 1) < smoothPath.Count)
                    {
                        currentPoint = smoothPath[smoothPath.IndexOf(currentPoint) + 1];
                    }
                    else
                    {
                        currentPoint = null;
                    }
                   
                   
                }
                else
                {
                    Node temp = currentPoint;
                    if ((smoothPath.IndexOf(currentPoint) + 1) < smoothPath.Count)
                    {
                        currentPoint = smoothPath[smoothPath.IndexOf(currentPoint) + 1];
                    }
                    else
                    {
                        currentPoint = null;
                    }
                    smoothPath.Remove(temp);
                }
            }
            print("Smooth Finished: " + smoothPath.Count);
            /*
            checkPoint = starting point of path
        currentPoint = next point in path
        while (currentPoint->next != NULL)
        if Walkable(checkPoint, currentPoint->next)
        // Make a straight path between those points:
        temp = currentPoint
        currentPoint = currentPoint->next
        delete temp from the path
        else
        checkPoint = currentPoint
        currentPoint = currentPoint->next
*/
            return smoothPath;
        }
 
Now, from this (unfortunately separate) video (https://youtu.be/myosIgGyLME)  we can see that sometimes the AI will clip through nearby obstacles. I have a few different methods to solve this, which result in slightly different behaviours for the pathing, but for the exposition I went with my default settings, as I prefer their result for now.
As the smoothing adds a further step onto path generation, it does increase lag during gameplay, but the function is quite fast so its not a major concern at this stage, at least not as much as the pathing itself.
 
Practical Exercise B
My chosen algorithm is A*.
A* is not only well optimised, for both swift prebaking and live gameplay, but it has an abundance of documentation and literature about it, allowing for many variations to be studied and integrated into my gameplay.
A drawback to this approach is the cost of operations; ie, repeated calls for path generation. A* will not perform as well as D*, as D* stores path data and changes when needed.
As a resolution to this problem, I am finding “probable” paths between important nodes and storing them. Then, when a character needs to move between important points they can simply draw on the pre-generated paths.
E.g., For this week I created a mock village simulator, with villages going from building to building. In this instance, we may assume that we can create paths from every building to every other building and store them. When the character needs to go from fields to storage, it queries the field for its storage path and uses that rather than generating its own. While workable, this approach will need some refinement to be properly usable. Perhaps not all buildings need to reference each other?