Pathfinding, and your A* Heuristic of choice?

Game Mechanics Artificial Intelligence
#1

I’ve just gotten to the point in my game that I need to tweak my enemy AI, which has led me to research pathfinding and subsequently A* and its heuristics.

I find it really fascinating, which leads me to wonder what other game devs think about the different heuristics used for this purpose.

So far I’ve come across the Manhattan, Diagonal and Euclidean methods and I can’t wait to try and implement this in my game.

Do you have a personal favorite heuristic method?

P.S. - These tutorials have been great reads:

A* Pathfinding for Beginners
Heuristics and A* Pathfinding
A*’s Use of the Heuristic

#2

I haven’t implemented any AI yet, but from extensive testing during my degree course on AI it seams like the Heuristic of choice is the one that fits the job at the time. The problem is there isn’t a fits all heuristic, you have to test and see what works with what you are trying to do. So my heuristic of choice is the one that fits the job ;D

#3

Ill just try implementing the Manhattan method first :stuck_out_tongue:

#4

Here are some quotes of my findings from one of my Assignments from the course with the open university ‘Natural and Artificial Intelligence’.

context : search in Sokoban ( a puzzle game)

[quote]“One method of developing heuristics is to identify constraints in the problem and relax them to form an easier problem. The cost of solving the easier problem can be quickly calculated; which gives an approximate cost for solving the real problem…”
[/quote]

[quote]How many constraints you relax to develop a heuristic depends on the complexity of the task and the time it takes to evaluate. Relaxing one might be enough to create the most efficient heuristic or you might need two or more, but there is a balance that needs to be met so that the best heuristic is found within the allotted development time. Bringing in too much complexity can lead to confusing and unmanageable code. However exploring a number of constraints can lead to a better solution.
The best heuristic is the one which more accurately estimates the cost and so more accurately guides the search towards the goal state, resulting in fewer nodes expanded which means a faster and optimal search. The heuristic should also be admissible.
[/quote]

[quote]A heuristic is admissible if it always underestimates the cost of the path to the solution. It is important for finding optimal solutions at it means the partially constructed optimal paths will always be chosen over the sub optimal paths to the goal state.
[/quote]

[quote]The things that affect the relative performance of the algorithms using different heuristics appear to be the size of the state space, if it is small then a less complex algorithm can find it fast. If the state space is large then the similar algorithm that is slightly less complex can be faster but expands more nodes. So I if you had to choose only one algorithm/ heuristic it would be best to use A* (displaced heuristic) as it is complete optimal and efficient…
[/quote]
Obviously my results are only valid for the Sokoban puzzle that i was experimenting with but there are some general principles to draw from.
We used a program called ‘search lab’ which let you try out many different combinations of algorithms.

#5

Programming AI is kicking my ass :stuck_out_tongue: Spent the last two days tweaking my enemy AI to follow a path towards the player and avoid any obstacles it may encounter.

I’m getting there using A*, but there are still occassions where I’m not liking how my enemies move, so I’ll have to continue tweaking.

I must say, doing this has been a pain, but utterly fascinating.

#6

The AI part of my game engine is the part I’m most looking forward to. I really enjoyed studying it so I’m hoping it wont take to long to get started on.

So how does your AI work, are they free roaming or stuck on a grid of nodes?

#7

I divided my game area into a grid of nodes and the general logic follows pretty much the “A* Pathfinding for Beginners” tutorial (I used the Manhattan Method as my heuristic).

Most of the logic I had to figure out was how to check for nodes that can’t be traversed due to containing obstacles and such; but since I’m using Box2D, I did this via QueryAABB and RayCast.

It has all worked fine so far and has come quite a long way since I started with my primitive logic although there are some situations where the enemies in the game still don’t act realistically enough. I already have some fixes in mind, which I hope to implement soon when I find time.

So far this has been the most challenging and interesting aspect of learning how to develop games thus far :stuck_out_tongue:

(EDIT: Although I should probably use the Euclidean distance heuristic since my game is not actually divided into grids and the objects can move in fractional increments in any direction)

#8

There’s this new algorithm I came across called a Jump Point Search btw.

I haven’t yet absorbed it all though: