Skip to main content

Adventure Game #003 A* Pathfinding (Version 2)





Following the previous post (here) The AstarPathfinding package is now wrapped up.
I added the following features:

1) Get shortest path with Gameobjects
2) Get shortest path with AstarNodes
3) Return null if end point is unreachable
4) AstarPathfinding is now static
5) Added summaries to the methods for ease of use
6) removed char[,] references.

1) Get shortest path with Gameobjects


The tiles on the game all have a component "AstarTileNode" and have the following members:

+ public enum AstarNodeState { Open, Closed, Start, End}
+ public AstarNodeState CurrentNodeState


///<summary>
///<para>Takes a array of Gameobjects with Component AstarNode and returns a
///recursive node path of the shortest path</para>
///<para>Returns: AstarNode shortest path node, null is no path</para>
///</summary>
public static AstarNode GetShortestPath(GameObject[] gos) {
    List<AstarNode> nodes = new List<AstarNode>();
    foreach(var n in gos) {
        var wsn = n.GetComponent<AstarTileNode>();
        var node = new AstarNode(
            (int) n.transform.position.x,
            (int) n.transform.position.y,
            wsn.CurrentNodeState != AstarTileNode.AstarNodeState.Closed,
            wsn.CurrentNodeState == AstarTileNode.AstarNodeState.Start,
            wsn.CurrentNodeState == AstarTileNode.AstarNodeState.End
        );
        nodes.Add(node);
    }
    return GetShortestPath(nodes);
}


2) Get shortest path with AstarNodes


All nodes in this list or array are of type AstarNode. They have Position, Open/Closed, Start/End information stored within.

///<summary>
///<para>Takes an array of AstarNodes and returns a recurive node path of the shortest path</para>
///<para>Returns: AstarNode shorest path node, null is no path</para>
///</summary>
public static AstarNode GetShortestPath(AstarNode[] nodes) {
    var openList = new List<AstarNode>();
    var Map = CreateMapFromNodes(nodes);
    var startPosition = GetPosition(Map, TOKEN_START);
    var endPosition = GetPosition(Map, TOKEN_END);
    SetAllHValues(Map, endPosition);
    AstarNode current = Map.GetNodeAt((int)startPosition.x, (int)startPosition.y);
    current.State = AstarNode.state.CLOSED;
    while (!current.endposition) {
        var l = GetAdjacentWalkableNodes(Map, current);
        foreach (var n in l)
            if (!openList.Contains(n))
                openList.Add(n);
        current = MinNode(openList);
        if (current == null)
            return null;
        current.State = AstarNode.state.CLOSED;
        openList.Remove(current);
    }
    return current;
}

3) Return null if end point is unreachable


This is pretty self explanatory. If the algorithm is unable to traverse from start to end, for any reason, then the process is canceled and NULL is returned to the user.

The user is expected to check for null on return.

4) AstarPathfinding is now static


In the spirit for making the package easy to use, AstarPathfinding is now static so that the user does not need to create an object and store it.

This decision was made mainly from the idea that the object never stored information and would act as a static in use.

Future builds will include a non-static method to “save” a map and generate a path with only a start and end position.

TODO


During the writing of this post it came to my attention that the map and start/end should be separated.

    + static AstarNode GetShortestPath(AstarNode[] nodes)
will change to:
    + static AstarNode GetShortestPath(AstarNode[] nodes, vector2 start, vector2 end)

and

    + static AstarNode GetShortestPath(GameObject[] gos)
will change to:
    + static AstarNode GetShortestPath(GameObject[] gos, vector2 start, vector2 end)

and

    + enum AstarNodeState { Open, Closed, Start, End}
    + AstarNodeState CurrentNodeState
will change to:
    + enum AstarNodeState { Open, Closed}
    + AstarNodeState CurrentNodeState
OR
    + enum AstarNodeState { Open, Closed}
    + AstarNodeState CurrentNodeState
    + bool OpenAstarNodeState

 

Downloads & Links

Comments

Popular posts from this blog

Adventure Game #001: Waypoint Traversal

Way-points have always seemed to be an important part of gaming; traversing a unit through a path, patrolling an area, etc. Project and Source downloads are at the bottom of the post.

I started this post with what I thought was a well rounded and defined goal. As I moved forward with the code I thought "Hey, it would be cool to do this and add that". after going around and tripling my scope I decided to pair the features down to the basics: Moving to Random way-points and Traversing a way-point list in order. All other code was shelved for a part 2 and 3 (Reversing Direction, Shortest Paths)

I set forth with the idea to have unique customization events happen to each individual object traversing and with that in mind each unit contains the follow options:

 eWaypointAction {TraverseNext,Random}
eWaypointStartAction { TraverseNext, Random }
eWaypointIntermediateAction { TraverseNext, Random }
eWaypointEndAction { Destroy, GoToStart, Random }
eWaypointState { WaitingForPoints,…

Adventure Game #000: Testing

First post for testing.

I am a Computer Science graduate from the University of Washington turned indie developer. My goal is to create a Module built adventure game piece by piece and document the process with the hopes to help someone in the future. I have been part of several game projects including Defense of AllendaGhostlight Manor, and GoArmy Edge Football

Here we go!

Thank you for checking out my page, I intend to post every 1-2 weeks on a new part of my adventure game.

For now, here is a sneak peak at my first Adventure Game post (Waypoints)