无限大grid上找最短路径问题

被激光射到的grid直接当作障碍物就行了吧。。
搜索遇到一个新格子，判断
1.他是否是障碍物
2.他是否被激光穿过

mint0715 发表于 2019-11-22 04:17
被激光射到的grid直接当作障碍物就行了吧。。
搜索遇到一个新格子，判断
1.他是否是障碍物

请问怎么判断这个点被激光穿过呢?

Ericson1995 发表于 2019-11-22 04:53
请问怎么判断这个点被激光穿过呢?

一个激光，起点a, b，方向k, j。
那么这个激光的直线方程就是: (x-a)*j - (y-b)*k = 0

你需要检查：
1. 方格是否在直线上
对于一个格子的四个角，这四个角的坐标代进方程，全都大于0(或全都小于0)，那么这个方格的四个顶点都在直线的某一侧，它一定不会被射到。如果既有大于0，又有小于0，那么:
2. 方格的四个顶点分布在直线的两侧->方格被直线穿过。（但未必被射线穿过，可能在射线反方向被穿过）
用方格的四条边方程代入方程，易得四个交点。如果任何一个交点满足1.他在方格上 2.他的x值满足x = a+kt且t>0，那么这个方块就被射线穿过。