Problem of collision with obstacles *

Question

I am working on a project with a robot that needs to find its way to the object and avoid some obstacles when moving to the object that it should pick up.

The problem is that the robot and the object to be assembled by the robot have a width of one pixel in the pointer. In fact, they are much larger. Often A * pathfinder chooses a route along the edges of obstacles, sometimes it encounters them, which we do not want to do.

I tried to add some more intransitive fields to the obstacles, but this does not always work well. He still encounters obstacles, also adding too many points where he is not allowed to walk, leading to the fact that there is no way.

Do you have any suggestions on what to do with this problem?

Edit:

So, I did as Justin L suggested, adding a lot of cost to the hurdles that lead to the following: Grid without path http://sogaard.us/uploades/1_grid_no_path.png

Here you can see the value around the obstacles, initially the middle two obstacles should look the same as those in the corners, but after starting our pathfinder it seems that the costs are redefined:

Grid with outline http://sogaard.us/uploades/1_map_grid.png

Image showing everything in the picture http://sogaard.us/uploades/2_complete_map.png

The figure above shows what things are in the picture.

Found path http://sogaard.us/uploades/3_path.png

This is a path that, like our problem before, embraces an obstacle.

Default mesh with track http://sogaard.us/uploades/4_mg_path.png

And another image with a cost map with a track.

So I find it strange why A * pathfinder redefines these field costs, which are very high.

Will it be when he evaluates the nodes inside the open list with the current field to see if the current path by fields is shorter than the one inside the open list?

And here is the code I use for pathfinder:

Pathfinder.cs: http://pastebin.org/343774

Field.cs and Grid.cs: http://pastebin.org/343775

Answer 1

Have you considered adding gradient values ​​to pixels near objects?

Perhaps as simple as a linear gradient:

C = -mx + b 

Where x is the distance to the nearest object, b is the cost outside the border, and m is the speed at which the cost dies. Of course, if C is negative, it should be 0.

Perhaps simple hyperbolic decay

 C = b/x 

where b is the required value right outside the border. Cut to 0 as soon as it reaches some low point.

Alternatively you can use exponential decay

 C = ke^(-hx) 

Where k is the moving constant, h is the decay rate. Again, clipping is smart.

---

Second sentence

I have never applied A * to a pixel map; almost always, tiles.

Could you try to massively reduce the "resolution" of your boards? Perhaps one tile in ten to ten or twenty twenty pixels; tile cost is the highest pixel value in the tile.

In addition, you can try to de-evaluate the shortest distance heuristic that you use for A *.

Answer 2

You can try to increase the obstacles taking into account the size of the robot. You can go around the corners of obstacles to solve the blocking problem. Then the filled gaps are too small for the robot to squeeze anyway.

Answer 3

I made one such physical robot. My solution was to move one step back when there is a left and right turn.

Red line, as I understand your problem. The black line is what I did to solve the problem. The robot can step back and turn right.