Skip to main content

Adventure Game #002: A* Pathfinding

By

A* Pathfinding is kinda an essential to the gaming world, it lets you player move around, it helps AI both in NPC and Enemies, it can help validate paths, mazes, and dungeons, etc. so naturally Pathfinding is something that I had to implement.

Years ago in college I developed the algorithm for A* Pathfinding, however it was more of an theoretical exercise than a piece of code I could use, so with the help of YouTube.com and my old notes I put this together!

The code is simple, give the object a 2D char array, the start location, and the end location and it will spit you out a node with a recursive parent to take you to the end location.

Assumptions:
Diagonal movement costs 1.4
vertical/horizontal movement cost 1

Limitations:
Maps only work with (0,ymax) as the top left corner and (xmax,0) as the bottom right corner
ArgumentOutOfRangeException if the end point is unreachable
These limitations will be solved in the next iteration of the A* Pathfinding post

s = start
o = open space
c = closed space
e = end


The following is the output:
from start, move to (0,2) then (1,2) ..... ending at (0,0)



How It Works


When calling GetShortestPath() with a char array map, the class will do the following steps:
1. create open/closed lists to keep track of visited nodes
2. create a map, get the start/end position, and set all the h values
3. LOOP:
3A. Get all adjactent open nodes
3B. Get the node with the smallest F (Movement Cost + Distance from end) and set to parent
4. when the current node is the end position return the end position and recursivly call node.ParentNode to get a path from start to end.



take a look at the AstarPathfinding class to check out the whole process (including all the private functions that help make the whole thing possible)

Downloads & Links

Source code: AstarPathfinding.cs
Labels:

Comments

Post a Comment

Popular posts from this blog

Adventure Game #003 A* Pathfinding (Version 2)

By
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>();     f...
Post a Comment
Read more

Adventure Game #001: Waypoint Traversal

By
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 { Waitin...
Post a Comment
Read more