About Pathfinding in AI

Implementing Pathfiding

I finally want to make a first person view Tower Defense so I began to generate the map and I took elements from the previous tutorials to spawn enemies, but, the main issue was to decide how to make the pathfinding. Indeed pathfinding is a crucial element for enemies AI in many games where monsters or enemies are following the
player, or going to a particular point while avoiding obstacles.

Obstacles could be different for different units. For example, an air force unit might be able to pass over a mountain, while the ground or artillery units need to find a way around it

Implementing Enemy Pathfinding

After making some researches, it seems that A* and Dijkstra are the most used algorithms for pathfinding in AI but there are differences between theses.

Dijkstra is a greedy algorithm which explore all possibilities (nodes) to find the best path possible from one point to another.

A* is considered a “best first search” because it greedily chooses which vertex to explore next. It will find the best path according to the value of f(v) [f(v) = h(v) + g(v)] – where h is the heuristic and g is the cost so far..

A* is both complete (finds a path if one exists) and optimal (always finds the shortest path) if you use an Admissible heuristic function. If the function is not admissible it will not provide the optimal path.

A* complexity depends on the chosen heuristic but usually the complexity is much inferior to Dijkstra which is running in O(|E|+|V| log |V|) ( E is the number of edges and V the number of nodes). Indeed, A* is faster than Dijkstra, it requires and more operations so more memory per node but it explores a lot less nodes and the gain is good in any case.

To conclude, the choice between those 2 algorithms depends on how you will use the algorithm in your game, but usually A* is mostly used because of its performance and accuracy.

If you need the best path possible, you can either code Dijkstra or A* algorithm, but if the chosen graph is getting huge, you better have to choose A* algorithm ( since Dijkstra will visit all nodes of the graph). Therefore Dijkstra can be considered as a “special case of A*” where the heuristic is 0 (no estimation of the goal’s distance from the start point).

But then when would I choose Dijkstra ?

You may use Dijkstra if you need to explore almost all the nodes in your graph. Since Dijkstra will provide all path from the start point to another in certain case it can be worth to do it.

capture

source : https://www.youtube.com/watch?v=5GT5hYzjNoo&t=410s

For example, if you have a fixed environment and several characters to move from the same point towards different end points. In the previous example, the shortest path from A to H is = A – C – D – E – G- F – H, but you can also have the shortest path from A to B : A – C – D – B.

I decided to code A* algorithm since in my future game, enemies will only have to move from one point to another but I still keep Dijkstra in mind.

First path-finding try

First I needed to get the nodes from the map since I actually have tiles on my map.

1

Each tiles have the same dimensions (x,y,z) : (4,1,4)

2

The map I have generated is a 10 by 10 tiles map, so here is the actual graph that I should get :

3

So each tile has a maximum of 8 neighbors and if the neighbor is walkable, a path exist (edge) between the tile and its neighbor.

Here is my representation of my nodes :

node

So I tried to code A star algorithm by myself using pseudo code :

sans-titre

I mainly used theses websites to code my algorithm:

http://blog.two-cats.com/2014/06/a-star-example/

http://web.mit.edu/eranki/www/tutorials/search/

Then for the heuristic part, I used a simple diagonal heuristic found on youtube :

4

Source : https://www.youtube.com/watch?v=mZfyt03LDH4&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW&index=3

So here is the result:

The yellow tile is the starting point, the black one is the end, the blue tiles show the path and the red tiles are the obstacles.

6

I realized that my algorithm was not the most efficient one because I didn’t choose the best heuristic or there was a mistake in my algorithm.

So I made more research and I found a really good article on heuristic here: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

It is said “If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.”

So I tried several heuristics but it didn’t change.

And after some more research, I figure out that my algorithm wasn’t providing the optimal path but was faster than the basic A* :

Source : https://en.wikipedia.org/wiki/A*_search_algorithm

Indeed it was not exploring as many nodes as the original A* algorithm does. This algorithm is actually a Best-First Search algorithm which will prioritize closest nodes using heuristics.

And that’s because instead of exploring all the nodes in the open (using FIFO) list I was choosing the closest node from the end point and visiting its neighbors first.

sans-titre2

And then my algorithm worked fine :

(Before/After)

Here is my complete code if you want :

http://pastebin.com/8Nmq5ns9

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s