Am I Taking The Right Path?

Ah the ambiguous title technique to draw in readers, classic.

The real topic of this blog is pathfinding, which for me is actually a topic I find exciting although outside my primary interests. In order to actually implement it effectively I found that I had to research and understand that not only are there different types of pathfinding but that there are also a range of approaches.

The difference in approaches lies in how nodes are represented. As nodes themselves are the simplified representation of the world, how they are implemented impacts the pathfinding. These types of node representations are discrete points, polygons (usually triangles or squares) and polyhedrons which is most often cubes. The names of these approaches are Spatial Graph, Navigation Mesh and Volumetric.

When using a pathfinding algorithm it is important to determine which algorithm is the most appropriate for the situation. Two of these are depth first and breadth first algorithms, both of which are uninformed searches that will follow the same search pattern every time. An alternate solution to this is to use Dijkstra which is a more informed search that uses a cost for each node, however, it has a flood fill effect.

An alternative to these options is A* (A-Star) which uses a heuristic algorithm to determine which surrounding node is the closest to the target position.

An A* spatial graph approach is the method I decided to take in the video in the above tweet. The pathfinding also allows for a somewhat dynamic map as the way that it determines if an area is traverse-able or not is by creating each node and when checking the node for distance to target a unity boxcastnonalloc is performed to determine if the node is blocked.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s