This is a blog post by iOS Tutorial Team member Johann Fradj, a software developer currently full-time dedicated to iOS. He is the co-founder of Hot Apps Factory which is the creator of App Cooker. Have you ever had a game where you wanted to make monsters or players move to a particular point, while […]
I’ve read this and several of the links including the Amit’s A* Pages but I am still confused about how to estimate my heuristics for this algorithm when walls are a factor like you did here. You used the “Manhattan length” in your example on this page but later you used something else that gave you the exact amount of squares from one point to another that even factored in walls. How can I replicate the latter?
I understand everything else but I need some explanation about how to estimate steps to go around walls so I can get a proper H variable for the “F = G + H” function. Everything I do in my head involves already knowing all the paths’ estimates I need to get an estimate. So I pretty much need to know all paths to find the best path. Which makes little sense since figuring out ALL paths for every time a character is on any tile is a heavy processing task and then I need to store it.
In your example on this page you use the “Manhattan length” but the paths go through walls it turns into the Greedy Algorithm which returns a very poor path when obstacles are involved (A* pages told me that and it makes sense).
Also the red line in the image is a perfect example of needing to know the best path to find the best path since if it continues to go up to avoid the wall and then go right and then down it will have a much higher estimated heuristic value than if it just went right and then up instead which will ruin the algorithm for finding the best path since estimates won’t always be the shortest path.
Can anyone help me get a better understanding of calculating the heuristics for the “F = G + H” function when walls are a factor that doesn’t use the basic “Manhattan length”?
This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]