about jps-2d

[923047247]

怎样构建一个2d地图下的JPS算法，它和3D哪里不同，怎样表达当前节点和父节点的方向呢？

[LenaShengzhen]

about 2d-JPS, see "Online Graph Pruning for Pathfinding on Grid Maps". and: https://harablog.wordpress.com/2011/09/07/jump-point-search/ https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html https://www.gamedev.net/tutorials/programming/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220/

There is no difference between 3d-jps and 2d-jps in principle. 3d-jps has one more 3D-diagonal than 2d-jps.

The direction of the node and the parent node, you can see the code:

struct( ...
         'pos', map_start, ...
         'fa', 1, ...
         'id', 1, ...
         'dir', all_direction);

[923047247]

非常感谢您的回答，我已经阅读过您的代码了，其中有几处不太理解，想要跟您再请教一下。 一、在struct中：①id是用来表示该节点是否被扩展过吗？②fa是用来表示父节点在地图中的下标索引吗？为什么初始化为1呢？ struct( ... 'pos', map_start, ... 'fa', 1, ... 'id', 1, ... 'dir', all_direction); —

二、在下列这段代码中，nodeNew.id=length(closelist)+1，这句话不理解，麻烦您指导一下

 if (map_visit(nodeNew.pos(1), nodeNew.pos(2), nodeNew.pos(3)) == 0)                 nodeNew.fa = fa;                 nodeNew.id = length(closelist) + 1;                   ds = ManhattanDistance(map_goal, nodeNew.pos);                 ManDis = [ManDis ds];                 openlist = [openlist; nodeNew];                 closelist = [closelist; nodeNew];                 map_visit(nodeNew.pos(1), nodeNew.pos(2), nodeNew.pos(3)) = 1;                                  % find the goal                 if (nodeNew.pos == map_goal)                     findgoal = 1;                     break;                 end     end

三、您在代码中的启发式函数只关于h(n)，不考虑g(n)，这样做会不会对最后的最优路径产生影响呢？

------------------ 原始邮件 ------------------ 发件人: "LenaShengzhen/AerialRobotics" <notifications@github.com>; 发送时间: 2021年2月15日(星期一) 凌晨2:57 收件人: "LenaShengzhen/AerialRobotics"<AerialRobotics@noreply.github.com>; 抄送: "孙悟空，悟饭"<923047247@QQ.COM>;"Author"<author@noreply.github.com>; 主题: Re: [LenaShengzhen/AerialRobotics] about jps-2d (#1)

about 2d-JPS, see "Online Graph Pruning for Pathfinding on Grid Maps". and: https://harablog.wordpress.com/2011/09/07/jump-point-search/ https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html https://www.gamedev.net/tutorials/programming/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220/

There is no difference between 3d-jps and 2d-jps in principle. 3d-jps has one more 3D-diagonal than 2d-jps.

The direction of the node and the parent node, you can see the code: struct( ... 'pos', map_start, ... 'fa', 1, ... 'id', 1, ... 'dir', all_direction);
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[LenaShengzhen]

fa records the index of the parent node in the closelist id records the index of node in closelist

Initialized to 1 because the index of the matlab array starts at 1.

I forgot to add g(n) to it. The distance between two adjacent nodes should be used to update g(n).

[923047247]

Thanks for you answer,i have other questions to ask you. IF you use 0 to express free area，use 1 to express obstacles in the map？ In the struct of node, if the "pos" records the coordinate of the node in the map ? Why is the nodeNew.id=length(closelist)+1, i think it is different from the index of the node in the map. In the function of hasforceneighbor , what are the functions of the following three pieces of code {d1 = [abs(d(3)) abs(d(1)) abs(d(2))]; d2 = [abs(d(2)) abs(d(3)) abs(d(1))]; dob = [d1; -d1; d2; -d2; d1+d2; -d1-d2; d1-d2; -d1+d2];}

[LenaShengzhen]

1: 1 meaning obstacles.

2: node.pos meaning index of the point on the grid-map.

3: nodeNew.id meaning index of the nodeNew at the closelist array.

4: Check up, down, left and right + top left, top right, bottom left, bottom right, a total of 8 locations, whether there are obstacles.The dob array contains these 8 directions

[923047247]

thank you very much. i have solved all the problems for jps-2d. Recently, I'm learning the artificial potential field ,I'd like to ask you how to caculate the direction of the gradient in matlab ？

[LenaShengzhen]

Congratulations!

You can refer to this course： coursera "Robotics: Computational Motion Planning". The assignment for the fourth week will talk about how to realize artificial potential field.

[923047247]

Thanks，where can i learn it?

[LenaShengzhen]

google : coursera "Robotics: Computational Motion Planning" The first one in the search results is it.

[923047247]

Thank you very much.

[923047247]

Hello, blogger. I'd like to learn something about trapezoidal time allocation. Is it convenient for you to share？

[LenaShengzhen]

I know very little about trapezoidal time allocation. May be this can help for you：https://github.com/LenaShengzhen/AerialRobotics/wiki/Time_Allocation