The problem lies in that the robot and the object the robot needs to pick up are both one pixel wide in the pathfinder. In reality they are a lot bigger. Often the A* pathfinder chooses to place the route along the edges of the obstacles, sometimes making it collide with them, which we do not wish to have to do.

I have tried to add some more non-walkable fields to the obstacles, but it does not always work out very well. It still collides with the obstacles, also adding too many points where it is not allowed to walk, results in that there is no path it can run on.

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

Edit:

So I did as Justin L suggested by adding a lot of cost around the obstacles which results in the folling:
Grid with no path http://sogaard.us/uploades/1_grid_no_path.png

Here you can see the cost around the obstacles, initially the middle two obstacles should look just like the ones in the corners, but after running our pathfinder it seems like the costs are overridden:

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

Picture that shows things found on the picture http://sogaard.us/uploades/2_complete_map.png

Picture above shows what things are found on the picture.

Path found http://sogaard.us/uploades/3_path.png

This is the path found which as our problem also was before is hugging the obstacle.

The grid from before with the path on http://sogaard.us/uploades/4_mg_path.png

And another picture with the cost map with the path on.

So what I find strange is why the A* pathfinder is overriding these field costs, which are VERY high.

Would it be when it evaluates the nodes inside the open list with the current field to see whether the current fields path is shorter than the one inside the open list?

And here is the code I am using for the pathfinder:

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

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

稀香 2024-09-13 19:01:40

您是否考虑过向物体附近的像素添加梯度成本？

也许就像线性梯度一样简单：

C = -mx + b

其中 x 是到最近物体的距离，b 是边界外的成本，m 是成本消失的速率。当然，如果 C 为负，则应将其设置为 0。

也许是一个简单的双曲线衰减

C = b/x

，其中 b 再次是边界之外的所需成本。一旦达到某个低点，就将其截止为 0。

或者，您可以使用指数衰减，

C = k e^(-hx)

其中 k 是缩放常数，h 是衰减率。再说一遍，有一个截止点是明智的。

第二个建议

我从未将 A* 应用于像素映射地图；几乎总是，瓷砖。

您可以尝试大幅降低瓷砖的“分辨率”吗？也许每 10×10 或 20×20 像素组有一个图块；图块的成本是图块中像素的最高成本。

另外，您可以尝试降低用于 A* 的最短距离启发式的值。

Have you considered adding a gradient cost to pixels near objects?

Perhaps one as simple as a linear gradient:

C = -mx + b

Where x is the distance to the nearest object, b is the cost right outside the boundary, and m is the rate at which the cost dies off. Of course, if C is negative, it should be set to 0.

Perhaps a simple hyperbolic decay

C = b/x

where b is the desired cost right outside the boundary, again. Have a cut-off to 0 once it reaches a certain low point.

Alternatively, you could use exponential decay

C = k e^(-hx)

Where k is a scaling constant, and h is the rate of decay. Again, having a cut-off is smart.

Second suggestion

I've never applied A* to a pixel-mapped map; nearly always, tiles.

You could try massively decreasing the "resolution" of your tiles? Maybe one tile per ten-by-ten or twenty-by-twenty set of pixels; the tile's cost being the highest cost of a pixel in the tile.

Also, you could try de-valuing the shortest-distance heuristic you are using for A*.

回复收藏 0 原文