How to build the shortest path through the cells, having the ability to rearrange the obstacles?

Good day!

It is necessary to develop an algorithm to move the object from the cell a to cell B so that the sum of the displacements of the obstacles to liberation the path + sum of the displacements of the object itself was minimal. Movement is possible in 8 directions(forward/backward, left/right, diagonal). You need to consider that the obstacles we have to get back to their seats.

Please tell me ideas to implement, something in my head nothing good comes.

July 2nd 19 at 17:18
2 answers
July 2nd 19 at 17:20
Build a tree of moves, build the objective function, take one of the popular optimization algorithms on graphs (or ant colony or simulated annealing), mix, but do not stir.
July 2nd 19 at 17:22
Response refers to the standard pathfinding algorithms.


Any algorithm successfully is complicated by the use of potential fields.
Thank you.

In the articles says anything about static obstacles, or moving on its own trajectory, necessary to complicate the movement of the unit. In my case, on the contrary it is necessary to arrange the obstacles so that was 100% guaranteed trajectory to achieve the unit of point B from point A, the sum of the displacement unit + amount of displacement of the obstacles should be minimal. - Ell commented on July 2nd 19 at 17:25
, It reminds me of one genre of toys. I do not bot if you decided for these toys make? :)
You need a little longer to smoke the proposed materials. I feel there is a solution. Only you gave very little information on their task.
Let's say that obstacles will box. The player only to push can? What if in the way push close another box worth? Or the player can just take a box and move it to any other empty cell around you? And you can walk as well in 8 directions? And if you want to go diagonally when the opposite diagonal is occupied boxes, then what? Interaction with a box is a course or not? During the interaction the player moves to the location of the box or not?
I do this all day to ask questions can. :) I think if you allocate the max possible rules - decision with the A* itself will catch up. - Benjamin_McClure commented on July 2nd 19 at 17:28
In toys I haven't played and can't remember a game where we would need such functionality. Except that the HWM, but there is much more complicated. :)
I will go into detail of the books, although with some familiar algorithms. Thank you!
Player - abstraction. You just need to build a path from cell A to cell B given that you can still move obstacles(boxes). Moving obstacles similar to the movement of the player, i.e. step by step(if the adjacent cell a[x][x] is free, then move on it). The ability of moving obstacles is not associated with the player, ie you can move the "box" though, at the other end of the field, just to the point of this was. Moving obstacles are also in 8 directions. - Ell commented on July 2nd 19 at 17:31
those who love the sea - a genre of "push the box" or "sokoban". :) But, Yes, in the genre have direct player interaction with the box.
You would think, probably so.
You can build a weighted graph, the optimal move. In this graph should be not only free cells, but all obstacles to the optimal move. On this count it will become clear whether any moving obstacles. Let initially the transition to the place of obstruction is twice the price of the transition to the empty cell.
And then begins the "optimization" of the graph. right thinking dictates.
Optimization is to try to push the "cheap" obstacles, each time counting the cost of the entire path.

You can still simplify your life by setting the potential appreciation of the route on the cage of each obstacle. In this case, the first step is the creation of a potential field. It is created from the most similar to free cells of the obstacles to the center of mass and literally determines the appreciation of the way when moving through obstacles. And the second step will be a simple A*. - Benjamin_McClure commented on July 2nd 19 at 17:34
: Thank you!
This relatively clear. And what if the obstacles are of different types, which have different forms of movement? Well, like figures in chess. How in this case to build the path? - Ell commented on July 2nd 19 at 17:37
: maybe in this case you need to look in the direction of neural networks? - Ell commented on July 2nd 19 at 17:40
Yes no, not necessary.
The complexity of the task from a variety of obstacles does not change. Besides, even if all the obstacles can move to any of 8 cells around themselves, that if two obstacles are close nearby, they have been there the specifics of the move. They can not move on the cells to each other. And so on.
The case of chess pieces does not affect the search, because the goal of movement of the obstacle - free optimal motion path.

Maybe we should transfer the discussion directly in the task area? And I can smell what you try to do only leading questions. :) - Benjamin_McClure commented on July 2nd 19 at 17:43

Find more questions by tags JavaAlgorithms