Thread: A Pathfinding Story

Hi guys, I have a question about pathfinding methods. For now I am only interested in Tile Based pathfinding, which, as anyone who has broached the topic will know, is worlds easier.
I have developed several pathfinding algorithms and some have had more success than others, but ultimately they are too inefficient.
So I was wondering if some people could outline their own successful algorithms, so I can see what other ways people have come up with. Also if anyone has more general tips for optimising this process then please let me know,

Thanks java pros

Show or describe your own favorite algorithm and explain what you believe is inefficient about it.

Well, my algorithm involves designating tiles on a grid to be 'updated'. It then goes through all the tiles that need to be updated and effectively 'spreads' across neighbouring tiles which it adds to the update list. The cycle then repeats until the flow reaches the target and the path can be traced back. I was just wondering if there were any drastically different approaches to the problem.

Hmmm. Not sure I get your explanation.

My maze generator and solver contains 'cells'. I assume those are like tiles. My cells have characteristics. I don't remember them all, but each of the 4 sides is either a wall or open, the cell is either on the solution path or not, it has either been visited or not, the possible exits remaining to be tried, etc. The cell's side characteristics are set on creation, the others are discovered and set by the solver.

The solver starts at the beginning and crawls the puzzle as needed to find the exit, backtracking when reaching a dead end by following the path that has been pushed to a stack in reverse until finding a cell that has an exit that hasn't been explored. Not all cells in the maze have to be visited, only those needed to discover the solution.

Is that any better than yours? Who knows?

Haha, I think your right this would be a tricky topic to discuss, thanks for your explanation though, It does sound interestingly different.

You can simply use the Dijkstra Algorithm for pathfinding in tile maps since they are just bidirectional graphs where each tile is a node and adjacency of tiles is adjacency of nodes in the graph.

Thanks Cornix, I've been looking for just that kind of algorithm!

I like A* (A star) using the manhattan heuristic. This of course can only be applied to virtual type problem because a read device cannot teleport to unchecked locations.

I suppose there is the conventional breadth and depth first search too. Then again I guess it depends on if you want to visit each node to ensure accuracy or disregard some that are assumed to be no benefit to you.