In this version of the game, I implemented a Pathfinder algorithm. As the video below shows, the AI system computes a path towards the goal. Notice how the white jersey player drives the ball towards the goal.
Implementing a Pathfinder algorithm requires knowledge about Graph Theory and the Dijkstra's algorithm. I've heard about these topics, but I wasn't well versed on them. So I decided to spend my weekend reading about them. I did learn a lot. However, as I was about to implement the algorithm, I realized that the Dijkstra's algorithm might not be suitable for soccer.
Let me explain.
In Graph Theory, a graph is composed of nodes and edges, as shown in the figure below:
A node can represent a location. An edge represents a connection. For example, you can go from your Home to the School by taking the path towards the Park. Or by taking the path towards your friend's house and CoffeeHouse.
By scanning the image, you can see that the shortest path from your home to school is towards the park (only takes two connections). However, this route may not be the fastest.
If each edge is given a weight; in this case representing traffic, then the fastest path is the one towards your friend's house. The Dijkstra's algorithm is used for these instances. It analyzes a graph and determines the fastest path between two endpoints.
I figured that I could use the Dijkstra's algorithm in the game. My idea was to compute the path a dribbling player can pursue to reach the goal.
However, the Dijkstra's algorithm works well for static nodes. It does not operate well in a dynamic environment such as in soccer. For example, a path computed at time t=0s will be invalid at time t=1s.
So, instead of using Dijkstra's algorithm, I decided to implement a "Look and Go" algorithm. The algorithm works as follows:
Once a player obtains possession of the ball, the algorithm divides the player's surrounding area into 36 positions. The algorithm then scans each location. If an opposing player is close to the location, the algorithm discards the position.
The algorithm then analyzes the location that would bring the player closer to the goal. The AI system uses this information to move the player towards that direction.
Does this algorithm work? It works quite well as shown in the image below.
As you can see, unlike the Dijkstra's Algorithm, which computes a complete set of paths, the "Look and Go" algorithm analyzes one path at a time and is more suitable for dynamic environments.
