There is a certain game. It is necessary to quickly find the shortest sequence of moves to achieve the transition from one game state to another. (or all sorts of sequences of a certain length). What will need the function of the possibility of limiting possible moves. For example, if there are 4 possible moves (left, right, up, down), then we could request a path that, for example, does not use moves to the left and down. How is this business better kept and what algorithms to use for searching?

[Reflections] I imagine the principle as follows ... Each time a graph is built, where the edge is a move, and the node is a state of the game after a given move (i.e., it will be possible to both analyze the existing game and generate various "virtual" combinations for searching them). The direction of the course is weight, apparently. But I don’t remember a single standard algorithm that would exclude certain weights from the search ... Ie do you need to go over the graph and put down indecently high weight for eliminated moves? (which also does not exclude its participation by 100%) Or is it better to correct the algorithm so that it ignores certain weights on the list, and the graph itself perceived as unweighted?

At the input of the algorithm, there are certain states of the game, i.e. for each node, you need to store some hash (because storing all the states is quite expensive), so that the input data can be immediately associated with the necessary nodes of the graph. And then the search for the shortest path (A * probably will be optimal in this case?) It will be possible to find the shortest path, and search depth (?) With a depth limit for a certain length.

  • При каждом ходе строится граф, где ребро это ход, а узел это состояние игры после данного хода . And then the scales are not needed, the graph will not be weighted - tym32167
  • 2
    I would simply build a graph during the search for a path — that is, build only those nodes that may be needed. For example, take the state A. You know the possible moves from this state, taking into account the restrictions. Build all moves from A to B1, B2, ... Bn. Then from each Bi, build moves in C1 ... Cn, that is, such a search in width. Well, build until you get to the right state of O, how to get - come back from O -> A, this will be the shortest path - tym32167
  • As a premature optimization :) You can do 2 searches at the same time, one of A, the other of O, and look for the moment when some vertex will be processed by two algorithms. - tym32167
  • @ tym32167 ну и искать момент , I’m looking ну и искать момент to search for this moment to eat the whole idea of преждевременной оптимизации ) - Isaev
  • one
    why? you also have a state - this is a node. At the node count the hash. Enter 2 hash tables of visited sites, one for each search. When the next node in search 1 is already contained in search hash table 2, then the moment has arrived. - tym32167

1 answer 1

This is all solved through A *, oddly enough. A * is designed to find routes along the graph between the vertices.

Take the starting state of the game (input vertex) and go through all possible transitions (graph edges), go through them, get new states (vertices). Check whether the vertices do not coincide with the previously known ones, and combine them. For each vertex, record the minimum "price" of its achievement from the starting vertex. Repeat recursively, each time choosing a vertex with the lowest "price", until one of the vertices is the target state of the game. In the process of building a graph, watch your rules and check from which state (vertices) they let you go to another or not. Those. in other words, transition edges can be unidirectional.

The direction of the course is the weight, apparently.

Not. A direction is the existence of a one-way link (edge). The ribs may be one-sided, this is normal.

At the input of the algorithm, there are certain states of the game, i.e. for each node you need to store some kind of hash

You can hash, it will speed up the search for identical states in a large graph.

  • And if a graph can have a large number of vertices with a possible 1-6 number of edges from each, then, as I understand it, it is better to use the adjacency list for storage? - Isaev
  • If you have not tens of thousands of vertices, and not fifty edges from each, then there is no particular difference in the choice of storage method. Do as it is more convenient. Anyway, in the end, you have a list of vertices sorted by "price" and each time you take the top one, go around and put its neighbors with the "prices" in this list. And repeat to the victorious. - Kromster
  • there may be tens of thousands or even hundreds of peaks ... but there are few edges of each. I mean that with a small number of edges the adjacency matrix will eat an unreasonably large amount of memory? - Isaev
  • I would not use the adjacency matrix in any case. It is more convenient to store adjacencies with a list at each vertex (and the unidirectionality of links is more accurately specified, simply by the presence or absence of a link). Anyway, the memory access will be almost random as the vertices are iterated. - Kromster