Hello!

Please help me implement the path search algorithm A *. I am new to programming and I don't know much about it.

I read the article Algorithm A * for beginners (well, it is most understandable) + found some source code in Java.

Intuitive algorithm is clear. On each crock for each point from the open list, we consider the value F = G + H (how to calculate them, I understand), etc.

It is not clear how to do all this programmatically at the "beginner" level.

For example, I don’t understand how to work with lists, how to check points and how to determine the parent point for the current point.

Probably, we need some class of type DOT with properties x, y, F, G, H, a parent that can count the values ​​of F, G, H and save the parent. But if so, then immediately create objects for each point of the map or how.

As lists I thought to use <vector>.

Examples of sources that I found on the web are obscure.

    3 answers 3

    1. http://www.policyalmanac.org/games/aStarTutorial_rus.htm
    2. Maybe better to get acquainted with the basics, and then take up such a difficult algorithm?
    3. Will you program in C ++? Concluded at the mention of the template class <vector>. Well, well - not the worst choice.

    Probably, we need some class of type DOT with properties x, y, F, G, H, a parent that can count the values ​​of F, G, H and save the parent.

    A class or structure is needed. But consider F, G, H can be manually. Parent save, obviously, at the time of adding a point to the list. You can either specify the index of the parent in the list, or coordinates, or simply give a pointer to it (obviously, the parent will always be in the list of points). But no one bothers to use the OOP approach. For example, make an element constructor that will accept the parameters you specify. And some of the parameters - to count on their own.

    Examples of sources that I found on the web are obscure.

    Give a link, try to figure it out. What exactly was not clear?

      You can read more here . - Various path finding algorithms, their advantages and disadvantages in various cases of gaming environments are considered. In addition to finding the path, the resource Programming Magic Games contains other information on programming games ...

        Yes, the cell class will be needed with the fields you specified. Creating new objects of this class is worth considering when looking at the neighbors of a cell with the smallest f from the open list. For example, if a cell is square, then we take the lowest-cost cell from the open list, create 3 new cells with the coordinates of its neighbors (three, since the fourth neighbor probably will be the parent from the closed list), calculate all the parameters for them and put it in the open list. In no case should you create all the cells for the map at once, as many probably will remain unclaimed. And for an open list, I would advise something like a priorityQueue (it’s better if this container still has an index return on the element).