I was suppose to post an article on Code Project about this, but there is a new project that I need to work on ASAP, the article will have to wait.
This post will serve as a quick intro to the path finding world. Everything is implemented in C#. If you want source code, post in comments and i’ll get back to you.
This article is written by TSXY [at] 12thocean.com. Website: http://blog.12thocean.com
You are welcome to repost or use any part of the article for your own post. Source code are available upon request. Please send me a link if you post this anywhere.
First one is DFS or depth first search. As you can see, it’s not very smart. Due to the fact it’s looking down the road accoding to a predetermined path. In this case, counter clock wise.
Well, this obviously is not a good solution, people then started think more efficient way to find a path. In this case, a 3 line change to our non-recursive DFS made it into BFS or breath first search. The idea is simple, look at all your neighbors before moving on.
Here is the result, impressive, but not efficient enough. Why? just look at the memory comsumption. The little blue squares means that block was part of the search. Not very efficient..
Then there is the ultimate algorithm for correctness. (Note, not efficient, but correct) Dijkstra Algorithm.
This is designed to evaluate all possible routes and find the minimun path. Kinda like dynamic programming, where you keep looking for ALL possible solutions and update the grid with lowest solution.
The result is impressive, since it’s the most efficient path. The cost? LOL. I don’t even want to think about it.
Well, those are obviously not great solutions, what people came up is a combination of DFS and Dijkstra Algorithm. The idea is simple – Instead of looking at all possible routes, try the one closest to the destination first. And the result? Can I say WOW! Look, no square is wasted during the path finding.
This is super smart in terms of path finding. It’ll find a close to optimal result all the time. But as you can see, it’s not THE most efficient path. Why? Because there is a function, let’s call it G(x). G(x) is the estimated cost from cell x to destination. In this implementation, G(x) is the direct distance between x and destination. The cell with lowst G(x) will be evaluated first. This makes sense since this cell will “likely” be closer to the destination.
However, it might not be correct due to blocks on the road etc.
Then here is the ultimate algorithm. I call it A* Plus. Since it’s just a little addition to A*. It finds the optimal path, while uses far less memory than Dijkstra.
How? It’s all about how G(x) is designed. In this case, G(x) is direct distance + Obsticals on the direct path.
It’s very tricky to count obsticals along the path as you may notice. I actually implemented Bresenham’s line algorithm to calculate the cost. And the result:
Now let me mark this to be the end of this project. It’s unlikely for me to do the actual post to code project at this point. But who knows!
