7/13/2023 0 Comments The ultimate game nerd kingdom![]() We are currently exploring algorithms and graph representations for our world in TUG but so far we have implemented a navigational grid. The goal is to find the shortest distance path from the starting node to the goal node while avoiding the obstacle.The path found is highlighted in green at the end of the animation. The initial red node indicates the starting position and the green node indicates the goal position. I won’t get into the details of A* in this post because it gets technical very quickly but the image below provides a good visual representation of a typical A* search.īy Subh83 (Own work), via Wikimedia CommonsĪn illustration of an A* search. One of the most common algorithms used in games for pathfinding is A*. What this means to us is there are well known techniques, also known as algorithms, for dealing with graphs and finding best paths on them (see Pathfinding on Wikipedia). Graphs are cool because they have been studied by mathematicians since the 18th century (check out the Seven Bridges of Königsberg). ![]() In Computer Science we call a set of nodes and edges a “graph”. Most pathfinding techniques break up the world into spatial subsections (nodes) and store information about how those nodes are connected (edges). So now that we have defined Pathfinding and talked about what “best” means we can look at what tools we have for finding paths. “Ropes? We don’t need no stinkin’ ropes!” The path the goat and the human found are both the best path they can muster by their definition of best even if they are both very different.īy Darklich14 (Own work), via Wikimedia Commons Conversely, the human does have hands and can read so they take the tunnel. However, the goat is a sure-footed climber and does not have any problem scaling the mountain so it goes on its goaty way over the top of the mountain. If both the human and the goat want to get to the other side of the mountain what do they do? The goat does not have hands to open doors nor the ability to read. The human does not have any climbing gear and the mountain is far too steep to for the human to scale it without proper equipment. On the door is a sign that reads: “Tunnel to the Other Side”. Imagine a mountain goat and a human facing a mountain that extends as far to their left and right as their eyes can see. I think a small thought experiment helps to clarify the set of problems pathfinding tries to solve: ![]() The definition of best depends on the type of game you are making and the type of character you are trying to find a path for. Pathfinding is the act of finding the best path between two points in the world. Specifically I’d like to talk about Pathfinding and how it relates to TUG and our characters. Hey all! This is Northman from Nerd Kingdom here to share some AI bytes with you.
0 Comments
Leave a Reply. |