Artificial Intelligence IV – Pathfinding

Today I’ll write about Pathfinding. Pathfinding is the plotting of the shortest route between two points. Applied to videogames, it is a process through which the AI calculates the most suitable route to get from a starting point to the goal, even across mazes.

gdxAi provides an API for this feature, the (obviously) named Pathfinding API. While steering behaviors were the best option to pursue dynamic targets, pathing is optimized to pursue static targets. Thus, I implemented it on the kitten’s movement towards a waypoint.

Graph theory

Before getting into the code, I’d like to explain some discrete mathematics basics to depict the context somehow.

Pathfinding is solved using graphs. The graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Its main elements are:

  • Graph: representation of a set of interconnected objects.
  • Node: (vertex) Points of the graph where lines intersect, branch or terminate.
  • Connection: (edge) Lines that go from one node to another.

grafos

The Pathfinding API provides tools to transform these abstractions into code.

 

Code

Applied into the game, this is how I managed to implement graph’s elements:

Graph

The graph is the game’s map (MapModel because of my MVC structure). This class contains the list of nodes, and the methods through which access them.

mapmodel> Github link to MapModel

Node

A node stores its position (x, y), and a list of connections with neighboring nodes. In the example below, the node N4 lives at position (1, 1), and has connections with nodes N1, N3, N5 and N7 (no diagonals allowed):

node

You could allow diagonal neighbors, but that’s another story.

> Github link to Node

Connection

This class contains a reference to both start and end nodes, and the cost of going from one to the other. In the example below, there are two ways to get from the node ns to the ne, but the red path costs 6, while the green one costs 4. Pink nodes are collidable nodes or obstacles.

connection> Github link to Connection

 

Algorithm

Once we’ve gathered all the elements, we can use them to find the shortest path between two nodes. The algorithm I’ve used is the Indexed A* algorithm, which is an improved variation of A*.

As explained here, the higher performance of the Indexed A* lies in the way it marks the nodes.

A* uses two lists of nodes, the “open list”, and the “close list”. The algorithm explores each node, creates a node record for it, and decides whether it is suitable for the path or not. In the former case, the node record is added to the close list, while in the latter, it is added to the open list. Later, both lists are iterated to search for a node record corresponding to a particular node, and this is somewhat time-consuming.

Indexed A* uses categories to mark nodes as “Open”, “Closed” or “Unvisited” instead of maintaining two lists. Node records are accessed directly using an index, and provide the category of the node you are asking for.

Code excerpt:

 

The algorithm itself is contained inside IndexedAStarPathfinder, my custom implementation of gdxAI PathFinder interface:

pathfinderAs you can see, the path finder receives a start node, a goal node and the heuristic, and outputs a path.

This path is an array of nodes whose first value is the start node, and the last one is the goal node. The nodes in between are a set of nodes that are connected among them. The path fulfills these requirements:

  • It is the one that costs less: The summation of the cost of each connection has the lowest value (compared to other potential paths).
  • It avoids the collidable obstacles: The Node class has a boolean attribute named collidable, and collidable nodes cannot be selected for the path.

> Full implementation on Github.

 

Follow Path behavior

After calculating the path of nodes, we want the affected entity to follow that path. This is performed using the FollowPath behavior. This behavior is fed by a steerable agent and a path, leading to something like this:

 

There’s a quite tedious issue here that I want to complain about: Why the hell FollowPath receives a LinePath type, while PathFinder returns a GraphPath?? Couldn’t they make an adapter or something? 🙁

The point is that, in order to use this behavior, I had to develop a disgusting parser that iterates through nodes and creates a LinePath:

 

General execution flow

At the end, the goal was to implement pathfinding to get a kitten reaching the waypoint inputted by the player. This is how everything fits together:

PA: The code above does not show the exact implementation, as I eluded all the MVC abstraction layers to avoid messing the code excerpt.

  1. When the user drags a kitten to a position of the map, the listener warns the kitten, providing the input position.
  2. The kitten calls the PathFinder and asks him to update the path from the kitten’s position to the clicked position.
  3. The Pathfinder uses Indexed A* to calculate the path of nodes.
  4. The kitten retrieves the calculated path from the PathFinder.
  5. In an intermediate step, the retrieved path is parsed to LinePath, which is the data structure used by the FollowPath behavior.
  6. The FollowPath behavior is configured using the retrieved and parsed path.
  7. The FollowPath behavior is set as the steering behavior of the kitten.
  8. The kitten, obeying to the FollowPath behavior, walks his way along the path until a new drag request is received or until he reaches the goal node.

walk

> The complete and real implementation can be found on github.

Precalculate path

If you run the game, you may notice that when you click over a kitten and start the drag, a path of paws is drawn. This means that, as long as you don’t release the mouse, the path is calculated each time you change the position of the cursor.

I added this feature because it was quite helpful for debug and it turned out to be useful for the gameplay as well.

This will draw the potential path just for you to consider it, without applying any behavior to the kitten. Do you like it?

drag

 

Conclusion

I must confess that this has been one of the hardest tasks I’ve faced. The more troubling part was the parsing. Besides the unavoidable fact that pixels must be parsed to nodes and vice versa, (which was a nightmare by itself), the path received by the behavior is different from the path generated by the pathfinder! Seriously, that was a terrible idea. Sometimes it was hard to identify if a failure was caused by a bad implementation of the algorithm or by a conversion process.

I have that damn mania of twisting my hair between my fingers when I’m nervous, thoughtful, concentrated, or a combination of these states. Well this week, the hairs that have not been broken or fallen, almost become dreadlocks.

It was also difficult to erase the precalculated routes each time the mouse was dragged to another position. At first, all the precalculated routes were staying visible, and the screen became so full of paws that it looked like someone left a lot of cat food at the other side of the map. And I couldn’t find out why!! Although I was completely burned out at that point, so maybe the problem was actually not that bad.

But hey, you know what? After all the suffering, pain and extreme torture, one day the kitten started walking down a splendid (and unique) path, and I did start mourning and called my husband and told him that “eureka”. True story.

Thanks for reading and sharing! And remember that you can collaborate with this project sending your drawings ^^.

BTW, I noticed that the spam filter was preventing truly human users to post their comments, but now it is fixed.

Enjoy your day!

laberinto

 

Facebooktwittergoogle_plusredditpinterestlinkedintumblrmail

3 thoughts on “Artificial Intelligence IV – Pathfinding

Add yours

  1. Great work!

    Instead of parsing the GraphPath to return a LinePath, how about extending the LinePath to a sub-class named FollowablePath. This new class can also implement Graphpath interface which will pass nodes to the underlying data structure.

  2. Hi just want to say thank you for this tutorial on GdxAI, i’m currently making my own game now and im trying to understand/run this game with libgdx right now 🙂 and your tutorial is not so tedious as a lot other tutorials out there 🙂 wondering why there’s not a lot of comments here? Isn’t this tutorial recommended on the libgdx page?

Leave a Reply

Your email address will not be published. Required fields are marked *

Proudly powered by WordPress | Theme: Baskerville 2 by Anders Noren.

Up ↑