Is there any significant difference between using a square or hexagonal grid for the area searched by a path finding algorithm. In other words, is square or hexagonal better, and if so why.
The main consideration for deciding whether to use square vs hex grids shouldn't be ease of AI implementation -- breadth-first and depth-first search algorithms are pretty much the same no matter what kind of graph you have.
Rather, this is a gameplay issue that should be considered by the game designers. Square grids are more accessible to the mass market (hex boards tend to look "geeky"), and in a world of up/down/left/right controls it's a lot more intuitive to navigate around squares than hexes from a UI standpoint. Square grids also tend to restrict movement a bit more; assuming orthogonal movement (and not diagonal), it takes 4 moves to walk around a one-square obstacle, compared to 3 moves in a hex grid. From a programming standpoint, hexes are also a little bit easier to implement but it's not about search algorithms as much as that a square grid equals a two-dimensional array, but a hex grid doesn't really map to a standard data structure.
The down side of square grids is that the movement never feels right. Moving diagonally should take sqrt(2) movement points, but in practice it's either 1 movement (which makes it feel like walking on diagonals is fast and there's rarely a reason to walk orthogonally) or it's 2 movement (which makes diagonal movement feel too slow). With hex grids, movement distance is a lot more intuitive, as it's always the same distance from one hex to another no matter which path you take.
I'm not an AI expert by any means, but the difference should be negligible. Square grids are a bit faster (4 connections per node instead of 6), but that's really not the limiting factor in the algorithmic runtime. Depending on what algorithm you're planning to use, the code might be a bit more complex for a hex grid, since it's a bit more complicated to calculate coordinates, and it's harder to use the sort of quadtree/octree shortcuts that I believe are often used in pathfinding.
But for a simple world like a turn-based-strategy game level, the difference between the two layouts shouldn't matter much; a square grid will be slightly simpler and faster.
This guide on hexagons is awesome. The part about pathfinding has an interactive example and some info on how to adapy square pathfinding.
If you’re using graph-based pathfinding such as A* or Dijkstra’s algorithm or Floyd-Warshall, pathfinding on hex grids isn’t different from pathfinding on square grids.
- Neighbors. The sample code I provide in the pathfinding tutorial calls graph.neighbors to get the neighbors of a location. Use the function in the neighbors section for this. Filter out the neighbors that are impassable.
- Heuristic. The sample code for A* uses a heuristic function that gives a distance between two locations. Use the distance formula, scaled to match the movement costs. For example if your movement cost is 5 per hex, then multiply the distance by 5.