First steps: Tree/Graph Search Algorithms.

This will be first steps understanding knowledge acquired after reviewing the courses and sounds like I should start my understandings algorithm by developing an agent search to design these systems.

And use Python language to program all this systems.

First tutorial:

- Pathfinding with Python, Graphs, and A-Star
original post link: http://scriptogr.am/jdp/post/pathfinding-with-python-graphs-and-a-star

Using some basic graph knowledge and the A* algorithm, tying them together with Python, we can generalize pathfinding for games by being aware of the graph properties of maps.
The A* Search Algorithm:

A* is an algorithm used to find a path between a starting position and an end position in some search space. It is complete, meaning that a path is guaranteed to be found if one exists. It is also a best-first search, meaning it will prioritize exploring the paths judged to be most effective according to some heuristic. We won't be diving in to the implementation details of A*: the astar.py file can be dropped into your Python project and you can forget about the details.

The implementation of A* used here lays the foundation for pathfinding over any arbitrary graph, it isn't limited to the traditional Cartesian grid. That is why its constructor takes a graph as an argument instead of a rectangular multidimensional array, and the graph is implemented simply as a dict. Graphs can represent any map structure, including triangular and hexagonal grids, or even things like irregularly arranged overworlds. Rectangular grids can be thought of as a graph like any other.

The AStar class is the container for returning paths through a graph. It works by being initialized with the graph, and then calling search with a start and end vertex specified. The return value is the list of all vertices on the path. The heuristic method is used by search to judge the fitness of the vertices for being part of the best path to the end vertex. It can take the starting, ending, and current vertex into account when calculating the heuristic, but not all heuristics require all of that information.

The AStarNode class represents a vertex in the graph. Without being subclassed it contains no data about itself aside from some internal values used by A*. These properties are so named by tradition and would be expanded upon by an A* tutorial:
the g property is increased every time the vertex is walked over during the search, making it less likely to be a member of the best path if it is tested multiple times;
the h property is its current heuristic value.

When choosing the next vertex in a path A* tries to choose the vertex with the smallest sum of g and h. The move_cost method returns the cost for moving from one vertex to another, and is also the value by which g is incremented.

Video:

https://www.youtube.com/watch?v=ksINxQkmhXg&feature=youtu.be

Code:

http://scriptogr.am/jdp/post/pathfinding-with-python-graphs-and-a-star